隊頭阻塞

隊頭阻塞(英語:Head-of-line blocking,縮寫:HOL blocking)在計算機網絡的範疇中是一種性能受限的現象。它的原因是一列的第一個數據包(隊頭)受阻而導致整列數據包受阻。例如它有可能在緩存式輸入的交換機中出現,有可能因為傳輸順序錯亂而出現,亦有可能在HTTP流水線中有多個請求的情況下出現。

交換機中的隊頭阻塞

一個交換機有可能由緩存式輸入端口、交換架構以及緩存式的輸出端口所組成。如果在輸入端口處使用了先進先出(FIFO)的策略,那麼就只有最先進入的數據包可以被處理。而此時如果最先進入的數據包由於目標輸出端口正忙而無法被處理的話,那麼更晚到達的數據包就沒有辦法被處理(即便是更晚到達的數據包的目標輸出端口並沒有處於忙碌的狀態)。輸出正忙的情況有:

  • 存在輸出的競態關係;
  • 或者更常見的情況是輸出緩存已滿,從而導致了阻塞現象(例如多個輸入的數據傳輸速率超過了輸出的傳輸速率)。

如果沒有隊頭阻塞的話,新到達的數據包就有可能繞開被阻礙的數據包而被導向它們各自的(沒有處於阻塞狀態的)目標輸出端口了。這種現象有可能在緩存式輸入的系統中對性能造成極大的影響。

解決隊頭阻塞

解決這個問題的其中一個方法是使用虛擬輸出隊列[1]。只有在緩存式輸入的交換機中才會出現隊頭阻塞的情況。如果交換機內部的帶寬足夠的話,緩存輸入就是沒有必要的了——所有的緩存都可以在輸出處被處理,從而也避免了隊頭阻塞。這樣的無緩存式輸入架構在中小型規模的以太網交換機中非常常見。

參考資料

  1. ^ Nick McKeown; Adisak Mekkittikul; Venkat Anantharam; Jean Walrand. Achieving 100% Throughput in an Input-Queued Switch (PDF). IEEE Transactions on Communications. August 1999, 47 (8): 1260–1267 [2016-03-19]. doi:10.1109/26.780463. (原始內容 (PDF)存檔於2022-06-24).