Editing Network congestion (section)

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