Misplaced Pages

CoDel: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editContent deleted Content addedVisualWikitext
Revision as of 14:26, 17 April 2020 editKvng (talk | contribs)Extended confirmed users, New page reviewers107,681 edits Undid revision 950966328 by JzG (talk) WP:ELMAYBE #4. These are established experts so also allowed under WP:BLOG.Tags: citing a blog or free web host Undo← Previous edit Latest revision as of 15:43, 17 August 2024 edit undoKvng (talk | contribs)Extended confirmed users, New page reviewers107,681 editsm unpiped links using script simplify link 
(39 intermediate revisions by 19 users not shown)
Line 1: Line 1:
{{Short description|Queue management algorithm for computer network packets}}
{{for|an official visit abroad taken by a member or members of the United States Congress|Congressional delegation}} {{for|an official visit abroad taken by a member or members of the United States Congress|Congressional delegation}}


In ], '''CoDel''' (pronounced "]") for '''controlled delay''' is a ] for the ] developed by ] and ]. It is designed to overcome ] in ], such as ]s, by setting limits on the delay ]s experience as they pass through ]s in this equipment. CoDel aims to improve on the overall performance of the ] (RED) algorithm by addressing some of its fundamental misconceptions, as perceived by Jacobson, and by being easier to manage. '''CoDel''' (''Controlled Delay''; pronounced "]") is an ] (AQM) algorithm in ], developed by ] and ] and published as RFC8289.<ref name="RFC8289">{{cite IETF |title = Controlled Delay Active Queue Management|rfc = 8289 |last1 = Nichols|first1 = K. |author-link1 = Kathleen Nichols |last2 = Jacobson |first2 = V. |author-link2 = Van Jacobson |last3 = McGregor |first3 = A. |last4 = Iyengar |first4 = J. |date = Jan 2018 |publisher = ]}}</ref> It is designed to overcome ] in ], such as ]s, by setting limits on the delay ]s experience as they pass through ]s in this equipment. CoDel aims to improve on the overall performance of the ] (RED) algorithm by addressing some of its fundamental misconceptions, as perceived by Jacobson, and by being easier to manage.


In 2012, an implementation of CoDel was written by Dave Täht and Eric Dumazet for the ] and dual licensed under the ] and the ]. Dumazet's variant of CoDel is called fq_codel, standing for "] controlled delay"; it was adopted as the standard ] (AQM) and ] solution in the ] release called "Barrier Breaker". From there, CoDel and fq_codel have migrated into various downstream projects such as ], ] and ]. In 2012, an implementation of CoDel was written by ] and Eric Dumazet for the ] and dual licensed under the ] and the ]. Dumazet's improvement on CoDel is called ], standing for "Fair/Flow Queue CoDel"; it was first adopted as the standard AQM and ] solution in 2014 in the ] 14.07 release called "Barrier Breaker". From there, CoDel and FQ-CoDel have migrated into various downstream projects such as ], ], ] and ]'s "Smart Queues" feature.


== Theory ==
==Theoretical underpinnings==
⚫ The theory behind CoDel is based on observations of packet behavior in ]s under the influence of ]s. Some of these observations are about the fundamental nature of queueing and the causes of ], 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 = ]
| author = Joe Brockmeier
| date = 2012-05-08
| accessdate = 2012-08-16
| archive-url = https://web.archive.org/web/20120712012901/http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php
| archive-date = 2012-07-12
| url-status = dead
}}</ref>


⚫ CoDel is based on observations of packet behavior in ]s under the influence of ]s. Some of these observations are about the fundamental nature of queueing and the causes of ], 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 = ] | author = Joe Brockmeier | date = 2012-05-08 | accessdate = 2012-08-16 | archive-url = https://web.archive.org/web/20120712012901/http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php | archive-date = 2012-07-12 | url-status = dead }}</ref>
⚫ ===Bufferbloat===

⚫ === Bufferbloat ===
{{Main|Bufferbloat}} {{Main|Bufferbloat}}
⚫ 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 ] session, when there is a sudden burst of packets and the slower network may not be able to accept the burst quickly enough. ] exist to ease this problem by giving the fast network a place to store packets to be read by the slower network at its own pace.<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> In other words, buffers act like shock absorbers to convert bursty arrivals into smooth, steady departures. However, a buffer has limited capacity. 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 flow of packets slows down while traveling through a network link between a fast and a slow network, especially at the start of a ] session, when there is a sudden burst of packets and the slower network may not be able to accept the burst quickly enough. ] exist to ease this problem by giving the fast network a place to store packets to be read by the slower network at its own pace.<ref name="CoDel_ACMQ">{{cite journal |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 |journal=ACM Queue |volume=55 |issue=7 |pages=42–50 |publisher=ACM Publishing |accessdate=12 August 2012| doi=10.1145/2209249.2209264 |s2cid=381738 }}</ref> In other words, buffers act like shock absorbers to convert bursty arrivals into smooth, steady departures. However, a buffer has limited capacity. 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 ] algorithm relies on packet drops to determine the available ] between two communicating devices. 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 as it finds an equilibrium at the speed of the link. For this to work, the packet drops must occur in a timely manner so that the algorithm can responsively select a suitable transfer speed. With packets held in an overly-large buffer, the packets will arrive at their destination but with a higher ] but no packets are dropped so TCP does not slow down. Under these conditions, TCP may even decide that the path of the connection has changed and repeat the search for a new equilibrium.<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
| author2 = Karels, MJ
| year = 1988
| volume = 18
| issue = 4
| url-status = dead
| archiveurl = https://web.archive.org/web/20040622215331/http://www.cord.edu/faculty/zhang/cs345/assignments/researchPapers/congavoid.pdf
| archivedate = 2004-06-22
}}</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>


⚫ The ] algorithm relies on packet drops to determine the available ] between two communicating devices. 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 as it finds equilibrium at the speed of the link. For this to work, the packet drops must occur in a timely manner so that the algorithm can responsively select a suitable transfer speed. With packets held in an overly-large buffer, the packets will arrive at their destination but with a higher ] but no packets are dropped so TCP does not slow down. Under these conditions, TCP may even decide that the path of the connection has changed and repeat the search for a new equilibrium.<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 | author2 = Karels, MJ | year = 1988 | volume = 18 | issue = 4 | pages = 314–329 | doi = 10.1145/52325.52356 | url-status = dead | archiveurl = https://web.archive.org/web/20040622215331/http://www.cord.edu/faculty/zhang/cs345/assignments/researchPapers/congavoid.pdf | archivedate = 2004-06-22 }}</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 | author-link1 = Van Jacobson | year = 2006 | access-date = 12 August 2012 }}</ref>
⚫ 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 called bufferbloat. Available channel bandwidth can also end up being unused, as some fast destinations may not be reached due to buffers being clogged with data awaiting delivery to slow destinations.


⚫ Having a big and constantly full buffer that causes increased transmission delays and reduced interactivity, especially when looking at two or more simultaneous transmissions over the same channel, is called bufferbloat. Available channel bandwidth can also end up being unused, as some fast destinations may not be reached due to buffers being clogged with data awaiting delivery to slow destinations.
===Good and bad queues===
CoDel distinguishes between two types of queue:<ref name="CoDel_ACMQ"/><ref>{{cite web |url=https://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 === Good and bad queues ===
: Defined as a queue that exhibits no bufferbloat. Communication bursts cause no more than a temporary increase in queue delay. The network link utilization is maximized.
; Bad queue
: Defined as a queue that exhibits bufferbloat. Communication bursts cause 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 the form of an ] (AQM) algorithm must be able to recognize an occurrence of bufferbloat and react by deploying effective countermeasures. CoDel distinguishes between two types of queue:<ref name="CoDel_ACMQ"/><ref>{{cite web |url=https://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> A ''good queue'' is one that exhibits no bufferbloat. Communication bursts cause no more than a temporary increase in queue delay. The network link utilization is maximized. A ''bad queue'' exhibits bufferbloat. Communication bursts cause 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 the form of an ] (AQM) algorithm must be able to recognize an occurrence of bufferbloat and react by deploying effective countermeasures.


] asserted in 2006 that existing algorithms have been using incorrect means of recognizing bufferbloat.<ref name="Rant_Jacobson"/> Algorithms like ] measure the average queue length and consider it a case of bufferbloat if the average grows too large. Jacobson demonstrated in 2006 that this measurement is not a good metric, as the average queue length rises sharply in the case of a communications burst. The queue can then dissipate quickly (good queue) or become a standing queue (bad queue). Other factors in network traffic can also cause false positives or negatives, causing countermeasures to be deployed unnecessarily. Jacobson suggested 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 suggested that a better metric might be the minimum queue length during a sliding time window.<ref name="CoDel_ACMQ"/><!--Kvng RTH--> ] asserted in 2006 that existing algorithms have been using incorrect means of recognizing bufferbloat.<ref name="Rant_Jacobson"/> Algorithms like ] measure the average queue length and consider it a case of bufferbloat if the average grows too large. Jacobson demonstrated in 2006 that this measurement is not a good metric, as the average queue length rises sharply in the case of a communications burst. The queue can then dissipate quickly (good queue) or become a standing queue (bad queue). Other factors in network traffic can also cause false positives or negatives, causing countermeasures to be deployed unnecessarily. Jacobson suggested 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 suggested that a better metric might be the minimum queue length during a sliding time window.<ref name="CoDel_ACMQ"/>


==Algorithm== == 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 queue 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"/> 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 queue 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, especially in an environment with dynamic link rates. CoDel has no parameters to set at all. * CoDel is parameterless. One of the weaknesses in the RED algorithm (according to Jacobson) is that it is too difficult to configure, especially in an environment with dynamic link rates.
* CoDel treats good queue and bad queue differently. A good queue has low delays by nature, so the management algorithm can ignore it, while a bad queue is subject to management intervention in the form of dropping packets. * CoDel treats good queue and bad queue differently. A good queue has low delays by nature, so the management algorithm can ignore it, while a bad queue is subject 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 cannot be controlled or predicted by the local buffer. * CoDel works off of a parameter that is determined completely locally; It is independent of round-trip delays, link rates, traffic loads and other factors that 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. * 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 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. * The CoDel implementation is relatively simple 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 ]'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"/> 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 ]'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"/><!--Kvng RTH-->


===Description===
The algorithm is independently computed at each network ]. The algorithm operates over an ''interval'', initially 100 milliseconds. Per-packet ] is monitored through the hop. As each packet is dequeued for ], 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 the interval is reset to 100 milliseconds. The algorithm is independently computed at each network ]. The algorithm operates over an ''interval'', initially 100 milliseconds. Per-packet ] is monitored through the hop. As each packet is dequeued for ], 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 the interval is reset to 100 milliseconds.


When the interval is shortened, it is done so in accordance with the inverse ] 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> ... When the interval is shortened, it is done so in accordance with the inverse ] 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=== == 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 |archive-url=https://web.archive.org/web/20120822123432/http://www.pollere.net/CoDel.html |archive-date=22 August 2012 |url-status=dead }}</ref> 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 |archive-url=https://web.archive.org/web/20120822123432/http://www.pollere.net/CoDel.html |archive-date=22 August 2012 |url-status=dead }}</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). The measured link utilizations are consistently near 100% of link bandwidth. * In comparison to RED, CoDel keeps the packet delay closer to the target value across the full range of bandwidths (from 3 to 100&nbsp;Mbit/s). 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. * At lower MTU, packet delays are lower than at higher MTU. Higher MTU results in good link utilization, lower MTU results in good link utilization at lower bandwidth, degrading to fair utilization at high bandwidth.


Simulation was also performed by Greg White and Joey Padden at ].<ref>{{cite paper |url=http://www.cablelabs.com/wp-content/uploads/2014/05/PreliminaryStudyOfCoDelAQM_DOCSIS-Network.pdf |title=Preliminary Study of Codel AGM in a Docsis Network |author1=Greg White |author2=Joey Padden |date=November 2012 |accessdate=2015-06-14 |website=cablelabs.com |format=PDF}}</ref> Simulation was also performed by Greg White and Joey Padden at ].<ref>{{cite web |url=http://www.cablelabs.com/wp-content/uploads/2014/05/PreliminaryStudyOfCoDelAQM_DOCSIS-Network.pdf |title=Preliminary Study of Codel AGM in a Docsis Network |author1=Greg White |author2=Joey Padden |date=November 2012 |accessdate=2015-06-14 |website=cablelabs.com }}</ref>


===Implementation=== == Implementation ==

A full implementation of CoDel was realized in May 2012 and made available as ].<ref name="CoDel_ACMQ"/> It was implemented within the ] (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> Dave Täht back-ported CoDel to Linux kernel 3.3 for project ], which concerns itself among other things with bufferbloat,<ref>{{cite web|url=http://www.bufferbloat.net/projects/cerowrt |title=Cerowrt - Overview |publisher=Bufferbloat |accessdate=2014-01-24}}</ref> where it was exhaustively tested. 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 | website=proceranetworks.com | access-date=2013-07-24 | archive-url=https://archive.is/20130724211528/http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt | archive-date=2013-07-24 | url-status=dead }}</ref> FreeBSD had CoDel integrated into the 11.x<ref>{{cite web | url = https://svnweb.freebsd.org/base?view=revision&revision=300779 | title = Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE). | date = 2016-05-26 | author = truckman }}</ref> and 10.x<ref>{{cite web | url = https://svnweb.freebsd.org/base?view=revision&revision=301772| title = MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE). | date = 2016-06-10 |author = truckman }}</ref> ] in 2016.<ref>{{cite web | url = http://caia.swin.edu.au/freebsd/aqm/ | title = Implementing AQM in FreeBSD | first1 = Rasool | last1 = Al Saadi | first2 = Grenville | last2 = Armitage }}</ref> An implementation is distributed with ] since version 6.2.<ref>{{cite web|url=https://www.openbsd.org/62.html|accessdate=13 October 2017|title=OpenBSD 6.2}}</ref> A full implementation of CoDel was realized in May 2012 and made available as ].<ref name="CoDel_ACMQ"/> It was implemented within the ] (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> Dave Täht back-ported CoDel to Linux kernel 3.3 for project ], which concerns itself among other things with bufferbloat,<ref>{{cite web|url=http://www.bufferbloat.net/projects/cerowrt |title=Cerowrt - Overview |publisher=Bufferbloat |accessdate=2014-01-24}}</ref> where it was exhaustively tested. 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 | website=proceranetworks.com | access-date=2013-07-24 | archive-url=https://archive.today/20130724211528/http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt | archive-date=2013-07-24 | url-status=dead }}</ref> FreeBSD had CoDel integrated into the 11.x<ref>{{cite web | url = https://svnweb.freebsd.org/base?view=revision&revision=300779 | title = Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE). | date = 2016-05-26 | author = truckman }}</ref> and 10.x<ref>{{cite web | url = https://svnweb.freebsd.org/base?view=revision&revision=301772| title = MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE). | date = 2016-06-10 |author = truckman }}</ref> ] in 2016.<ref>{{cite web | url = http://caia.swin.edu.au/freebsd/aqm/ | title = Implementing AQM in FreeBSD | first1 = Rasool | last1 = Al Saadi | first2 = Grenville | last2 = Armitage }}</ref> An implementation is distributed with ] since version 6.2.<ref>{{cite web|url=https://www.openbsd.org/62.html|accessdate=13 October 2017|title=OpenBSD 6.2}}</ref>

== Derived algorithms ==
Fair/Flow Queue CoDel (FQ-CoDel; fq_codel in Linux code) adds flow queuing to CoDel so that it differentiates between multiple simultaneous connections and works fairly. It gives the first packet in each stream priority, so that small streams can start and finish quickly for better use of network resources. CoDel co-author Van Jacobson recommends the use of fq_codel over codel where it's available.<ref>{{cite web |title=Benchmarking Codel and FQ Codel - Bufferbloat.net |url=https://www.bufferbloat.net/projects/codel/Benchmarking_Codel_and_FQ_Codel/ |website=www.bufferbloat.net}}</ref> FQ-CoDel is published as RFC8290. It is written by T. Hoeiland-Joergensen, P. McKenney, D. Täht, J. Gettys, and E. Dumazet, all members of the "bufferbloat project".{{Ref RFC|8290}}

Common Applications Kept Enhanced (CAKE; sch_cake in Linux code) is a combined traffic shaper and AQM algorithm presented by the bufferbloat project in 2018. It builds on the experience of using fq_codel with the HTB (Hierarchy Token Bucket) ]. It improves over the Linux htb+fq_codel implementation by reducing hash collisions between flows, reducing CPU utilization in traffic shaping, and in a few other ways.<ref>{{cite web |title=Cake - Bufferbloat.net |url=https://www.bufferbloat.net/projects/codel/Cake/ |website=www.bufferbloat.net}}</ref>

In 2022, Dave Täht reviewed the state of fq_codel and sch_cake implementations in the wild. He found that while many systems have switched to either as the default AQM, several implementations have dubious deviations from the standard. For example, Apple's implementation of fq_codel (default in iOS) has a very large number of users but no "codel" component. Täht also notes the general lack of hardware offloading, made more important by the increase in network traffic brought by the ].<ref>{{cite web |author=Dave Täht|title=The state of fq_codel and sch_cake worldwide |date=April 23, 2022|url=http://blog.cerowrt.org/post/state_of_fq_codel/ |website=CeroWRT}}</ref>


== See also == == See also ==
Line 94: Line 68:


== References == == References ==

{{Reflist|30em}}
{{refs}}


== External links == == External links ==

* *
*
*
* *


] ]
] ]
]

Latest revision as of 15:43, 17 August 2024

Queue management algorithm for computer network packets For an official visit abroad taken by a member or members of the United States Congress, see Congressional delegation.

CoDel (Controlled Delay; pronounced "coddle") is an active queue management (AQM) algorithm in network routing, developed by Van Jacobson and Kathleen Nichols and published as RFC8289. It is designed to overcome bufferbloat in networking hardware, such as routers, by setting limits on the delay network packets experience as they pass through buffers in this equipment. CoDel aims to improve on the overall performance of the random early detection (RED) algorithm by addressing some of its fundamental misconceptions, as perceived by Jacobson, and by being easier to manage.

In 2012, an implementation of CoDel was written by Dave Täht and Eric Dumazet for the Linux kernel and dual licensed under the GNU General Public License and the 3-clause BSD license. Dumazet's improvement on CoDel is called FQ-CoDel, standing for "Fair/Flow Queue CoDel"; it was first adopted as the standard AQM and packet scheduling solution in 2014 in the OpenWrt 14.07 release called "Barrier Breaker". From there, CoDel and FQ-CoDel have migrated into various downstream projects such as Tomato, dd-wrt, OPNsense and Ubiquiti's "Smart Queues" feature.

Theory

CoDel is based on observations of packet behavior in packet-switched networks under the influence of data buffers. 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.

Bufferbloat

Main article: Bufferbloat

The flow of packets slows down while traveling through a network link between a fast and a slow network, especially at the start of a TCP session, when there is a sudden burst of packets and the slower network may not be able to accept the burst quickly enough. Buffers exist to ease this problem by giving the fast network a place to store packets to be read by the slower network at its own pace. In other words, buffers act like shock absorbers to convert bursty arrivals into smooth, steady departures. However, a buffer has limited capacity. 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.

The TCP congestion control algorithm relies on packet drops to determine the available bandwidth between two communicating devices. 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 as it finds equilibrium at the speed of the link. For this to work, the packet drops must occur in a timely manner so that the algorithm can responsively select a suitable transfer speed. With packets held in an overly-large buffer, the packets will arrive at their destination but with a higher latency but no packets are dropped so TCP does not slow down. Under these conditions, TCP may even decide that the path of the connection has changed and repeat the search for a new equilibrium.

Having a big and constantly full buffer that causes increased transmission delays and reduced interactivity, especially when looking at two or more simultaneous transmissions over the same channel, is called bufferbloat. Available channel bandwidth can also end up being unused, as some fast destinations may not be reached due to buffers being clogged with data awaiting delivery to slow destinations.

Good and bad queues

CoDel distinguishes between two types of queue: A good queue is one that exhibits no bufferbloat. Communication bursts cause no more than a temporary increase in queue delay. The network link utilization is maximized. A bad queue exhibits bufferbloat. Communication bursts cause 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 the form of an active queue management (AQM) algorithm must be able to recognize an occurrence of bufferbloat and react by deploying effective countermeasures.

Van Jacobson asserted in 2006 that existing algorithms have been using incorrect means of recognizing bufferbloat. Algorithms like RED measure the average queue length and consider it a case of bufferbloat if the average grows too large. Jacobson demonstrated in 2006 that this measurement is not a good metric, as the average queue length rises sharply in the case of a communications burst. The queue can then dissipate quickly (good queue) or become a standing queue (bad queue). Other factors in network traffic can also cause false positives or negatives, causing countermeasures to be deployed unnecessarily. Jacobson suggested that average queue length actually contains no information at all about packet demand or network load. He suggested that a better metric might be the minimum queue length during a sliding time window.

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 queue until the delay drops below the maximum level. Nichols and Jacobson cite several advantages to using nothing more than this metric:

  • CoDel is parameterless. One of the weaknesses in the RED algorithm (according to Jacobson) is that it is too difficult to configure, especially in an environment with dynamic link rates.
  • CoDel treats good queue and bad queue differently. A good queue has low delays by nature, so the management algorithm can ignore it, while a bad queue is subject to management intervention in the form of dropping packets.
  • CoDel works off of a parameter that is determined completely locally; It is independent of round-trip delays, link rates, traffic loads and other factors that 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.
  • The CoDel implementation is relatively simple 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 MTU's worth of bytes in the buffer). If these conditions do not hold, then CoDel drops packets probabilistically.

The algorithm is independently computed at each network hop. The algorithm operates over an interval, initially 100 milliseconds. Per-packet queuing delay is monitored through the hop. As each packet is dequeued for 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 the 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 100 {\displaystyle 100} , 100 2 {\displaystyle {100 \over {\sqrt {2}}}} , 100 3 {\displaystyle {100 \over {\sqrt {3}}}} , 100 4 {\displaystyle {100 \over {\sqrt {4}}}} , 100 5 {\displaystyle {100 \over {\sqrt {5}}}} ...

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:

  • 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). 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 utilization at lower bandwidth, degrading to fair utilization at high bandwidth.

Simulation was also performed by Greg White and Joey Padden at CableLabs.

Implementation

A full implementation of CoDel was realized in May 2012 and made available as open-source software. It was implemented within the Linux kernel (starting with the 3.5 mainline). Dave Täht back-ported CoDel to Linux kernel 3.3 for project CeroWrt, which concerns itself among other things with bufferbloat, where it was exhaustively tested. CoDel began to appear as an option in some proprietary/turnkey bandwidth management platforms in 2013. FreeBSD had CoDel integrated into the 11.x and 10.x code branches in 2016. An implementation is distributed with OpenBSD since version 6.2.

Derived algorithms

Fair/Flow Queue CoDel (FQ-CoDel; fq_codel in Linux code) adds flow queuing to CoDel so that it differentiates between multiple simultaneous connections and works fairly. It gives the first packet in each stream priority, so that small streams can start and finish quickly for better use of network resources. CoDel co-author Van Jacobson recommends the use of fq_codel over codel where it's available. FQ-CoDel is published as RFC8290. It is written by T. Hoeiland-Joergensen, P. McKenney, D. Täht, J. Gettys, and E. Dumazet, all members of the "bufferbloat project".

Common Applications Kept Enhanced (CAKE; sch_cake in Linux code) is a combined traffic shaper and AQM algorithm presented by the bufferbloat project in 2018. It builds on the experience of using fq_codel with the HTB (Hierarchy Token Bucket) traffic shaper. It improves over the Linux htb+fq_codel implementation by reducing hash collisions between flows, reducing CPU utilization in traffic shaping, and in a few other ways.

In 2022, Dave Täht reviewed the state of fq_codel and sch_cake implementations in the wild. He found that while many systems have switched to either as the default AQM, several implementations have dubious deviations from the standard. For example, Apple's implementation of fq_codel (default in iOS) has a very large number of users but no "codel" component. Täht also notes the general lack of hardware offloading, made more important by the increase in network traffic brought by the COVID-19 pandemic.

See also

References

  1. Nichols, K.; Jacobson, V.; McGregor, A.; Iyengar, J. (Jan 2018). Controlled Delay Active Queue Management. IETF. doi:10.17487/RFC8289. RFC 8289.
  2. Joe Brockmeier (2012-05-08). "Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution". ReadWriteWeb. Archived from the original on 2012-07-12. Retrieved 2012-08-16.
  3. ^ Nichols, Kathleen; Jacobson, Van (6 May 2012). "Controlling Queue Delay". ACM Queue. 55 (7). ACM Publishing: 42–50. doi:10.1145/2209249.2209264. S2CID 381738. Retrieved 12 August 2012.
  4. Jacobson, Van; Karels, MJ (1988). "Congestion avoidance and control" (PDF). ACM SIGCOMM Computer Communication Review. 18 (4): 314–329. doi:10.1145/52325.52356. Archived from the original (PDF) on 2004-06-22.
  5. ^ Jacobson, Van (2006). "A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA" (PDF). Retrieved 12 August 2012.
  6. Iljitsch van Beijnum (2012-05-10). "CoDel buffer management could solve the Internet's bufferbloat jams". Ars Technica. Retrieved 2012-08-16.
  7. Nichols, Kathleen (July 2012). "Controlled Delay (CoDel) Active Queue Management". Pollere Inc. Archived from the original on 22 August 2012. Retrieved 12 August 2012.
  8. Greg White; Joey Padden (November 2012). "Preliminary Study of Codel AGM in a Docsis Network" (PDF). cablelabs.com. Retrieved 2015-06-14.
  9. Gettys, Jim (22 May 2012). "A Milestone Reached: CoDel is in Linux!". jg's Ramblings. Retrieved 12 August 2012.
  10. "Cerowrt - Overview". Bufferbloat. Retrieved 2014-01-24.
  11. "Procera Packetlogic Changelog". proceranetworks.com. Archived from the original on 2013-07-24. Retrieved 2013-07-24.
  12. truckman (2016-05-26). "Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE)".
  13. truckman (2016-06-10). "MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE)".
  14. Al Saadi, Rasool; Armitage, Grenville. "Implementing AQM in FreeBSD".
  15. "OpenBSD 6.2". Retrieved 13 October 2017.
  16. "Benchmarking Codel and FQ Codel - Bufferbloat.net". www.bufferbloat.net.
  17. T. Høiland-Jørgensen; P. McKenney; J. Gettys; E. Dumazet (January 2018). The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm. Internet Engineering Task Force. doi:10.17487/RFC8290. ISSN 2070-1721. RFC 8290. Experimental.
  18. "Cake - Bufferbloat.net". www.bufferbloat.net.
  19. Dave Täht (April 23, 2022). "The state of fq_codel and sch_cake worldwide". CeroWRT.

External links

Categories: