Head-of-line blocking
Head-of-line blocking (HOL blocking) in
Network switches
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. If the oldest packet cannot be transmitted due to its target output being busy, then more recent arrivals cannot be forwarded. The output may be busy if there is output contention.
Without HOL blocking, the new arrivals could potentially be forwarded around the stuck oldest packet to their respective destinations. HOL blocking can produce 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
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]
In reliable byte streams
Head-of-line blocking can occur in
See also
References
- .
- .
- S2CID 26573611.
- ^ 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.
- S2CID 207155989.)
{{cite journal}}
: CS1 maint: multiple names: authors list (link - ^ Tyler McMullen (2015). "It Probably Works". ACM Queue.
- S2CID 34623442. Retrieved 10 June 2019.
- ^ Javier Garza (October 2017). "How does HTTP/2 solve the Head of Line blocking (HOL) issue".
- ^ a b Briscoe et al. 2016, pp. 29–30.
- ^ Langley et al. 2017, pp. 184, 186.
- ^ Marx et al. 2018, pp. 22–23.
- ^ Nowlan, Wolinsky & Ford 2013, p. 6.
- ^ Heijligers 2021, p. 65.
Bibliography
- Briscoe, Bob; Brunstrom, Anna; Petlund, Andreas; Hayes, David; Ros, David; Tsang, Ing-Jyh; Gjessing, Stein; Fairhurst, Gorry; Griwodz, Carsten; Welzl, Michael (2016). "Reducing Internet Latency: A Survey of Techniques and Their Merits". S2CID 206576469.
- Heijligers, Jaap (2021). Tor over QUIC (Thesis).
- Langley, Adam; Riddoch, Alistair; Wilk, Alyssa; Vicente, Antonio; Krasic, Charles; Zhang, Dan; Yang, Fan; Kouranov, Fedor; Swett, Ian; Iyengar, Janardhan; Bailey, Jeff; Dorfman, Jeremy; Roskind, Jim; Kulik, Joanna; Westin, Patrik; Tenneti, Raman; Shade, Robbie; Hamilton, Ryan; Vasiliev, Victor; Chang, Wan-Teh; Shi, Zhongyi (2017). "The QUIC Transport Protocol". Proceedings of the Conference of the ACM Special Interest Group on Data Communication. pp. 183–196. S2CID 2768765.
- Marx, Robin; Wijnants, Maarten; Quax, Peter; Faes, Axel; Lamotte, Wim (2018). "Web Performance Characteristics of HTTP/2 and Comparison to HTTP/1.1". Web Information Systems and Technologies. Lecture Notes in Business Information Processing. Vol. 322. pp. 87–114. S2CID 52009597.
- Nowlan, Michael F.; Wolinsky, David; Ford, Bryan (2013). Reducing Latency in Tor Circuits with Unordered Delivery. 3rd USENIX Workshop on Free and Open Communications on the Internet.