RFC 1254

Gateway Congestion Control Survey

📅 published August 1991, from ietf

RFC 1254: Gateway Congestion Control Survey 🎀

okay bestie, this is part 1 of 7 of RFC 1254 🦋 It's the Gateway Congestion Control Survey from August 1991, written by the editors A. Mankin (MITRE) and K. Ramakrishnan (Digital Equipment Corporation) for the Network Working Group. It's giving information, not a standard 💅 The title block doesn't list anything it obsoletes or updates, so it's just vibing on its own ✨

Status of this Memo 📜

okay so this memo provides information for the Internet community 🌸 It's a survey of some of the major directions and issues, and it does not specify an Internet standard. Distribution of this memo is unlimited, no cap 🫶

Abstract 💜

the growth of network-intensive Internet apps made gateway congestion control a top priority 🔥 The IETF Performance and Congestion Control Working Group surveyed and reviewed gateway congestion control and avoidance approaches. The whole point of this paper is to share their review so people start new discussions and experiments 🧪

The survey covers Source Quench, Random Drop, Congestion Indication (DEC Bit), and Fair Queueing. And the task is still open: Internet implementors need to figure out and agree on the most effective mechanisms for controlling gateway congestion. Main character homework, honestly 👑

1. Introduction ✨

ngl Internet users run into congestion all the time, usually in mild forms 🙈 But severe episodes have been reported too, and gateway congestion is still a blocker for apps like scientific supercomputing data transfer.

The need for Internet congestion control first got real during several periods in 1986 and 1987, when the Internet hit the "congestion collapse" state that Nagle [Nag84] predicted. A huge number of widely spread-out Internet sites had simultaneous slowdowns or total stops in networking services for long stretches 💀 BBN, the firm in charge of maintaining the Internet's backbone at the time (the ARPANET), responded to the collapse by adding link capacity [Gar87].

Much of the Internet now uses the National Science Foundation Network (NSFNET) as its transmission backbone 🌈 Lots of monitoring and capacity planning are happening for the NSFNET backbone. Still, demand for that capacity keeps growing, and resource-hungry apps like wide-area file system management [Sp89] are leaning on the backbone more and more. So effective congestion control policies are going to be a critical requirement 🍓

Only a few mechanisms exist right now in Internet hosts and gateways to avoid or control congestion. The ones set out in the specs for the DoD Internet protocols are limited to:

Window flow control in TCP [Pos81b], mainly for controlling the demand on the receiver's capacity, both in terms of processing and buffers.
Source quench in ICMP, the message IP sends to ask a sender to throttle back [Pos81a].

One approach to beefing up Internet congestion control has been layering more powerful mechanisms over the simple existing ones in TCP and ICMP 🧚 Since 1987, the TCP congestion control policy Slow-start has been widely adopted. It's a collection of several algorithms developed by Van Jacobson and Mike Karels [Jac88]. Successful Internet experiences with Slow-start led the Host Requirements RFC [HREQ89] to classify the algorithms as mandatory for TCP 👑 Slow-start changes the user's demand once congestion gets to the point where packets are dropped at the gateway. By the time those overflows happen, the gateway is already congested 😭 Jacobson writes that Slow-start is intended to work best with a complementary gateway policy [Jac88].

1.1. Definitions 🦋

the Internet we care about is, in general, an arbitrary mesh-connected network, and the internetwork protocol is connectionless 💖 The number of users placing demands on the network isn't limited by any explicit mechanism. No resources get reserved, and transport layer set-ups aren't blocked because of lack of resources. A path from source host to destination host can have multiple hops through several gateways and links. Paths through the Internet can be heterogeneous (homogeneous paths exist too, and they experience congestion as well). In other words, links can be different speeds. The gateways and hosts can also be different speeds, or only give part of their processing power to communication-related stuff 🌸 The buffers storing information flowing through Internet gateways are finite, and the nature of the internet protocol is to drop packets when those buffers overflow 💅

Gateway congestion happens when demand for one or more of a gateway's resources is bigger than that resource's capacity ✨ Those resources include transmission links, processing, and buffer space. Operationally, uncongested gateways run 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] says a resource is congested when the operating point is greater than the point where resource power is maximum. Resource power is the ratio of throughput to delay (see Section 2.2). At that 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, like dominant round-trip time and queue regeneration cycle (see Section 2.1).

Mechanisms for handling congestion fall into two categories: congestion recovery and congestion avoidance 🔥 Congestion recovery tries to restore an operating state once demand has already gone past capacity. Congestion avoidance is preventive. It tries to keep demand on the network at or near the point of maximum power, so congestion never happens. Without congestion recovery, the network can stop working entirely (zero throughput), whereas the Internet has been running without congestion avoidance for a long time. Overall performance may improve with an effective congestion avoidance mechanism. Even so, congestion recovery schemes would still be needed to keep throughput steady when sudden changes (a jump in demand, loss of resources) could lead to congestion 🍓

In this paper, the term "user" refers to each individual transport entity (TCP or another transport protocol). For example, a TCP connection is a "user" in this terminology 🧚 Some authors use "flow" and "stream" in the same sense. Some of the congestion control policies discussed here, like Selective Feedback Congestion Indication and Fair Queueing, group multiple TCP connections from a single host (or between a source host and destination host pair) together as a virtual user 🌈

"Cooperating transport entities" is defined as a set of TCP connections (for example) that follow an effective method of adjusting their demand on the Internet in response to congestion 💜 The most restrictive reading is that the transport entities follow identical algorithms for congestion control and avoidance. There can still be some variation in those algorithms 👑 How far heterogeneous end-system congestion control and avoidance can be accommodated by gateway policies should be a subject of future research 🔮 Non-cooperating transport entities and their role in Internet performance are discussed in Section 5 ⭐

1.2. Goals and Scope of This Paper 🎀

the task is still on Internet implementors to figure out effective mechanisms for controlling gateway congestion 💖 Minimal common practice exists to base recommendations for Internet gateway congestion control on. In this survey, we describe the characteristics of one experimental gateway congestion management policy, Random Drop, plus several better-known ones: Source Quench, Congestion Indication, Selective Feedback Congestion Indication, and Fair Queueing (both Bit-Round and Stochastic) 🦋 The big reason for documenting Random Drop is that its primary goals are low overhead and suitability for scaling up to Internets with higher speed links. Both are important for future gateway implementations that will have fast links, fast processors, and have to serve large numbers of interconnected hosts 🚀

Here's how the paper is laid out 🌸 First, we discuss performance goals, including timescale and fairness considerations. Second, we talk through the gateway congestion control policies. Random Drop gets sketched out, with a recommendation to use it for congestion recovery and a separate section on its use for congestion avoidance. Third, since gateway congestion control by itself doesn't change end-systems' demand, we briefly present how two end-system congestion control schemes respond to these policies: Slow-start and End-System Congestion Indication 💅 Among our conclusions, we address transport entities that don't cooperate with gateway congestion control. And as an appendix, because of the potential interactions with gateway congestion policies, we report on a scheme for controlling the performance of Internet gateways to connection-oriented subnets (in particular, X.25) 🧚

Resources in the current Internet aren't charged to the users of them 🙈 Congestion avoidance techniques can't be expected to help when users go beyond the capacity of the underlying facilities. There are two possible fixes: increase the facilities and available bandwidth, or forcibly reduce the demand 😭 When congestion stays persistent despite implemented congestion control mechanisms, administrative responses are needed. Those are naturally outside the scope of this paper. Routing techniques that relocate demand away from congested individual resources (for example, path-splitting and load-balancing) are also out of scope 🍓

2. Performance Goals 💅

okay so, to talk about the design and use of different mechanisms for improving Internetwork performance, we need clear performance goals for how gateways and sets of end-systems operate ✨ Internet experience shows that congestion control should be based on adaptive principles. That requires efficient computation of metrics by congestion control algorithms. The first issue is the interval over which those metrics are estimated and/or measured 🔥

2.1. Interval for Measurement/Estimation of Performance Metrics ✨

okay so bestie, network performance metrics can get DISTORTED if you measure them over intervals that are too short or too long for how the network actually changes 😭. in a tiny window, two FTP users on equal paths can look like they want wildly different amounts of stuff, just because of brief little blips in their processing 🙈. and if the window is too long, the number of users sharing the resource keeps changing while you're measuring, so the numbers get warped too 💀. it's also super important for congestion control running at end systems to find a good interval 💅

The first approach to picking the monitoring (or averaging) interval for congestion control is based on round-trip times 🦋. the reasoning is that control mechanisms need to adapt to changes in Internet congestion as fast as possible 🏃‍♀️. even on an uncongested path, the sender won't notice changed conditions any faster than one round-trip time. and the effect of a sending end-system's control won't show up in less than a round-trip time, across the whole path or at the end systems 🕰️. for the control to be adaptive, new information about the path is needed before changing the control being applied. the statistics and metrics used in congestion control have to give the control mechanism enough info to make an informed decision 🧠. transient info that might already be obsolete by the time the end-system acts should be avoided 🙅‍♀️. so the monitoring/estimating interval is one lasting one or more round trips ✨. the requirements here give bounds on:

How short an interval: not so small that obsolete information gets 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 even IS a round-trip time? 🤔 if all the users of a given gateway have the same path through the Internet, they also have the same round-trip time through the gateway. but that's rarely the case, honestly 😩.

A meaningful interval has to 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.

Queue regeneration cycle has been described as part of the Congestion Indication policy 🎀. the averaging time period starts when a resource goes from idle to busy. the basic averaging interval is a "regeneration cycle", made of busy and idle intervals. since an average based on just one previous regeneration can go stale, the recommendation in [JRC87] is to average over the sum of two intervals: the previous (busy and idle) period, plus the time since the current busy period began 🌸.

If the gateway users are window-based transport entities, you can 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 while that user is awaiting acknowledgements. then the users with short paths get gateway congestion info averaged over several of their round-trip times 😭. if short-path traffic dominates the gateway (the connections with shorter round-trip times are the main users of its resources), then the regeneration interval is shorter and the info sent back to them can be more timely ⚡. in that case, users with longer paths get multiple samples of the dominant traffic within one of their round-trip times 🧩. the end-system averaging is based on each individual user's intervals, so those multiple samples get integrated properly for these longer-path connections 💖.

The use of frequency analysis has been described by [Jac89] 🌈. in this approach, gateway congestion control is done at intervals based on spectral analysis of traffic arrivals. it's possible for users to have round-trip times close to each other but be out of phase 🌀. a spectral analysis algorithm detects this. otherwise, if multiple round-trip times are significant, multiple intervals will be identified. either one will be predominant, or several will be comparable 👑. an as yet difficult problem for designing algorithms with this technique is the likelihood of "locking" to the frequency of periodic traffic of low intensity, such as routing updates 🙃.

2.2. Power and its Relationship to the Operating Point 🔥

Performance goals for a congestion control/avoidance strategy have a built-in conflict 💔. they call for as HIGH a throughput as possible, with as LITTLE delay as possible. a measure often used to reflect this tradeoff is power, which is the ratio of throughput to delay. we want to maximize the value of power for a given resource 📈. the standard expression is:

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, 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), alpha equal to one is chosen 🍓. the operating point where power is maximized is the "knee" in the throughput and delay curves 🎢. it's desirable for the operating point of the resource to be driven towards the knee, where power is maximized 💅. a useful property of power is that it decreases 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 an equal share for each user. but even over short intervals, demands are not equal, so 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 measuring the global performance of "the network" is not only difficult but 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 🙅‍♀️.

3. Gateway Congestion Control Policies 🚦

There have been a handful of proposed 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 💖

okay so the congestion control the Internet uses right now is the Source Quench message from 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], says gateways should only send Source Quench messages with a limited frequency, so they don't burn up CPU resources during heavy load 💻. we note that running the gateway for long periods under those loaded conditions should be averted by a gateway congestion control policy ✨. a revised Gateway Requirements RFC is being prepared by the IETF 🧚.

another big drawback of Source Quench is that its details are discretionary. or, put another way, it's really a whole family of varied policies 🌈. major Internet gateway manufacturers have implemented a variety of source quench frequencies, so it's giving chaos 💀. the end-system user who receives a Source Quench can't be certain of the circumstances in which it was issued 🙈. that makes the needed end-system response super 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 don't 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 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 meant 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 means users who generate lots of traffic end up with a greater number of packets dropped compared with those generating little traffic 💅. the selection of packets to be dropped is completely uniform. so a user whose traffic is 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 actually a primary goal that Random Drop tries to achieve ✨.

the other primary goal is a theoretical overhead that's 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, the processing demands can get higher as congestion increases, which is not it 🙅‍♀️. the low-overhead goal of Random Drop also 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's used within a scheme that groups traffic more or less by round-trip time 🫠.

3.2.2. For Congestion Avoidance

Random Drop is also proposed as a congestion avoidance policy [Jac89] 🌤️. the intent is to start dropping packets when the gateway is expected to become congested and to stay that way unless some control is exercised 🔮. this implies selecting 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, and it depends on the current operating point and the prediction of congestion 🧮.

a part of the policy is determining 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 signals to some user(s) that they need to reduce the level of demand that's driving the gateway beyond the desired operating point 🫶. that's the goal a policy of Random Drop for congestion avoidance is trying to hit 🏹.

there are several parameters to be determined for a Random Drop congestion avoidance policy 📝. the first is an interval, in terms of the 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 the 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 it 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 come from the initial inputs to the gateway 🙅‍♀️. we suggest they would be selected only from packets destined for the resource that's 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, and 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 don't 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 that lead to them giving up bandwidth 🕊️.

another problem arises 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 called 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 adjustment in the window offered to the sender 🔄.

this policy tries 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 ✨

okay so the simple Congestion Indication policy is kinda blunt 💅 It only looks at the total demand on the gateway. It doesn't care how many users there are or whether just a few of them are the ones causing the jam 😭 For fairness, only the users sending more than their fair share should be asked to slow down, while everyone else could try to speed up where they can 🦋 That's the whole point of Selective Feedback Congestion Indication, and it uses the Congestion Experienced Bit to get it done 🎀

Selective Feedback works by counting how many packets each user has sent since the start of the queue averaging interval 🧮 That's basically the same as watching their throughputs. From the total throughput, it works out a fair share for each user. When congestion starts to approach, it sets the congestion bit for the users whose demand is higher than their fair share 🔥 And if the gateway is running below the throughput-delay knee, congestion indications are not set at all 🌸

A min-max algorithm is used to figure out the fair share of capacity, and the other details of this policy are described in [RJC87] 📚 One thing that needs computing is the capacity of each resource to be split among the users. This depends on the distribution of inter-arrival times and packet sizes from the users, and trying to work that out in real time inside the gateway is a no-go 🙅‍♀️ So instead, the capacity is estimated from the throughput seen when the gateway is operating in congestion, as shown by the average queue length. Above the knee, the gateway's service rate is what limits its throughput. Multiply that throughput by a capacity factor (somewhere between 0.5 and 0.9) to adjust for those distributions, and you get a capacity estimate that works out acceptably in simulations ✨

Selective Feedback Congestion Indication takes in a vector of the number of packets sent by each source-destination pair of end-systems 💖 Other options are 1) destination address, 2) input/output link, and 3) transport connection (source and destination addresses and ports).

These options give different levels of fairness granularity 🍓 If paths are the same or the round-trip times of the users are close together, basing the selective feedback on source or destination address evens out the throughputs in a similar way. Honestly, if the RTTs are close enough, the simple congestion indication policy would already give a fair allocation 💅 Counts based on source/destination pairs make sure that paths with different lengths and network conditions each get a fair throughput at the individual gateways 👑 Counting packets by link pairs has low overhead, but it can be unfair to users whose demand is below the fair share and who are using a long path 🙈 Counts based on transport layer connection identifiers would make really good distinctions, if Internet gateways could get that information, because the demand of different applications and different instances of applications would each be monitored separately 🧚

The problems with Selective Feedback Congestion Indication are that the gateway has a lot of processing to do 😩 And with the realistic choices of aggregation at the gateway, unfairness across users inside the same group is likely. For example, an interactive connection that gets lumped together with one or more bulk transfer connections will receive congestion indications, even though its own use of the gateway resources is very low 💀

3.5. Fair Queueing 🧸

Fair Queueing is the policy of keeping separate gateway output queues for individual end-systems, grouped by source-destination pair 🌈 In the policy proposed by [Nag85], the gateway's processing and link resources are handed out to the end-systems on a round-robin basis. When congestion hits, packets are dropped from the longest queue. This policy leads to equal allocations of resources for each source-destination pair ⭐ A source-destination pair that demands more than a fair share just ends up increasing its own queueing delay and congestion drops 😭

3.5.1. Bit-Round Fair Queuing

An enhancement of Nagle Fair Queueing, the Bit-Round Fair Queuing algorithm described and simulated by [DKS89] fixes several shortcomings of Nagle's scheme 🔥 It works out the order of service for packets using their lengths, with a technique that emulates a bit-by-bit round-robin discipline. That way, long packets don't get an advantage over short ones. Otherwise the round-robin would be unfair. For example, hosts whose traffic is mainly long packets would get more bandwidth than hosts sending short packets, and that's just not it 🙅‍♀️

Grouping users of a source-destination pair with Fair Queueing has the nice property of putting together users whose round-trips are similar 🦋 This may be one reason why Bit-Round Fair Queueing combined with Congestion Indication had particularly good simulated performance in [DKS89] 👑

Aggregating users has the expected drawbacks too, though 😬 A TELNET user sharing a queue with an FTP user doesn't get any delay benefits. And a host pair with a high volume of connections gets treated the same as a host pair with only a small number of connections, so it ends up getting unfair service 💅

There's also a concern about Fair Queueing, though it's more about implementation than policy, so it might not really belong in a policy discussion 🤔 The resources (processing) used to decide which queue an incoming packet goes into could themselves become congested, and they wouldn't get the benefits of the Fair Queueing discipline. If the gateway processor isn't up to the demands on it, the gateway would need a different congestion control policy for the queue waiting for processing 🫶 Clever implementation can probably find an efficient way to route packets to the right queues before the other input processing happens, so the processing resources can be controlled too ✨ There's also the issue that bit-by-bit round FQ requires non-FCFS queueing even within the same source-destination pair, so that different connections between those end-systems get fair treatment 🌸

Another potential concern is whether Fair Queueing 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, and that number will be high in backbone gateways 🧠

3.5.2. Stochastic Fairness Queuing

Stochastic Fairness Queueing (SFQ) has been suggested as a technique [McK90] to deal with the implementation issues of Fair Queueing 💖 The first overhead it cuts down is looking up the source-destination address pair in an incoming packet and figuring out which queue that packet belongs in. SFQ doesn't need as many memory accesses as Fair Queueing to place the packet in the right queue, so it's claimed to be more practical to implement for high-speed networks [McK90] 🚀

SFQ uses a simple hash function to map each source-destination address pair onto a fixed set of queues 🎀 Because that assignment is probabilistic, multiple address pairs might collide and land in the same queue. That could seriously weaken the extra fairness you get from Fair Queueing 😭 And if two or more address pairs collide, they'd keep on colliding. So to handle a collision, SFQ periodically perturbs the hash function, which makes it unlikely those address pairs will collide again later 🔀

The price for this implementation efficiency is that SFQ needs a potentially large number of queues. (Heads up though, these queues can be organized separately from the buffers that hold the packets. The buffers themselves can come from a common pool, with the 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, you may need up to 5 to 10 times the number of active source-destination pairs. In a typical gateway, that could mean around 1000 to 2000 queues 📦

[McK90] reports simulation results for SFQ 📊 The particular hash function studied uses the HDLC's cyclic redundancy check (CRC). Before applying the CRC, the hash function is perturbed by multiplying each byte by a sequence number in the range 1 to 255. 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 (that's 64 times the number of source-destination pairs) gets to about 3 times the standard deviation of Fair Queueing. For comparison, an FCFS queueing discipline has a standard deviation that's almost 175 times the standard deviation of Fair Queueing 😱

[McK90] conjectures that a good value for the interval between perturbations of the hash function is somewhere between twice the queue flush time of the stochastic fairness queue and one-tenth the average conversation time between a source-destination pair ⏱️

SFQ may also ease the scaling problems that come up with Fair Queueing, because it doesn't strictly require the number of queues to equal the possible source-destination pairs loading a particular gateway 🌊 But SFQ gets this by trading off some of the fairness for implementation efficiency 🫠

[McK90] looks at alternative strategies for implementing Fair Queueing and SFQ, and estimates their complexity on common hardware platforms (for example, a Motorola 68020) 🖥️ It's suggested that mapping an IP address pair may take around 24 instructions per packet for Fair Queueing in the best case, while SFQ takes 10 instructions in the worst case. The main source of that gain is that SFQ avoids comparing the s-d address pair on the packet with the identity of the queue header. The relative benefit of SFQ over Fair Queueing is expected to be bigger when the addresses are longer 🙌

SFQ offers promising implementation benefits, no cap 💜 But the cost is a significantly larger number of queues (plus the data structures and management that come with them) than the number of s-d pairs loading the gateway, and that's a real concern 😬 SFQ is also attractive because it may be used together with the DEC-bit scheme for Selective Feedback Congestion Indication, to provide fairness as well as congestion avoidance 💅✨

4. END-SYSTEM CONGESTION CONTROL POLICIES 💅

okay so ideally, in gateway congestion control, the end-system transport entities adjust (decrease) their demand in response to the control the gateway is exerting 🫶. Schemes have actually been put into practice so transport entities can adjust their demand dynamically based on congestion feedback 💖. The way it usually goes: the user gradually increases demand until they get info that the load on the gateway is too high 😭. Then they decrease their load and begin an exploratory increase again 🦋. This cycle just keeps repeating, with the goal that total demand oscillates around the optimal level ✨.

We already noted that a Slow-start connection can give up a lot of bandwidth when it's sharing a gateway with aggressive transport entities 💀. There's currently no way to enforce that end-systems use a congestion avoidance policy 🙈, though the Host Requirements RFC [HR89] defined Slow-start as mandatory for TCP. This adverse effect on Slow-start connections gets mitigated by the Fair Queueing policy 🎀. Our conclusions discuss the coexistence of different end-system strategies in more detail.

This section briefly presents two fielded transport congestion control and avoidance schemes, Slow-start and End-System Congestion Indication, plus the responses they use to cooperate with gateway policies 🌸. They both use the control paradigm described above. Slow-start, like we 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's fielded in DEC's Digital Network Architecture, and it's been specified for ISO TP4 as well [NIST88] 🍓.

Both Slow-start and End-System Congestion Indication see the relationship between users and gateways as a control system 👑. They have feedback and control components, and the control part breaks down further into a procedure that brings a new connection to equilibrium and a procedure that keeps demand at the proper level 🧚. They use policies for increasing and decreasing the transport sender's window size. These policies require the sender to follow a set of self-restraining rules that dynamically adjust the send window whenever congestion is sensed 🌈.

A predecessor of these, CUTE, developed by [Jai86], introduced using retransmission timeouts as congestion feedback 🔥. Slow-start 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 set off an end-system congestion response ✨.

In reliable transport protocols like TCP and TP4, the retransmission timer has to juggle two goals that fight each other 😤. On one hand, the timer has to rapidly detect lost packets. On the other hand, it has to minimize false alarms 🫠. Since the retransmit timer is used as a congestion signal in these end-system policies, it's all the more important that timeouts reliably correspond to packet drops 💜. One important rule for retransmission is to avoid bad sampling in the measurements used to estimate round-trip delay. [KP87] describes techniques to ensure accurate sampling, and 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. So as the utilization of a network increases, it becomes increasingly important to take the variance of the round trip time into account when estimating 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 📉. So 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 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 have to be dropped during congestion because of the finite buffer space, feedback of congestion to the users exists even when there's 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 under 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 an ambiguous meaning but is usually 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 using 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 leads quickly to a decreased probability of drop. As an ideal, there would be a self-adjusting overall amount of control ✨.

4.4 Response to Congestion Indication 🚦

Since the Congestion Indication mechanism attempts to keep gateways uncongested, cooperating end-system congestion control policies don't need to 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 🎀

okay so the impact of users with excessive demand is basically the driving force behind gateway policies as they get closer to actually being implemented 😭 Random Drop and Congestion Indication can only be fair if every transport entity sharing the gateway is cooperative and cuts back demand when needed 🫶 Within some corners of the Internet, good end-system behavior might eventually get enforced through administration 👑 But for various reasons, we can expect non-cooperating transports to be a persistent population on the Internet, ngl 💀 Congestion avoidance mechanisms won't get deployed all at once, even once they're adopted as standards 🍓 Without enforcement, or even with penalties for excessive demand, some end-systems will literally never implement congestion avoidance mechanisms 🙈

Since it's outside the context of any of the gateway policies, we're going to mention a suggestion for a relatively small-scale response to users who run especially aggressive policies 🦋 This has been tried experimentally by [Jac89] ✨ It would set up a low priority queue, and most of the traffic would not be routed there 💅 The candidate traffic to be queued there would be identified by a cache of recent recipients of whatever control indications the gateway policy makes 🌸 Staying in the cache over multiple control intervals is the criterion for getting routed to the low priority queue 🧚 When congestion is approaching or already established, the bandwidth given to the low-service queue is decreased 📉

The goal of end-system cooperation itself has been questioned, and honestly same 🙈 As [She89] points out, it's difficult to define 🫠 A TCP implementation that retransmits before it has determined that loss has been indicated, and does so 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 does, even while responding to congestion in a cooperative way 🌈

Fair Queueing keeps 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 make the whole gateway's performance worse? 🤔 The tax on all users imposed by the "over-users" is much smaller than in gateways with other policies, but how can it be made sufficiently low? 💭

In the sections on Selective Feedback Congestion Indication and Bit-Round Fair Queueing, we 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, uniform, dynamic treatment of users (streams/flows), low overhead, and good scaling characteristics in large and loaded networks, are seriously significant 💜

Appendix: Congestion and Connection-oriented Subnets 🧚

This section presents a recommendation for gateway implementation in an area 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 😩 IP is a pure datagram protocol, so it 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 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 is sent, and the circuit is closed (without a guarantee of packet delivery) 💀 To counteract this, each circuit should be allowed to remain open for 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 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.

[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.

[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 ✨

okay bestie, last stop 🧚 these are the two legends who wrote this whole thing, and yes, here's where you can find them 💅 Allison Mankin and K.K. Ramakrishnan, with their work addresses and emails 💖

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

and that's the whole RFC, periodt 🌈🎀

📦 where this page comes from

ietf: rfc1254 1991-08
💖 girlified by claude-haiku-5-5 on 2026-10-15: a language model's rewrite of the original, under its terms