Network Congestion Avoidance

Network congestion in data networking and queueing theory is the reduced quality of service that occurs when a network node or link is carrying more data than it can handle. Typical effects include queueing delay, packet loss or the blocking of new connections. A consequence of congestion is that an incremental increase in offered load leads either only to a small increase or even a decrease in network throughput.

Network protocols that use aggressive retransmissions to compensate for packet loss due to congestion can increase congestion, even after the initial load has been reduced to a level that would not normally have induced network congestion. Such networks exhibit two stable states under the same level of load. The stable state with low throughput is known as congestive collapse.

Networks use congestion control and congestion avoidance techniques to try to avoid collapse. These include: exponential backoff in protocols such as CSMA/CA in 802.11 and the similar CSMA/CD in the original Ethernet, window reduction in TCP, and fair queueing in devices such as routers and network switches. Other techniques that address congestion include priority schemes which transmit some packets with higher priority ahead of others and the explicit allocation of network resources to specific flows through the use of admission control.

Network capacity

Network resources are limited, including router processing time and link throughput. Resource contention may occur on networks in several common circumstances. 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. Denial-of-service attacks by botnets are capable of filling even the largest Internet backbone network links, generating large-scale network congestion. In telephone networks, a mass call event can overwhelm digital telephone circuits.

Congestive collapse

Congestive collapse (or congestion collapse) is the condition in which congestion prevents or limits useful communication. Congestion collapse generally occurs at choke points in the network, where incoming traffic exceeds outgoing bandwidth. Connection points between a local area network and a wide area network are common choke points. When a network is in this condition, it settles into a stable state where traffic demand is high but little useful throughput is available, during which packet delay and loss occur and quality of service is extremely poor.

Congestive collapse was identified as a possible problem by 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, which continued until end nodes started implementing Van Jacobson and Sally Floyd's congestion control between 1987 and 1988. 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 poor retransmission behavior. When this packet loss occurred, the endpoints sent extra packets that repeated the information lost, doubling the incoming rate.

Congestion control

Congestion control modulates traffic entry into a telecommunications network in order to avoid congestive collapse resulting from oversubscription. This is typically accomplished by reducing the rate of packets. Whereas congestion control prevents senders from overwhelming the ''network'', flow control prevents the sender from overwhelming the ''receiver''.

Theory of congestion control

The 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 proportionally fair allocation, although many others are possible.

Let $x_i$ be the rate of flow $i$, $c_l$ be the capacity of link $l$, and $r_$ 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'' signaled by the network. Each link capacity imposes a constraint, which gives rise to a Lagrange multiplier, $p_l$. The sum of these multipliers, $y_i=\sum_l p_l r_,$ is the price to which the flow responds.

Congestion control then becomes a distributed optimization algorithm. 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 is that it assigns the same price to all flows, while sliding window flow control causes burstiness that causes different flows to observe different loss or delay at a given link.

Classification of congestion control algorithms

Among the ways to classify congestion control algorithms are:
*By type and amount of feedback received from the network: Loss; delay; single-bit or multi-bit explicit signals
*By incremental deployability: Only sender needs modification; sender and receiver need modification; only router needs modification; sender, receiver and routers need modification.
*By performance aspect: high bandwidth-delay product networks; lossy links; fairness; advantage to short flows; variable-rate links
*By fairness criterion: Max-min fairness; proportionally fair; controlled delay

Mitigation

Mechanisms have been invented to prevent network congestion or to deal with a network collapse:
* Network scheduler