Network congestion avoidance

Network congestion avoidance is a process used in computer networks to avoid congestion.

The fundamental problem is that all network resources are limited, including router processing time and link throughput. Eg.:
*today's (2006) Wireless LAN effective bandwidth throughput (15-100Mbit/s) is easily filled by a single personal computer.
*Even on fast computer networks (e.g. 1 Gbit), the backbone can easily be congested by a few servers and client PCs.
*Because P2P scales very well, file transmissions by P2P have no problem filling and will fill an uplink or some other network bottleneck, particularly when nearby peers are preferred over distant peers.
*Denial of service attacks by botnets are capable of filling even the largest Internet backbone network links (40 Gbit/s as of 2007), generating large-scale network congestion

Implementations of connection-oriented protocols, such as the widely-used TCP protocol, generally watch for packet errors, losses, or delays (see Quality of Service) 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. [ [http://citeseer.ist.psu.edu/lee00tcp.html TCP Tunnels: Avoiding Congestion Collapse (2000)] ]

TCP/IP congestion avoidance

The TCP congestion avoidance algorithm is the primary basis for congestion control in the Internet. [Van Jacobson, Michael J. Karels. [http://citeseer.ist.psu.edu/484335.html Congestion Avoidance and Control] (1988). "Proceedings of the Sigcomm '88 Symposium", vol.18(4): pp.314–329. Stanford, CA. August, 1988. This paper originated many of the congestion avoidance algorithms used in TCP/IP.] [RFC 2001 - TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms] [RFC 2581 - TCP Congestion Control] [RFC 3390 - TCP Increasing TCP's Initial WindowOriginal RFC3390] ] [ [http://www.eventhelix.com/RealtimeMantra/Networking/TCP_Congestion_Avoidance.pdf TCP Congestion Avoidance Explained via a Sequence Diagram] ]

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.Problems can be cured or greatly reducedwith a netequalizer http://www.netequalizer.com/

Active Queue Management (AQM)

Purpose

"Recommendations on Queue Management and Congestion Avoidance in the Internet" (RFC 2309 [RFC 2309 - April 1998: Recommendations on Queue Management and Congestion Avoidance in the Internet] ) states that:
* Fewer packets will be dropped with Active Queue Management (AQM).
* The link utilization will increase because less TCP global synchronization will occur.
* By keeping the average queue size small, queue management will reduce the delays and jitter seen by flows.
* The connection bandwidth will be more equally shared among connection oriented flows, even without flow-based RED or WRED.

Random early detection

One solution is to use random early detection (RED) on network equipments port queue buffer. [http://www.icir.org/floyd/red.html Sally Floyd: RED (Random Early Detection) Queue Management] ] [Sally Floyd, Van Jacobson. [http://citeseer.ist.psu.edu/462978.html Random Early Detection Gateways for Congestion Avoidance] (1993). "IEEE/ACM Transactions on Networking", vol.1(4): pp.397–413. Invented Random Early Detection (RED) gateways.] On network equipment ports with more than one queue buffer, weighted random early detection (WRED) could be used if available.

RED indirectly signals to sender and receiver by deleting some packets, eg. when the average queue buffer lengths are more than eg. 50% (lower threshold) filled and deletes linearly more or (better according to paper) cubical more packets, [ [http://www.ist-mobydick.org/publications/aqm_iscc2003.pdf An Analytical RED Function Design Guaranteeing Stable System Behavior] Quote: "...The advantage of this function lies not only in avoiding heavy oscillations but also in avoiding link under-utilization at low loads. The applicability of the derived function is independent of the load range, no parameters are to be adjusted. Compared to the original linear drop function applicability is extended by far...Our example with realistic system parameters gives an approximation function of the cubic of the queue size..."] up to eg. 100% (higher threshold). The average queue buffer lengths are computed over 1 second at a time.

Flowbased-RED/WRED

Some network equipment are equipped with ports that can follow and measure each flow (flowbased-RED/WRED) 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.

IP ECN

Another approach is to use IP ECN [RFC 3168 - The Addition of Explicit Congestion Notification (ECN) to IP] . ECN is only used when the two hosts signal that they want to use it. With this method, an ECN bit is used to signal that there is 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. [ [http://citeseer.ist.psu.edu/bagal99comparative.html Comparative study of RED, ECN and TCP Rate Control (1999)] ] Some outdated or buggy network equipment drops packets with the ECN bit set, rather than ignoring the bit. More information on the status of ECN including the version required for Cisco IOS, by Sally Floyd, one of the authors of ECN.

When a router receives a packet marked as ECN capable and anticipates (using RED) congestion, it will set an ECN-flag notifying the sender of congestion. The sender then ought to decrease its transmission bandwidth; eg. by decreasing the tcp window size (sending rate) or by other means.

Cisco AQM: Dynamic buffer limiting (DBL)

Cisco has taken a step further in their Catalyst 4000 series with engine IV and V. Engine IV and V has the possibility to classify all flows in "aggressive" (bad) and "adaptive" (good). It ensures that no flows fill the port queues for a long time. DBL can utilize IP ECN instead of packet-delete-signalling. [ [http://www.cisco.com/univercd/cc/td/doc/product/lan/cat4000/12_1_19/config/qos.htm#1271743 Active Queue Management] ] [ [http://www.cisco.com/univercd/cc/td/doc/product/lan/cat4000/12_1_19/config/qos.htm#1271759 Enabling Dynamic Buffer Limiting] ]

TCP Window Shaping

Congestion avoidance can also efficiently be achieved by reducing the amount of traffic flowing into your 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 (assuming the file is larger than the window). When you have many applications simultaneously requesting downloads, this data creates a congestion point at your 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.

ee also

*Traffic shaping
*Quality of service
*Exponential backoff
*max-min fairness

References

* "Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice" by John Evans, Clarence Filsfils (Morgan Kaufmann, 2007, ISBN 0-12-370549-5)

Books

* "Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice" by John Evans, Clarence Filsfils (Morgan Kaufmann, 2007, ISBN 0-12-370549-5)

External links

* [http://www.linktionary.com/q/queuing.html Linktionary term: Queuing]
* [http://www.cse.wustl.edu/~jain/papers.html Pierre-Francois Quet, Sriram Chellappan, Arjan Durresi, Mukundan Sridharan, Hitay Ozbay, Raj Jain, " Guidelines for optimizing Multi-Level ECN, using fluid flow based TCP model"]
* [http://www.cs.washington.edu/homes/ratul/red-pd/ Sally Floyd, Ratul Mahajan, David Wetherall: RED-PD: RED with Preferential Dropping]
* [http://code.google.com/p/guduz/ A Generic Simple RED Simulator for educational purposes by Mehmet Suzen]