Editing Network congestion (section)

==Congestion control==<!--[[Congestion control]] (redirect) links here-->
Congestion control modulates traffic entry into a telecommunications network in order to avoid congestive collapse resulting from oversubscription.<ref>{{Cite journal |last=Nanda |first=Priyadarsi |date=2000-11-01 |title=A Control Theory Approach for Congestion Control in Intranetwork |url=https://www.sciencedirect.com/science/article/pii/S1474667017367356 |journal=IFAC Proceedings Volumes |series=16th IFAC Workshop on Distributed Computer Control Systems (DCCS 2000), Sydney, Australia, 29 November-1 December 2000 |language=en |volume=33 |issue=30 |pages=91–94 |doi=10.1016/S1474-6670(17)36735-6 |issn=1474-6670}}</ref> This is typically accomplished by reducing the rate of packets. Whereas congestion control prevents senders from overwhelming the ''network'', [[flow control (data)|flow control]] prevents the sender from overwhelming the ''receiver''.

===Theory of congestion control===
{{unreferenced section|date=May 2013}}
The theory of congestion control was pioneered by [[Frank Kelly (professor)|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 fairness|max-min fair allocation]] and Kelly's suggestion of [[proportionally fair]] allocation, although many others are possible.

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

:  <math>\max\limits_x \sum_i U(x_i)</math>

:  such that <math>Rx \le c</math>

The [[Lagrange duality|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]], <math>p_l</math>. The sum of these multipliers, <math>y_i=\sum_l p_l r_{li},</math> is the price to which the flow responds.

Congestion control then becomes a distributed optimization algorithm. Many current congestion control algorithms can be modeled in this framework, with <math>p_l</math> being either the loss probability or the queueing delay at link <math>l</math>. A major weakness is that it assigns the same price to all flows, while sliding window flow control causes [[Burst transmission|burstiness]] that causes different flows to observe different loss or delay at a given link.

===Classification of congestion control algorithms===
{{See also|TCP congestion control}}

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