diff options
Diffstat (limited to 'doc/rfc/rfc1254.txt')
| -rw-r--r-- | doc/rfc/rfc1254.txt | 1403 |
1 files changed, 1403 insertions, 0 deletions
diff --git a/doc/rfc/rfc1254.txt b/doc/rfc/rfc1254.txt new file mode 100644 index 0000000..8cc3b10 --- /dev/null +++ b/doc/rfc/rfc1254.txt @@ -0,0 +1,1403 @@ + + + + + + +Network Working Group A. Mankin +Request for Comments: 1254 MITRE + K. Ramakrishnan + Digital Equipment Corporation + Editors + August 1991 + + + Gateway Congestion Control Survey + +Status of this Memo + + This memo provides information for the Internet community. It is a + survey of some of the major directions and issues. It does not + specify an Internet standard. Distribution of this memo is + unlimited. + +Abstract + + The growth of network intensive Internet applications has made + gateway congestion control a high priority. The IETF Performance and + Congestion Control Working Group surveyed and reviewed gateway + congestion control and avoidance approaches. The purpose of this + paper is to present our review of the congestion control approaches, + as a way of encouraging new discussion and experimentation. Included + in the survey are Source Quench, Random Drop, Congestion Indication + (DEC Bit), and Fair Queueing. The task remains for Internet + implementors to determine and agree on the most effective mechanisms + for controlling gateway congestion. + +1. Introduction + + Internet users regularly encounter congestion, often in mild forms. + However, severe congestion episodes have been reported also; and + gateway congestion remains an obstacle for Internet applications such + as scientific supercomputing data transfer. The need for Internet + congestion control originally became apparent during several periods + of 1986 and 1987, when the Internet experienced the "congestion + collapse" condition predicted by Nagle [Nag84]. A large number of + widely dispersed Internet sites experienced simultaneous slowdown or + cessation of networking services for prolonged periods. BBN, the + firm responsible for maintaining the then backbone of the Internet, + the ARPANET, responded to the collapse by adding link capacity + [Gar87]. + + Much of the Internet now uses as a transmission backbone the National + Science Foundation Network (NSFNET). Extensive monitoring and + capacity planning are being done for the NSFNET backbone; still, as + + + +Performance and Congestion Control Working Group [Page 1] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + the demand for this capacity grows, and as resource-intensive + applications such as wide-area file system management [Sp89] + increasingly use the backbone, effective congestion control policies + will be a critical requirement. + + Only a few mechanisms currently exist in Internet hosts and gateways + to avoid or control congestion. The mechanisms for handling + congestion set forth in the specifications for the DoD Internet + protocols are limited to: + + Window flow control in TCP [Pos81b], intended primarily for + controlling the demand on the receiver's capacity, both in terms + of processing and buffers. + + Source quench in ICMP, the message sent by IP to request that a + sender throttle back [Pos81a]. + + One approach to enhancing Internet congestion control has been to + overlay the simple existing mechanisms in TCP and ICMP with more + powerful ones. Since 1987, the TCP congestion control policy, Slow- + start, a collection of several algorithms developed by Van Jacobson + and Mike Karels [Jac88], has been widely adopted. Successful Internet + experiences with Slow-start led to the Host Requirements RFC [HREQ89] + classifying the algorithms as mandatory for TCP. Slow-start modifies + the user's demand when congestion reaches such a point that packets + are dropped at the gateway. By the time such overflows occur, the + gateway is congested. Jacobson writes that the Slow-start policy is + intended to function best with a complementary gateway policy + [Jac88]. + +1.1 Definitions + + The characteristics of the Internet that we are interested in include + that it is, in general, an arbitrary mesh-connected network. The + internetwork protocol is connectionless. The number of users that + place demands on the network is not limited by any explicit + mechanism; no reservation of resources occurs and transport layer + set-ups are not disallowed due to lack of resources. A path from a + source to destination host may have multiple hops, through several + gateways and links. Paths through the Internet may be heterogeneous + (though homogeneous paths also exist and experience congestion). + That is, links may be of different speeds. Also, the gateways and + hosts may be of different speeds or may be providing only a part of + their processing power to communication-related activity. The + buffers for storing information flowing through Internet gateways are + finite. The nature of the internet protocol is to drop packets when + these buffers overflow. + + + + +Performance and Congestion Control Working Group [Page 2] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + Gateway congestion arises when the demand for one or more of the + resources of the gateway exceeds the capacity of that resource. The + resources include transmission links, processing, and space used for + buffering. Operationally, uncongested gateways operate with little + queueing on average, where the queue is the waiting line for a + particular resource of the gateway. One commonly used quantitative + definition [Kle79] for when a resource is congested is when the + operating point is greater than the point at which resource power is + maximum, where resource power is defined as the ratio of throughput + to delay (See Section 2.2). At this operating point, the average + queue size is close to one, including the packet in service. Note + that this is a long-term average queue size. Several definitions + exist for the timescale of averaging for congestion detection and + control, such as dominant round-trip time and queue regeneration + cycle (see Section 2.1). + + Mechanisms for handling congestion may be divided into two + categories, congestion recovery and congestion avoidance. Congestion + recovery tries to restore an operating state, when demand has already + exceeded capacity. Congestion avoidance is preventive in nature. It + tries to keep the demand on the network at or near the point of + maximum power, so that congestion never occurs. Without congestion + recovery, the network may cease to operate entirely (zero + throughput), whereas the Internet has been operating without + congestion avoidance for a long time. Overall performance may + improve with an effective congestion avoidance mechanism. Even if + effective congestion avoidance was in place, congestion recovery + schemes would still be required, to retain throughput in the face of + sudden changes (increase of demand, loss of resources) that can lead + to congestion. + + In this paper, the term "user" refers to each individual transport + (TCP or another transport protocol) entity. For example, a TCP + connection is a "user" in this terminology. The terms "flow" and + "stream" are used by some authors in the same sense. Some of the + congestion control policies discussed in this paper, such as + Selective Feedback Congestion Indication and Fair Queueing aggregate + multiple TCP connections from a single host (or between a source + host-destination host pair) as a virtual user. + + The term "cooperating transport entities" will be defined as a set of + TCP connections (for example) which follow an effective method of + adjusting their demand on the Internet in response to congestion. + The most restrictive interpretation of this term is that the + transport entities follow identical algorithms for congestion control + and avoidance. However, there may be some variation in these + algorithms. The extent to which heterogeneous end-system congestion + control and avoidance may be accommodated by gateway policies should + + + +Performance and Congestion Control Working Group [Page 3] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + be a subject of future research. The role played in Internet + performance of non-cooperating transport entities is discussed in + Section 5. + +1.2 Goals and Scope of This Paper + + The task remains for Internet implementors to determine effective + mechanisms for controlling gateway congestion. There has been + minimal common practice on which to base recommendations for Internet + gateway congestion control. In this survey, we describe the + characteristics of one experimental gateway congestion management + policy, Random Drop, and several that are better-known: Source + Quench, Congestion Indication, Selective Feedback Congestion + Indication, and Fair Queueing, both Bit-Round and Stochastic. A + motivation for documenting Random Drop is that it has as primary + goals low overhead and suitability for scaling up for Internets with + higher speed links. Both of these are important goals for future + gateway implementations that will have fast links, fast processors, + and will have to serve large numbers of interconnected hosts. + + The structure of this paper is as follows. First, we discuss + performance goals, including timescale and fairness considerations. + Second, we discuss the gateway congestion control policies. Random + Drop is sketched out, with a recommendation for using it for + congestion recovery and a separate section on its use as congestion + avoidance. Third, since gateway congestion control in itself does + not change the end-systems' demand, we briefly present the effective + responses to these policies by two end-system congestion control + schemes, Slow-start and End-System Congestion Indication. Among our + conclusions, we address the issues of transport entities that do not + cooperate with gateway congestion control. As an appendix, because + of the potential interactions with gateway congestion policies, we + report on a scheme to help in controlling the performance of Internet + gateways to connection-oriented subnets (in particular, X.25). + + Resources in the current Internet are not charged to users of them. + Congestion avoidance techniques cannot be expected to help when users + increase beyond the capacity of the underlying facilities. There are + two possible solutions for this, increase the facilities and + available bandwidth, or forcibly reduce the demand. When congestion + is persistent despite implemented congestion control mechanisms, + administrative responses are needed. These are naturally not within + the scope of this paper. Also outside the scope of this paper are + routing techniques that may be used to relocate demand away from + congested individual resources (e.g., path-splitting and load- + balancing). + + + + + +Performance and Congestion Control Working Group [Page 4] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + +2. Performance Goals + + To be able to discuss design and use of various mechanisms for + improving Internetwork performance, we need to have clear performance + goals for the operation of gateways and sets of end-systems. + Internet experience shows that congestion control should be based on + adaptive principles; this requires efficient computation of metrics + by algorithms for congestion control. The first issue is that of the + interval over which these metrics are estimated and/or measured. + +2.1 Interval for Measurement/Estimation of Performance Metrics + + Network performance metrics may be distorted if they are computed + over intervals that are too short or too long relative to the dynamic + characteristics of the network. For instance, within a small + interval, two FTP users with equal paths may appear to have sharply + different demands, as an effect of brief, transient fluctuations in + their respective processing. An overly long averaging interval + results in distortions because of the changing number of users + sharing the resource measured during the time. It is similarly + important for congestion control mechanisms exerted at end systems to + find an appropriate interval for control. + + The first approach to the monitoring, or averaging, interval for + congestion control is one based on round-trip times. The rationale + for it is as follows: control mechanisms must adapt to changes in + Internet congestion as quickly as possible. Even on an uncongested + path, changed conditions will not be detected by the sender faster + than a round-trip time. The effect of a sending end-system's control + will also not be seen in less than a round-trip time in the entire + path as well as at the end systems. For the control mechanism to be + adaptive, new information on the path is needed before making a + modification to the control exerted. The statistics and metrics used + in congestion control must be able to provide information to the + control mechanism so that it can make an informed decision. + Transient information which may be obsolete before a change is made + by the end-system should be avoided. This implies the + monitoring/estimating interval is one lasting one or more round + trips. The requirements described here give bounds on: + + How short an interval: not small enough that obsolete information + is used for control; + + How long: not more than the period at which the end-system makes + changes. + + But, from the point of view of the gateway congestion control policy, + what is a round-trip time? If all the users of a given gateway have + + + +Performance and Congestion Control Working Group [Page 5] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + the same path through the Internet, they also have the same round- + trip time through the gateway. But this is rarely the case. + + A meaningful interval must be found for users with both short and + long paths. Two approaches have been suggested for estimating this + dynamically, queue regeneration cycle and frequency analysis. + + Use of the queue regeneration cycle has been described as part of the + Congestion Indication policy. The time period used for averaging + here begins when a resource goes from the idle to busy state. The + basic interval for averaging is a "regeneration cycle" which is in + the form of busy and idle intervals. Because an average based on a + single previous regeneration may become old information, the + recommendation in [JRC87] is to average over the sum of two + intervals, that is, the previous (busy and idle) period, and the time + since the beginning of the current busy period. + + If the gateway users are window-based transport entities, it is + possible to see how the regeneration interval responds to their + round-trip times. If a user with a long round-trip time has the + dominant traffic, the queue length may be zero only when that user is + awaiting acknowledgements. Then the users with short paths will + receive gateway congestion information that is averaged over several + of their round-trip times. If the short path traffic dominates the + activity in the gateway, i.e., the connections with shorter round- + trip times are the dominant users of the gateway resources, then the + regeneration interval is shorter and the information communicated to + them can be more timely. In this case, users with longer paths + receive, in one of their round-trip times, multiple samples of the + dominant traffic; the end system averaging is based on individual + user's intervals, so that these multiple samples are integrated + appropriately for these connections with longer paths. + + The use of frequency analysis has been described by [Jac89]. In this + approach, the gateway congestion control is done at intervals based + on spectral analysis of the traffic arrivals. It is possible for + users to have round-trip times close to each other, but be out of + phase from each other. A spectral analysis algorithm detects this. + Otherwise, if multiple round-trip times are significant, multiple + intervals will be identified. Either one of these will be + predominant, or several will be comparable. An as yet difficult + problem for the design of algorithms accomplishing this technique is + the likelihood of "locking" to the frequency of periodic traffic of + low intensity, such as routing updates. + + + + + + + +Performance and Congestion Control Working Group [Page 6] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + +2.2 Power and its Relationship to the Operating Point + + Performance goals for a congestion control/avoidance strategy embody + a conflict in that they call for as high a throughput as possible, + with as little delay as possible. A measure that is often used to + reflect the tradeoff between these goals is power, the ratio of + throughput to delay. We would like to maximize the value of power + for a given resource. In the standard expression for power, + + Power = (Throughput^alpha)/Delay + + the exponent alpha is chosen for throughput, based on the relative + emphasis placed on throughput versus delay: if throughput is more + important, then a value of A alpha greater than one is chosen. If + throughput and delay are equally important (e.g., both bulk transfer + traffic and interactive traffic are equally important), then alpha + equal to one is chosen. The operating point where power is maximized + is the "knee" in the throughput and delay curves. It is desirable + that the operating point of the resource be driven towards the knee, + where power is maximized. A useful property of power is that it is + decreasing whether the resource is under- or over-utilized relative + to the knee. + + In an internetwork comprising nodes and links of diverse speeds and + utilization, bottlenecks or concentrations of demand may form. Any + particular user can see a single bottleneck, which is the slowest or + busiest link or gateway in the path (or possibly identical "balanced" + bottlenecks). The throughput that the path can sustain is limited by + the bottleneck. The delay for packets through a particular path is + determined by the service times and queueing at each individual hop. + The queueing delay is dominated by the queueing at the bottleneck + resource(s). The contribution to the delay over other hops is + primarily the service time, although the propagation delay over + certain hops, such as a satellite link, can be significant. We would + like to operate all shared resources at their knee and maximize the + power of every user's bottleneck. + + The above goal underscores the significance of gateway congestion + control. If techniques can be found to operate gateways at their + resource knee, it can improve Internet performance broadly. + +2.3 Fairness + + We would like gateways to allocate resources fairly to users. A + concept of fairness is only relevant when multiple users share a + gateway and their total demand is greater than its capacity. If + demands were equal, a fair allocation of the resource would be to + provide an equal share to each user. But even over short intervals, + + + +Performance and Congestion Control Working Group [Page 7] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + demands are not equal. Identifying the fair share of the resource + for the user becomes hard. Having identified it, it is desirable to + allocate at least this fair share to each user. However, not all + users may take advantage of this allocation. The unused capacity can + be given to other users. The resulting final allocation is termed a + maximally fair allocation. [RJC87] gives a quantitative method for + comparing the allocation by a given policy to the maximally fair + allocation. + + It is known that the Internet environment has heterogeneous transport + entities, which do not follow the same congestion control policies + (our definition of cooperating transports). Then, the controls given + by a gateway may not affect all users and the congestion control + policy may have unequal effects. Is "fairness" obtainable in such a + heterogeneous community? In Fair Queueing, transport entities with + differing congestion control policies can be insulated from each + other and each given a set share of gateway bandwidth. + + It is important to realize that since Internet gateways cannot refuse + new users, fairness in gateway congestion control can lead to all + users receiving small (sub-divided) amounts of the gateway resources + inadequate to meet their performance requirements. None of the + policies described in this paper currently addresses this. Then, + there may be policy reasons for unequal allocation of the gateway + resources. This has been addressed by Bit-Round Fair Queueing. + +2.4 Network Management + + Network performance goals may be assessed by measurements in either + the end-system or gateway frame of reference. Performance goals are + often resource-centered and the measurement of the global performance + of "the network," is not only difficult to measure but is also + difficult to define. Resource-centered metrics are more easily + obtained, and do not require synchronization. That resource-centered + metrics are appropriate ones for use in optimization of power is + shown by [Jaf81]. + + It would be valuable for the goal of developing effective gateway + congestion handling if Management Information Base (MIB) objects + useful for evaluating gateway congestion were developed. The + reflections on the control interval described above should be applied + when network management applications are designed for this purpose. + In particular, obtaining an instantaneous queue length from the + managed gateway is not meaningful for the purposes of congestion + management. + + + + + + +Performance and Congestion Control Working Group [Page 8] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + +3. Gateway Congestion Control Policies + + There have been proposed a handful of approaches to dealing with + congestion in the gateway. Some of these are Source Quench, Random + Drop, Congestion Indication, Selective Feedback Congestion + Indication, Fair Queueing, and Bit-Round Fair Queueing. They differ + in whether they use a control message, and indeed, whether they view + control of the end-systems as necessary, but none of them in itself + lowers the demand of users and consequent load on the network. End- + system policies that reduce demand in conjunction with gateway + congestion control are described in Section 4. + +3.1 Source Quench + + The method of gateway congestion control currently used in the + Internet is the Source Quench message of the RFC-792 [Pos81a] + Internet Control Message Protocol (ICMP). When a gateway responds to + congestion by dropping datagrams, it may send an ICMP Source Quench + message to the source of the dropped datagram. This is a congestion + recovery policy. + + The Gateway Requirements RFC, RFC-1009 [GREQ87], specifies that + gateways should only send Source Quench messages with a limited + frequency, to conserve CPU resources during the time of heavy load. + We note that operating the gateway for long periods under such loaded + conditions should be averted by a gateway congestion control policy. + A revised Gateway Requirements RFC is being prepared by the IETF. + + Another significant drawback of the Source Quench policy is that its + details are discretionary, or, alternatively, that the policy is + really a family of varied policies. Major Internet gateway + manufacturers have implemented a variety of source quench + frequencies. It is impossible for the end-system user on receiving a + Source Quench to be certain of the circumstances in which it was + issued. This makes the needed end-system response problematic: is + the Source Quench an indication of heavy congestion, approaching + congestion, a burst causing massive overload, or a burst slightly + exceeding reasonable load? + + To the extent that gateways drop the last arrived datagram on + overload, Source Quench messages may be distributed unfairly. This + is because the position at the end of the queue may be unfairly often + occupied by the packets of low demand, intermittent users, since + these do not send regular bursts of packets that can preempt most of + the queue space. + + [Fin89] developed algorithms for when to issue Source Quench and for + responding to it with a rate-reduction in the IP layer on the sending + + + +Performance and Congestion Control Working Group [Page 9] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + host. The system controls end-to-end performance of connections in a + manner similar to the congestion avoidance portion of Slow-start TCP + [Jac88]. + +3.2 Random Drop + + Random Drop is a gateway congestion control policy intended to give + feedback to users whose traffic congests the gateway by dropping + packets on a statistical basis. The key to this policy is the + hypothesis that a packet randomly selected from all incoming traffic + will belong to a particular user with a probability proportional to + the average rate of transmission of that user. Dropping a randomly + selected packet results in users which generate much traffic having + a greater number of packets dropped compared with those generating + little traffic. The selection of packets to be dropped is completely + uniform. Therefore, a user who generates traffic of an amount below + the "fair share" (as defined in Section 2.3) may also experience a + small amount of packet loss at a congested gateway. This character of + uniformity is in fact a primary goal that Random Drop attempts to + achieve. + + The other primary goal that Random Drop attempts to achieve is a + theoretical overhead which is scaled to the number of shared + resources in the gateway rather than the number of its users. If a + gateway congestion algorithm has more computation the more users + there are, this can lead to processing demands that are higher as + congestion increases. Also the low-overhead goal of Random Drop + addresses concerns about the scale of gateway processing that will be + required in the mid-term Internet as gateways with fast processors + and links are shared by very large active sets of users. + +3.2.1 For Congestion Recovery + + Random Drop has been proposed as an improvement to packet dropping at + the operating point where the gateway's packet buffers overflow. + This is using Random Drop strictly as a congestion recovery + mechanism. + + In Random Drop congestion recovery, instead of dropping the last + packet to arrive at the queue, a packet is selected randomly from the + queue. Measurements of an implementation of Random Drop Congestion + Recovery [Man90] showed that a user with a low demand, due to a + longer round-trip time path than other users of the gateway, had a + higher drop rate with RDCR than without. The throughput accorded to + users with the same round-trip time paths was nearly equal with RDCR + as compared to without it. These results suggest that RDCR should be + avoided unless it is used within a scheme that groups traffic more or + less by round-trip time. + + + +Performance and Congestion Control Working Group [Page 10] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + +3.2.2 For Congestion Avoidance + + Random Drop is also proposed as a congestion avoidance policy + [Jac89]. The intent is to initiate dropping packets when the gateway + is anticipated to become congested and remain so unless there is some + control exercised. This implies selection of incoming packets to + be randomly dropped at a rate derived from identifying the level of + congestion at the gateway. The rate is the number of arrivals + allowed between drops. It depends on the current operating point and + the prediction of congestion. + + A part of the policy is to determine that congestion will soon occur + and that the gateway is beginning to operate beyond the knee of the + power curve. With a suitably chosen interval (Section 2.1), the + number of packets from each individual user in a sample over that + interval is proportional to each user's demand on the gateway. Then, + dropping one or more random packets indicates to some user(s) the + need to reduce the level of demand that is driving the gateway beyond + the desired operating point. This is the goal that a policy of + Random Drop for congestion avoidance attempts to achieve. + + There are several parameters to be determined for a Random Drop + congestion avoidance policy. The first is an interval, in terms of + number of packet arrivals, over which packets are dropped with + uniform probability. For instance, in a sample implementation, if + this interval spanned 2000 packet arrivals, and a suitable + probability of drop was 0.001, then two random variables would be + drawn in a uniform distribution in the range of 1 to 2,000. The + values drawn would be used by counting to select the packets dropped + at arrival. The second parameter is the value for the probability of + drop. This parameter would be a function of an estimate of the + number of users, their appropriate control intervals, and possibly + the length of time that congestion has persisted. [Jac89] has + suggested successively increasing the probability of drop when + congestion persists over multiple control intervals. The motivation + for increasing the packet drop probability is that the implicit + estimate of the number of users and random selection of their packets + to drop does not guarantee that all users have received enough + signals to decrease demand. Increasing the probability of drop + increases the probability that enough feedback is provided. + Congestion detection is also needed in Random Drop congestion + avoidance, and could be implemented in a variety of ways. The + simplest is a static threshold, but dynamically averaged measures of + demand or utilization are suggested. + + The packets dropped in Random Drop congestion avoidance would not be + from the initial inputs to the gateway. We suggest that they would + be selected only from packets destined for the resource which is + + + +Performance and Congestion Control Working Group [Page 11] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + predicted to be approaching congestion. For example, in the case of + a gateway with multiple outbound links, access to each individual + link is treated as a separate resource, the Random Drop policy is + applied at each link independently. Random Drop congestion avoidance + would provide uniform treatment of all cooperating transport users, + even over individual patterns of traffic multiplexed within one + user's stream. There is no aggregation of users. + + Simulation studies [Zha89], [Has90] have presented evidence that + Random Drop is not fair across cooperating and non-cooperating + transport users. A transport user whose sending policies included + Go-Back-N retransmissions and did not include Slow-start received an + excessive share of bandwidth from a simple implementation of Random + Drop. The simultaneously active Slow-start users received unfairly + low shares. Considering this, it can be seen that when users do not + respond to control, over a prolonged period, the Random Drop + congestion avoidance mechanism would have an increased probability of + penalizing users with lower demand. Their packets dropped, these + users exert the controls leading to their giving up bandwidth. + + Another problem can be seen to arise in Random Drop [She89] across + users whose communication paths are of different lengths. If the + path spans congested resources at multiple gateways, then the user's + probability of receiving an unfair drop and subsequent control (if + cooperating) is exponentially increased. This is a significant + scaling problem. + + Unequal paths cause problems for other congestion avoidance policies + as well. Selective Feedback Congestion Indication was devised to + enhance Congestion Indication specifically because of the problem of + unequal paths. In Fair Queueing by source-destination pairs, each + path gets its own queue in all the gateways. + +3.3 Congestion Indication + + The Congestion Indication policy is often referred to as the DEC Bit + policy. It was developed at DEC [JRC87], originally for the Digital + Network Architecture (DNA). It has also been specified for the + congestion avoidance of the ISO protocols TP4 and CLNP [NIST88]. + Like Source Quench, it uses explicit communications from the + congested gateway to the user. However, to use the lowest possible + network resources for indicating congestion, the information is + communicated in a single bit, the Congestion Experienced Bit, set in + the network header of the packets already being forwarded by a + gateway. Based on the condition of this bit, the end-system user + makes an adjustment to the sending window. In the NSP transport + protocol of DECNET, the source makes an adjustment to its window; in + the ISO transport protocol, TP4, the destination makes this + + + +Performance and Congestion Control Working Group [Page 12] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + adjustment in the window offered to the sender. + + This policy attempts to avoid congestion by setting the bit whenever + the average queue length over the previous queue regeneration cycle + plus part of the current cycle is one or more. The feedback is + determined independently at each resource. + +3.4 Selective Feedback Congestion Indication + + The simple Congestion Indication policy works based upon the total + demand on the gateway. The total number of users or the fact that + only a few of the users might be causing congestion is not + considered. For fairness, only those users who are sending more than + their fair share should be asked to reduce their load, while others + could attempt to increase where possible. In Selective Feedback + Congestion Indication, the Congestion Experienced Bit is used to + carry out this goal. + + Selective Feedback works by keeping a count of the number of packets + sent by different users since the beginning of the queue averaging + interval. This is equivalent to monitoring their throughputs. Based + on the total throughput, a fair share for each user is determined and + the congestion bit is set, when congestion approaches, for the users + whose demand is higher than their fair share. If the gateway is + operating below the throughput-delay knee, congestion indications are + not set. + + A min-max algorithm used to determine the fair share of capacity and + other details of this policy are described in [RJC87]. One parameter + to be computed is the capacity of each resource to be divided among + the users. This metric depends on the distribution of inter-arrival + times and packet sizes of the users. Attempting to determine these + in real time in the gateway is unacceptable. The capacity is instead + estimated from on the throughput seen when the gateway is operating + in congestion, as indicated by the average queue length. In + congestion (above the knee), the service rate of the gateway limits + its throughput. Multiplying the throughput obtained at this + operating point by a capacity factor (between 0.5 and 0.9) to adjust + for the distributions yields an acceptable capacity estimate in + simulations. + + Selective Feedback Congestion Indication takes as input a vector of + the number of packets sent by each source-destination pair of end- + systems. Other alternatives include 1) destination address, 2) + input/output link, and 3) transport connection (source/destination + addresses and ports). + + These alternatives give different granularities for fairness. In the + + + +Performance and Congestion Control Working Group [Page 13] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + case where paths are the same or round-trip times of users are close + together, throughputs are equalized similarly by basing the selective + feedback on source or destination address. In fact, if the RTTs are + close enough, the simple congestion indication policy would result in + a fair allocation. Counts based on source/destination pairs ensure + that paths with different lengths and network conditions get a fair + throughput at the individual gateways. Counting packets based on + link pairs has a low overhead, but may result in unfairness to users + whose demand is below the fair share and are using a long path. + Counts based on transport layer connection identifiers, if this + information was available to Internet gateways, would make good + distinctions, since the differences of demand of different + applications and instances of applications would be separately + monitored. + + Problems with Selective Feedback Congestion Indication include that + the gateway has significant processing to do. With the feasible + choice of aggregation at the gateway, unfairness across users within + the group is likely. For example, an interactive connection + aggregated with one or more bulk transfer connections will receive + congestion indications though its own use of the gateway resources is + very low. + +3.5 Fair Queueing + + Fair Queueing is the policy of maintaining separate gateway output + queues for individual end-systems by source-destination pair. In the + policy as proposed by [Nag85], the gateway's processing and link + resources are distributed to the end-systems on a round-robin basis. + On congestion, packets are dropped from the longest queue. This + policy leads to equal allocations of resources to each source- + destination pair. A source-destination pair that demands more than a + fair share simply increases its own queueing delay and congestion + drops. + +3.5.1 Bit-Round Fair Queueing + + An enhancement of Nagle Fair Queueing, the Bit-Round Fair Queuing + algorithm described and simulated by [DKS89] addresses several + shortcomings of Nagle's scheme. It computes the order of service to + packets using their lengths, with a technique that emulates a bit- + by-bit round-robin discipline, so that long packets do not get an + advantage over short ones. Otherwise the round-robin would be + unfair, for example, giving more bandwidth to hosts whose traffic is + mainly long packets than to hosts sourcing short packets. + + The aggregation of users of a source-destination pair by Fair + Queueing has the property of grouping the users whose round-trips are + + + +Performance and Congestion Control Working Group [Page 14] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + similar. This may be one reason that the combination of Bit-Round + Fair Queueing with Congestion Indication had particularly good + simulated performance in [DKS89]. + + The aggregation of users has the expected drawbacks, as well. A + TELNET user in a queue with an FTP user does not get delay benefits; + and host pairs with high volume of connections get treated the same + as a host pair with small number of connections and as a result gets + unfair services. + + A problem can be mentioned about Fair Queueing, though it is related + to implementation, and perhaps not properly part of a policy + discussion. This is a concern that the resources (processing) used + for determining where to queue incoming packets would themselves be + subject to congestion, but not to the benefits of the Fair Queuing + discipline. In a situation where the gateway processor was not + adequate to the demands on it, the gateway would need an alternative + policy for congestion control of the queue awaiting processing. + Clever implementation can probably find an efficient way to route + packets to the queues they belong in before other input processing is + done, so that processing resources can be controlled, too. There is + in addition, the concern that bit-by-bit round FQ requires non-FCFS + queueing even within the same source destination pairs to allow for + fairness to different connections between these end systems. + + Another potential concern about Fair Queueing is whether it can scale + up to gateways with very large source-destination populations. For + example, the state in a Fair Queueing implementation scales with the + number of active end-to-end paths, which will be high in backbone + gateways. + +3.5.2 Stochastic Fairness Queuing + + Stochastic Fairness Queueing (SFQ) has been suggested as a technique + [McK90] to address the implementation issues relating to Fair + Queueing. The first overhead that is reduced is that of looking up + the source-destination address pair in an incoming packet and + determining which queue that packet will have to be placed in. SFQ + does not require as many memory accesses as Fair Queueing to place + the packet in the appropriate queue. SFQ is thus claimed to be more + amenable to implementation for high-speed networks [McK90]. + + SFQ uses a simple hash function to map from the source-destination + address pair to a fixed set of queues. Since the assignment of an + address pair to a queue is probabilistic, there is the likelihood of + multiple address pairs colliding and mapping to the same queue. This + would potentially degrade the additional fairness that is gained with + Fairness Queueing. If two or more address pairs collide, they would + + + +Performance and Congestion Control Working Group [Page 15] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + continue to do so. To deal with the situation when such a collision + occurs, SFQ periodically perturbs the hash function so that these + address pairs will be unlikely to collide subsequently. + + The price paid for achieving this implementation efficiency is that + SFQ requires a potentially large number of queues (we must note + however, that these queues may be organized orthogonally from the + buffers in which packets are stored. The buffers themselves may be + drawn from a common pool, and buffers in each queue organized as a + linked list pointed to from each queue header). For example, [McK90] + indicates that to get good, consistent performance, we may need to + have up to 5 to 10 times the number of active source-destination + pairs. In a typical gateway, this may require around 1000 to 2000 + queues. + + [McK90] reports simulation results with SFQ. The particular hash + function that is studied is using the HDLC's cyclic redundancy check + (CRC). The hash function is perturbed by multiplying each byte by a + sequence number in the range 1 to 255 before applying the CRC. The + metric considered is the standard deviation of the number of packets + output per source-destination pair. A perfectly fair policy would + have a standard deviation of zero and an unfair policy would have a + large standard deviation. In the example studied (which has up to 20 + source-destination (s-d) pairs going through a single overloaded + gateway), SFQ with 1280 queues (i.e., 64 times the number of source- + destination pairs), approaches about 3 times the standard deviation + of Fairness Queueing. This must be compared to a FCFS queueing + discipline having a standard deviation which is almost 175 times the + standard deviation of Fairness Queueing. + + It is conjectured in [McK90] that a good value for the interval in + between perturbations of the hash function appears to be in the area + between twice the queue flush time of the stochastic fairness queue + and one-tenth the average conversation time between a source- + destination pair. + + SFQ also may alleviate the anticipated scaling problems that may be + an issue with Fair Queueing by not strictly requiring the number of + queues equal to the possible source-destination pairs that may be + presenting a load on a particular gateway. However, SFQ achieves this + property by trading off some of the fairness for implementation + efficiency. + + [McK90] examines alternative strategies for implementation of Fair + Queueing and SFQ and estimates their complexity on common hardware + platforms (e.g., a Motorola 68020). It is suggested that mapping an + IP address pair may require around 24 instructions per packet for + Fair Queueing in the best case; in contrast SFQ requires 10 + + + +Performance and Congestion Control Working Group [Page 16] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + instructions in the worst case. The primary source of this gain is + that SFQ avoids a comparison of the s-d address pair on the packet to + the identity of the queue header. The relative benefit of SFQ over + Fair Queueing is anticipated to be greater when the addresses are + longer. + + SFQ offers promising implemenatation benefits. However, the price to + be paid in terms of having a significantly larger number of queues + (and the consequent data structures and their management) than the + number of s-d pairs placing a load on the gateway is a concern. SFQ + is also attractive in that it may be used in concert with the DEC-bit + scheme for Selective Feedback Congestion Indication to provide + fairness as well as congestion avoidance. + +4. END-SYSTEM CONGESTION CONTROL POLICIES + + Ideally in gateway congestion control, the end-system transport + entities adjust (decrease) their demand in response to control + exerted by the gateway. Schemes have been put in practice for + transport entities to adjust their demand dynamically in response to + congestion feedback. To accomplish this, in general, they call for + the user to gradually increase demand until information is received + that the load on the gateway is too high. In response to this + information, the user decreases load, then begins an exploratory + increases again. This cycle is repeated continuously, with the goal + that the total demand will oscillate around the optimal level. + + We have already noted that a Slow-start connection may give up + considerable bandwidth when sharing a gateway with aggressive + transport entities. There is currently no way to enforce that end- + systems use a congestion avoidance policy, though the Host + Requirements RFC [HR89] has defined Slow-start as mandatory for TCP. + This adverse effect on Slow-start connections is mitigated by the + Fair Queueing policy. Our conclusions discuss further the + coexistence of different end-system strategies. + + This section briefly presents two fielded transport congestion + control and avoidance schemes, Slow-start and End-System Congestion + Indication, and the responses by means of which they cooperate with + gateway policies. They both use the control paradigm described + above. Slow-start, as mentioned in Section 1, was developed by + [Jac88], and widely fielded in the BSD TCP implementation. End- + system Congestion Indication was developed by [JRC87]. It is fielded + in DEC's Digital Network Architecture, and has been specified as well + for ISO TP4 [NIST88]. + + Both Slow-start and End-system Congestion Indication view the + relationship between users and gateways as a control system. They + + + +Performance and Congestion Control Working Group [Page 17] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + have feedback and control components, the latter further broken down + into a procedure bringing a new connection to equilibrium, and a + procedure to maintain demand at the proper level. They make use of + policies for increasing and decreasing the transport sender's window + size. These require the sender to follow a set of self-restraining + rules which dynamically adjust the send window whenever congestion is + sensed. + + A predecessor of these, CUTE, developed by [Jai86], introduced the + use of retransmission timeouts as congestion feedback. The Slow- + start scheme was also designed to use timeouts in the same way. The + End-System policies for Congestion Indication use the Congestion + Experienced Bit delivered in the network header as the primary + feedback, but retransmission timeouts also provoke an end-system + congestion response. + + In reliable transport protocols like TCP and TP4, the retransmission + timer must do its best to satisfy two conflicting goals. On one hand, + the timer must rapidly detect lost packets. And, on the other hand, + the timer must minimize false alarms. Since the retransmit timer is + used as a congestion signal in these end-system policies, it is all + the more important that timeouts reliably correspond to packet drops. + One important rule for retransmission is to avoid bad sampling in the + measurements that will be used in estimating the round-trip delay. + [KP87] describes techniques to ensure accurate sampling. The Host + Requirements RFC [HR89] makes these techniques mandatory for TCP. + + The utilization of a resource can be defined as the ratio of its + average arrival rate to its mean service rate. This metric varies + between 0 and 1.0. In a state of congestion, one or more resources + (link, gateway buffer, gateway CPU) has a utilization approaching + 1.0. The average delay (round trip time) and its variance approach + infinity. Therefore, as the utilization of a network increases, it + becomes increasingly important to take into account the variance of + the round trip time in estimating it for the retransmission timeout. + + The TCP retransmission timer is based on an estimate of the round + trip time. [Jac88] calls the round trip time estimator the single + most important feature of any protocol implementation that expects to + survive a heavy load. The retransmit timeout procedure in RFC-793 + [Pos81b] includes a fixed parameter, beta, to account for the + variance in the delay. An estimate of round trip time using the + suggested values for beta is valid for a network which is at most 30% + utilized. Thus, the RFC-793 retransmission timeout estimator will + fail under heavy congestion, causing unnecessary retransmissions that + add to the load, and making congestive loss detection impossible. + + Slow-start TCP uses the mean deviation as an estimate of the variance + + + +Performance and Congestion Control Working Group [Page 18] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + to improve the estimate. As a rough view of what happens with the + Slow-start retransmission calculation, delays can change by + approximately two standard deviations without the timer going off in + a false alarm. The same method of estimation may be applicable to + TP4. The procedure is: + + Error = Measured - Estimated + Estimated = Estimated + Gain_1 * Error + Deviation = Deviation + Gain_2 * (|Error| - Deviation) + Timeout = Estimated + 2 * Deviation + + Where: Gain_1, Gain_2 are gain factors. + +4.1 Response to No Policy in Gateway + + Since packets must be dropped during congestion because of the finite + buffer space, feedback of congestion to the users exists even when + there is no gateway congestion policy. Dropping the packets is an + attempt to recover from congestion, though it needs to be noted that + congestion collapse is not prevented by packet drops if end-systems + accelerate their sending rate in these conditions. The accurate + detection of congestive loss by all retransmission timers in the + end-systems is extremely important for gateway congestion recovery. + +4.2 Response to Source Quench + + Given that a Source Quench message has ambiguous meaning, but usually + is issued for congestion recovery, the response of Slow-start to a + Source Quench is to return to the beginning of the cycle of increase. + This is an early response, since the Source Quench on overflow will + also lead to a retransmission timeout later. + +4.3 Response to Random Drop + + The end-system's view of Random Drop is the same as its view of loss + caused by overflow at the gateway. This is a drawback of the use of + packet drops as congestion feedback for congestion avoidance: the + decrease policy on congestion feedback cannot be made more drastic + for overflows than for the drops the gateway does for congestion + avoidance. Slow-start responds rapidly to gateway feedback. In a + case where the users are cooperating (all Slow-start), a desired + outcome would be that this responsiveness would lead quickly to a + decreased probability of drop. There would be, as an ideal, a self- + adjusting overall amount of control. + + + + + + + +Performance and Congestion Control Working Group [Page 19] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + +4.4 Response to Congestion Indication + + Since the Congestion Indication mechanism attempts to keep gateways + uncongested, cooperating end-system congestion control policies need + not reduce demand as much as with other gateway policies. The + difference between the Slow-start response to packet drops and the + End-System Congestion Indication response to Congestion Experienced + Bits is primarily in the decrease policy. Slow-start decreases the + window to one packet on a retransmission timeout. End-System + Congestion Indication decreases the window by a fraction (for + instance, to 7/8 of the original value), when the Congestion + Experienced Bit is set in half of the packets in a sample spanning + two round-trip times (two windows full). + +4.5 Response to Fair Queuing + + A Fair Queueing policy may issue control indications, as in the + simulated Bit-Round Fair Queueing with DEC Bit, or it may depend only + on the passive effects of the queueing. When the passive control is + the main effect (perhaps because most users are not responsive to + control indications), the behavior of retransmission timers will be + very important. If retransmitting users send more packets in + response to increases in their delay and drops, Fair Queueing will be + prone to degraded performance, though collapse (zero throughput for + all users) may be prevented for a longer period of time. + +5. Conclusions + + The impact of users with excessive demand is a driving force as + proposed gateway policies come closer to implementation. Random Drop + and Congestion Indication can be fair only if the transport entities + sharing the gateway are all cooperative and reduce demand as needed. + Within some portions of the Internet, good behavior of end-systems + eventually may be enforced through administration. But for various + reasons, we can expect non-cooperating transports to be a persistent + population in the Internet. Congestion avoidance mechanisms will not + be deployed all at once, even if they are adopted as standards. + Without enforcement, or even with penalties for excessive demand, + some end-systems will never implement congestion avoidance + mechanisms. + + Since it is outside the context of any of the gateway policies, we + will mention here a suggestion for a relatively small-scale response + to users which implement especially aggressive policies. This has + been made experimentally by [Jac89]. It would implement a low + priority queue, to which the majority of traffic is not routed. The + candidate traffic to be queued there would be identified by a cache + of recent recipients of whatever control indications the gateway + + + +Performance and Congestion Control Working Group [Page 20] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + policy makes. Remaining in the cache over multiple control intervals + is the criterion for being routed to the low priority queue. In + approaching or established congestion, the bandwidth given to the + low-service queue is decreased. + + The goal of end-system cooperation itself has been questioned. As + [She89] points out, it is difficult to define. A TCP implementation + that retransmits before it determines that has been loss indicated + and in a Go-Back-N manner is clearly non-cooperating. On the other + hand, a transport entity with selective acknowledgement may demand + more from the gateways than TCP, even while responding to congestion + in a cooperative way. + + Fair Queueing maintains its control of allocations regardless of the + end-system congestion avoidance policies. [Nag85] and [DKS89] argue + that the extra delays and congestion drops that result from + misbehavior could work to enforce good end-system policies. Are the + rewards and penalties less sharply defined when one or more + misbehaving systems cause the whole gateway's performance to be less? + While the tax on all users imposed by the "over-users" is much less + than in gateways with other policies, how can it be made sufficiently + low? + + In the sections on Selective Feedback Congestion Indication and Bit- + Round Fair Queueing we have pointed out that more needs to be done on + two particular fronts: + + How can increased computational overhead be avoided? + + The allocation of resources to source-destination pairs is, in + many scenarios, unfair to individual users. Bit-Round Fair + Queueing offers a potential administrative remedy, but even if it + is applied, how should the unequal allocations be propagated + through multiple gateways? + + The first question has been taken up by [McK90]. + + Since Selective Feedback Congestion Indication (or Congestion + Indication used with Fair Queueing) uses a network bit, its use in + the Internet requires protocol support; the transition of some + portions of the Internet to OSI protocols may make such a change + attractive in the future. The interactions between heterogeneous + congestion control policies in the Internet will need to be explored. + + The goals of Random Drop Congestion Avoidance are presented in this + survey, but without any claim that the problems of this policy can be + solved. These goals themselves, of uniform, dynamic treatment of + users (streams/flows), of low overhead, and of good scaling + + + +Performance and Congestion Control Working Group [Page 21] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + characteristics in large and loaded networks, are significant. + +Appendix: Congestion and Connection-oriented Subnets + + This section presents a recommendation for gateway implementation in + an areas that unavoidably interacts with gateway congestion control, + the impact of connection-oriented subnets, such as those based on + X.25. + + The need to manage a connection oriented service (X.25) in order to + transport datagram traffic (IP) can cause problems for gateway + congestion control. Being a pure datagram protocol, IP provides no + information delimiting when a pair of IP entities need to establish a + session between themselves. The solution involves compromise among + delay, cost, and resources. Delay is introduced by call + establishment when a new X.25 SVC (Switched Virtual Circuit) needs to + be established, and also by queueing delays for the physical line. + Cost includes any charges by the X.25 network service provider. + Besides the resources most gateways have (CPU, memory, links), a + maximum supported or permitted number of virtual circuits may be in + contest. + + SVCs are established on demand when an IP packet needs to be sent and + there is no SVC established or pending establishment to the + destination IP entity. Optionally, when cost considerations, and + sufficient numbers of unused virtual circuits allow, redundant SVCs + may be established between the same pair of IP entities. Redundant + SVCs can have the effect of improving performance when coping with + large end-to-end delay, small maximum packet sizes and small maximum + packet windows. It is generally preferred though, to negotiate large + packet sizes and packet windows on a single SVC. Redundant SVCs must + especially be discouraged when virtual circuit resources are small + compared with the number of destination IP entities among the active + users of the gateway. + + SVCs are closed after some period of inactivity indicates that + communication may have been suspended between the IP entities. This + timeout is significant in the operation of the interface. Setting + the value too low can result in closing of the SVC even though the + traffic has not stopped. This results in potentially large delays + for the packets which reopen the SVC and may also incur charges + associated with SVC calls. Also, clearing of SVCs is, by definition, + nongraceful. If an SVC is closed before the last packets are + acknowledged, there is no guarantee of delivery. Packet losses are + introduced by this destructive close independent of gateway traffic + and congestion. + + When a new circuit is needed and all available circuits are currently + + + +Performance and Congestion Control Working Group [Page 22] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + in use, there is a temptation to pick one to close (possibly using + some Least Recently Used criterion). But if connectivity demands are + larger than available circuit resources, this strategy can lead to a + type of thrashing where circuits are constantly being closed and + reopened. In the worst case, a circuit is opened, a single packet + sent and the circuit closed (without a guarantee of packet delivery). + To counteract this, each circuit should be allowed to remain open a + minimum amount of time. + + One possible SVC strategy is to dynamically change the time a circuit + will be allowed to remain open based on the number of circuits in + use. Three administratively controlled variables are used, a minimum + time, a maximum time and an adaptation factor in seconds per + available circuit. In this scheme, a circuit is closed after it has + been idle for a time period equal to the minimum plus the adaptation + factor times the number of available circuits, limited by the maximum + time. By administratively adjusting these variables, one has + considerable flexibility in adjusting the SVC utilization to meet the + needs of a specific gateway. + +Acknowledgements + + This paper is the outcome of discussions in the Performance and + Congestion Control Working Group between April 1988 and July 1989. + Both PCC WG and plenary IETF members gave us helpful reviews of + earlier drafts. Several of the ideas described here were contributed + by the members of the PCC WG. The Appendix was written by Art + Berggreen. We are particularly thankful also to Van Jacobson, Scott + Shenker, Bruce Schofield, Paul McKenney, Matt Mathis, Geof Stone, and + Lixia Zhang for participation and reviews. + +References + + [DKS89] Demers, A., Keshav, S., and S. Shenker, "Analysis and + Simulation of a Fair Queueing Algorithm", Proceedings of SIGCOMM '89. + + [Fin89] Finn, G., "A Connectionless Congestion Control Algorithm", + Computer Communications Review, Vol. 19, No. 5, October 1989. + + [Gar87] Gardner, M., "BBN Report on the ARPANET", Proceedings of the + McLean IETF, SRI-NIC IETF-87/3P, July 1987. + + [GREQ87] Braden R., and J. Postel, "Requirements for Internet + Gateways", RFC 1009, USC/Information Sciences Institute, June 1987. + + [HREQ89] Braden R., Editor, "Requirements for Internet Hosts -- + Communications Layers", RFC 1122, Internet Engineering Task Force, + October 1989. + + + +Performance and Congestion Control Working Group [Page 23] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + [Has90] Hashem, E., "Random Drop Congestion Control", M.S. Thesis, + Massachusetts Institute of Technology, Department of Computer + Science, 1990. + + [Jac88] Jacobson, V., "Congestion Avoidance and Control", Proceedings + of SIGCOMM '88. + + [Jac89] Jacobson, V., "Presentations to the IETF Performance and + Congestion Control Working Group". + + [Jaf81] Jaffe, J., "Bottleneck Flow Control", IEEE Transactions on + Communications, COM-29(7), July, 1981. + + [Jai86] Jain, R., "A Timeout-based Congestion Control Scheme for + Window Flow-controlled Networks", IEEE Journal on Selected Areas in + Communications, SAC-4(7), October 1986. + + [JRC87] Jain, R., Ramakrishnan, K., and D. Chiu, "Congestion + Avoidance in Computer Networks With a Connectionless Network Layer", + Technical Report DEC-TR-506, Digital Equipment Corporation. + + [Kle79] Kleinrock, L., "Power and Deterministic Rules of Thumb for + Probabilistic Problems in Computer Communications", Proceedings of + the ICC '79. + + [KP87] Karn, P., and C. Partridge, "Improving Round Trip Estimates in + Reliable Transport Protocols", Proceedings of SIGCOMM '87. + + [Man90] Mankin, A., "Random Drop Congestion Control", Proceedings of + SIGCOMM '90. + + [McK90] McKenney, P., "Stochastic Fairness Queueing", Proceedings of + INFOCOM '90. + + [Nag84] Nagle, J., "Congestion Control in IP/TCP Internetworks", RFC + 896, FACC Palo Alto, 6 January 1984. + + [Nag85] Nagle, J., "On Packet Switches With Infinite Storage", RFC + 970, FACC Palo Alto, December 1985. + + [NIST88] NIST, "Stable Implementation Agreements for OSI Protocols, + Version 2, Edition 1", National Institute of Standards and Technology + Special Publication 500-162, December 1988. + + [Pos81a] Postel, J., "Internet Control Message Protocol - DARPA + Internet Program Protocol Specification", RFC-792, USC/Information + Sciences Institute, September 1981. + + + + +Performance and Congestion Control Working Group [Page 24] + +RFC 1254 Gateway Congestion Control Survey August 1991 + + + [Pos81b] Postel, J., "Transmission Control Protocol - DARPA Internet + Program Protocol Specification", RFC-793, DARPA, September 1981. + + [RJC87] Ramakrishnan, K., Jain, R., and D. Chiu, "A Selective Binary + Feedback Scheme for General Topologies", Technical Report DEC-TR-510, + Digital Equipment Corporation. + + [She89] Shenker, S., "Correspondence with the IETF Performance and + Congestion Control Working Group". + + [Sp89] Spector, A., and M. Kazar, "Uniting File Systems", Unix + Review, Vol. 7, No. 3, March 1989. + + [Zha89] Zhang, L., "A New Architecture for Packet Switching Network + Protocols", Ph.D Thesis, Massachusetts Institute of Technology, + Department of Computer Science, 1989. + +Security Considerations + + Security issues are not discussed in this memo. + +Authors' Addresses + + Allison Mankin + The MITRE Corporation + M/S W425 + 7525 Colshire Drive + McLean, VA 22102 + + Email: mankin@gateway.mitre.org + + + K.K. Ramakrishnan + Digital Equipment Corporation + M/S LKG1-2/A19 + 550 King Street + Littleton, MA 01754 + + Email: rama@kalvi.enet.dec.com + + + + + + + + + + + + +Performance and Congestion Control Working Group [Page 25] +
\ No newline at end of file |