Head-of-line blocking (HOL blocking) in

computer networking A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ma ...

is a performance-limiting phenomenon that occurs when a line of

packet Packet may refer to: * A small container or pouch ** Packet (container), a small single use container ** Cigarette packet ** Sugar packet * Network packet, a formatted unit of data carried by a packet-mode computer network * Packet radio, a fo ...

s is held up in a

queue __NOTOC__ Queue () may refer to: * Queue area, or queue, a line or area where people wait for goods or services Arts, entertainment, and media *''ACM Queue'', a computer magazine * ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...

by a first packet. Examples include input buffered

network switch A network switch (also called switching hub, bridging hub, and, by the IEEE, MAC bridge) is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destination device. A netw ...

es,

out-of-order delivery In computer networking, out-of-order delivery is the delivery of data packets in a different order from which they were sent. Out-of-order delivery can be caused by packets following multiple paths through a network, by lower-layer retransmissio ...

and multiple requests in

HTTP pipelining HTTP pipelining is a feature of HTTP/1.1 which allows multiple HTTP requests to be sent over a single TCP connection without waiting for the corresponding responses. HTTP/1.1 requires servers to respond to pipelined requests correctly, with non-p ...

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. 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 Contention or contentious may refer to: * Resource contention, in computer science, a conflict over access to a shared resource * Contention (telecommunications), a media access method to share a broadcast medium * Bus contention, an undesirable ...

. 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. One way to overcome this limitation is by using virtual output queues. 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 switch A network switch (also called switching hub, bridging hub, and, by the IEEE, MAC bridge) is networking hardware that connects devices on a computer network by using packet switching to receive and forward data to the destination device. A netw ...

es.

Out-of-order delivery

Out-of-order delivery In computer networking, out-of-order delivery is the delivery of data packets in a different order from which they were sent. Out-of-order delivery can be caused by packets following multiple paths through a network, by lower-layer retransmissio ...

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. Reliably broadcasting messages across a lossy network among a large number of peers is a difficult problem. While

atomic broadcast In fault-tolerant distributed computing, an atomic broadcast or total order broadcast is a broadcast where all correct processes in a system of multiple processes receive the same set of messages in the same order; that is, the same sequence of me ...

algorithms solve the

single point of failure A single point of failure (SPOF) is a part of a system that, if it fails, will stop the entire system from working. SPOFs are undesirable in any system with a goal of high availability or reliability, be it a business practice, software appl ...

problem of centralized servers, those algorithms introduce a head-of-line blocking problem. The Bimodal Multicast algorithm, a

randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

that uses a

gossip protocol A gossip protocol or epidemic protocol is a procedure or process of computer peer-to-peer communication that is based on the way epidemics spread. Some distributed systems use peer-to-peer gossip to ensure that data is disseminated to all members o ...

, avoids head-of-line blocking by allowing some messages to be received out-of-order.

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 HTTP/2 (originally named HTTP/2.0) is a major revision of the HTTP network protocol used by the World Wide Web. It was derived from the earlier experimental SPDY protocol, originally developed by Google. HTTP/2 was developed by the HTTP Working ...

addresses this issue through request multiplexing, which eliminates HOL blocking at the application layer, but HOL still exists at the transport (TCP) layer.

In reliable byte streams

Head-of-line blocking can occur in

reliable byte stream A reliable byte stream is a common service paradigm in computer networking; it refers to a byte stream in which the bytes which emerge from the communication channel at the recipient are exactly the same, and in exactly the same order, as they wer ...

s: if packets are reordered or

lost Lost may refer to getting lost, or to: Geography *Lost, Aberdeenshire, a hamlet in Scotland * Lake Okeechobee Scenic Trail, or LOST, a hiking and cycling trail in Florida, US History *Abbreviation of lost work, any work which is known to have bee ...

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 Network delay is a design and performance characteristic of a telecommunications network. It specifies the Latency (engineering), latency for a bit of data to travel across the network from one communication endpoint to another. It is typically ...

. If multiple independent higher-level messages are encapsulated and

multiplexed In telecommunications and computer networking, multiplexing (sometimes contracted to muxing) is a method by which multiple analog or digital signals are combined into one signal over a shared medium. The aim is to share a scarce resource - a ...

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. This affects, for example,

, which frames multiple request–response pairs onto a single stream;

HTTP/3 HTTP/3 is the third major version of the Hypertext Transfer Protocol used to exchange information on the World Wide Web, complementing the widely-deployed HTTP/1.1 and HTTP/2. Unlike previous versions which relied on the well-established TCP ( ...

, which has an

application-layer framing Application-layer framing or application-level framing (ALF) is a method of allowing an application to use its semantics for the design of its network protocols. This procedure was first proposed by D. D. Clark and David L. Tennenhouse.Clark, D ...

design and uses

datagram A datagram is a basic transfer unit associated with a packet-switched network. Datagrams are typically structured in header and payload sections. Datagrams provide a connectionless communication service across a packet-switched network. The del ...

rather than stream transport, avoids this problem. The latency degradation from head-of-line blocking depends on the underlying packet loss rate and

round-trip time In telecommunications, round-trip delay (RTD) or round-trip time (RTT) is the amount of time it takes for a signal to be sent ''plus'' the amount of time it takes for acknowledgement of that signal having been received. This time delay includes pr ...

, with higher losses producing worse latency. 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 In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...

to send redundant data so that a certain amount of loss can be tolerated without incurring retransmissions.

References

Bibliography