288:, 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.
230:
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.
178:
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.
512:
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)
238:
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
229:
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
189:
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
500:
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
177:
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
197:
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
501:
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".
484:, 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
504:
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)
214:
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
246:
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
451:
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
250:
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
455:
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
264:
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
597:
194:
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.
513:
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
243:
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.
437:
406:
375:
344:
190:
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
509:. 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.
254:
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.
447:
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:
313:
210:
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
701:
775:
605:
17:
155:, others relate to weaknesses of alternative queue management algorithms. CoDel was developed as an attempt to address the problem of bufferbloat.
901:
260:
The CoDel implementation is relatively simple and therefore can span the spectrum from low-end home routers to high-end routing solutions.
239:
queue until the delay drops below the maximum level. Nichols and
Jacobson cite several advantages to using nothing more than this metric:
169:
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
1123:
824:
295:
of the number of successive intervals in which packets were dropped due to excessive queuing delay. The sequence of intervals is
1133:
88:(RED) algorithm by addressing some of its fundamental misconceptions, as perceived by Jacobson, and by being easier to manage.
119:
14.07 release called "Barrier
Breaker". From there, CoDel and FQ-CoDel have migrated into various downstream projects such as
173:
session, when there is a sudden burst of packets and the slower network may not be able to accept the burst quickly enough.
219:(AQM) algorithm must be able to recognize an occurrence of bufferbloat and react by deploying effective countermeasures.
225:
asserted in 2006 that existing algorithms have been using incorrect means of recognizing bufferbloat. Algorithms like
1108:
724:
855:
797:
269:'s worth of bytes in the buffer). If these conditions do not hold, then CoDel drops packets probabilistically.
198:
destinations may not be reached due to buffers being clogged with data awaiting delivery to slow destinations.
996:
411:
380:
349:
318:
170:
1128:
485:
909:
174:
100:
81:
266:
946:
931:
31:
526:
216:
144:
49:
226:
182:
85:
480:(starting with the 3.5 mainline). Dave Täht back-ported CoDel to Linux kernel 3.3 for project
186:
30:
For an official visit abroad taken by a member or members of the United States
Congress, see
151:. Some of these observations are about the fundamental nature of queueing and the causes of
1043:
579:
473:
104:
8:
1013:
298:
69:
675:
257:
CoDel adapts to dynamically changing link rates with no negative impact on utilization.
73:
1035:
514:
285:
120:
112:
111:, standing for "Fair/Flow Queue CoDel"; it was first adopted as the standard AQM and
1063:
1025:
716:
667:
647:
569:
551:
273:
61:
1082:
679:
191:
53:
1046:
1015:
1014:
Toke Høiland-Jørgensen; Paul McKenney; Jim Gettys; Eric
Dumazet (January 2018).
750:
582:
559:
506:
77:
880:
472:
A full implementation of CoDel was realized in May 2012 and made available as
1117:
1103:
1039:
655:
291:
When the interval is shortened, it is done so in accordance with the inverse
281:
671:
1017:
The Flow Queue CoDel Packet
Scheduler and Active Queue Management Algorithm
746:
651:
601:
555:
477:
222:
96:
84:
in this equipment. CoDel aims to improve on the overall performance of the
57:
92:
947:"MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE)"
292:
164:
152:
148:
65:
720:
45:
961:
851:
751:"A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA"
598:"Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution"
531:
1030:
932:"Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE)"
776:"CoDel buffer management could solve the Internet's bufferbloat jams"
574:
461:
801:
132:
128:
108:
975:
489:
481:
116:
460:
Simulation was also performed by Greg White and Joey Padden at
124:
550:
894:
284:
is monitored through the hop. As each packet is dequeued for
185:
algorithm relies on packet drops to determine the available
1021:
565:
272:
The algorithm is independently computed at each network
27:
Queue management algorithm for computer network packets
822:
414:
383:
352:
321:
301:
143:
CoDel is based on observations of packet behavior in
64:
and published as RFC8289. It is designed to overcome
825:"Preliminary Study of Codel AGM in a Docsis Network"
773:
997:"Benchmarking Codel and FQ Codel - Bufferbloat.net"
91:In 2012, an implementation of CoDel was written by
798:"Controlled Delay (CoDel) Active Queue Management"
699:
431:
400:
369:
338:
307:
206:CoDel distinguishes between two types of queue: A
1115:
741:
739:
737:
646:
488:in 2016. An implementation is distributed with
1083:"The state of fq_codel and sch_cake worldwide"
595:
642:
959:
734:
640:
638:
636:
634:
632:
630:
628:
626:
624:
622:
107:. Dumazet's improvement on CoDel is called
844:
544:
1080:
1029:
856:"A Milestone Reached: CoDel is in Linux!"
823:Greg White; Joey Padden (November 2012).
789:
709:ACM SIGCOMM Computer Communication Review
619:
573:
280:, initially 100 milliseconds. Per-packet
1109:Fundamental Progress Solving Bufferbloat
944:
929:
745:
561:Controlled Delay Active Queue Management
558:; McGregor, A.; Iyengar, J. (Jan 2018).
1007:
960:Al Saadi, Rasool; Armitage, Grenville.
795:
432:{\displaystyle {100 \over {\sqrt {5}}}}
401:{\displaystyle {100 \over {\sqrt {4}}}}
370:{\displaystyle {100 \over {\sqrt {3}}}}
339:{\displaystyle {100 \over {\sqrt {2}}}}
14:
1116:
850:
201:
495:
442:
774:Iljitsch van Beijnum (2012-05-10).
24:
702:"Congestion avoidance and control"
700:Jacobson, Van; Karels, MJ (1988).
25:
1145:
1097:
467:
276:. The algorithm operates over an
76:, by setting limits on the delay
18:CAKE (queue management algorithm)
1124:Packets (information technology)
476:. It was implemented within the
80:experience as they pass through
1074:
1056:
989:
968:
953:
938:
923:
902:"Procera Packetlogic Changelog"
873:
796:Nichols, Kathleen (July 2012).
816:
767:
693:
589:
158:
13:
1:
1134:Network scheduling algorithms
962:"Implementing AQM in FreeBSD"
800:. Pollere Inc. Archived from
596:Joe Brockmeier (2012-05-08).
537:
1081:Dave Täht (April 23, 2022).
666:(7). ACM Publishing: 42–50.
233:
99:and dual licensed under the
7:
520:
135:'s "Smart Queues" feature.
10:
1150:
162:
101:GNU General Public License
29:
656:"Controlling Queue Delay"
138:
95:and Eric Dumazet for the
1064:"Cake - Bufferbloat.net"
145:packet-switched networks
115:solution in 2014 in the
32:Congressional delegation
945:truckman (2016-06-10).
930:truckman (2016-05-26).
672:10.1145/2209249.2209264
527:Sliding window protocol
217:active queue management
147:under the influence of
50:active queue management
433:
402:
371:
340:
309:
183:TCP congestion control
86:random early detection
434:
403:
372:
341:
310:
881:"Cerowrt - Overview"
474:open-source software
412:
381:
350:
319:
299:
105:3-clause BSD license
1129:Network performance
1068:www.bufferbloat.net
1001:www.bufferbloat.net
906:proceranetworks.com
721:10.1145/52325.52356
492:since version 6.2.
308:{\displaystyle 100}
202:Good and bad queues
70:networking hardware
52:(AQM) algorithm in
496:Derived algorithms
443:Simulation results
429:
398:
367:
336:
305:
804:on 22 August 2012
648:Nichols, Kathleen
515:COVID-19 pandemic
427:
425:
396:
394:
365:
363:
334:
332:
113:packet scheduling
16:(Redirected from
1141:
1104:CoDel pseudocode
1091:
1090:
1078:
1072:
1071:
1060:
1054:
1050:
1033:
1031:10.17487/RFC8290
1011:
1005:
1004:
993:
987:
986:
984:
982:
972:
966:
965:
957:
951:
950:
942:
936:
935:
927:
921:
920:
918:
917:
908:. Archived from
898:
892:
891:
889:
888:
877:
871:
870:
868:
866:
848:
842:
841:
839:
838:
829:
820:
814:
813:
811:
809:
793:
787:
786:
784:
783:
771:
765:
764:
762:
760:
755:
743:
732:
731:
729:
723:. Archived from
706:
697:
691:
690:
688:
686:
644:
617:
616:
614:
613:
604:. Archived from
593:
587:
586:
577:
575:10.17487/RFC8289
548:
438:
436:
435:
430:
428:
426:
421:
416:
407:
405:
404:
399:
397:
395:
390:
385:
376:
374:
373:
368:
366:
364:
359:
354:
345:
343:
342:
337:
335:
333:
328:
323:
314:
312:
311:
306:
62:Kathleen Nichols
42:Controlled Delay
21:
1149:
1148:
1144:
1143:
1142:
1140:
1139:
1138:
1114:
1113:
1100:
1095:
1094:
1079:
1075:
1062:
1061:
1057:
1012:
1008:
995:
994:
990:
980:
978:
974:
973:
969:
958:
954:
943:
939:
928:
924:
915:
913:
900:
899:
895:
886:
884:
879:
878:
874:
864:
862:
854:(22 May 2012).
849:
845:
836:
834:
827:
821:
817:
807:
805:
794:
790:
781:
779:
772:
768:
758:
756:
753:
744:
735:
727:
704:
698:
694:
684:
682:
645:
620:
611:
609:
594:
590:
549:
545:
540:
523:
498:
470:
445:
420:
415:
413:
410:
409:
389:
384:
382:
379:
378:
358:
353:
351:
348:
347:
327:
322:
320:
317:
316:
300:
297:
296:
236:
204:
167:
161:
141:
78:network packets
56:, developed by
54:network routing
35:
28:
23:
22:
15:
12:
11:
5:
1147:
1137:
1136:
1131:
1126:
1112:
1111:
1106:
1099:
1098:External links
1096:
1093:
1092:
1073:
1055:
1006:
988:
967:
952:
937:
922:
893:
872:
860:jg's Ramblings
843:
815:
788:
778:. Ars Technica
766:
733:
730:on 2004-06-22.
715:(4): 314–329.
692:
654:(6 May 2012).
618:
588:
542:
541:
539:
536:
535:
534:
529:
522:
519:
507:traffic shaper
497:
494:
469:
468:Implementation
466:
458:
457:
453:
444:
441:
424:
419:
393:
388:
362:
357:
331:
326:
304:
262:
261:
258:
255:
252:
248:
244:
235:
232:
203:
200:
163:Main article:
160:
157:
140:
137:
44:; pronounced "
26:
9:
6:
4:
3:
2:
1146:
1135:
1132:
1130:
1127:
1125:
1122:
1121:
1119:
1110:
1107:
1105:
1102:
1101:
1088:
1084:
1077:
1069:
1065:
1059:
1053:
1052:Experimental.
1048:
1045:
1041:
1037:
1032:
1027:
1023:
1019:
1018:
1010:
1002:
998:
992:
977:
976:"OpenBSD 6.2"
971:
963:
956:
948:
941:
933:
926:
912:on 2013-07-24
911:
907:
903:
897:
883:. Bufferbloat
882:
876:
861:
857:
853:
847:
833:
832:cablelabs.com
826:
819:
803:
799:
792:
777:
770:
752:
748:
747:Jacobson, Van
742:
740:
738:
726:
722:
718:
714:
710:
703:
696:
681:
677:
673:
669:
665:
661:
657:
653:
652:Jacobson, Van
649:
643:
641:
639:
637:
635:
633:
631:
629:
627:
625:
623:
608:on 2012-07-12
607:
603:
599:
592:
584:
581:
576:
571:
567:
563:
562:
557:
553:
547:
543:
533:
530:
528:
525:
524:
518:
516:
510:
508:
502:
493:
491:
487:
486:code branches
483:
479:
475:
465:
463:
454:
450:
449:
448:
440:
422:
417:
391:
386:
360:
355:
329:
324:
302:
294:
289:
287:
283:
282:queuing delay
279:
275:
270:
268:
259:
256:
253:
249:
245:
242:
241:
240:
231:
228:
224:
220:
218:
213:
209:
199:
195:
193:
188:
184:
179:
176:
172:
166:
156:
154:
150:
146:
136:
134:
130:
126:
122:
118:
114:
110:
106:
102:
98:
94:
89:
87:
83:
79:
75:
71:
67:
63:
59:
55:
51:
47:
43:
39:
33:
19:
1086:
1076:
1067:
1058:
1051:
1016:
1009:
1000:
991:
979:. Retrieved
970:
955:
940:
925:
914:. Retrieved
910:the original
905:
896:
885:. Retrieved
875:
863:. Retrieved
859:
846:
835:. Retrieved
831:
818:
806:. Retrieved
802:the original
791:
780:. Retrieved
769:
757:. Retrieved
725:the original
712:
708:
695:
683:. Retrieved
663:
659:
610:. Retrieved
606:the original
602:ReadWriteWeb
591:
560:
556:Jacobson, V.
546:
511:
503:
499:
478:Linux kernel
471:
459:
446:
290:
277:
271:
263:
237:
223:Van Jacobson
221:
211:
207:
205:
196:
180:
168:
149:data buffers
142:
97:Linux kernel
90:
58:Van Jacobson
41:
37:
36:
852:Gettys, Jim
552:Nichols, K.
293:square root
165:Bufferbloat
159:Bufferbloat
153:bufferbloat
66:bufferbloat
1118:Categories
981:13 October
916:2013-07-24
887:2014-01-24
837:2015-06-14
782:2012-08-16
612:2012-08-16
538:References
532:TCP tuning
456:bandwidth.
452:bandwidth.
286:forwarding
208:good queue
72:, such as
1040:2070-1721
865:12 August
808:12 August
759:12 August
685:12 August
660:ACM Queue
462:CableLabs
234:Algorithm
212:bad queue
187:bandwidth
93:Dave Täht
48:") is an
749:(2006).
521:See also
278:interval
247:packets.
133:Ubiquiti
129:OPNsense
109:FQ-CoDel
103:and the
1087:CeroWRT
490:OpenBSD
482:CeroWrt
251:buffer.
192:latency
175:Buffers
117:OpenWrt
82:buffers
74:routers
1038:
680:381738
678:
139:Theory
125:dd-wrt
121:Tomato
46:coddle
828:(PDF)
754:(PDF)
728:(PDF)
705:(PDF)
676:S2CID
38:CoDel
1047:8290
1036:ISSN
1022:IETF
983:2017
867:2012
810:2012
761:2012
687:2012
583:8289
566:IETF
439:...
181:The
131:and
60:and
1044:RFC
1026:doi
717:doi
668:doi
580:RFC
570:doi
418:100
387:100
356:100
325:100
303:100
274:hop
267:MTU
227:RED
171:TCP
68:in
1120::
1085:.
1066:.
1042:.
1034:.
1024:.
1020:.
999:.
904:.
858:.
830:.
736:^
713:18
711:.
707:.
674:.
664:55
662:.
658:.
650:;
621:^
600:.
578:.
568:.
564:.
554:;
517:.
464:.
408:,
377:,
346:,
315:,
127:,
123:,
1089:.
1070:.
1049:.
1028::
1003:.
985:.
964:.
949:.
934:.
919:.
890:.
869:.
840:.
812:.
785:.
763:.
719::
689:.
670::
615:.
585:.
572::
423:5
392:4
361:3
330:2
40:(
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.