ABSTRACT
In October of '86, the Internet had the first of what became a series of 'congestion collapses'. During this period, the data throughput from LBL to UC Berkeley (sites separated by 400 yards and three IMP hops) dropped from 32 Kbps to 40 bps. Mike Karels1 and I were fascinated by this sudden factor-of-thousand drop in bandwidth and embarked on an investigation of why things had gotten so bad. We wondered, in particular, if the 4.3BSD (Berkeley UNIX) TCP was mis-behaving or if it could be tuned to work better under abysmal network conditions. The answer to both of these questions was “yes”.
Since that time, we have put seven new algorithms into the 4BSD TCP:
round-trip-time variance estimation
exponential retransmit timer backoff
slow-start
more aggressive receiver ack policy
dynamic window sizing on congestion
Karn's clamped retransmit backoff
fast retransmit Our measurements and the reports of beta testers suggest that the final product is fairly good at dealing with congested conditions on the Internet.
This paper is a brief description of (i) - (v) and the rationale behind them. (vi) is an algorithm recently developed by Phil Karn of Bell Communications Research, described in [KP87]. (viii) is described in a soon-to-be-published RFC.
Algorithms (i) - (v) spring from one observation: The flow on a TCP connection (or ISO TP-4 or Xerox NS SPP connection) should obey a 'conservation of packets' principle. And, if this principle were obeyed, congestion collapse would become the exception rather than the rule. Thus congestion control involves finding places that violate conservation and fixing them.
By 'conservation of packets' I mean that for a connection 'in equilibrium', i.e., running stably with a full window of data in transit, the packet flow is what a physicist would call 'conservative': A new packet isn't put into the network until an old packet leaves. The physics of flow predicts that systems with this property should be robust in the face of congestion. Observation of the Internet suggests that it was not particularly robust. Why the discrepancy?
There are only three ways for packet conservation to fail:
The connection doesn't get to equilibrium, or
A sender injects a new packet before an old packet has exited, or
The equilibrium can't be reached because of resource limits along the path. In the following sections, we treat each of these in turn.
- Ald87.David J. Aldous. Ultimate instability of exponential back-off protocol for acknowledgment based transmission control of random access communication channels. IEEE Transactions on Information Theory, IT- 33(2), March 1987.]] Google ScholarDigital Library
- Cla82.David Clark. Window and Acknowlegement Strategy in TCP. ARPANET Working Group Requests for Comment, DDN Network Information Center, SRI International Menlo Park, CA, July 1982. RFC-813.]] Google ScholarDigital Library
- Edg83.Stephen William Edge. An adaptive timeout algorithm for retransmission across a packet switching network. In Proceedings of SIGCOMM '83. ACM, March 1983.]]Google Scholar
- Fel71.William Feller Probability Theory and its Applications, volume II. John Wiley & Sons, second edition, 1971.]]Google Scholar
- IETF87.Internet Engineering Task Force meeting, Boston, MA, April 1987. Proceedings available as NIC document IETF-87/2P from DDN Network Information Center, SRI International, Menlo Park, CA.]]Google Scholar
- IETF88.Internet Engineering Task Force meeting, San Diego, CA, March 1988. Proceedings available as NIC document IETF-88/?P from DDN Network Information Center, $RI international, Menlo Park, CA.]]Google Scholar
- ISO86.International Organization for Standardization. ISO International Standard 8473, Information Processing Systems-- Open Systems Interconnection -Connectionless-mode Network Service Protocol Specification, March 1986.]]Google Scholar
- Jai86a.Raj Jain. Divergence of timeout algorithms for packet retransmissions. In Proceedings Fifth Annual International Phoenix Conference on Computers and Communications, Scottsdale, AZ, March 1986.]]Google Scholar
- Jai86b.RajJain. A timeout-based congestion control scheme for window flow-controlled networks. IEEE Journal on Selected Areas in Communications, SAC-4(7), October 1986.]]Google Scholar
- JRC87.Raj Jain, K.K. Ramakrishnan, and Dah-Ming Chiu. Congestion avoidance in computer networks with a connectionless network layer. Technical Report DEC-TR-506, Digital Equipment Corporation, August 1987.]]Google Scholar
- Kle76.Leonard Kleinrock. Queueing Systems, volume II. John Wiley & Sons, 1976.]]Google Scholar
- Kli87.Charley Kline. Supercomputers on the Internet: A case study. In Proceedings of SIGCOMM '87. ACM, August 1987.]] Google ScholarDigital Library
- KP87.Phil Karn and Craig Partridge. Estimating roundtrip times in reliable transport protocols. In Proceedings of SIGCOMM '87. ACM, August 1987.]] Google ScholarDigital Library
- LS83.Lennart Ljung and Torsten SSderstrSm. Theory and Practice of Recursive Identification. MIT Press, 1983.]]Google Scholar
- Mil83.David Mills. Internet Delay Experiments. ARPANET Working Group Requests for Comment, DDN Network Information Center, SRI International, Menlo Park, CA, December 1983. RFC-889.]] Google ScholarDigital Library
- Nag84.John Nagle. Congestion Control in IP/TCP Internetworks. ARPANET Working Group Requests for Comment, DDN Network Information Center, SRI International, Menlo Park, CA, January 1984. RFC-896.]] Google ScholarDigital Library
- PP87.W. Prue and J. Postel. Something A Host Could Do with Source Quench. ARPANti'r Working Group Requests for Comment, DDN Network Information Center, SRI International, Menlo Park, CA, July 1987. RFC- 1016.]] Google ScholarDigital Library
- RFC793.Jon Postel, editor. Transmission Control Protocol Specification. ARP^NET Working Group Requests for Comment, DDN Network Information Center, SRI International, Menlo Park, CA, September 1981. RFC-793.]]Google Scholar
- Zha86.Lixia Zhang. Why TCP timers don't work well. In Proceedings of StGCOMM '86. ACM, August 1986.]] Google ScholarDigital Library
Index Terms
- Congestion avoidance and control
Recommendations
Delay-based congestion avoidance for TCP
The set of TCP congestion control algorithms associated with TCP/Reno (e.g., slow-start and congestion avoidance) have been crucial to ensuring the stability of the Internet. Algorithms such as TCP/NewReno (which has been deployed) and TCP/Vegas (which ...
Delay-based TCP congestion avoidance: A network calculus interpretation and performance improvements
In delay-based TCP congestion avoidance mechanisms, a source adjusts its window size to adapt to changes in network conditions as measured through changing queueing delays. Although network calculus (NC) has been used to study window flow control and ...
Comments