Head-of-line blocking

Image:HOL blocking.png

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.{{cite journal |title= Input Versus Output Queuing on a Space-Division Packet Switch |author1= M. Karo |author2= M. Hluchyj |author3= S. Morgan |journal= IEEE Transactions on Communications |volume= 35 |issue= 12 |date= December 1987 |pages= 1347–1356 |doi= 10.1109/TCOM.1987.1096719 }}

One way to overcome this limitation is by using virtual output queues.{{cite journal |title=Achieving 100% Throughput in an Input-Queued Switch |author1= Nick McKeown |author2= Adisak Mekkittikul |author3= Venkat Anantharam |author4= Jean Walrand |journal= IEEE Transactions on Communications |volume= 47 |issue= 8 |date= August 1999 |pages= 1260–1267 |url= http://tiny-tera.stanford.edu/~nickm/papers/IEEE_COMM_V3.pdf |doi= 10.1109/26.780463 |author-link1=Nick McKeown |author-link2=Adisak Mekkittikul |citeseerx= 10.1.1.18.7529 }}

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 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.{{cite journal |title= Packet reordering is not pathological network behavior |author1= Jon C. R. Bennett |author2= Craig Partridge |author3= Nicholas Shectman |journal= IEEE/ACM Transactions on Networking |volume= 7 |issue= 6 |date= December 1999 |pages= 789–798|doi= 10.1109/90.811445|citeseerx= 10.1.1.461.7629 |s2cid= 26573611 }}{{Cite web|url=http://www.scn.rain.com/~neighorn/PDF/reorderingpaper.pdf|title=Packet Reordering is Not Pathological Network Behavior [Slides]|last1=Bennett|first1=J. C. R.|last2=Partridge|first2=C.|date=April 2000|editor-last=Sarisky|editor-first=Dan|website=SC N Research|access-date=2017-08-19|last3=Shectman|first3=N.|archive-url=https://web.archive.org/web/20170820074443/http://www.scn.rain.com/~neighorn/PDF/reorderingpaper.pdf|archive-date=2017-08-20|url-status=dead}}

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.{{cite journal |author1=Defago, X. |author2=Schiper |author3=A., Urban, P. |date=2004 |title=Total order broadcast and multicast algorithms: taxonomy and survey |journal=ACM Computing Surveys |volume=36 |issue=4 |page=372-421 |doi=10.1145/1041680.1041682|s2cid=207155989 |url=https://infoscience.epfl.ch/record/88271/files/DSU04.pdf }} 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.{{cite journal |author=Tyler McMullen |url=https://queue.acm.org/detail.cfm?id=2855183 |title=It Probably Works |journal=ACM Queue |date=2015}}

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.{{cite journal |last1=Grigorik |first1=Ilya |title=Making the Web Faster with HTTP 2.0 |journal=ACM Queue |date=October 2013 |volume=11 |issue=10 |page=40 |doi=10.1145/2542661.2555617 |s2cid=34623442 |url=https://queue.acm.org/detail.cfm?id=2555617 |access-date=10 June 2019|doi-access=free }}{{cite web|url=https://community.akamai.com/customers/s/article/How-does-HTTP-2-solve-the-Head-of-Line-blocking-HOL-issue?language=en_US|author=Javier Garza|date=October 2017|title=How does HTTP/2 solve the Head of Line blocking (HOL) issue}}

Head-of-line blocking can occur in reliable byte streams: if packets are reordered or lost and need to be retransmitted (and thus arrive out-of-order), data from sequentially later parts of the stream may be received before sequentially earlier parts of the stream; however, the later data cannot typically be used until the earlier data has been received, incurring network latency. If multiple independent higher-level messages are encapsulated and multiplexed onto a single reliable byte stream, then head-of-line blocking can cause processing of a fully-received message that was sent later to wait for delivery of a message that was sent earlier.{{sfn|Briscoe|Brunstrom|Petlund|Hayes|2016|pp=29-30}} This affects, for example, HTTP/2, which frames multiple request–response pairs onto a single stream; HTTP/3, which has an application-layer framing design and uses datagram rather than stream transport, avoids this problem.{{sfn|Langley|Riddoch|Wilk|Vicente|2017|pp=184,186}}{{sfn|Marx|Wijnants|Quax|Faes|2018|pp=22-23}} The latency degradation from head-of-line blocking depends on the underlying packet loss rate and round-trip time, with higher losses producing worse latency.{{sfn|Nowlan|Wolinsky|Ford|2013|p=6}}{{sfn|Heijligers|2021|p=65}} Without changing the stream abstraction, reducing packet loss can reduce the harm from head-of-line blocking; an alternative is to implement the reliable byte stream using forward error correction to send redundant data so that a certain amount of loss can be tolerated without incurring retransmissions.{{sfn|Briscoe|Brunstrom|Petlund|Hayes|2016|pp=29-30}}

• Bufferbloat
• FIFO
• HTTP pipelining
• Network scheduler
• Pipeline stall

{{reflist}}

• {{ cite journal | doi = 10.1109/COMST.2014.2375213 | title = Reducing Internet Latency: A Survey of Techniques and Their Merits | year = 2016 | last1 = Briscoe | first1 = Bob | last2 = Brunstrom | first2 = Anna | last3 = Petlund | first3 = Andreas | last4 = Hayes | first4 = David | last5 = Ros | first5 = David | last6 = Tsang | first6 = Ing-Jyh | last7 = Gjessing | first7 = Stein | last8 = Fairhurst | first8 = Gorry | last9 = Griwodz | first9 = Carsten | last10 = Welzl | first10 = Michael | journal = IEEE Communications Surveys & Tutorials | volume = 18 | issue = 3 | pages = 2149–2196 | hdl = 2164/8018 | hdl-access = free | s2cid = 206576469 }}
• {{cite thesis | url=http://resolver.tudelft.nl/uuid:1f473ff9-7d2c-43c9-8cfc-8f42e629b80f | title=Tor over QUIC | year=2021 | last1=Heijligers | first1=Jaap }}
• {{cite book | doi=10.1145/3098822.3098842 | doi-access=free | chapter=The QUIC Transport Protocol | title=Proceedings of the Conference of the ACM Special Interest Group on Data Communication | year=2017 | last1=Langley | first1=Adam | last2=Riddoch | first2=Alistair | last3=Wilk | first3=Alyssa | last4=Vicente | first4=Antonio | last5=Krasic | first5=Charles | last6=Zhang | first6=Dan | last7=Yang | first7=Fan | last8=Kouranov | first8=Fedor | last9=Swett | first9=Ian | last10=Iyengar | first10=Janardhan | last11=Bailey | first11=Jeff | last12=Dorfman | first12=Jeremy | last13=Roskind | first13=Jim | last14=Kulik | first14=Joanna | last15=Westin | first15=Patrik | last16=Tenneti | first16=Raman | last17=Shade | first17=Robbie | last18=Hamilton | first18=Ryan | last19=Vasiliev | first19=Victor | last20=Chang | first20=Wan-Teh | last21=Shi | first21=Zhongyi | pages=183–196 | isbn=9781450346535 | s2cid=2768765 }}
• {{cite book | hdl=1942/26146 | hdl-access = free | doi=10.1007/978-3-319-93527-0_5 | chapter=Web Performance Characteristics of HTTP/2 and Comparison to HTTP/1.1 | title=Web Information Systems and Technologies | series=Lecture Notes in Business Information Processing | year=2018 | last1=Marx | first1=Robin | last2=Wijnants | first2=Maarten | last3=Quax | first3=Peter | last4=Faes | first4=Axel | last5=Lamotte | first5=Wim | volume=322 | pages=87–114 | isbn=978-3-319-93526-3 | s2cid=52009597 }}
• {{cite conference | url=https://www.usenix.org/conference/foci13/workshop-program/presentation/nowlan | title=Reducing Latency in Tor Circuits with Unordered Delivery | conference=3rd USENIX Workshop on Free and Open Communications on the Internet | date = 2013 | last1 = Nowlan | first1 = Michael F. | last2 = Wolinsky | first2 = David | last3 = Ford | first3 = Bryan }}

Category:Queue management

Category:Packets (information technology)