[Search] [txt|pdfized|bibtex] [Tracker] [WG] [Email] [Nits]
Versions: 00 01 02 03 04 05 06                                          
draft-leith-tcp-htcp-00                                         D. Leith
Internet-Draft                                                R. Shorten
Expires: December 27, 2005                            Hamilton Institute
                                                           June 25, 2005


  H-TCP: TCP Congestion Control for High Bandwidth-Delay Product Paths


Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on December 27, 2005.

Copyright Notice

   Copyright (C) The Internet Society (2005).

Abstract

   Our objective in this document is to renew discussion on how the TCP
   congestion control algorithm might best be modified to improve
   performance in high bandwidth-delay product paths.  We focus on
   changes to the additive increase element of the TCP AIMD algorithm.







Leith & Shorten         Expires December 27, 2005               [Page 1]


Internet-Draft                    H-TCP                        June 2005


1.  Conventions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119.














































Leith & Shorten         Expires December 27, 2005               [Page 2]


Internet-Draft                    H-TCP                        June 2005


2.  Introduction

   The current TCP congestion control algorithm is known to perform
   poorly on paths where the TCP congestion window becomes very large.
   [Kelly02, Flo03, FAST04].  Following congestion, the congestion
   window is halved and only increases at a rate of 1 packet per RTT.
   As a result flows can take an unacceptably long time to recover their
   window size after a congestion event.

   A direct solution is to make the time between congestion events
   smaller.  This can be achieved by, for example, adjusting the AIMD
   additive increase rate to be greater for flows with larger congestion
   window.  Backward compatibility with legacy TCP can be ensured
   through the inclusion of a separate mode of operation that behaves as
   legacy TCP in the appropriate circumstances.

   The logic that orchestrates switching between the legacy and more
   aggressive modes of operation can clearly be designed several ways.
   One approach is to make the AIMD increase parameter, which we denote
   here by alpha, a function of the flow congestion window.  That is,
   alpha is increased as congestion window increases thereby resulting
   in an additive increase algorithm that directly scales with
   congestion window.  This is precisely the approach adopted in the
   High-Speed TCP [Flo03] proposal.  In addition to adjusting the AIMD
   increase parameter alpha as a function of congestion window, this
   proposal also increases the multiplicative decrease factor beta to
   further increase the aggressiveness of a flow.  (Note.  On
   multiplicative decrease, the congestion window cwnd is updated to
   beta x cwnd.  We use this definition of the backoff factor beta
   throughout this document).

   While such modifications might appear straightforward, it has been
   shown [Sho04, Yi05] that they often negatively impact the behaviour
   of networks of TCP flows.  High-speed TCP[Flo03] and BIC-TCP [BIC04]
   can exhibit extremely slow convergence following network disturbances
   such as the start-up of new flows; Scalable-TCP [Kelly02] is a
   multiplicative-increase multiplicative-decrease strategy and as such
   it is known that it may fail to converge to fairness in drop-tail
   networks [Jain89].

   Our objective in this document is to therefore to renew discussion on
   how the TCP congestion control algorithm might best be modified to
   improve performance when the congestion window is large.  Large
   congestion windows are associated with high bandwidth-delay product
   (BDP) paths and with the ongoing increase in network speeds, high BDP
   paths are becoming increasingly prevalent.  In this document we focus
   on changes to the additive increase element of the TCP AIMD algorithm
   (we leave discussion of modifications to the backoff factor to a



Leith & Shorten         Expires December 27, 2005               [Page 3]


Internet-Draft                    H-TCP                        June 2005


   later date).  In particular, we present proposed changes to the
   additive increase algorithm that we argue are promising enough (based
   on the outcome of experimental tests carried out by a number of
   groups [Hegde04, Yi05, Cot05]) to warrant further discussion within
   the wider networking community.

   Scope
   -----

   Our focus in this document is on the behaviour of long-lived flows
   and so we do not consider changes to slow-start.  We also seek to
   make the smallest possible changes to the existing TCP congestion
   control algorithm, and so confine consideration to the AIMD packet-
   loss based paradigm.  Use of jumbo packets is viewed as complementary
   to the changes proposed here.  We confine consideration to drop-tail
   queues as this is the prevalent queueing discipline in the current
   Internet and leave discussion of active queueing to a later date.


































Leith & Shorten         Expires December 27, 2005               [Page 4]


Internet-Draft                    H-TCP                        June 2005


3.  Additive Increase for High Bandwidth-Delay Product Paths

   The AIMD algorithm used in TCP has two key features that underpin its
   convergence behaviour.  Firstly, flows with the same RTT increase
   their congestion windows at the same rate.  Secondly, the backoff
   mechanism is multiplicative.  Hence, following congestion, flows with
   a larger congestion window will reduce their congestion window by
   more, in absolute terms, than flows with a smaller congestion window.
   Thus larger flows yield more bandwidth than smaller flows.  Since
   flows increase congestion window at the same rate, flows with smaller
   congestion window thereby gain a certain advantage over flows with
   larger congestion window, and it is this that enables flows with
   small congestion window to seize bandwidth from flows with large
   congestion window until balance is reached in the network.

   It follows from this observation that modifying the AIMD backoff
   factor can have a very significant impact on network responsiveness,
   and this is discussed in more detail elsewhere [Sho04, Sho05].  In
   this document we do not consider changes to the backoff factor.
   Instead, we confine attention to modifications to the AIMD increase
   rate with the aim of improving performance in high bandwidth-delay
   product paths.  Provided we retain appropriate symmetry between the
   increase rates of competing flows, modifying the increase rate
   affects the interval between congestion events but otherwise does not
   affect the responsiveness of TCP.

   We therefore propose generalising the AIMD algorithm by allowing the
   increase parameter alpha to vary as a function of the elapsed time
   since the last congestion event.  Specifically, if we let Delta
   denote the time in seconds that has elapsed since the last congestion
   event experienced by a flow, we adjust the AIMD increase parameter
   according to some function which we denote f_alpha(Delta).  To
   provide backward compatibility with legacy TCP flows we consider
   adjusting the increase parameter as follows

   if Delta <= Delta_L
      alpha  = 1
   else
      alpha = f_alpha(Delta)

   where Delta_L is the threshold for switching from standard/legacy
   operation to the new increase function.  The choice of function
   f_alpha is governed by the rate at which bandwidth should be
   acquired.

   We can immediately make the observation that, because the adjustment
   is based on time since the last backoff, a degree of symmetry is
   maintained between competing network flows and in particular flows



Leith & Shorten         Expires December 27, 2005               [Page 5]


Internet-Draft                    H-TCP                        June 2005


   already in high speed mode are not awarded a long-term advantage over
   newer flows.  Specifically, when packet drops are synchronised Delta
   is necessarily the same for all flows.  Hence all flows share
   identical increase profiles and symmetry is maintained [Sho04].  When
   drops are not synchronised, Delta is the same *on average* for all
   flows provided flows share the same probability of backing off on
   congestion.  Hence, symmetry is still maintained, albeit in an
   average sense.

   We select the increase function f_alpha such that the duration of the
   congestion epochs remains reasonably small as the bandwidth-delay
   product on a path increases.  Below, we discuss one choice of
   increase function that yields convergence times that seem reasonable.
   However, the precise responsiveness requirement in future networks is
   currently not well defined and so we leave this, and the associated
   specific choice of increase function, as a question for further
   debate.


































Leith & Shorten         Expires December 27, 2005               [Page 6]


Internet-Draft                    H-TCP                        June 2005


4.  Choice of Increase Function

   We consider, as an illustrative example, use of the increase function

   f_alpha(Delta) = 1 + 10(Delta-Delta_L)+0.5(Delta-Delta_L)^2   (1)

   and Delta_L=1 second.  This choice yields the congestion epoch
   duration for a single flow, as a function of congestion window size,
   shown in Table 1.

   -------------------------------------
   Congestion              Congestion
   window                  epoch
   (packets)               duration (s)
   -------------------------------------
   100                     1.1
   1000                    3.1
   2000                    4.3
   5000                    6.6
   10000                   9.2
   20000                   12.8
   50000                   19.4
   -------------------------------------
   Table 1 - Congestion epoch duration vs congestion window
   size for an RTT of 100ms


4.1  RTT unfairness

   It follows from the introductory discussion that (when RTT scaling is
   not used) the level of unfairness between flows with different RTT's
   is similar to that with the current AIMD algorithm.  This behaviour
   is confirmed in experimental and simulation tests [HTCP04, Yi05].

4.2  Friendliness

   The mean AIMD increase parameter is shown in Table 2 for a range of
   bandwidth-delay products.  This an indication of the number of
   standard TCP flows (neglecting statistical multiplexing of backoffs)
   whose aggregate would be equivalent to a flow using increase function
   (1).  That is, an indication of friendliness and also of the packet
   drop overhead associated with the AIMD probing action.









Leith & Shorten         Expires December 27, 2005               [Page 7]


Internet-Draft                    H-TCP                        June 2005


   ------------------------------------------------------------------
   Congestion              Effective number of standard TCP flows
     window
   (packets)               10ms RTT        100ms RTT       250ms RTT
   ------------------------------------------------------------------
   10                      1               1               1
   100                     1               2               5
   1000                    3               12              22
   2000                    4               19              32
   5000                    8               33              55
   10000                   12              49              82
   20000                   19              72              123
   50000                   32              122             208
   ------------------------------------------------------------------
   Table 2 - Mean increase parameter (packets/RTT) vs congestion window
   size


4.3  Responsiveness

   Responsiveness is qualitatively similar to that of the current AIMD
   congestion control algorithm, i.e. the convergence time of TCP flows
   using an AIMD backoff factor of 0.5 is approximately 4 congestion
   epochs, although the congestion epoch duration is significantly
   shorter on high bandwidth-delay product paths (see Table 1).

4.4  Efficiency

   Link utilisation depends on queue provisioning in a similar manner to
   the current TCP congestion control algorithm.  That is, for a single
   flow (or multiple synchronised flows) 100% link utilisation requires
   that the queue be sized as the bandwidth-delay product.  Simulation
   and experimental tests indicate that statistical multiplexing between
   unsynchronised flows yields similar efficiency gains to standard TCP.

















Leith & Shorten         Expires December 27, 2005               [Page 8]


Internet-Draft                    H-TCP                        June 2005


5.  RTT Scaling

   We note that the parameter alpha determines the AIMD increase rate in
   packets per RTT.  Hence, flows with the same RTT have the same
   increase rate in packets per second, but flows with different RTTs
   have different increase rate in packets per second.  It is this that
   primarily leads to unfairness between flows with different RTTs.
   Removing RTT unfairness is not one of our objectives here.  However,
   we note that an AIMD flow generates roughly alpha packet drops per
   RTT as a result of its probing action.  Hence, flows with short RTT
   are more aggressive than flows with long RTT in the sense that they
   generate more packet drops over intervals of time measured in
   seconds.  We can reduce the aggressiveness of short RTT flows by
   scaling the increase parameter alpha with RTT.  This need not
   compromise the responsiveness of TCP flows.  As noted in [Sh04, Sh05,
   HTCP04], the convergence time of TCP flows using an AIMD backoff
   factor of 0.5 is approximately 4 congestion epochs.  Scaling alpha by
   RTT leads to scaling of the congestion epoch duration to become
   effectively the same for both short and long RTT flows.  The
   convergence time is therefore also scaled to be effectively the same
   for both short and long RTT flows.

   Such RTT scaling can be readily implemented by modifying the increase
   rule to

   if Delta <= Delta_L
      alpha  = 1
   else
      alpha = K x f_alpha(Delta)

   where K = RTT/RTT_ref.  Note that RTT scaling is not applied in low-
   speed conditions in order to maintain backward compatibility with
   legacy TCP flows (ensuring adequate backward compatibility presented
   a major difficulty in previous studies on the use of RTT scaling).
   Note also that the scaling is proportional to RTT rather than RTT^2,
   as we do not seek to achieve throughput fairness here.  RTT_ref is
   the reference RTT for which f_alpha is designed to ensure acceptable
   congestion epoch durations.













Leith & Shorten         Expires December 27, 2005               [Page 9]


Internet-Draft                    H-TCP                        June 2005


6.  Security Considerations

   Security implications are not discussed in this document.
















































Leith & Shorten         Expires December 27, 2005              [Page 10]


Internet-Draft                    H-TCP                        June 2005


7.  Acknowledgements

   This work was supported by Science Foundation Ireland grants 00/PI.1/
   C067 and 04/IN3/I460.















































Leith & Shorten         Expires December 27, 2005              [Page 11]


Internet-Draft                    H-TCP                        June 2005


8.  Informative References

   [Jain89] D.M. Chiu, R. Jain, Analysis of the increase and decrease
   algorithms for congestion avoidance in computer networks.  Computer
   Networks and ISDN Systems, 1989.

   [Flo03] S.Floyd, HighSpeed TCP for Large Congestion Windows .  Sally
   Floyd.  IETF RFC 3649, Experimental, Dec 2003.

   [FAST04] C. Jin, D.X. Wei, S,H. Low, FAST TCP: motivation,
   architecture, algorithms, performance.  Proc IEEE INFOCOM 2004.

   [Kelly02] T. Kelly, On engineering a stable and scalable TCP variant,
   Cambridge University Engineering Department Technical Report CUED/
   F-INFENG/TR.435, June 2002.

   [HTCP04] D.J.Leith, R.N.Shorten, H-TCP Protocol for High-Speed Long-
   Distance Networks.  Proc. 2nd Workshop on Protocols for Fast Long
   Distance Networks.  Argonne, USA, 2004.
   http://www.hamilton.ie/net/htcp3.pdf

   [BIC04] L. Xu, K. Harfoush, I. Rhee, Binary Increase Congestion
   Control for Fast Long-Distance Networks.  Proc.  INFOCOM 2004.

   [Sho04] R.N.Shorten, D.J.Leith,J.Foy, R.Kilduff, Analysis and design
   of congestion control in synchronised communication networks.
   Automatica, 2004. http://www.hamilton.ie/net/synchronised.pdf

   [Sho05] R.N.Shorten, F. Wirth,F., D.J. Leith, A positive systems
   model of TCP-like congestion control: Asymptotic results.
   http://www.hamilton.ie/net/unsynchronised_final.pdf

   [Yi05] Y.Li, D.J.Leith, R.N.Shorten, Experimental evaluation of TCP
   protocols of high-speed networks. http://www.hamilton.ie/net/eval/

   [Cot05] R.L. Cottrell, S. Ansari, P. Khandpur, R. Gupta, R. Hughes-
   Jones, M. Chen, L. MacIntosh, F. Leers, Characterization and
   Evaluation of TCP and UDP-Based Transport On Real Networks. .  Proc.
   3rd Workshop on Protocols for Fast Long-distance Networks, Lyon,
   France, 2005.

   [Hegde04] S. Hegde, D. Lapsley, B. Wydrowski, J. Lindheim, D.Wei, C.
   Jin, S. Low, H. Newman, FAST TCP in High Speed Networks: An
   Experimental Study.  Proc.  GridNets, San Jose, 2004.







Leith & Shorten         Expires December 27, 2005              [Page 12]


Internet-Draft                    H-TCP                        June 2005


Authors' Addresses

   Doug Leith
   Hamilton Institute
   NUI Maynooth
   Maynooth, Co. Kildare
   Ireland

   Email: doug.leith@nuim.ie


   Robert Shorten
   Hamilton Institute
   NUI Maynooth
   Maynooth, Co. KIldare
   Ireland

   Email: robert.shorten@nuim.ie

































Leith & Shorten         Expires December 27, 2005              [Page 13]


Internet-Draft                    H-TCP                        June 2005


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Disclaimer of Validity

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Copyright Statement

   Copyright (C) The Internet Society (2005).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.




Leith & Shorten         Expires December 27, 2005              [Page 14]