Poverty gap index

2014-01-28T16:19:12Z

152.23.142.120: /* Related measures */

{{for|an official visit abroad taken by a member or members of the United States Congress|Congressional delegation}}

In [[network routing]], '''CoDel''' (pronounced "[[wikt:coddle|coddle]]") for '''controlled delay''' is a [[scheduling algorithm]] for the [[network scheduler]] developed by [[Van Jacobson]] and [[Kathleen Nichols]].<ref name="CoDel_ACMQ">{{cite web |url=http://queue.acm.org/detail.cfm?id=2209336 |title=Controlling Queue Delay |authorlink=Kathleen Nichols |last1=Nichols |first1=Kathleen |authorlink2=Van Jacobson|last2=Jacobson |first2=Van |date=6 May 2012 |work=ACM Queue |publisher=ACM Publishing |accessdate=12 August 2012| doi=10.1145/2209249.2209264 }}</ref><ref name="CoDel_JimGettys">{{cite web |url=http://gettys.wordpress.com/2012/05/08/fundamental-progress-solving-bufferbloat/ |title=Fundamental Progress Solving Bufferbloat
|last=Gettys |first=Jim |authorlink=Jim Gettys
|date=May 8, 2012 |work=jg's Ramblings |publisher=Wordpress |accessdate=12 August 2012}}</ref> It is designed to overcome [[bufferbloat]] in network links (such as [[router (computing)|router]]s) by setting limits on the delay [[network packet]]s suffer due to passing through the [[buffer (telecommunication)|buffer]] being managed by CoDel.

CoDel aims at improving on the overall performance of the [[Random early detection|RED]] algorithm by addressing some fundamental misconceptions in the algorithm (as perceived by Jacobson) and by being easier to manage (since, unlike RED, CoDel does not require manual configuration).<ref name="CoDel_ACMQ"/>

An implementation of CoDel was written by Dave Täht and Eric Dumazet for the [[Linux kernel]]<ref>{{cite web |url=https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/net/sched/sch_codel.c |title=CoDel Linux kernel network scheduler module |publisher=[[kernel.org]] |accessdate=2013-09-07}}</ref> and dual licensed under the [[GNU General Public License]] and the [[3-clause BSD license]]. Dave Täht back-ported CoDel to Linux kernel 3.3 for project [[CeroWrt]], which concerns itself among other things with bufferbloat,<ref>{{cite web|url=http://www.bufferbloat.net/projects/cerowrt |title=Cerowrt - Overview |publisher=Bufferbloat |date= |accessdate=2014-01-24}}</ref> where it was exaustively tested. It was then pushed into [[OpenWrt]].<ref>{{cite web |url=https://dev.openwrt.org/changeset/31756 |title=Backport of CoDel and FQ_CoDel to Linux 3.3 |publisher=[[OpenWrt]] |date=2012-05-16 |accessdate=2013-09-07}}</ref> Dumazet's variant of CoDel, [[FQ_Codel]] was adopted as the standard [[Active queue management|AQM]] and [[packet scheduling]] solution in OpenWrt "Barrier Breaker" in 2012.<ref>{{cite web |url=https://dev.openwrt.org/browser/trunk/package/network/config/qos-scripts/files/usr/lib/qos/tcrules.awk |title=Adoption of CoDel in OpenWrt default QoS scripts |publisher=[[OpenWrt]]}}</ref> From there, Codel and FQ_Codel has migrated into various downstream projects such as [[dd-wrt]], [[IpFire]], and technologies like [[StreamBoost]].

==Theoretical underpinnings==
The theory behind CoDel is based on a number of observations of packet behavior in [[packet-switched network]]s under the influence of [[data buffer]]s. Some of these observations are about the fundamental nature of queueing and the causes of bufferbloat, others relate to weaknesses of alternative queue management algorithms. CoDel was developed as an attempt to address the problem of bufferbloat.<ref>{{cite web
| url = http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php
| title = Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution
| publisher = [[ReadWriteWeb]]
| author = Joe Brockmeier
| date = 2012-05-08 | accessdate = 2012-08-16}}</ref>

===Bufferbloat===
{{Main|Bufferbloat}}
{{See also|Receive_window#Window_size|l1=TCP window size|Slow-start|l2=TCP slow start}}

The flow of packets slows down while travelling through a network link between a fast and a slow network, especially at the start of a [[Transmission Control Protocol|TCP]] session, when there is a sudden burst of packets and link to the slower network may not be able to process the burst quickly enough. [[buffer (telecommunication)|Buffers]] exist to ease this problem by giving the fast network a place to push packets, to be read by the slower network as fast as it can.<ref name="CoDel_ACMQ"/> In other words, buffers act like shock absorbers to convert bursty arrivals into smooth, steady departures. However, a buffer has a finite size, and it can hold only a specific maximum number of packets. The ideal buffer is sized so it can handle a sudden burst of communication and match the speed of that burst to the speed of the slower network. Ideally, the "shock absorbing" situation is characterized by a temporary delay for packets in the buffer during the transmission burst, after which the delay rapidly disappears and the network reaches a balance in offering and handling packets.<ref name="CoDel_ACMQ" />

The TCP congestion avoidance algorithm relies on packet drops to determine the available [[bandwidth (computing)|bandwidth]]. It speeds up the data transfer until packets start to drop, and then slows down the transmission rate. Ideally it keeps speeding up and slowing down the transmission rate, until it finds an equilibrium to the speed of the link. However, for this to work the packet drops must occur in a timely manner, so that the algorithm can select a suitable transfer speed. With a large buffer that has been filled, the packets will arrive at their destination, but with a higher latency. The packet is not dropped, so TCP does not slow down once the uplink has been saturated, further filling the buffer. Newly arriving packets are dropped only when the buffer is fully saturated. TCP may even decide that the path of the connection has changed, and again go into the more aggressive search for a new operating point.<ref>{{cite journal
| url = http://www.cord.edu/faculty/zhang/cs345/assignments/researchPapers/congavoid.pdf
| title = Congestion avoidance and control
| journal = ACM SIGCOMM Computer Communication Review
| last = Jacobson | first = Van
| coauthors = Karels, MJ
| year = 1988 | volume = 18 | issue = 4
}}</ref><ref name="Rant_Jacobson">{{cite web
| url = http://www.pollere.net/Pdfdocs/QrantJul06.pdf
| title = A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA
| last1 = Jacobson
| first1 = Van
| authorlink1 = Van Jacobson
| year = 2006 | accessdate = 12 August 2012
}}</ref>

In the problematic situation, packets queued in a network buffer are only dropped if the buffer is full. Having a big and constantly full buffer which causes increased transmission delays and reduced interactivity — especially when looking at two or more simultaneous transmissions over the same channel — is what's called '''bufferbloat'''. Available channel bandwidth can also end up being unused, as some fast destinations may not be reached due to buffers clogged with data avaiting delivery to slow destinations — caused by contention between simultaneous transmissions competing for some space in an already full buffer.

===Good and bad queues===
CoDel distinguishes between two "types" of a queue (or rather, the effects produced by a queue):<ref name="CoDel_ACMQ"/><ref>{{cite web |url=http://arstechnica.com/information-technology/2012/05/codel-buffer-management-could-solve-the-internets-bufferbloat-jams/ |title=CoDel buffer management could solve the Internet’s bufferbloat jams |publisher=Ars Technica |date=2012-05-10 |author=Iljitsch van Beijnum |accessdate=2012-08-16}}</ref>

; Good queue
: Defined as a queue that exhibits no buffer bloat, i.e. catches and handles communications bursts with no more than a temporary increase in queue delay and which maximizes utilization of the network link.
; Bad queue
: Defined as a queue that exhibits buffer bloat, i.e. where a communications burst has caused the buffer to fill up and stay filled, resulting in low utilization and a constantly high buffer delay.

In order to be effective against bufferbloat, a solution in form of an [[Active queue management]] (AQM) algorithm must be able to '''recognize''' an occurrence of bufferbloat and '''react''' with deploying effective countermeasures.

Regarding the recognition of an unwanted situation, [[Van Jacobson]] asserted in 2006 that existing algorithms have been using incorrect means of recognizing bufferbloat.<ref name="Rant_Jacobson"/> In an attempt to recognize the telltale standing queue of bufferbloat, algorithms like [[Random early detection|RED]] measure the average queue length (in packets or stored bytes) and consider it a case of bufferbloat if the average grows too large. However, Jacobson demonstrated in 2006 that this measurement is not a good metric — the average queue length rises sharply in case of a communications burst. But this can then dissipate quickly (good queue) or develop a standing queue (bad queue). Also, other factors in network traffic can cause false positives or negatives, causing countermeasures to be deployed unnecessarily — Jacobson suggested therefore that average queue length actually contains no information at all about packet demand or network load.<ref name="CoDel_ACMQ"/><ref name="Rant_Jacobson"/> He then suggested that a better metric might be the minimum amount of delay experienced by any packet in the sliding window of the buffer.{{Citation needed|date=December 2012}}

==The CoDel algorithm==
Based on Jacobson's notion from 2006, CoDel was developed to manage queues under control of the minimum delay experienced by packets in the running buffer window. The goal is to keep this minimum delay below 5 milliseconds. If the minimum delay rises to too high a value, packets are dropped from the window until the delay drops below the maximum level.<ref name="CoDel_ACMQ"/>

Nichols and Jacobson cite several advantages to using nothing more than this metric:<ref name="CoDel_ACMQ"/>

* CoDel is parameterless. One of the weaknesses in the RED algorithm (according to Jacobson) is that it is too difficult to configure (and too difficult to configure correctly, especially in an environment with dynamic link rates). CoDel has no parameters to set at all.
* CoDel treats good queue and bad queue differently. Good queue has low delays by nature, so the management algorithm can ignore it. Bad queue is susceptible to management intervention in the form of dropping packets.
* CoDel works off of a parameter that is determined completely locally, so it is independent of round-trip delays, link rates, traffic loads and other factors that simply cannot be controlled or predicted by the local buffer.
* The local minimum delay can only be determined when a packet leaves the buffer. So no extra delay is needed to run the queue to collect statistics to manage the queue.
* CoDel adapts to dynamically changing link rates with no negative impact on utilization.
* CoDel can be implemented relatively simply and therefore can span the spectrum from low-end home routers to high-end routing solutions.

CoDel does nothing to manage the buffer if the minimum delay for the buffer window is below the maximum allowed value. It also does nothing if the buffer is relatively empty (if there are fewer than one [[maximum transmission unit|MTU]]'s worth of bytes in the buffer).<ref name="CoDel_ACMQ"/> If these conditions do not hold, then CoDel drops packets probabilistically.<ref name="CoDel_ACMQ"/>

===Description===
The algorithm is independently computed at each [[Hop (networking)|hop]]. The algorithm operates over an ''interval''. The initial ''interval'' is 100 milliseconds. Per-packet [[queuing delay]] is monitored through the hop. As each packet is dequeued for [[Packet forwarding|forwarding]], the queuing delay (amount of time the packet spent waiting in the queue) is calculated. The lowest queuing delay for the interval is stored. When the last packet of the interval is dequeued, if the lowest queuing delay for the interval is greater than 5 milliseconds, this single packet is dropped and the ''interval'' used for the next group of packets is shortened. If the lowest queuing delay for the interval is less than 5 milliseconds, the packet is forwarded and ''interval'' is reset to 100 milliseconds.

When the ''interval'' is shortened, it is done so in accordance with the inverse [[square root]] of the number of successive intervals in which packets were dropped due to excessive queuing delay. The sequence of intervals is <math>100</math>, <math>{100 \over \sqrt{2}}</math>, <math>{100 \over \sqrt{3}}</math>, <math>{100 \over \sqrt{4}}</math>, <math>{100 \over \sqrt{5}}</math> ...

===Simulation results===
CoDel has been tested in simulation tests by Nichols and Jacobson, at different MTUs and link rates and other variations of conditions. In general, results indicate:<ref name="CoDel_ACMQ"/><ref name="CoDel_sims">{{cite web |url=http://www.pollere.net/CoDel.html |title=Controlled Delay (CoDel) Active Queue Management |last1=Nichols |first1=Kathleen |date=July 2012 |publisher=Pollere Inc. |accessdate=12 August 2012}}</ref>

* In comparison to RED, CoDel keeps the packet delay closer to the target value across the full range of bandwidths (from 3 to 100 Mbit/s). This seems to result in good queue, since the measured link utilizations are consistently near 100% of link bandwidth.
* At lower MTU, packet delays are lower than at higher MTU. Higher MTU results in good link utilization, lower MTU results in good link utilizations at lower bandwidth, degrading to fair utilization at high bandwidth.

Simulation was also performed by Greg White and Joey Padden at [[CableLabs]].<ref>{{cite paper |url=http://www.cablelabs.com/downloads/pubs/PreliminaryStudyOfCoDelAQMinaDOCSISNetwork.pdf |title=PRELIMINARY STUDY OF CODEL AQM IN A DOCSIS NETWORK |author1=Greg White |author2=Joey Padden |date=November 2012 |accessdate=2012-11-26}}</ref>

===CoDel in use===
A full implementation of CoDel was realized in May 2012 and is available as [[open-source software]] to all interested parties. This implementation will be used by different parties to study CoDel in actual use.<ref name="CoDel_ACMQ"/>

As of 21 May 2012, CoDel has been implemented within the [[Linux kernel]] (starting with the 3.5 mainline).<ref name="CoDel_Linux">{{cite web |url=http://gettys.wordpress.com/2012/05/22/a-milestone-reached-codel-is-in-linux/ |title=A Milestone Reached: CoDel is in Linux! |last=Gettys |first=Jim |authorlink=Jim Gettys |date=22 May 2012 |work=jg's Ramblings |accessdate=12 August 2012}}</ref>

CoDel began to appear as an option in some proprietary/turnkey bandwidth management platforms in 2013.<ref name="Procera_PacketLogic_Changelog">{{cite web | url="http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt" | title=Procera Packetlogic Changelog}}</ref>

== See also ==
* [[Bufferbloat]]
* [[Receive window#Window size|TCP window size]]
* [[TCP tuning]]

== References ==
{{Reflist|30em}}

== External links ==
* [http://queue.acm.org/appendices/codel.html CoDel pseudocode]
* [http://www.orospakr.ca/blog/2013/01/22/bufferbloat-demystified/ Bufferbloat demystified]

[[Category:Packets (information technology)]]
[[Category:Network performance]]

formulasearchengine - User contributions [en]

Poverty gap index