“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

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. The phenomenon 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]

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

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.

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.^[5]

See also

References

1. ^{{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 }}
2. ^{{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 |authorlink1=Nick McKeown |authorlink2=Adisak Mekkittikul |citeseerx= 10.1.1.18.7529 }}
3. ^{{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|url= |doi= 10.1109/90.811445|citeseerx= 10.1.1.461.7629 }}
4. ^{{Cite web|url=http://www.scn.rain.com/~neighorn/PDF/reorderingpaper.pdf|title=Packet Reordering is Not Pathological Network Behavior [Slides]|last=Bennett|first=J. C. R.|last2=Partridge|first2=C.|date=April 2000|editor-last=Sarisky|editor-first=Dan|website=SC N Research|archive-url=|archive-date=|dead-url=|access-date=2017-08-19|last3=Shectman|first3=N.}}
5. ^Tyler McMullen.[https://queue.acm.org/detail.cfm?id=2855183 "It Probably Works"].acmqueue 2015.