Bloqueig de cap de línia

Model TCP/IP
per capes
Xarxes informàtiques
  • Vegeu aquesta plantilla

El bloqueig de cap de línia (bloqueig HOL) a les xarxes d'ordinadors és un fenomen que limita el rendiment que es produeix quan una línia de paquets es manté en una cua per un primer paquet. Alguns exemples inclouen commutadors de xarxa amb memòria intermèdia d'entrada, lliurament fora de comanda i diverses sol·licituds en canalització HTTP.

Exemple de bloqueig de cap de línia: els fluxos d'entrada 1r i 3r competeixen per enviar paquets a la mateixa interfície de sortida. En aquest cas, si el teixit de commutació decideix transferir el paquet del 3r flux d'entrada, el 1r flux d'entrada no es pot processar en el mateix interval de temps. Tingueu en compte que el primer flux d'entrada està bloquejant un paquet per a la interfície de sortida 3, que està disponible per al processament.

Commutadors de xarxa

[modifica]

Un commutador pot estar compost per ports d'entrada amb memòria intermèdia, un teixit de commutació i ports de sortida amb memòria intermèdia. Si s'utilitzen els buffers d'entrada del primer en entrar, primer en sortir (FIFO), només el paquet més antic està disponible per reenviar-lo. Si el paquet més antic no es pot transmetre perquè la seva sortida objectiu està ocupada, no es poden reenviar les arribades més recents. La sortida pot estar ocupada si hi ha conflicte de sortida.

Sense el bloqueig HOL, les noves arribades podrien ser reenviades al voltant del paquet més antic enganxat a les seves respectives destinacions. El bloqueig de HOL pot produir efectes que degraden el rendiment en sistemes de buffer d'entrada.

Aquest fenomen limita el rendiment dels interruptors. Per als buffers d'entrada FIFO, un model senzill de cel·les de mida fixa a destinacions distribuïdes uniformement, fa que el rendiment es limiti al 58,6% del total a mesura que el nombre d'enllaços es fa gran.[1]

Una manera de superar aquesta limitació és utilitzant cues de sortida virtuals.[2]

Només els interruptors amb memòria intermèdia d'entrada poden patir bloqueig HOL. Amb una amplada de banda interna suficient, la memòria intermèdia d'entrada és innecessària; tot el buffer es gestiona a les sortides i s'evita el bloqueig HOL. Aquesta arquitectura sense búfer d'entrada és habitual en commutadors Ethernet de mida petita i mitjana.

Lliurament fora de comanda

[modifica]

El lliurament fora de comanda es produeix quan els paquets seqüenciats arriben fora de comanda. Això pot passar a causa de diferents camins que prenen els paquets o dels paquets que s'han deixat caure i es reenvien. El bloqueig HOL pot augmentar significativament la reordenació de paquets.[3][4]

Emetre missatges de manera fiable a través d'una xarxa amb pèrdues entre un gran nombre d'iguals és un problema difícil. Mentre que els algorismes de difusió atòmica resolen el problema del punt únic de fallada dels servidors centralitzats, aquests algorismes introdueixen un problema de bloqueig de cap de línia.[5] L'algoritme Bimodal Multicast, un algorisme aleatoritzat que utilitza un protocol de xafarderies, evita el bloqueig de cap de línia permetent que alguns missatges es rebin fora d'ordre.[6]

Referències

[modifica]
  1. ↑ M. Karo; M. Hluchyj; S. Morgan IEEE Transactions on Communications, 35, 12, 12-1987, pàg. 1347–1356. DOI: 10.1109/TCOM.1987.1096719.
  2. ↑ Nick McKeown; Adisak Mekkittikul; Venkat Anantharam; Jean Walrand IEEE Transactions on Communications, 47, 8, 8-1999, pàg. 1260–1267. DOI: 10.1109/26.780463.
  3. ↑ Jon C. R. Bennett; Craig Partridge; Nicholas Shectman IEEE/ACM Transactions on Networking, 7, 6, 12-1999, pàg. 789–798. DOI: 10.1109/90.811445.
  4. ↑ Bennett, J. C. R. «Packet Reordering is Not Pathological Network Behavior [Slides]». SC N Research. Sarisky, 01-04-2000. Arxivat de l'original el 2017-08-20. [Consulta: 19 agost 2017].
  5. ↑ Defago, X.; Schiper; A., Urban, P. ACM Computing Surveys, 36, 4, 2004, pàg. 372-421. DOI: 10.1145/1041680.1041682.
  6. ↑ Tyler McMullen ACM Queue, 2015.