Mostra la font per a CoDel

'''CoDel''' (''Controlled Delay''; pronunciat "[[wiktionary:coddle|coddle]]") és un algorisme de [[gestió activa de cues]] (AQM) en [[Encaminament|l'encaminament de la xarxa]], desenvolupat per [[Van Jacobson]] i [[Kathleen Nichols]] i publicat com a RFC8289.  Està dissenyat per superar [[Bufferbloat|el bufferbloat]] en [[Maquinari de xarxa|el maquinari de xarxa]], com ara [[Encaminador|els encaminadors]], establint límits a l'experiència de retard [[Paquet de xarxa|dels paquets de xarxa]] a mesura que passen a través dels [[Memòria intermèdia|buffers]] d'aquest equip. CoDel té com a objectiu millorar el rendiment general de l'algoritme de [[detecció precoç aleatòria]] (RED) abordant alguns dels seus conceptes erronis fonamentals, tal com els percep Jacobson, i sent més fàcil de gestionar.

El 2012, [[Dave Täht]] i Eric Dumazet van escriure una implementació de CoDel per al [[Linux (nucli)|nucli de Linux]] i amb llicència dual sota la [[GNU General Public License|llicència pública general de GNU]] i la [[Llicència BSD|llicència BSD de 3 clàusules]]. La millora de Dumazet a CoDel s'anomena [[FQ-CoDel]], que significa "Fair/Flow Queue CoDel"; es va adoptar per primera vegada com a solució estàndard de [[planificador|programació de paquets]] i AQM l'any 2014 a la versió [[OpenWrt]] 14.07 anomenada "Barrier Breaker". A partir d'aquí, CoDel i FQ-CoDel han migrat a diversos projectes aigües avall, com ara [[Tomato]], [[DD-WRT|dd-wrt]], [[OPNsense]] i la funció "Smart Queues" d'[[Ubiquiti]].

== Teoria ==
CoDel es basa en observacions del comportament dels paquets en [[Commutació de paquets|xarxes de commutació de paquets]] sota la influència dels [[Memòria intermèdia|buffers de dades]]. Algunes d'aquestes observacions es refereixen a la naturalesa fonamental de les cues i les causes del [[bufferbloat]], d'altres es relacionen amb les debilitats dels algorismes alternatius de gestió de cues. CoDel es va desenvolupar com un intent d'abordar el problema del bufferbloat.<ref>{{Ref-web|url=http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php|títol=Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution|editor=[[ReadWriteWeb]]|cognom=Joe Brockmeier|data=2012-05-08|consulta=2012-08-16|arxiuurl=https://web.archive.org/web/20120712012901/http://www.readwriteweb.com/enterprise/2012/05/good-news-for-solving-bufferbloat-codel-provides-no-knobs-solution.php|arxiudata=2012-07-12|llengua=anglès}}</ref>

=== Bufferbloat ===
El flux de paquets s'alenteix mentre es viatja a través d'un enllaç de xarxa entre una xarxa ràpida i una lenta, especialment a l'inici d'una sessió [[Transmission Control Protocol|TCP]], quan hi ha una explosió sobtada de paquets i és possible que la xarxa més lenta no pugui acceptar la ràfega ràpidament. prou. Existeixen [[Memòria intermèdia|búfers]] per alleujar aquest problema donant a la xarxa ràpida un lloc on emmagatzemar paquets per ser llegits per la xarxa més lenta al seu propi ritme.<ref name="CoDel_ACMQ">{{Ref-publicació|url=http://queue.acm.org/detail.cfm?id=2209336|enllaçautor=Kathleen Nichols|cognom=Nichols|nom=Kathleen|enllaçautor2=Van Jacobson|cognom2=Jacobson|nom2=Van|data=6 May 2012|publicació=ACM Queue|volum=55|exemplar=7|pàgines=42–50|consulta=12 August 2012|doi=10.1145/2209249.2209264}}</ref> En altres paraules, els amortidors actuen com a amortidors per convertir les arribades explosives en sortides suaus i constants. Tanmateix, un buffer té una capacitat limitada. La memòria intermèdia ideal té la mida de manera que pugui gestionar una ràfega sobtada de comunicació i fer coincidir la velocitat d'aquesta ràfega amb la velocitat de la xarxa més lenta. Idealment, la situació d'absorció de xocs es caracteritza per un retard temporal dels paquets a la memòria intermèdia durant la ràfega de transmissió, després del qual el retard desapareix ràpidament i la xarxa arriba a un equilibri en l'oferta i el maneig de paquets.<ref name="CoDel_ACMQ" />

L'algoritme [[Control de congestió TCP|de control de congestió TCP]] es basa en les caigudes de paquets per determinar l'[[Amplada de banda (informàtica)|amplada de banda]] disponible entre dos dispositius que es comuniquen. Accelera la transferència de dades fins que els paquets comencen a caure i, a continuació, alenteix la velocitat de transmissió. L'ideal és que segueixi accelerant i alentint-se a mesura que troba l'equilibri a la velocitat de l'enllaç. Perquè això funcioni, les caigudes de paquets s'han de produir de manera oportuna perquè l'algoritme pugui seleccionar de manera sensible una velocitat de transferència adequada. Amb els paquets guardats en una memòria intermèdia massa gran, els paquets arribaran a la seva destinació, però amb una [[Retard de xarxa|latència]] més alta, però no es deixa caure paquets perquè el TCP no s'alentiri. En aquestes condicions, TCP fins i tot pot decidir que el camí de la connexió ha canviat i repetir la recerca d'un nou equilibri.<ref>{{Ref-publicació|url=http://www.cord.edu/faculty/zhang/cs345/assignments/researchPapers/congavoid.pdf|publicació=ACM SIGCOMM Computer Communication Review|cognom=Jacobson|nom=Van|cognom2=Karels, MJ|any=1988|volum=18|exemplar=4|pàgines=314–329|doi=10.1145/52325.52356}}</ref><ref name="Rant_Jacobson">{{Ref-web|url=http://www.pollere.net/Pdfdocs/QrantJul06.pdf|títol=A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA|cognom=Jacobson|nom=Van|consulta=12 August 2012|llengua=anglès}}</ref>

Tenir un buffer gran i constantment ple que provoca un augment dels retards de transmissió i una interactivitat reduïda, especialment quan es veuen dues o més transmissions simultànies pel mateix canal, s'anomena bufferbloat. L'amplada de banda del canal disponible també pot acabar sense utilitzar-se, ja que és possible que no s'arribi a algunes destinacions ràpides a causa que els buffers estan obstruïts amb dades pendents de lliurament a destinacions lentes.

=== Cues bones i dolentes ===
CoDel distingeix entre dos tipus de cua: <ref name="CoDel_ACMQ2">{{Ref-publicació|url=http://queue.acm.org/detail.cfm?id=2209336|enllaçautor=Kathleen Nichols|cognom=Nichols|nom=Kathleen|enllaçautor2=Van Jacobson|cognom2=Jacobson|nom2=Van|data=6 May 2012|publicació=ACM Queue|volum=55|exemplar=7|pàgines=42–50|consulta=12 August 2012|doi=10.1145/2209249.2209264}}</ref><ref>{{Ref-web|url=https://arstechnica.com/information-technology/2012/05/codel-buffer-management-could-solve-the-internets-bufferbloat-jams/|títol=CoDel buffer management could solve the Internet's bufferbloat jams|editor=Ars Technica|data=2012-05-10|cognom=Iljitsch van Beijnum|consulta=2012-08-16|llengua=anglès}}</ref> Una ''bona cua'' és aquella que no presenta cap bufferbloat. Les ràfegues de comunicació no provoquen més que un augment temporal del retard de la cua. La utilització de l'enllaç de xarxa es maximitza. Una ''mala cua'' mostra un bufferbloat. Les ràfegues de comunicació fan que la memòria intermèdia s'ompli i es mantingui omplerta, donant lloc a una baixa utilització i un retard constant de la memòria intermèdia. Per ser eficaç contra bufferbloat, una solució en forma d'algorisme de [[gestió activa de cues]] (AQM) ha de ser capaç de reconèixer l'ocurrència de bufferbloat i reaccionar mitjançant la implementació de contramesures efectives.

[[Van Jacobson]] va afirmar l'any 2006 que els algorismes existents han estat utilitzant mitjans incorrectes per reconèixer el bufferbloat.<ref name="Rant_Jacobson2">{{Ref-web|url=http://www.pollere.net/Pdfdocs/QrantJul06.pdf|títol=A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA|cognom=Jacobson|nom=Van|consulta=12 August 2012|llengua=anglès}}</ref> Algorismes com [[Detecció precoç aleatòria|RED]] mesuren la longitud mitjana de la cua i ho consideren un cas de bufferbloat si la mitjana creix massa. Jacobson va demostrar el 2006 que aquesta mesura no és una bona mètrica, ja que la longitud mitjana de la cua augmenta bruscament en el cas d'una ràfega de comunicacions. Aleshores, la cua es pot dissipar ràpidament (cua bona) o convertir-se en una cua permanent (cua dolenta). Altres factors en el trànsit de la xarxa també poden provocar falsos positius o negatius, fent que les contramesures es desplegaran innecessàriament. Jacobson va suggerir que la longitud mitjana de la cua en realitat no conté cap informació sobre la demanda de paquets o la càrrega de la xarxa.<ref name="CoDel_ACMQ3">{{Ref-publicació|url=http://queue.acm.org/detail.cfm?id=2209336|enllaçautor=Kathleen Nichols|cognom=Nichols|nom=Kathleen|enllaçautor2=Van Jacobson|cognom2=Jacobson|nom2=Van|data=6 May 2012|publicació=ACM Queue|volum=55|exemplar=7|pàgines=42–50|consulta=12 August 2012|doi=10.1145/2209249.2209264}}</ref><ref name="Rant_Jacobson2" /> Va suggerir que una mètrica millor podria ser la longitud mínima de la cua durant una finestra de temps lliscant.<ref name="CoDel_ACMQ3" />

== Algorisme ==
Basant-se en la idea de Jacobson del 2006, CoDel es va desenvolupar per gestionar les cues sota control del retard mínim experimentat pels paquets a la finestra de memòria intermèdia en execució. L'objectiu és mantenir aquest retard mínim per sota dels 5 mil·lisegons. Si el retard mínim augmenta a un valor massa alt, els paquets s'eliminen de la cua fins que el retard cau per sota del nivell màxim.<ref name="CoDel_ACMQ4">{{Ref-publicació|url=http://queue.acm.org/detail.cfm?id=2209336|enllaçautor=Kathleen Nichols|cognom=Nichols|nom=Kathleen|enllaçautor2=Van Jacobson|cognom2=Jacobson|nom2=Van|data=6 May 2012|publicació=ACM Queue|volum=55|exemplar=7|pàgines=42–50|consulta=12 August 2012|doi=10.1145/2209249.2209264}}</ref> Nichols i Jacobson citen diversos avantatges d'utilitzar res més que aquesta mètrica: <ref name="CoDel_ACMQ4" />

* CoDel no té paràmetres. Una de les debilitats de l'algorisme RED (segons Jacobson) és que és massa difícil de configurar, sobretot en un entorn amb velocitats d'enllaç dinàmics.
* CoDel tracta la cua bona i la cua dolenta de manera diferent. Una bona cua té retards baixos per naturalesa, de manera que l'algoritme de gestió pot ignorar-la, mentre que una mala cua està subjecta a una intervenció de gestió en forma de caiguda de paquets.
* CoDel funciona a partir d'un paràmetre que es determina completament localment; És independent dels retards d'anada i tornada, les taxes d'enllaç, les càrregues de trànsit i altres factors que no es poden controlar ni predir pel buffer local.
* El retard mínim local només es pot determinar quan un paquet surt de la memòria intermèdia, de manera que no cal cap retard addicional per executar la cua per recopilar estadístiques per gestionar la cua.
* CoDel s'adapta a les taxes d'enllaç que canvien dinàmicament sense cap impacte negatiu en la utilització.
* La implementació de CoDel és relativament senzilla i, per tant, pot abastar l'espectre des d'encaminadors domèstics de gamma baixa fins a solucions d'encaminament de gamma alta.


CoDel no fa res per gestionar la memòria intermèdia si el retard mínim per a la finestra de memòria intermèdia està per sota del valor màxim permès. Tampoc no fa res si la memòria intermèdia està relativament buida (si hi ha menys d'un [[Unitat de transmissió màxima|MTU]] de bytes a la memòria intermèdia).<ref name="CoDel_ACMQ5">{{Ref-publicació|url=http://queue.acm.org/detail.cfm?id=2209336|enllaçautor=Kathleen Nichols|cognom=Nichols|nom=Kathleen|enllaçautor2=Van Jacobson|cognom2=Jacobson|nom2=Van|data=6 May 2012|publicació=ACM Queue|volum=55|exemplar=7|pàgines=42–50|consulta=12 August 2012|doi=10.1145/2209249.2209264}}</ref> Si aquestes condicions no es compleixen, llavors CoDel deixa caure els paquets probabilísticament.<ref name="CoDel_ACMQ5" />

L'algorisme es calcula de manera independent a cada [[Hop (xarxes)|salt]] de xarxa. L'algorisme funciona durant un ''interval'', inicialment 100 mil·lisegons. [[Queuing delay|El retard de la cua]] per paquet es controla a través del salt. A mesura que cada paquet es retira de la cua per [[Packet forwarding|al reenviament]], es calcula el retard de la cua (quantitat de temps que el paquet ha passat esperant a la cua). S'emmagatzema el retard de cua més baix per a l'interval. Quan l'últim paquet de l'interval es retira de la cua, si el retard de cua més baix per a l'interval és superior a 5 mil·lisegons, aquest paquet únic s'elimina i l'interval utilitzat per al següent grup de paquets s'escurça. Si el retard de cua més baix per a l'interval és inferior a 5 mil·lisegons, el paquet es reenvia i l'interval es restableix a 100 mil·lisegons.

Quan s'escurça l'interval, es fa d'acord amb l'[[arrel quadrada]] inversa del nombre d'intervals successius en què els paquets s'han deixat caure a causa d'un retard excessiu en la cua. La seqüència d'intervals és <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>...

== Implementació ==
El maig de 2012 es va realitzar una implementació completa de CoDel i es va posar a disposició com a [[programari de codi obert]].<ref name="CoDel_ACMQ6">{{Ref-publicació|url=http://queue.acm.org/detail.cfm?id=2209336|enllaçautor=Kathleen Nichols|cognom=Nichols|nom=Kathleen|enllaçautor2=Van Jacobson|cognom2=Jacobson|nom2=Van|data=6 May 2012|publicació=ACM Queue|volum=55|exemplar=7|pàgines=42–50|consulta=12 August 2012|doi=10.1145/2209249.2209264}}</ref> Es va implementar dins del [[Linux (nucli)|nucli Linux]] (començant amb la línia principal 3.5).<ref name="CoDel_Linux">{{Ref-web|url=http://gettys.wordpress.com/2012/05/22/a-milestone-reached-codel-is-in-linux/|títol=A Milestone Reached: CoDel is in Linux!|cognom=Gettys|nom=Jim|data=22 May 2012|obra=jg's Ramblings|consulta=12 August 2012}}</ref> Dave Täht va portar enrere CoDel al nucli Linux 3.3 per al projecte [[OpenWrt|CeroWrt]], que es preocupa entre altres coses de bufferbloat, <ref>{{Ref-web|url=http://www.bufferbloat.net/projects/cerowrt|títol=Cerowrt - Overview|editor=Bufferbloat|consulta=2014-01-24}}</ref> on es va provar exhaustivament. CoDel va començar a aparèixer com una opció en algunes plataformes de gestió d'ample de banda propietàries/clau en mà el 2013.<ref name="Procera_PacketLogic_Changelog">{{Ref-web|url=http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt|títol=Procera Packetlogic Changelog|obra=proceranetworks.com|consulta=2013-07-24|arxiuurl=https://archive.today/20130724211528/http://download.proceranetworks.com/client-bin/14.0/11/changelog.txt|arxiudata=2013-07-24}}</ref> FreeBSD tenia CoDel integrat a les [[branca de control de versions|branques de codi]] 11.x <ref>{{Ref-web|url=https://svnweb.freebsd.org/base?view=revision&revision=300779|títol=Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).|data=2016-05-26|cognom=truckman}}</ref> i 10.x <ref>{{Ref-web|url=https://svnweb.freebsd.org/base?view=revision&revision=301772|títol=MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).|data=2016-06-10|cognom=truckman}}</ref> el 2016.<ref>{{Ref-web|url=http://caia.swin.edu.au/freebsd/aqm/|títol=Implementing AQM in FreeBSD|nom=Rasool|cognom=Al Saadi}}</ref> Una implementació es distribueix amb [[OpenBSD]] des de la versió 6.2.<ref>{{Ref-web|url=https://www.openbsd.org/62.html|consulta=13 October 2017|títol=OpenBSD 6.2}}</ref>


== Referències ==
{{Referències}}

[[Categoria:Xarxes informàtiques]]