Congestion control

Congestion control

:"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.

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 x_i be the rate of flow i, C_l be the capacity of link l, and r_{li} 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

: maxlimits_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, p_l. The sum of these Lagrange multipliers, y_i=sum_l p_l r_{li}, 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 p_l 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.

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"

ee also

* Bandwidth management
* TCP congestion avoidance algorithm
* Transmission Control Protocol#Development_of_TCP

External links

* [ Approaches to Congestion Control in Packet Networks]
* [ Papers in Congestion Control]
* [ Random Early Detection Homepage]
* [ Explicit Congestion Notification Homepage]
* [ TFRC Homepage]
* [ AIMD-FC Homepage]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Congestion control — Die Artikel Überlastkontrolle, Network congestion avoidance und Random early detection überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese… …   Deutsch Wikipedia

  • Congestion control (transportation) — This article concerns road traffic. For telecommunications traffic, see congestion control. Congestion control is a proposed alternative to congestion charging, which is used in a number of cities around the world (e.g. London congestion charge… …   Wikipedia

  • Taxonomy of congestion control — refers to grouping congestion control algorithms according to their characteristics.Example classificationThe following is one possible classification according to the following properties: #The type and amount of feedback received from the… …   Wikipedia

  • Datagram Congestion Control Protocol — Internet protocol suite Application layer BGP DHCP DNS FTP HTTP …   Wikipedia

  • Datagram Congestion Control Protocol — DCCP im TCP/IP‑Protokollstapel: Anwendung Streaming Protokoll Transport DCCP Internet IP (IPv4, IPv6) Netzzugang Ethernet …   Deutsch Wikipedia

  • Datagram Congestion Control Protocol — Pile de protocoles 7.  Application 6.  Présentation 5.  Session 4.  T …   Wikipédia en Français

  • Datagram Congestion Control Protocol — …   Википедия

  • Congestión de red — La congestión de redes es el fenómeno producido cuando a la red (o parte de ella) se le ofrece más tráfico del que puede cursar. Contenido 1 Causas de la congestión 2 Control de una congestión 2.1 Mecanismos de control de una congestión …   Wikipedia Español

  • Congestion pricing — Typical traffic congestion in an urban freeway. Shown here I 80 Eastshore Freeway, Berkeley, United States …   Wikipedia

  • Congestion window — Internet protocol suite Application layer BGP DHCP DNS FTP HTTP …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”