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

[[422925]]

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

隊(duì)列的概念

什么是隊(duì)列?

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

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

為什么需要隊(duì)列

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

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

隊(duì)列的位置

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

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

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

單隊(duì)列調(diào)度：

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

先入先出隊(duì)列：

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

壓入先出隊(duì)列：

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

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

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

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

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

參考文獻(xiàn)：

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

作者簡(jiǎn)介：黃玉棟，北京郵電大學(xué)網(wǎng)絡(luò)與交換國(guó)家重點(diǎn)實(shí)驗(yàn)室博一在讀，研究方向?yàn)槲磥?lái)網(wǎng)絡(luò)體系架構(gòu)，確定性網(wǎng)絡(luò)，郵箱地址: hyduni@163.com。