隊列調度是計算機網絡中的一個核心問題，過去的幾十年里，在工業網絡、數據中心網絡、廣域網等場景中，大量的調度算法被設計來提供不同的特性和優化不同的目標，可編程包調度更是近幾年數據中心網絡研究領域的皇冠。隨著應用對網絡服務質量的要求不斷提高，確定性網絡中的隊列機制也不斷推陳出新。本文帶大家玩轉隊列，按照隊列的概念、隊列的演進、隊列的確定性增強，分為三小節，揭開眾多機制背后的核心奧秘。

[[422925]]

本文首先解釋隊列的概念，從隊列的位置講起，介紹單個隊列的入隊、調度、出隊過程，呈現先入先出(FIFO, First-In-First-Out)、壓入先出(PIFO,Push-In-First-Out)兩種經典的隊列形式，以及相關的調度算法;然后分析隊列機制的演進過程，從單隊列延伸到多隊列，從硬件隊列延伸到軟件隊列，以及每包、每流、每類、每隊列等調度粒度;最后講解確定性網絡中的流量整形、門控、幀搶占等隊列增強機制。

隊列的概念

什么是隊列?

如圖1所示，一臺交換機有多個端口，交換機內部通過交換矩陣將端口連接起來，數據包總是從一個端口進，然后通過交換矩陣，再從另一個端口出，在全雙工模式下每個端口既是入端口也是出端口。交換機里有一塊存儲資源叫緩沖區，大部分交換機的片上緩存都不大，一般是幾MB到幾十MB，均分到各個端口也就幾百KB，有突發流量時大概能存下幾十個包。

雖然單端口帶寬在不到十年的時間里從1G發展到了400G，但緩存并沒有很大提升，因為大緩存雖能減少丟包，但需要相對多的尋址時間，會降低數據包的轉發速度，增加設備成本和網絡延遲。隊列是緩沖區里的一種數據結構，用于針對不同的應用優化網絡的丟包率和時延性能。

為什么需要隊列

隊列主要解決排隊的問題，如果網絡是一個帶寬相同的線型拓撲，速率處處匹配，流量總大小不超過端口帶寬，則無需隊列。如圖2所示，現實中網絡拓撲復雜，存在流量的微突發(比如由TCP滑動窗口導致的突發)和多打一等上下游端口速率不匹配問題，因此需要隊列調度。

在緩存排隊的過程中，有的應用需要低時延，要求緩存小且被優先調度;有的應用需要零丟包，則緩存越大越好;有的追求網絡吞吐量和利用率，要求針對帶寬進行優化;有的追求公平性，要求隊列資源盡量平均分配;有的又對流完成時間有要求，需要降低流量的長尾時延。同時滿足多種應用需求給隊列調度帶來了巨大的挑戰。

隊列的位置

關于緩沖隊列應該放在什么位置，有很多不同的見解，如圖3所示，總的有輸出端口緩沖、輸入端口緩沖+虛擬輸出隊列(Virtual Output Queues, VOQs)、交叉點緩沖、共享緩沖四種方式[1]。

• 輸出端口緩沖是將緩沖區放在出端口的位置，它相比于輸入端口緩沖有更好的時延和吞吐性能，然而它要求每個出端口具有N倍的線速處理能力，以處理N個入端口連向同一個出端口的情況，這種N倍的處理能力往往是不切實際的;
• 于是有了入端口緩沖+虛擬輸出隊列VOQs的架構，可以滿足線速處理但吞吐量下降，這也是當前最常用的緩沖方式。
• 交叉點緩沖能夠保證高吞吐，但對于具有N 個入端口和N個出端口的交換機需要 O(N*N) 的內存成本。事實上，在這種架構中每個輸入-輸出對都擁有自己的交叉點緩沖，不能共享不同的交叉點緩沖區，因此當N較大時，會造成相當大的內存浪費。在片上內存有限的嵌入式系統中，高昂的內存成本也是不可接受的。
• 最后還有一種“交換-內存-交換”的共享緩沖架構，在架構中間使用至少2N-1個緩沖區來模擬輸出緩沖區切換;這些緩沖區由所有端口共享，因此即使僅使用一小部分端口，也可以獲得高達 100% 的內存使用率。

總的來說，不管緩沖區放在什么位置，當提到“隊列調度”時，默認發生在交換機出端口就好了。

單隊列調度：

• 下面來看單隊列的調度，其分為入隊、調度、出隊三個過程。其中，入隊是做接入控制，對流量進行識別和分類，對不符合要求的流量進行丟棄;調度是對隊列中的數據包進行選擇出隊，在單隊列中有“先入先出FIFO”、“壓入先出PIFO”兩種最常用的模式，在模式之上可以做各式各樣的調度算法創新;出隊是將數據包傳輸到鏈路上，鏈路連接到下一節點的入端口，在出隊時做流量整形(即控制流量在出端口傳輸時的發送速率)，可以降低或避免下游節點擁塞。

先入先出隊列：

• 先入先出隊列是最基本最純粹的隊列，是其他隊列改進的母版。如圖4(a)所示，它讓最先到達的數據包最先出隊，不改變包的順序，也就是沒有調度算法，不進行調度。當然，它也可以在入隊做接入控制，在出隊做流量整形。

壓入先出隊列：

• 如圖4(b)所示，每個數據包攜帶有一個數字標記作為它的秩，一般秩越小表示數據包的等級越高，越需要被優先傳輸[2]。壓入先出隊列首先在入隊時對不符合秩條件的數據包進行丟棄，然后根據秩大小進行排序，把秩小的包壓入隊頭優先出隊傳輸。

隊列調度算法：

• 僅在單隊列模式的基礎上，人們就做了大量的隊列調度算法創新，比如主動隊列管理，給隊列長度設定一個閾值，如果隊列長度超過這個閾值，就丟棄后面的包，從而保證傳輸時延不會過大;再比如在此基礎上衍生出的ECN顯示擁塞通知，如果隊列長度超過這個閾值，就通知上游發送節點降低發送速率，直到反饋到發送端降低發送速率，等到隊列長度小于這個閾值了，又可以通知發送端增大發送速率。

此外，在選擇誰應該被放在前面優先調度上，不僅可以用秩，還可以用時延預估，比如截止時間小的包優先調度，可以用流的體積，當大象流和老鼠流同時到達，體積小的老鼠流優先調度。在確定性網絡中，還可以給隊列長度設定一個上界，流量不超過隊列長度的最大值，從而保證零丟包以及有界低時延。

下一節將介紹隊列機制的演進過程，以及確定性網絡中的隊列增強機制，更多內容請看下回分解。

參考文獻：

[1] Z. Li et al., "Time-triggered switch-memory-switch architecture for time-sensitive networking switches," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 1, pp. 185-198, 2020.

[2] Zhuolong Yu, et al., “Programmable packet scheduling with a single queue”. In SIGCOMM '21. New York, USA, 179–193.

作者簡介：黃玉棟，北京郵電大學網絡與交換國家重點實驗室博一在讀，研究方向為未來網絡體系架構，確定性網絡，郵箱地址: hyduni@163.com。