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

[[422925]]

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

隊列的概念

什么是隊列?

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

雖然單端口帶寬在不到十年的時間里從1G發(fā)展到了400G，但緩存并沒有很大提升，因為大緩存雖能減少丟包，但需要相對多的尋址時間，會降低數(shù)據(jù)包的轉(zhuǎn)發(fā)速度，增加設(shè)備成本和網(wǎng)絡(luò)延遲。隊列是緩沖區(qū)里的一種數(shù)據(jù)結(jié)構(gòu)，用于針對不同的應(yīng)用優(yōu)化網(wǎng)絡(luò)的丟包率和時延性能。

為什么需要隊列

隊列主要解決排隊的問題，如果網(wǎng)絡(luò)是一個帶寬相同的線型拓?fù)洌俾侍幪幤ヅ洌髁靠偞笮〔怀^端口帶寬，則無需隊列。如圖2所示，現(xiàn)實中網(wǎng)絡(luò)拓?fù)鋸?fù)雜，存在流量的微突發(fā)(比如由TCP滑動窗口導(dǎo)致的突發(fā))和多打一等上下游端口速率不匹配問題，因此需要隊列調(diào)度。

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

隊列的位置

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

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

總的來說，不管緩沖區(qū)放在什么位置，當(dāng)提到“隊列調(diào)度”時，默認(rèn)發(fā)生在交換機出端口就好了。

單隊列調(diào)度：

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

先入先出隊列：

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

壓入先出隊列：

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

隊列調(diào)度算法：

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

此外，在選擇誰應(yīng)該被放在前面優(yōu)先調(diào)度上，不僅可以用秩，還可以用時延預(yù)估，比如截止時間小的包優(yōu)先調(diào)度，可以用流的體積，當(dāng)大象流和老鼠流同時到達(dá)，體積小的老鼠流優(yōu)先調(diào)度。在確定性網(wǎng)絡(luò)中，還可以給隊列長度設(shè)定一個上界，流量不超過隊列長度的最大值，從而保證零丟包以及有界低時延。

下一節(jié)將介紹隊列機制的演進過程，以及確定性網(wǎng)絡(luò)中的隊列增強機制，更多內(nèi)容請看下回分解。

參考文獻：

[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.

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