Network congestion

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

${\displaystyle \max \limits _{x}\sum _{i}U(x_{i})}$

such that ${\displaystyle Rx\leq 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, ${\displaystyle p_{l}}$. The sum of these multipliers, ${\displaystyle y_{i}=\sum _{l}p_{l}r_{li},}$ 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 ${\displaystyle p_{l}}$ being either the loss probability or the queueing delay at link ${\displaystyle 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.

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

Connection-oriented protocols, such as the widely used TCP protocol watch for packet loss, or queuing delay to adjust their transmission rate. Various network congestion avoidance processes support different trade-offs.[9]

The TCP congestion avoidance algorithm is the primary basis for congestion control on the Internet.[10][11][12][13][14]

Problems occur when concurrent TCP flows experience tail-drops, especially when bufferbloat is present. This delayed packet loss interferes with TCP's automatic congestion avoidance. All flows that experience this packet loss begin a TCP retrain at the same moment – this is called TCP global synchronization.

Active queue management (AQM) is the reordering or dropping of network packets inside a transmit buffer that is associated with a network interface controller (NIC). This task is performed by the network scheduler.

One solution is to use random early detection (RED) on the network equipment's egress queue.[15][16] On networking hardware ports with more than one egress queue, weighted random early detection (WRED) can be used.

RED indirectly signals TCP sender and receiver by dropping some packets, e.g. when the average queue length is more than a threshold (e.g. 50%) and deletes linearly or cubically more packets,[17] up to e.g. 100%, as the queue fills further.

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 confirmed that RED-like algorithms were vulnerable under LDoS attacks due to the oscillating TCP queue size caused by the attacks.[18]

Some network equipment is equipped with ports that can follow and measure each flow and are thereby able to signal a too big bandwidth flow according to some quality of service policy. A policy could then divide the bandwidth among all flows by some criteria.[19]

Another approach is to use Explicit Congestion Notification (ECN).[20] ECN is used only when 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 congestion notification signaled by packet loss by the RED/WRED algorithms, but it requires support by both hosts.[21][15]

When a router receives a packet marked as ECN-capable and the router 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 its sending rate by reducing the TCP window size or by other means.

Congestion avoidance can be achieved efficiently by reducing traffic. 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 many applications simultaneously request downloads, this data can create a congestion point at an upstream provider. By reducing the window advertisement, the remote servers send less data, thus reducing the congestion.[22][23]

Backward ECN (BECN) is another proposed congestion notification mechanism. It uses ICMP source quench messages as an IP signaling mechanism to implement a basic ECN mechanism for IP networks, keeping congestion notifications at the IP level and requiring no negotiation between network endpoints. Effective congestion notifications can be propagated to transport layer protocols, such as TCP and UDP, for the appropriate adjustments.[24]

The protocols that avoid congestive collapse generally assume that data loss is caused by congestion. On wired networks, errors during transmission are rare. WiFi, 3G and other networks with a radio layer are susceptible to data loss due to interference and may experience poor throughput in some cases. The TCP connections running over a radio-based physical layer see the data loss and tend to erroneously believe that congestion is occurring.

The slow-start protocol performs badly for short connections. Older web browsers created many short-lived connections and opened and closed the connection for each file. This kept most connections in the slow start mode. Initial performance can be poor, and many connections never get out of the slow-start regime, significantly increasing latency. To avoid this problem, modern browsers either open multiple connections simultaneously or reuse one connection for all files requested from a particular server.