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