diff options
Diffstat (limited to 'doc/rfc/rfc896.txt')
| -rw-r--r-- | doc/rfc/rfc896.txt | 512 |
1 files changed, 512 insertions, 0 deletions
diff --git a/doc/rfc/rfc896.txt b/doc/rfc/rfc896.txt new file mode 100644 index 0000000..d8a480a --- /dev/null +++ b/doc/rfc/rfc896.txt @@ -0,0 +1,512 @@ + + +Network Working Group John Nagle +Request For Comments: 896 6 January 1984 + Ford Aerospace and Communications Corporation + + Congestion Control in IP/TCP Internetworks + +This memo discusses some aspects of congestion control in IP/TCP +Internetworks. It is intended to stimulate thought and further +discussion of this topic. While some specific suggestions are +made for improved congestion control implementation, this memo +does not specify any standards. + + Introduction + +Congestion control is a recognized problem in complex networks. +We have discovered that the Department of Defense's Internet Pro- +tocol (IP) , a pure datagram protocol, and Transmission Control +Protocol (TCP), a transport layer protocol, when used together, +are subject to unusual congestion problems caused by interactions +between the transport and datagram layers. In particular, IP +gateways are vulnerable to a phenomenon we call "congestion col- +lapse", especially when such gateways connect networks of widely +different bandwidth. We have developed solutions that prevent +congestion collapse. + +These problems are not generally recognized because these proto- +cols are used most often on networks built on top of ARPANET IMP +technology. ARPANET IMP based networks traditionally have uni- +form bandwidth and identical switching nodes, and are sized with +substantial excess capacity. This excess capacity, and the abil- +ity of the IMP system to throttle the transmissions of hosts has +for most IP / TCP hosts and networks been adequate to handle +congestion. With the recent split of the ARPANET into two inter- +connected networks and the growth of other networks with differ- +ing properties connected to the ARPANET, however, reliance on the +benign properties of the IMP system is no longer enough to allow +hosts to communicate rapidly and reliably. Improved handling of +congestion is now mandatory for successful network operation +under load. + +Ford Aerospace and Communications Corporation, and its parent +company, Ford Motor Company, operate the only private IP/TCP +long-haul network in existence today. This network connects four +facilities (one in Michigan, two in California, and one in Eng- +land) some with extensive local networks. This net is cross-tied +to the ARPANET but uses its own long-haul circuits; traffic +between Ford facilities flows over private leased circuits, +including a leased transatlantic satellite connection. All +switching nodes are pure IP datagram switches with no node-to- +node flow control, and all hosts run software either written or +heavily modified by Ford or Ford Aerospace. Bandwidth of links +in this network varies widely, from 1200 to 10,000,000 bits per +second. In general, we have not been able to afford the luxury +of excess long-haul bandwidth that the ARPANET possesses, and our +long-haul links are heavily loaded during peak periods. Transit +times of several seconds are thus common in our network. + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +Because of our pure datagram orientation, heavy loading, and wide +variation in bandwidth, we have had to solve problems that the +ARPANET / MILNET community is just beginning to recognize. Our +network is sensitive to suboptimal behavior by host TCP implemen- +tations, both on and off our own net. We have devoted consider- +able effort to examining TCP behavior under various conditions, +and have solved some widely prevalent problems with TCP. We +present here two problems and their solutions. Many TCP imple- +mentations have these problems; if throughput is worse through an +ARPANET / MILNET gateway for a given TCP implementation than +throughput across a single net, there is a high probability that +the TCP implementation has one or both of these problems. + + Congestion collapse + +Before we proceed with a discussion of the two specific problems +and their solutions, a description of what happens when these +problems are not addressed is in order. In heavily loaded pure +datagram networks with end to end retransmission, as switching +nodes become congested, the round trip time through the net +increases and the count of datagrams in transit within the net +also increases. This is normal behavior under load. As long as +there is only one copy of each datagram in transit, congestion is +under control. Once retransmission of datagrams not yet +delivered begins, there is potential for serious trouble. + +Host TCP implementations are expected to retransmit packets +several times at increasing time intervals until some upper limit +on the retransmit interval is reached. Normally, this mechanism +is enough to prevent serious congestion problems. Even with the +better adaptive host retransmission algorithms, though, a sudden +load on the net can cause the round-trip time to rise faster than +the sending hosts measurements of round-trip time can be updated. +Such a load occurs when a new bulk transfer, such a file +transfer, begins and starts filling a large window. Should the +round-trip time exceed the maximum retransmission interval for +any host, that host will begin to introduce more and more copies +of the same datagrams into the net. The network is now in seri- +ous trouble. Eventually all available buffers in the switching +nodes will be full and packets must be dropped. The round-trip +time for packets that are delivered is now at its maximum. Hosts +are sending each packet several times, and eventually some copy +of each packet arrives at its destination. This is congestion +collapse. + +This condition is stable. Once the saturation point has been +reached, if the algorithm for selecting packets to be dropped is +fair, the network will continue to operate in a degraded condi- +tion. In this condition every packet is being transmitted +several times and throughput is reduced to a small fraction of +normal. We have pushed our network into this condition experi- +mentally and observed its stability. It is possible for round- +trip time to become so large that connections are broken because + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +the hosts involved time out. + +Congestion collapse and pathological congestion are not normally +seen in the ARPANET / MILNET system because these networks have +substantial excess capacity. Where connections do not pass +through IP gateways, the IMP-to host flow control mechanisms usu- +ally prevent congestion collapse, especially since TCP implemen- +tations tend to be well adjusted for the time constants associ- +ated with the pure ARPANET case. However, other than ICMP Source +Quench messages, nothing fundamentally prevents congestion col- +lapse when TCP is run over the ARPANET / MILNET and packets are +being dropped at gateways. Worth noting is that a few badly- +behaved hosts can by themselves congest the gateways and prevent +other hosts from passing traffic. We have observed this problem +repeatedly with certain hosts (with whose administrators we have +communicated privately) on the ARPANET. + +Adding additional memory to the gateways will not solve the prob- +lem. The more memory added, the longer round-trip times must +become before packets are dropped. Thus, the onset of congestion +collapse will be delayed but when collapse occurs an even larger +fraction of the packets in the net will be duplicates and +throughput will be even worse. + + The two problems + +Two key problems with the engineering of TCP implementations have +been observed; we call these the small-packet problem and the +source-quench problem. The second is being addressed by several +implementors; the first is generally believed (incorrectly) to be +solved. We have discovered that once the small-packet problem +has been solved, the source-quench problem becomes much more +tractable. We thus present the small-packet problem and our +solution to it first. + + The small-packet problem + +There is a special problem associated with small packets. When +TCP is used for the transmission of single-character messages +originating at a keyboard, the typical result is that 41 byte +packets (one byte of data, 40 bytes of header) are transmitted +for each byte of useful data. This 4000% overhead is annoying +but tolerable on lightly loaded networks. On heavily loaded net- +works, however, the congestion resulting from this overhead can +result in lost datagrams and retransmissions, as well as exces- +sive propagation time caused by congestion in switching nodes and +gateways. In practice, throughput may drop so low that TCP con- +nections are aborted. + +This classic problem is well-known and was first addressed in the +Tymnet network in the late 1960s. The solution used there was to +impose a limit on the count of datagrams generated per unit time. +This limit was enforced by delaying transmission of small packets + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +until a short (200-500ms) time had elapsed, in hope that another +character or two would become available for addition to the same +packet before the timer ran out. An additional feature to +enhance user acceptability was to inhibit the time delay when a +control character, such as a carriage return, was received. + +This technique has been used in NCP Telnet, X.25 PADs, and TCP +Telnet. It has the advantage of being well-understood, and is not +too difficult to implement. Its flaw is that it is hard to come +up with a time limit that will satisfy everyone. A time limit +short enough to provide highly responsive service over a 10M bits +per second Ethernet will be too short to prevent congestion col- +lapse over a heavily loaded net with a five second round-trip +time; and conversely, a time limit long enough to handle the +heavily loaded net will produce frustrated users on the Ethernet. + + The solution to the small-packet problem + +Clearly an adaptive approach is desirable. One would expect a +proposal for an adaptive inter-packet time limit based on the +round-trip delay observed by TCP. While such a mechanism could +certainly be implemented, it is unnecessary. A simple and +elegant solution has been discovered. + +The solution is to inhibit the sending of new TCP segments when +new outgoing data arrives from the user if any previously +transmitted data on the connection remains unacknowledged. This +inhibition is to be unconditional; no timers, tests for size of +data received, or other conditions are required. Implementation +typically requires one or two lines inside a TCP program. + +At first glance, this solution seems to imply drastic changes in +the behavior of TCP. This is not so. It all works out right in +the end. Let us see why this is so. + +When a user process writes to a TCP connection, TCP receives some +data. It may hold that data for future sending or may send a +packet immediately. If it refrains from sending now, it will +typically send the data later when an incoming packet arrives and +changes the state of the system. The state changes in one of two +ways; the incoming packet acknowledges old data the distant host +has received, or announces the availability of buffer space in +the distant host for new data. (This last is referred to as +"updating the window"). Each time data arrives on a connec- +tion, TCP must reexamine its current state and perhaps send some +packets out. Thus, when we omit sending data on arrival from the +user, we are simply deferring its transmission until the next +message arrives from the distant host. A message must always +arrive soon unless the connection was previously idle or communi- +cations with the other end have been lost. In the first case, +the idle connection, our scheme will result in a packet being +sent whenever the user writes to the TCP connection. Thus we do +not deadlock in the idle condition. In the second case, where + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +the distant host has failed, sending more data is futile anyway. +Note that we have done nothing to inhibit normal TCP retransmis- +sion logic, so lost messages are not a problem. + +Examination of the behavior of this scheme under various condi- +tions demonstrates that the scheme does work in all cases. The +first case to examine is the one we wanted to solve, that of the +character-oriented Telnet connection. Let us suppose that the +user is sending TCP a new character every 200ms, and that the +connection is via an Ethernet with a round-trip time including +software processing of 50ms. Without any mechanism to prevent +small-packet congestion, one packet will be sent for each charac- +ter, and response will be optimal. Overhead will be 4000%, but +this is acceptable on an Ethernet. The classic timer scheme, +with a limit of 2 packets per second, will cause two or three +characters to be sent per packet. Response will thus be degraded +even though on a high-bandwidth Ethernet this is unnecessary. +Overhead will drop to 1500%, but on an Ethernet this is a bad +tradeoff. With our scheme, every character the user types will +find TCP with an idle connection, and the character will be sent +at once, just as in the no-control case. The user will see no +visible delay. Thus, our scheme performs as well as the no- +control scheme and provides better responsiveness than the timer +scheme. + +The second case to examine is the same Telnet test but over a +long-haul link with a 5-second round trip time. Without any +mechanism to prevent small-packet congestion, 25 new packets +would be sent in 5 seconds.* Overhead here is 4000%. With the +classic timer scheme, and the same limit of 2 packets per second, +there would still be 10 packets outstanding and contributing to +congestion. Round-trip time will not be improved by sending many +packets, of course; in general it will be worse since the packets +will contend for line time. Overhead now drops to 1500%. With +our scheme, however, the first character from the user would find +an idle TCP connection and would be sent immediately. The next +24 characters, arriving from the user at 200ms intervals, would +be held pending a message from the distant host. When an ACK +arrived for the first packet at the end of 5 seconds, a single +packet with the 24 queued characters would be sent. Our scheme +thus results in an overhead reduction to 320% with no penalty in +response time. Response time will usually be improved with our +scheme because packet overhead is reduced, here by a factor of +4.7 over the classic timer scheme. Congestion will be reduced by +this factor and round-trip delay will decrease sharply. For this +________ + * This problem is not seen in the pure ARPANET case because the + IMPs will block the host when the count of packets + outstanding becomes excessive, but in the case where a pure + datagram local net (such as an Ethernet) or a pure datagram + gateway (such as an ARPANET / MILNET gateway) is involved, it + is possible to have large numbers of tiny packets + outstanding. + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +case, our scheme has a striking advantage over either of the +other approaches. + +We use our scheme for all TCP connections, not just Telnet con- +nections. Let us see what happens for a file transfer data con- +nection using our technique. The two extreme cases will again be +considered. + +As before, we first consider the Ethernet case. The user is now +writing data to TCP in 512 byte blocks as fast as TCP will accept +them. The user's first write to TCP will start things going; our +first datagram will be 512+40 bytes or 552 bytes long. The +user's second write to TCP will not cause a send but will cause +the block to be buffered. Assume that the user fills up TCP's +outgoing buffer area before the first ACK comes back. Then when +the ACK comes in, all queued data up to the window size will be +sent. From then on, the window will be kept full, as each ACK +initiates a sending cycle and queued data is sent out. Thus, +after a one round-trip time initial period when only one block is +sent, our scheme settles down into a maximum-throughput condi- +tion. The delay in startup is only 50ms on the Ethernet, so the +startup transient is insignificant. All three schemes provide +equivalent performance for this case. + +Finally, let us look at a file transfer over the 5-second round +trip time connection. Again, only one packet will be sent until +the first ACK comes back; the window will then be filled and kept +full. Since the round-trip time is 5 seconds, only 512 bytes of +data are transmitted in the first 5 seconds. Assuming a 2K win- +dow, once the first ACK comes in, 2K of data will be sent and a +steady rate of 2K per 5 seconds will be maintained thereafter. +Only for this case is our scheme inferior to the timer scheme, +and the difference is only in the startup transient; steady-state +throughput is identical. The naive scheme and the timer scheme +would both take 250 seconds to transmit a 100K byte file under +the above conditions and our scheme would take 254 seconds, a +difference of 1.6%. + +Thus, for all cases examined, our scheme provides at least 98% of +the performance of both other schemes, and provides a dramatic +improvement in Telnet performance over paths with long round trip +times. We use our scheme in the Ford Aerospace Software +Engineering Network, and are able to run screen editors over Eth- +ernet and talk to distant TOPS-20 hosts with improved performance +in both cases. + + Congestion control with ICMP + +Having solved the small-packet congestion problem and with it the +problem of excessive small-packet congestion within our own net- +work, we turned our attention to the problem of general conges- +tion control. Since our own network is pure datagram with no +node-to-node flow control, the only mechanism available to us + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +under the IP standard was the ICMP Source Quench message. With +careful handling, we find this adequate to prevent serious +congestion problems. We do find it necessary to be careful about +the behavior of our hosts and switching nodes regarding Source +Quench messages. + + When to send an ICMP Source Quench + +The present ICMP standard* specifies that an ICMP Source Quench +message should be sent whenever a packet is dropped, and addi- +tionally may be sent when a gateway finds itself becoming short +of resources. There is some ambiguity here but clearly it is a +violation of the standard to drop a packet without sending an +ICMP message. + +Our basic assumption is that packets ought not to be dropped dur- +ing normal network operation. We therefore want to throttle +senders back before they overload switching nodes and gateways. +All our switching nodes send ICMP Source Quench messages well +before buffer space is exhausted; they do not wait until it is +necessary to drop a message before sending an ICMP Source Quench. +As demonstrated in our analysis of the small-packet problem, +merely providing large amounts of buffering is not a solution. +In general, our experience is that Source Quench should be sent +when about half the buffering space is exhausted; this is not +based on extensive experimentation but appears to be a reasonable +engineering decision. One could argue for an adaptive scheme +that adjusted the quench generation threshold based on recent +experience; we have not found this necessary as yet. + +There exist other gateway implementations that generate Source +Quenches only after more than one packet has been discarded. We +consider this approach undesirable since any system for control- +ling congestion based on the discarding of packets is wasteful of +bandwidth and may be susceptible to congestion collapse under +heavy load. Our understanding is that the decision to generate +Source Quenches with great reluctance stems from a fear that ack- +nowledge traffic will be quenched and that this will result in +connection failure. As will be shown below, appropriate handling +of Source Quench in host implementations eliminates this possi- +bility. + + What to do when an ICMP Source Quench is received + +We inform TCP or any other protocol at that layer when ICMP +receives a Source Quench. The basic action of our TCP implemen- +tations is to reduce the amount of data outstanding on connec- +tions to the host mentioned in the Source Quench. This control is +________ + * ARPANET RFC 792 is the present standard. We are advised by + the Defense Communications Agency that the description of + ICMP in MIL-STD-1777 is incomplete and will be deleted from + future revision of that standard. + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +applied by causing the sending TCP to behave as if the distant +host's window size has been reduced. Our first implementation +was simplistic but effective; once a Source Quench has been +received our TCP behaves as if the window size is zero whenever +the window isn't empty. This behavior continues until some +number (at present 10) of ACKs have been received, at that time +TCP returns to normal operation.* David Mills of Linkabit Cor- +poration has since implemented a similar but more elaborate +throttle on the count of outstanding packets in his DCN systems. +The additional sophistication seems to produce a modest gain in +throughput, but we have not made formal tests. Both implementa- +tions effectively prevent congestion collapse in switching nodes. + +Source Quench thus has the effect of limiting the connection to a +limited number (perhaps one) of outstanding messages. Thus, com- +munication can continue but at a reduced rate, that is exactly +the effect desired. + +This scheme has the important property that Source Quench doesn't +inhibit the sending of acknowledges or retransmissions. Imple- +mentations of Source Quench entirely within the IP layer are usu- +ally unsuccessful because IP lacks enough information to throttle +a connection properly. Holding back acknowledges tends to pro- +duce retransmissions and thus unnecessary traffic. Holding back +retransmissions may cause loss of a connection by a retransmis- +sion timeout. Our scheme will keep connections alive under +severe overload but at reduced bandwidth per connection. + +Other protocols at the same layer as TCP should also be respon- +sive to Source Quench. In each case we would suggest that new +traffic should be throttled but acknowledges should be treated +normally. The only serious problem comes from the User Datagram +Protocol, not normally a major traffic generator. We have not +implemented any throttling in these protocols as yet; all are +passed Source Quench messages by ICMP but ignore them. + + Self-defense for gateways + +As we have shown, gateways are vulnerable to host mismanagement +of congestion. Host misbehavior by excessive traffic generation +can prevent not only the host's own traffic from getting through, +but can interfere with other unrelated traffic. The problem can +be dealt with at the host level but since one malfunctioning host +can interfere with others, future gateways should be capable of +defending themselves against such behavior by obnoxious or mali- +cious hosts. We offer some basic self-defense techniques. + +On one occasion in late 1983, a TCP bug in an ARPANET host caused +the host to frantically generate retransmissions of the same +datagram as fast as the ARPANET would accept them. The gateway +________ + * This follows the control engineering dictum "Never bother + with proportional control unless bang-bang doesn't work". + + +RFC 896 Congestion Control in IP/TCP Internetworks 1/6/84 + + +that connected our net with the ARPANET was saturated and little +useful traffic could get through, since the gateway had more +bandwidth to the ARPANET than to our net. The gateway busily +sent ICMP Source Quench messages but the malfunctioning host +ignored them. This continued for several hours, until the mal- +functioning host crashed. During this period, our network was +effectively disconnected from the ARPANET. + +When a gateway is forced to discard a packet, the packet is +selected at the discretion of the gateway. Classic techniques +for making this decision are to discard the most recently +received packet, or the packet at the end of the longest outgoing +queue. We suggest that a worthwhile practical measure is to dis- +card the latest packet from the host that originated the most +packets currently queued within the gateway. This strategy will +tend to balance throughput amongst the hosts using the gateway. +We have not yet tried this strategy, but it seems a reasonable +starting point for gateway self-protection. + +Another strategy is to discard a newly arrived packet if the +packet duplicates a packet already in the queue. The computa- +tional load for this check is not a problem if hashing techniques +are used. This check will not protect against malicious hosts +but will provide some protection against TCP implementations with +poor retransmission control. Gateways between fast local net- +works and slower long-haul networks may find this check valuable +if the local hosts are tuned to work well with the local network. + +Ideally the gateway should detect malfunctioning hosts and +squelch them; such detection is difficult in a pure datagram sys- +tem. Failure to respond to an ICMP Source Quench message, +though, should be regarded as grounds for action by a gateway to +disconnect a host. Detecting such failure is non-trivial but is +a worthwhile area for further research. + + Conclusion + +The congestion control problems associated with pure datagram +networks are difficult, but effective solutions exist. If IP / +TCP networks are to be operated under heavy load, TCP implementa- +tions must address several key issues in ways at least as effec- +tive as the ones described here. + |