digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Business

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

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 (CFTXOPs) in the ITU-T G.hn standard, which provides high-speed (up to 1 Gbit/s) Local area networking over existing home wires (power lines, phone lines and coaxial cables).

RFC 2914 addresses the subject of congestion control in detail.

Network capacity[edit]

The fundamental problem is that all network resources are limited, including router processing time and link throughput.

For example:

Congestive collapse[edit]

Congestive collapse (or congestion 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 (under overload) 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 (caused by routers discarding packets because their output queues are too full) and general quality of service is extremely poor.

History[edit]

Congestion collapse was identified as a possible problem as far back as 1984 (RFC 896, dated 6 January). 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[edit]

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 behavior. 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[edit]

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[edit]

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 x_i be the rate of flow i, C_l be the capacity of link l, and r_{li} be 1 if flow i uses link l and 0 otherwise. Let x, c and R be the corresponding vectors and matrix. Let U(x) be an increasing, strictly concave function, called the utility, which measures how much benefit a user obtains by transmitting at rate x. The optimal rate allocation then satisfies

\max\limits_x \sum_i U(x_i)
such that Rx \le c

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, p_l. The sum of these Lagrange multipliers, y_i=\sum_l p_l r_{li}, 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 p_l being either the loss probability or the queueing delay at link l.

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[edit]

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[edit]

A couple of mechanism have been invented to prevent network congestion and or deal with a network collapse:

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[citation needed], but it was not until Van Jacobson's inclusion of an open source solution in the Berkeley Standard Distribution UNIX ("BSD") 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.[citation needed]

Practical network congestion avoidance[edit]

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

TCP/IP congestion avoidance[edit]

The TCP congestion avoidance algorithm is the primary basis for congestion control in the Internet.[2] [3] [4] [5] [6]

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 (AQM)[edit]

Random early detection[edit]

One solution is to use random early detection (RED) on the network equipment's port queue buffer. [7] [8] 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, e.g. when the average queue buffer lengths are more than e.g. 50% (lower threshold) filled and deletes linearly more or (better according to paper) cubical more packets, [9] up to e.g. 100% (higher threshold). The average queue buffer lengths are computed over 1 second at a time.

Robust random early detection (RRED)[edit]

The robust random early detection (RRED) algorithm was proposed to improve the TCP throughput against denial-of-service (DoS) attacks, particularly low-rate denial-of-service (LDoS) attacks. Experiments have confirmed that the existing RED-like algorithms are notably vulnerable under Low-rate Denial-of-Service (LDoS) attacks due to the oscillating TCP queue size caused by the attacks.[10] RRED algorithm can significantly improve the performance of TCP under Low-rate Denial-of-Service attacks.[10]

Flowbased-RED/WRED[edit]

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.

Explicit Congestion Notification[edit]

Another approach is to use IP Explicit Congestion Notification (ECN).[11] 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.[12] Some outdated or buggy network equipment drops packets with the ECN bit set, rather than ignoring the bit.[original research?] Sally Floyd, one of the authors of ECN has published detailed information on the status of ECN, including the version required for Cisco IOS.[7]

When a router receives a packet marked as ECN capable and anticipates (using RED) 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 (sending rate) or by other means.

Cisco AQM: Dynamic buffer limiting (DBL)[edit]

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 (bad) or 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. [13] [14]

TCP window shaping[edit]

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 (assuming the file is larger than the window). 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.[citation needed]

Side effects of congestive collapse avoidance[edit]

Radio links[edit]

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[edit]

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[edit]

References[edit]

  1. ^ TCP Tunnels: Avoiding Congestion Collapse (2000)
  2. ^ Van Jacobson, Michael J. Karels. 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.
  3. ^ RFC 2001 - TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms
  4. ^ RFC 2581 - TCP Congestion Control
  5. ^ RFC 3390 - TCP Increasing TCP's Initial Window
  6. ^ TCP Congestion Avoidance Explained via a Sequence Diagram
  7. ^ a b Sally Floyd: RED (Random Early Detection) Queue Management
  8. ^ Sally Floyd, Van Jacobson. 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.
  9. ^ 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..."
  10. ^ a b Changwang Zhang, Jianping Yin, Zhiping Cai, and Weifeng Chen, RRED: Robust RED Algorithm to Counter Low-rate Denial-of-Service Attacks, IEEE Communications Letters, vol. 14, pp. 489-491, 2010. Ref
  11. ^ RFC 3168 - The Addition of Explicit Congestion Notification (ECN) to IP
  12. ^ Comparative study of RED, ECN and TCP Rate Control (1999)
  13. ^ Active Queue Management
  14. ^ Enabling Dynamic Buffer Limiting
  • "Deploying IP and MPLS QoS for Multiservice Networks: Theory and Practice" by John Evans, Clarence Filsfils (Morgan Kaufmann, 2007, ISBN 0-12-370549-5)
  • 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[edit]

  • "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[edit]


Original courtesy of Wikipedia: http://en.wikipedia.org/wiki/Network_congestion — Please support Wikipedia.
A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia.
61209 videos foundNext > 

Network Congestion

This video shows about network congestion and how TCP controls it.

Lecture - 22 Congestion Control

Lecture Series on Data Communication by Prof.A. Pal, Department of Computer Science Engineering,IIT Kharagpur. For more details on NPTEL visit http://nptel.i...

MSCT 600 - Controlling Network Congestion With TCP

Describing how congestion occurs in the network and how TCP attempts to control network congestion.

Computer Networks 7-1: Congestion Overview

Computer Networks by David Wetherall, Arvind Krishnamurthy, John Zahorjan University of Washingon Overview Computer networks from ISPs to WiFi and cellular n...

GoNet Systems - 3G Network Congestion

Cellular networks are experiencing an explosion of data traffic with the proliferation of smartphones, tablet PC and laptops using USB dongles. The 3G networ...

LTE and Real-Time Network Congestion Management - 4G Telecom

CommProve Releases Guide to Effective LTE Management eBook Helps Mobile Operators Revolutionize Subscriber QoE And Network QoS. The deployment of LTE has cre...

Computer Networks 7-4: History of TCP Congestion Control

Computer Networks by David Wetherall, Arvind Krishnamurthy, John Zahorjan University of Washingon Overview Computer networks from ISPs to WiFi and cellular n...

Computer Networks 7-8: Explicit Congestion Notification

Computer Networks by David Wetherall, Arvind Krishnamurthy, John Zahorjan University of Washingon Overview Computer networks from ISPs to WiFi and cellular n...

Igal Milchtaich - "Representation of Finite Games as Network Congestion Games"

The 20th Anniversary of the Center for the Study of Rationality Igal Milchtaich -- "Representation of Finite Games as Network Congestion Games"

Testing TCP Congestion Avoidance | Protocol Testing | Maxwell Pro Network Emulator (Director's Cut)

Despite the opening titles, this video is in English.) A well implemented TCP stack should detect congestion and take appropriate steps to avoid adding to t...

61209 videos foundNext > 

158 news items

TODAYonline

TODAYonline
Fri, 11 Apr 2014 13:18:38 -0700

SingTel seeks to tackle mobile network congestion. SingTel seeks to tackle mobile network congestion. SingTel is considering the use of data analytics to ensure a faster and smoother surfing experience for users, especially during the morning rush hour.
 
No Jitter
Wed, 23 Apr 2014 04:03:45 -0700

Added together, this creates massive network congestion. Wireless Priority Service ("Elite Queue") The U.S. Government has set up a Wireless Priority Service (WPS) to allow high-priority emergency users to gain better access to the cellular network ...
 
Virtual-Strategy Magazine (press release)
Wed, 23 Apr 2014 00:30:00 -0700

This is creating rapid growth in data transfer volume between the cloud and data centers resulting in network congestion and slower response time. CloudOpt's technology dramatically reduces the volume of data being transferred enabling significantly ...
 
Huffington Post
Mon, 21 Apr 2014 10:03:45 -0700

The government is preparing to auction off some of those unused broadcast airwaves to wireless companies so they can improve service and avoid network congestion. An Aereo victory could prompt broadcasters to sell more of those airwaves to wireless ...

Ferret

Ferret
Tue, 22 Apr 2014 21:18:45 -0700

... greater versatility, adding analogue input modules alongside its current line of digital I/O. The use of differential inputs and Innovasic's PriorityChannel technology eliminate the risks of signal interference and network congestion, greatly ...
 
CNNMoney
Mon, 14 Apr 2014 15:17:02 -0700

Comcast attributed the problem to network congestion and, given that Netflix accounts for around a third of data consumption online during peak hours, argued that the streaming video company should help foot the bill for delivery. Netflix accused ...
 
IPTV News
Tue, 15 Apr 2014 03:18:45 -0700

Operators need easy monitoring and quick reaction to network congestion,” says Joe Hoffman, Practice Director at ABI Research. “Video optimisation solutions have to get the analytics right and deliver them with a user-friendly dashboard. Otherwise ...
 
Herald Sun
Sun, 20 Apr 2014 07:15:00 -0700

Leader Newspapers is not responsible for any technical malfunctions or problems with internet or network congestion, including injury or damage to the participant's or any other person's computer which may affect participation in this promotion or ...
Loading

Oops, we seem to be having trouble contacting Twitter

Talk About Network congestion

You can talk about Network congestion with people all over the world in our discussions.

Support Wikipedia

A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia. Please add your support for Wikipedia!