- Congestion control
:"This article concerns telecommunications traffic. For road traffic, see
Congestion control concerns controlling traffic entry into a
telecommunications network, so as to avoid congestive collapseby 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
The modern theory of congestion control was pioneered by Frank Kelly, who applied
microeconomic theoryand convex optimizationtheory 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 be the rate of flow , be the capacity of link , and be 1 if flow uses link and 0 otherwise. Let , and be the corresponding vectors and matrix. Let be an increasing, strictly convex function, called the
utility, which measures how much benefit a user obtains by transmitting at rate . The optimal rate allocation then satisfies
: such that
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, . The sum of these
Lagrange multipliers, 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 being either the loss probability or the queueing delay at link .
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
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"
TCP congestion avoidance algorithm
Transmission Control Protocol#Development_of_TCP
* [http://utopia.duth.gr/~emamatas/jie2007.pdf Approaches to Congestion Control in Packet Networks]
* [http://www.ecse.rpi.edu/Homepages/shivkuma/research/cong-papers.html Papers in Congestion Control]
* [http://www.icir.org/floyd/red.html Random Early Detection Homepage]
* [http://www.icir.org/floyd/ecn.html Explicit Congestion Notification Homepage]
* [http://www.icir.org/tfrc/ TFRC Homepage]
* [http://www.ccs.neu.edu/home/ladrian/abstract/aimdfc.html AIMD-FC Homepage]
Wikimedia Foundation. 2010.