In data networking and queueing theory, network congestion occurs when a link or node is carrying
so much data that its quality of service deteriorates. Typical effects include queueing delay, packet
loss or the blocking of new connections. A consequence of these latter two is that an
incremental increase in offered load leads either only to a small increase in network
throughput, or to an actual reduction in network throughput.
Network protocols which use aggressive retransmissions to compensate for packet loss tend to keep
systems in a state of network congestion, even after the initial load has been reduced
to a level which would not normally have induced network congestion. Thus, networks using these
protocols can exhibit two stable states under the same level of load. The stable state with
low throughput is known as congestive collapse. Modern networks use congestion control and
congestion avoidance techniques to try to avoid congestion collapse. These include:
exponential backoff in protocols such as 802.11's CSMA/CA and the original Ethernet, window
reduction in TCP, and fair queueing in devices such as routers. Another method to avoid the
negative effects of network congestion is implementing priority schemes, so that some
packets are transmitted with higher priority than others. Priority schemes do not solve
network congestion by themselves, but they help to alleviate the effects of congestion
for some services. An example of this is 802.1p. A third method to avoid network congestion
is the explicit allocation of network resources to specific flows. One example of this is
the use of Contention-Free Transmission Opportunities in the ITU-T G.hn standard, which provides
high-speed local area networking over existing home wires.
RFC 2914 addresses the subject of congestion control in detail.
Network capacity The fundamental problem is that all network
resources are limited, including router processing time and link throughput.
For example: A wireless LAN is easily filled by a single
personal computer Even on fast computer networks, the backbone
can easily be congested by a few servers and client PCs
The aggregate transmission from P2P networks have no problem filling an uplink or some
other network bottleneck Denial-of-service attacks by botnets are capable
of filling even the largest Internet backbone network links, generating large-scale network
congestion In telephony networks, a mass call event can
overwhelm digital telephone circuits Congestive collapse
Congestive collapse is a condition that a packet-switched computer network can reach,
when little or no useful communication is happening due to congestion. Congestion collapse
generally occurs at "choke points" in the network, where the total incoming traffic
to a node exceeds the outgoing bandwidth. Connection points between a local area network
and a wide area network are the most likely choke points.
When a network is in such a condition, it has settled into a stable state where traffic
demand is high but little useful throughput is available, and there are high levels of
packet delay and loss and general quality of service is extremely poor.
History Congestion collapse was identified as a possible
problem as far back as 1984. It was first observed on the early Internet in October
1986, when the NSFnet phase-I backbone dropped three orders of magnitude from its capacity
of 32 kbit/s to 40 bit/s, and this continued to occur until end nodes started implementing
Van Jacobson's congestion control between 1987 and 1988.
Cause When more packets were sent than could be
handled by intermediate routers, the intermediate routers discarded many packets, expecting
the end points of the network to retransmit the information. However, early TCP implementations
had very bad retransmission behaviour. When this packet loss occurred, the end points
sent extra packets that repeated the information lost, doubling the data rate sent, exactly
the opposite of what should be done during congestion. This pushed the entire network
into a 'congestion collapse' where most packets were lost and the resultant throughput was
negligible. Congestion control
Congestion control concerns controlling traffic entry into a telecommunications network, so
as to avoid congestive collapse by attempting to avoid oversubscription of any of the processing
or link capabilities of the intermediate nodes and networks and taking resource reducing
steps, such as reducing the rate of sending packets. It should not be confused with flow
control, which prevents the sender from overwhelming the receiver.
Theory of congestion control The modern theory of congestion control was
pioneered by Frank Kelly, who applied microeconomic theory and convex optimization theory to describe
how individuals controlling their own rates can interact to achieve an "optimal" network-wide
rate allocation. Examples of "optimal" rate allocation are
max-min fair allocation and Kelly's suggestion of proportional fair allocation, although
many others are possible. The mathematical expression for optimal rate
allocation is as follows. Let be the rate of flow , be the capacity of link , and be
1 if flow uses link and 0 otherwise. Let , and be the corresponding vectors and matrix. Let
be an increasing, strictly concave function, called the utility, which measures how much
benefit a user obtains by transmitting at rate . The optimal rate allocation then satisfies
such that The Lagrange dual of this problem decouples,
so that each flow sets its own rate, based only on a "price" signalled by the network.
Each link capacity imposes a constraint, which gives rise to a Lagrange multiplier, . The
sum of these Lagrange multipliers, is the price to which the flow responds.
Congestion control then becomes a distributed optimisation algorithm for solving the above
problem. Many current congestion control algorithms can be modelled in this framework, with being
either the loss probability or the queueing delay at link .
A major weakness of this model is that it assumes all flows observe the same price,
while sliding window flow control causes "burstiness" which causes different flows to observe different
loss or delay at a given link. Classification of congestion control algorithms
There are many ways to classify congestion control algorithms:
By the type and amount of feedback received from the network: Loss; delay; single-bit
or multi-bit explicit signals By incremental deployability on the current
Internet: Only sender needs modification; sender and receiver need modification; only
router needs modification; sender, receiver and routers need modification.
By the aspect of performance it aims to improve: high bandwidth-delay product networks; lossy
links; fairness; advantage to short flows; variable-rate links
By the fairness criterion it uses: max-min, proportional, "minimum potential delay"
Mitigation A couple of mechanisms have been invented
to prevent network congestion or to deal with a network collapse:
Network scheduler – a program in routers to do Active Queue Management
Explicit Congestion Notification – an extension to the IP and TCP communications protocol,
which adds a flow control mechanism upon which both ends react appropriately
TCP congestion-avoidance algorithm – several implementations of efforts to deal with network
congestion The correct end point behavior is usually
still to repeat dropped information, but progressively slow the rate that information is repeated.
Provided all end points do this, the congestion lifts and good use of the network occurs,
and the end points all get a fair share of the available bandwidth. Other strategies
such as slow-start ensure that new connections don't overwhelm the router before the congestion
detection can kick in. The most common router mechanisms used to
prevent congestive collapses are fair queuing and other scheduling algorithms, and random
early detection, or RED, where packets are randomly dropped proactively triggering the
end points to slow transmission before congestion collapse actually occurs. Fair queuing is
most useful in routers at choke points with a small number of connections passing through
them. Larger routers must rely on RED. Some end-to-end protocols are better behaved
under congested conditions than others. TCP is perhaps the best behaved. The first TCP
implementations to handle congestion well were developed in 1984, but it was not until
Van Jacobson's inclusion of an open source solution in the Berkeley Standard Distribution
UNIX in 1988 that good TCP implementations became widespread.
UDP does not, in itself, have any congestion control mechanism. Protocols built atop UDP
must handle congestion in their own way. Protocols atop UDP which transmit at a fixed rate, independent
of congestion, can be troublesome. Real-time streaming protocols, including many Voice
over IP protocols, have this property. Thus, special measures, such as quality-of-service
routing, must be taken to keep packets from being dropped from streams.
In general, congestion in pure datagram networks must be kept out at the periphery of the network,
where the mechanisms described above can handle it. Congestion in the Internet backbone is
very difficult to deal with. Fortunately, cheap fiber-optic lines have reduced costs
in the Internet backbone. The backbone can thus be provisioned with enough bandwidth
to keep congestion at the periphery. Practical network congestion avoidance
Implementations of connection-oriented protocols, such as the widely used TCP protocol, generally
watch for packet errors, losses, or delays in order to adjust the transmit speed. There
are many different network congestion avoidance processes, since there are a number of different
trade-offs available. TCP/IP congestion avoidance
The TCP congestion avoidance algorithm is the primary basis for congestion control in
the Internet. Problems occur when many concurrent TCP flows
are experiencing port queue buffer tail-drops. Then TCP's automatic congestion avoidance
is not enough. All flows that experience port queue buffer tail-drop will begin a TCP retrain
at the same moment – this is called TCP global synchronization.
Active Queue Management
Random early detection One solution is to use random early detection
on the network equipment's port queue buffer. On network equipment ports with more than
one queue buffer, weighted random early detection could be used if available.
RED indirectly signals to sender and receiver by deleting some packets, e.g. when the average
queue buffer lengths are more than e.g. 50% filled and deletes linearly more or cubical
more packets, up to e.g. 100%. The average queue buffer lengths are computed over 1 second
at a time. Robust random early detection
The robust random early detection algorithm was proposed to improve the TCP throughput
against denial-of-service attacks, particularly low-rate denial-of-service attacks. Experiments
have confirmed that the existing RED-like algorithms are notably vulnerable under Low-rate
Denial-of-Service attacks due to the oscillating TCP queue size caused by the attacks. RRED
algorithm can significantly improve the performance of TCP under Low-rate Denial-of-Service attacks.
Flowbased-RED/WRED Some network equipment are equipped with ports
that can follow and measure each flow and are hereby able to signal to a too big bandwidth
flow according to some QoS policy. A policy could divide the bandwidth among all flows
by some criteria. Explicit Congestion Notification
Another approach is to use IP Explicit Congestion Notification. ECN is only used when the two
hosts signal that they want to use it. With this method, a protocol bit is used to signal
explicit congestion. This is better than the indirect packet delete congestion notification
performed by the RED/WRED algorithms, but it requires explicit support by both hosts
to be effective. Some outdated or buggy network equipment drops packets with the ECN bit set,
rather than ignoring the bit. Sally Floyd, one of the authors of ECN has published detailed
information on the status of ECN, including the version required for Cisco IOS.
When a router receives a packet marked as ECN capable and anticipates congestion, it
sets the ECN flag notifying the sender of congestion. The sender should respond by decreasing
its transmission bandwidth, e.g., by decreasing the TCP window size or by other means.
Cisco AQM: Dynamic buffer limiting Cisco Systems has taken a step further in
the Catalyst 4000 series with engine IV and V. Engine IV and V has the capability to classify
all flows as aggressive or adaptive. It ensures that no flows fill the port queues for a long
time. DBL can utilize IP ECN instead of packet-delete-signalling. TCP window shaping
Congestion avoidance can also efficiently be achieved by reducing the amount of traffic
flowing into a network. When an application requests a large file, graphic or web page,
it usually advertises a "window" of between 32K and 64K. This results in the server sending
a full window of data. When there are many applications simultaneously requesting downloads,
this data creates a congestion point at an upstream provider by flooding the queue much
faster than it can be emptied. By using a device to reduce the window advertisement,
the remote servers will send less data, thus reducing the congestion and allowing traffic
to flow more freely. This technique can reduce congestion in a network by a factor of 40.
Side effects of congestive collapse avoidance Radio links
The protocols that avoid congestive collapse are often based on the idea that data loss
on the Internet is caused by congestion. This is true in nearly all cases; errors during
transmission are rare on today's fiber-based Internet. However, this causes WiFi, 3G or
other networks with a radio layer to have poor throughput in some cases since wireless
networks are susceptible to data loss due to interference. The TCP connections running
over a radio based physical layer see the data loss and tend to believe that congestion
is occurring when it isn't and erroneously reduce the data rate sent.
Short-lived connections The slow-start protocol performs badly for
short-lived connections. Older web browsers would create many consecutive short-lived
connections to the web server, and would open and close the connection for each file requested.
This kept most connections in the slow start mode, which resulted in poor response time.
To avoid this problem, modern browsers either open multiple connections simultaneously or
reuse one connection for all files requested from a particular web server. However, the
initial performance can be poor, and many connections never get out of the slow-start
regime, significantly increasing latency. See also
References
"Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice" by John Evans,
Clarence Filsfils RFC 2914 - Congestion Control Principles,
Sally Floyd, September, 2000 RFC 896 - "Congestion Control in IP/TCP",
John Nagle, 6 January 1984 Introduction to Congestion Avoidance and Control,
Van Jacobson and Michael J. Karels, November, 1988
Books "Deploying IP and MPLS QoS for Multiservice
Networks: Theory and Practice" by John Evans, Clarence Filsfils
External links