CoDel

CoDel (Controlled Delay; pronunciat "coddle") és un algorisme de gestió activa de cues (AQM) en l'encaminament de la xarxa, desenvolupat per Van Jacobson i Kathleen Nichols i publicat com a RFC8289. Està dissenyat per superar el bufferbloat en el maquinari de xarxa, com ara els encaminadors, establint límits a l'experiència de retard dels paquets de xarxa a mesura que passen a través dels 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 nucli de Linux i amb llicència dual sota la llicència pública general de GNU i la 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 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, OPNsense i la funció "Smart Queues" d'Ubiquiti.

Teoria

CoDel es basa en observacions del comportament dels paquets en xarxes de commutació de paquets sota la influència dels 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.[1]

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ó 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 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.[2] 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.[2]

L'algoritme de control de congestió TCP es basa en les caigudes de paquets per determinar l'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 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.[3][4]

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: [5][6] 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.[7] Algorismes com 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.[8][7] Va suggerir que una mètrica millor podria ser la longitud mínima de la cua durant una finestra de temps lliscant.[8]

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.[9] Nichols i Jacobson citen diversos avantatges d'utilitzar res més que aquesta mètrica: [9]

  • 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 MTU de bytes a la memòria intermèdia).[10] Si aquestes condicions no es compleixen, llavors CoDel deixa caure els paquets probabilísticament.[10]

L'algorisme es calcula de manera independent a cada salt de xarxa. L'algorisme funciona durant un interval, inicialment 100 mil·lisegons. 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 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 , , , , ...

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.[11] Es va implementar dins del nucli Linux (començant amb la línia principal 3.5).[12] Dave Täht va portar enrere CoDel al nucli Linux 3.3 per al projecte CeroWrt, que es preocupa entre altres coses de bufferbloat, [13] 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.[14] FreeBSD tenia CoDel integrat a les branques de codi 11.x [15] i 10.x [16] el 2016.[17] Una implementació es distribueix amb OpenBSD des de la versió 6.2.[18]


Referències

  1. ↑ Joe Brockmeier. «Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution» (en anglès). ReadWriteWeb, 08-05-2012. Arxivat de l'original el 2012-07-12. [Consulta: 16 agost 2012].
  2. ↑ 2,0 2,1 Nichols, Kathleen; Jacobson, Van ACM Queue, 55, 7, 06-05-2012, pàg. 42–50. DOI: 10.1145/2209249.2209264 [Consulta: 12 agost 2012].
  3. ↑ Jacobson, Van; Karels, MJ ACM SIGCOMM Computer Communication Review, 18, 4, 1988, pàg. 314–329. DOI: 10.1145/52325.52356.
  4. ↑ Jacobson, Van. «A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA» (en anglès). [Consulta: 12 agost 2012].
  5. ↑ Nichols, Kathleen; Jacobson, Van ACM Queue, 55, 7, 06-05-2012, pàg. 42–50. DOI: 10.1145/2209249.2209264 [Consulta: 12 agost 2012].
  6. ↑ Iljitsch van Beijnum. «CoDel buffer management could solve the Internet's bufferbloat jams» (en anglès). Ars Technica, 10-05-2012. [Consulta: 16 agost 2012].
  7. ↑ 7,0 7,1 Jacobson, Van. «A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA» (en anglès). [Consulta: 12 agost 2012].
  8. ↑ 8,0 8,1 Nichols, Kathleen; Jacobson, Van ACM Queue, 55, 7, 06-05-2012, pàg. 42–50. DOI: 10.1145/2209249.2209264 [Consulta: 12 agost 2012].
  9. ↑ 9,0 9,1 Nichols, Kathleen; Jacobson, Van ACM Queue, 55, 7, 06-05-2012, pàg. 42–50. DOI: 10.1145/2209249.2209264 [Consulta: 12 agost 2012].
  10. ↑ 10,0 10,1 Nichols, Kathleen; Jacobson, Van ACM Queue, 55, 7, 06-05-2012, pàg. 42–50. DOI: 10.1145/2209249.2209264 [Consulta: 12 agost 2012].
  11. ↑ Nichols, Kathleen; Jacobson, Van ACM Queue, 55, 7, 06-05-2012, pàg. 42–50. DOI: 10.1145/2209249.2209264 [Consulta: 12 agost 2012].
  12. ↑ Gettys, Jim. «A Milestone Reached: CoDel is in Linux!». jg's Ramblings, 22-05-2012. [Consulta: 12 agost 2012].
  13. ↑ «Cerowrt - Overview». Bufferbloat. [Consulta: 24 gener 2014].
  14. ↑ «Procera Packetlogic Changelog». proceranetworks.com. Arxivat de l'original el 2013-07-24. [Consulta: 24 juliol 2013].
  15. ↑ truckman. «Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).», 26-05-2016.
  16. ↑ truckman. «MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE).», 10-06-2016.
  17. ↑ Al Saadi, Rasool. «Implementing AQM in FreeBSD».
  18. ↑ «OpenBSD 6.2». [Consulta: 13 octubre 2017].