Congestion control

From Wikipedia, the free encyclopedia

This article concerns telecommunications traffic. For road traffic, see traffic congestion.

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.

Contents

[edit] 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 xi be the rate of flow i, Cl be the capacity of link l, and rli 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 convex 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, pl. The sum of these Lagrange multipliers,

yi = ∑ plrli,
l

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 pl 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.

[edit] Classification of congestion control algorithms

Main article: Taxonomy of congestion control

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"

[edit] See also

[edit] External links