HOL

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

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

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

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

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

=

：

（1）數據包到達每個輸入是獨立同分布的（IID）；

（2）數據包到達每個輸入時相互是獨立的，與其他輸入無關；

（3）所有輸入端口的數據包具有相同的到達率且目的地是均勻地分佈在所有輸出；

（4）到達的數據包是固定的和相等的長度；

（5）N足夠大（N->∞）。

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

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

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

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

b)每個數據包的目的輸出端口是等概率的（1 / N）；

c)數據包是否成功從輸入端口發送到輸出端口是相互獨立的。

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

概率母函數（PGF）為：

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

則概率母函數（PGF）為：

令

表示在第m個時隙後在指定輸出隊列中數據包的數量，

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

當

且

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

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

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

考慮一個交換結構的處理速率與輸入輸出相等，且數據包在輸入緩存排隊等待被髮送。現假設有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等等。