Head-of-line blocking

Head-of-line blocking (HOL blocking) in computer networking is a performance-limiting phenomenon that occurs when a line of packets is held up by the first packet. Examples include input buffered network switches, out-of-order delivery and multiple requests in HTTP pipelining.

Switches
Head-of-line blocking example: The 1st and 3rd input flows are competing to send packets to the same output interface. In this case if the switching fabric decides to transfer the packet from the 3rd input flow, the 1st input flow cannot be processed in the same time slot. Note that the 1st input flow is blocking a packet for output interface 3, which is available for processing.

A switch may be composed of buffered input ports, a switch fabric and buffered output ports. If first-in first-out (FIFO) input buffers are used, only the oldest packet is available for forwarding. More recent arrivals cannot be forwarded if the oldest packet cannot be forwarded because its destination output is busy. The output may be busy if there is output contention (see diagram) or when the output buffer is full due to congestion (for example the combined rate of multiple inputs exceeds the output rate).

Without HOL blocking, the new arrivals could potentially be forwarded around the stuck oldest packet to their respective destinations. HOL blocking can have severe performance-degrading effects in input-buffered systems.

This phenomenon limits the throughput of switches. For FIFO input buffers, a simple model of fixed-sized cells to uniformly distributed destinations, causes the throughput to be limited to 58.6% of the total as the number of links becomes large.[1]

One way to overcome this limitation is by using virtual output queues.[2]

Only switches with input buffering can suffer HOL blocking. With sufficient internal bandwidth, input buffering is unnecessary; all buffering is handled at outputs and HOL blocking is avoided. This no-input-buffering architecture is common in small to medium-sized ethernet switches.

Out-of-order delivery

Out-of-order delivery occurs when sequenced packets arrive out of order. This may happen due to different paths taken by the packets or from packets being dropped and resent. HOL blocking can significantly increase packet reordering.[3][4]

Reliably broadcasting messages across a lossy network among a large number of peers is a difficult problem. While atomic broadcast algorithms solve the single point of failure problem of centralized servers, those algorithms introduce a head-of-line blocking problem.[5] The Bimodal Multicast algorithm, a randomized algorithm that uses a gossip protocol, avoids head-of-line blocking by allowing some messages to be received out-of-order.[6]

In HTTP

One form of HOL blocking in HTTP/1.1 is when the number of allowed parallel requests in the browser is used up, and subsequent requests need to wait for the former ones to complete. HTTP/2 addresses this issue through request multiplexing, which eliminates HOL blocking at the application layer, but HOL still exists at the transport (TCP) layer.[7][8]

See also

References
  1. M. Karo; M. Hluchyj; S. Morgan (December 1987). "Input Versus Output Queuing on a Space-Division Packet Switch". IEEE Transactions on Communications. 35 (12): 1347–1356. doi:10.1109/TCOM.1987.1096719.
  2. Nick McKeown; Adisak Mekkittikul; Venkat Anantharam; Jean Walrand (August 1999). "Achieving 100% Throughput in an Input-Queued Switch" (PDF). IEEE Transactions on Communications. 47 (8): 1260–1267. CiteSeerX 10.1.1.18.7529. doi:10.1109/26.780463.
  3. Jon C. R. Bennett; Craig Partridge; Nicholas Shectman (December 1999). "Packet reordering is not pathological network behavior". IEEE/ACM Transactions on Networking. 7 (6): 789–798. CiteSeerX 10.1.1.461.7629. doi:10.1109/90.811445.
  4. Bennett, J. C. R.; Partridge, C.; Shectman, N. (April 2000). Sarisky, Dan (ed.). "Packet Reordering is Not Pathological Network Behavior [Slides]" (PDF). SC N Research. Archived from the original (PDF) on 2017-08-20. Retrieved 2017-08-19.
  5. Defago, X.; Schiper; A., Urban, P. (2004). "Total order broadcast and multicast algorithms: taxonomy and survey". ACM Computing Surveys 36(4): 372-421. doi:10.1145/1041680.1041682.CS1 maint: multiple names: authors list (link)
  6. Tyler McMullen. "It Probably Works". acmqueue 2015.
  7. Grigorik, Ilya (October 2013). "Making the Web Faster with HTTP 2.0". ACM Queue. 11 (10): 40. Retrieved 10 June 2019.
  8. Javier Garza (October 2017). "How does HTTP/2 solve the Head of Line blocking (HOL) issue".
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.