上一節(jié)介紹了隊(duì)列的概念(秒懂確定性網(wǎng)絡(luò)之玩轉(zhuǎn)隊(duì)列(上))，本節(jié)分析隊(duì)列機(jī)制的演進(jìn)過程，從單隊(duì)列延伸到多隊(duì)列，從軟件隊(duì)列延伸到硬件隊(duì)列，從軟件定義隊(duì)列延伸到可編程隊(duì)列，以及每用戶、每隊(duì)列、每流、每包等隊(duì)列調(diào)度粒度。

[[439182]]

隊(duì)列的演進(jìn)

1. 單隊(duì)列到多隊(duì)列

當(dāng)出端口只有一個隊(duì)列時，所有的包都被放在同一個隊(duì)列進(jìn)行調(diào)度，流與流之間缺少隔離性，容易導(dǎo)致亂序和抖動，因此交換機(jī)逐漸從單隊(duì)列發(fā)展到多隊(duì)列，利用多個隊(duì)列來保證隔離性。典型的多隊(duì)列是優(yōu)先級隊(duì)列，其具有0-7共八個隊(duì)列優(yōu)先級，且一般將7定義為最高優(yōu)先級。多隊(duì)列在調(diào)度時，不僅要考慮單個隊(duì)列中包的調(diào)度順序，還要考慮隊(duì)列之間的調(diào)度順序，即選擇哪一個隊(duì)列為出端口傳輸隊(duì)列，常用的傳輸選擇策略[1]有嚴(yán)格優(yōu)先級(SP, Strict Priority)、加權(quán)輪詢(WRR，Weighted Round Robin)、加權(quán)公平隊(duì)列(WRQ，Weighted Fair Queuing)。

SP調(diào)度就是嚴(yán)格按照隊(duì)列優(yōu)先級的高低順序進(jìn)行調(diào)度，只有高優(yōu)先級隊(duì)列中的報(bào)文全部調(diào)度完畢后，才調(diào)度低優(yōu)先級隊(duì)列。其優(yōu)點(diǎn)是關(guān)鍵業(yè)務(wù)可以優(yōu)先被傳輸以降低響應(yīng)延遲，其缺點(diǎn)是擁塞發(fā)生時，如果高優(yōu)先級隊(duì)列中一直有報(bào)文存在，那么低優(yōu)先級隊(duì)列中的報(bào)文將一直得不到服務(wù)。

RR調(diào)度即采用輪詢的方式，如果輪詢的隊(duì)列不為空，則從該隊(duì)列取走一個報(bào)文;如果該隊(duì)列為空，則直接跳過該隊(duì)列，調(diào)度器不等待。輪詢保證了隊(duì)列傳輸機(jī)會的均等性，WRR在輪詢的基礎(chǔ)上為隊(duì)列添加權(quán)重，根據(jù)權(quán)重初始化發(fā)包計(jì)數(shù)器，權(quán)重越大，調(diào)度機(jī)會越多，能被傳輸?shù)陌驮蕉?比如三個隊(duì)列的權(quán)重為50%、25%、25%，則50%權(quán)重的隊(duì)列傳輸機(jī)會比另外兩個隊(duì)列多一倍，能多發(fā)一個包。WRR的優(yōu)點(diǎn)是解決了SP隊(duì)列中低優(yōu)先級隊(duì)列長時間得不到服務(wù)的問題，缺點(diǎn)是其按照報(bào)文個數(shù)進(jìn)行調(diào)度，會由于報(bào)文長度變化導(dǎo)致無法保證每個隊(duì)列固定的帶寬。

WFQ加權(quán)公平隊(duì)列為使帶寬分配更加公平，不再像WRR那樣以報(bào)文數(shù)為單位，而是以比特?cái)?shù)為單位進(jìn)行調(diào)度，從而防止長報(bào)文比短報(bào)文獲得更多帶寬，并減少大小報(bào)文共存時的時延抖動。

此外，為了實(shí)現(xiàn)更好的隔離性，滿足不同維度的隔離需求，還可以采用多級分層隊(duì)列，各級可采用不同的傳輸選擇算法，實(shí)現(xiàn)豐富的調(diào)度策略。比如近年來提出的分層核心無狀態(tài)公平隊(duì)列HCSFQ，以及異步流量整形器ATS。

2. 軟件隊(duì)列到硬件隊(duì)列

上面提到的隊(duì)列策略都屬于軟件隊(duì)列，流量首先通過802.1p/DSCP/IP等字段在分類器進(jìn)行優(yōu)先級映射，進(jìn)入不同的軟件隊(duì)列，然后在調(diào)度器根據(jù)不同的調(diào)度策略進(jìn)行出隊(duì);出隊(duì)后進(jìn)入到硬件隊(duì)列中，最后從接口發(fā)送傳輸?shù)较乱惶?。?shí)際上，軟件隊(duì)列中存放的并不是真實(shí)的數(shù)據(jù)包，而是數(shù)據(jù)包的指針，指針就好比是數(shù)據(jù)包的名字，真實(shí)的數(shù)據(jù)包依然在緩沖區(qū)中，所以數(shù)據(jù)包的大小并不影響隊(duì)列的長度，一個1500字節(jié)的數(shù)據(jù)包和一個10K的數(shù)據(jù)包在隊(duì)列里占用的隊(duì)列長度均為1，軟件隊(duì)列的總隊(duì)列長度可以用隊(duì)列管理工具調(diào)整[2]。

硬件隊(duì)列是Tx輸出隊(duì)列，里面?zhèn)鬏數(shù)氖钦鎸?shí)的數(shù)據(jù)包，其采用先進(jìn)先出FIFO的方式，實(shí)現(xiàn)在接口的ASIC芯片上。每個物理接口上都有且僅有一個硬件隊(duì)列,且不能被隊(duì)列管理工具管理。硬件隊(duì)列的深度一般只有2-3個包，當(dāng)硬件隊(duì)列沒有被充滿或者為空時，說明接口沒有發(fā)生擁塞，一般數(shù)據(jù)不會經(jīng)過軟件隊(duì)列，而會被直接放入硬件隊(duì)列進(jìn)行傳輸。

3. 軟件定義隊(duì)列與可編程隊(duì)列

一方面，當(dāng)前商用交換機(jī)里的隊(duì)列調(diào)度策略都是選配的，即只支持諸如在某個端口關(guān)閉SP隊(duì)列、開啟WFQ隊(duì)列之類的操作，無法靈活地定制特定的隊(duì)列調(diào)度策略，因此軟件定義隊(duì)列的想法被提出。其借鑒軟件定義網(wǎng)絡(luò)中通過OpenFlow南向接口下發(fā)流表來實(shí)時改變轉(zhuǎn)發(fā)行為的思想，希望在控制器中實(shí)現(xiàn)諸如OpenQueue[3]的接口，定義入隊(duì)、調(diào)度、出隊(duì)等基本原語，從而能夠?qū)崟r的進(jìn)行添加隊(duì)列、刪除隊(duì)列、改變優(yōu)先級、改變調(diào)度算法等操作。理論上可以在每個端口定義65000[4]個虛擬隊(duì)列，并采用不同的調(diào)度算法。

另一方面，P4等可編程交換機(jī)的興起，激發(fā)了人們在可編程交換機(jī)中創(chuàng)新隊(duì)列調(diào)度算法的設(shè)想?？删幊剃?duì)列中的可編程主要作用在流量管理器(TM, Traffic Manager)中的調(diào)度器上，通過改變數(shù)據(jù)結(jié)構(gòu)、改變硬件設(shè)計(jì)等方式，針對特定場景實(shí)現(xiàn)更高效的隊(duì)列算法。在2016年的SIGCOMM大會上MIT首次利用可編程PIFO隊(duì)列[5]實(shí)現(xiàn)了WFQ等調(diào)度算法的調(diào)度器，并支持10Gbps的線速轉(zhuǎn)發(fā)能力;Sharma提出可編程日歷隊(duì)列(Calendar Queues)調(diào)度器[6]來實(shí)現(xiàn)公平隊(duì)列、pFabric等各種調(diào)度算法;近來SP-PIFO[7]調(diào)度器使用SP嚴(yán)格優(yōu)先級隊(duì)列實(shí)現(xiàn)了近似PIFO壓入先出隊(duì)列的調(diào)度效果，提升了隊(duì)列在應(yīng)對海量流量時的可擴(kuò)展性。

4. 隊(duì)列調(diào)度的粒度

隊(duì)列調(diào)度的粒度是眾多調(diào)度算法的兵家必爭之地，由粗粒度到細(xì)粒度大致可分為每端口、每用戶、每業(yè)務(wù)類、每隊(duì)列、每流、每包。

每端口粒度的調(diào)度基本只能在出隊(duì)時做端口限速，沒有調(diào)度算法;每用戶調(diào)度可以在邊緣側(cè)流量接入時保證用戶業(yè)務(wù)間的良好隔離性;在入隊(duì)映射時，用戶的多種業(yè)務(wù)流可能被分類進(jìn)不同的優(yōu)先級隊(duì)列;每隊(duì)列調(diào)度即如嚴(yán)格優(yōu)先級調(diào)度般的以隊(duì)列間的調(diào)度順序?yàn)樽钚≌{(diào)度單位;每流調(diào)度可以識別流ID，從而在不同流出隊(duì)時進(jìn)行每流粒度的限速和整形;每包調(diào)度是最細(xì)的調(diào)度粒度，比如PIFO隊(duì)列，其能改變一個包在單個隊(duì)列中的排隊(duì)順序。

調(diào)度粒度越細(xì)，網(wǎng)絡(luò)服務(wù)質(zhì)量越好，但所需要的開銷也越大，比如每流調(diào)度往往需要維護(hù)每流的狀態(tài)，缺少可擴(kuò)展性，當(dāng)有成千上萬條流需要調(diào)度時，調(diào)度性能會變得很低。不同的調(diào)度粒度可以通過分層的多級隊(duì)列調(diào)度來綜合，比如下圖的HQOS (Hierarchical Quality of Service)[8]技術(shù)。

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