HOL

排頭阻塞（Head-of-line blocking, HOL）是一種出現在快取式通信網路交換中的一種現象。交換結構通常由快取式先進先出輸入連線埠、一個交換結構以及快取式先進先出輸出連線埠組成。

基本介紹

• 中文名：排頭阻塞
• 外文名：Head-of-line blocking
• 英文縮寫：HOL
• 產生原因：先進先出(FIFO)的輸入佇列

發生原因

由於FIFO（先進先出）佇列機製造成的，每個輸入端的FIFO首先處理的是在佇列中最靠前的數據，而這時佇列後面的數據對應的出口快取可能已經空閒，但因為得不到處理而只能等待，這樣既浪費了頻寬又降低了系統性能。

舉個現實生活中的例子，這就如同你在只有一條行車路線的馬路上右轉，但你前面有直行車，雖然這時右行線已經空閒，但你也只能等待。

模型簡介

當在相同的輸入連線埠上到達的包被指向不同的輸出連線埠的時候就會出現排頭阻塞。由於輸入快取使用了FIFO佇列，交換結構在每一個時隙（周期）中將輸入佇列隊頭的數據包傳送到其對應的輸出連線埠中，佇列後部的數據包就只能等待前面傳輸完後再排到佇列前面，然後才可以傳輸。如果某一快取頭部的數據包由於擁塞而不能交換到一個輸出連線埠，那么後面的數據包就會被它阻塞，該快取中餘下的包也會被隊頭包所阻塞，即使這些數據包本身目的連線埠並沒有擁塞。

如右圖所示：當前1、3輸入佇列是相互競爭的，即它們相同的輸出連線埠口4傳送數據包。在這種情況下，如果交換結構決定從輸入佇列3中傳輸數據包，則在同一時鐘周期內不能處理輸入佇列1的數據包。而且處於輸出佇列1的後續數據包，如第二個數據包（輸出連線埠為3，當前空閒）也將無法被輸出到連線埠3。

性能損失

總體性能損失

根據卡羅爾等人在1986年發表的論文推導顯示，只要滿足下述5個條件，則一個具有N × N 的FIFO（先進先出）輸入輸出快取佇列的吞吐量（輸出利用率 = 實際輸出量/輸出連線埠總量）將為 =：

（1）數據包到達每個輸入是獨立同分布的（IID）；
（2）數據包到達每個輸入時相互是獨立的，與其他輸入無關；
（3）所有輸入連線埠的數據包具有相同的到達率且目的地是均勻地分布在所有輸出；
（4）到達的數據包是固定的和相等的長度；
（5）N足夠大（N->∞）。

當條件（1）和（2）成立時，我們認為，不同數據包到達輸出連線埠是相互獨立的，而當條件（3）成立時，我們認為，數據包的的輸入輸出是均勻的分布的。因為個別數據包被阻塞在隊頭，故它後續的數據包也將無法被傳送到輸出連線埠（即使它們的目的輸出連線埠不同），進而限制了網路的吞吐量。

性能損失分析

考慮在輸入排隊和在輸出排隊兩種情況：

1、在輸出排隊

基於上述五個條件，我們假設：

a)在任意一個時隙一個數據包到達一個特定輸入佇列的機率為p；

b)每個數據包的目的輸出連線埠是等機率的（1 / N）；

c)數據包是否成功從輸入連線埠傳送到輸出連線埠是相互獨立的。

我們研究其中一個特定的輸出佇列，定義隨機變數A為在給定時隙內到達特定輸出佇列的數據包個數，其中A服從二項分布：

機率母函式（PGF）為：

當N趨於無窮大，在一個特定時隙內到達特定輸出佇列的數據包數量服從泊松分布：

則機率母函式（PGF）為：

令 表示在第m個時隙後在指定輸出佇列中數據包的數量， 表示在第m個時隙內到達輸出佇列的數據包數量。於是我們得到的遞歸定義式：

當 且 時，在第m個時隙將會有一個新的數據包被傳送，也就是說此時數據流將會無延遲地被傳送到輸出連線埠（我們的討論都是基於離散時間馬氏鏈模型的），運用排隊分析理論我們可以得到處於穩態的佇列大小的機率母函式（PGF)：

結合式（2）到（6）我們可以得到：

接著對（7）式做變形，取極限z->1，我們得到穩定時輸出佇列平均長度：

2、在輸入排隊

考慮一個交換結構的處理速率與輸入輸出相等，且數據包在輸入快取排隊等待被傳送。現假設有k個隊頭數據包的目的輸出連線埠相同，交換結構的控制器等機率隨機地在這k個數據包中選擇一個數據包傳送到該輸出連線埠，而其它(k-1)個數據包被阻塞在隊頭。

假設所有輸入佇列都是飽和的，即在所有輸入佇列總有數據包等待被傳送。一旦隊頭的數據包被傳送到輸出連線埠，就有一個新的數據包補到隊頭。為方便討論現定義幾個隨機變數

（1）表示：在m時隙， 輸出連線埠為i，但被阻塞在隊頭的數據包數量。

（2）表示：在時隙m被移動到輸入佇列隊頭，且目的輸出連線埠為i的數據包數量（表明在m-1時隙有 個數據包被傳送到輸出佇列）；同樣的，新移動到隊頭的數據包的目的輸出連線埠也是隨機等機率的。

（3）表示：在m-1時隙總共有多少數據包被傳送到輸出連線埠，也即在時隙m，有新數據包移動到隊頭的輸人佇列的總數量，即：

我們可以根據上述定義寫出的遞歸定義如下（10）式：

注意到式（9）和式（5）具有相同的數學形式，且 服從二項分布：

其中，

令 ，F表示處於穩態的輸出量（即的統計平均數），則 表示交換結構的吞吐量，當N->∞時 （表示的統計穩態平均數），對於 服從泊松分布，再結合式（8）（10）我們能夠得到 （與 定義類似）平均數的表達式（註：對式（8）兩邊取極限N->∞），有：

（註：相當於把阻塞在輸入隊頭的數據包拿到輸出排隊）
另一方面，利用式（11）可得：

當輸入輸出佇列飽和且N足夠大時，結合（13）（14）兩式解得

解決方案

克服這種局限性的一種方法是使用虛擬輸出佇列（Virtual Output Queues）。因為只有具有輸入緩衝的交換結構才存在排頭阻塞問題。所以若有充足的內部頻寬，則輸入緩衝就是是不必要的，進而能夠避免排頭阻塞的問題。這種沒有輸入緩衝的交換結構結構在小到中等規模的乙太網交換機上十分常見。

虛擬輸出佇列（Virtual Output Queues）總體的想法十分樸素：在輸入連線埠將傳送到不同連線埠的數據包虛擬成不同的佇列，並且彼此互不影響，這樣一來即使隊頭數據包被阻塞也將不會影響傳送到其他連線埠的數據包的傳送。

如右圖2 × 4的輸入輸出交換結構中，每個輸入連線埠將根據數據包輸出連線埠的不同而加入專屬“虛擬佇列”（圖中以不同的顏色區分），這樣一來，在同一輸入連線埠而目的連線埠不同的數據包的傳送將彼此互不影響。

除了虛擬輸出佇列（Virtual Output Queues）外，還有其他許多解決排頭阻塞的算法，如神經網路、iSLIP等等。