秒懂確定性網絡之玩轉隊列（中）
上一節介紹了隊列的概念(秒懂確定性網絡之玩轉隊列(上))，本節分析隊列機制的演進過程，從單隊列延伸到多隊列，從軟件隊列延伸到硬件隊列，從軟件定義隊列延伸到可編程隊列，以及每用戶、每隊列、每流、每包等隊列調度粒度。
隊列的演進
1. 單隊列到多隊列
當出端口只有一個隊列時，所有的包都被放在同一個隊列進行調度，流與流之間缺少隔離性，容易導致亂序和抖動，因此交換機逐漸從單隊列發展到多隊列，利用多個隊列來保證隔離性。典型的多隊列是優先級隊列，其具有0-7共八個隊列優先級，且一般將7定義為最高優先級。多隊列在調度時，不僅要考慮單個隊列中包的調度順序，還要考慮隊列之間的調度順序，即選擇哪一個隊列為出端口傳輸隊列，常用的傳輸選擇策略[1]有嚴格優先級(SP, Strict Priority)、加權輪詢(WRR，Weighted Round Robin)、加權公平隊列(WRQ，Weighted Fair Queuing)。
SP調度就是嚴格按照隊列優先級的高低順序進行調度，只有高優先級隊列中的報文全部調度完畢后，才調度低優先級隊列。其優點是關鍵業務可以優先被傳輸以降低響應延遲，其缺點是擁塞發生時，如果高優先級隊列中一直有報文存在，那么低優先級隊列中的報文將一直得不到服務。
RR調度即采用輪詢的方式，如果輪詢的隊列不為空，則從該隊列取走一個報文;如果該隊列為空，則直接跳過該隊列，調度器不等待。輪詢保證了隊列傳輸機會的均等性，WRR在輪詢的基礎上為隊列添加權重，根據權重初始化發包計數器，權重越大，調度機會越多，能被傳輸的包就越多;比如三個隊列的權重為50%、25%、25%，則50%權重的隊列傳輸機會比另外兩個隊列多一倍，能多發一個包。WRR的優點是解決了SP隊列中低優先級隊列長時間得不到服務的問題，缺點是其按照報文個數進行調度，會由于報文長度變化導致無法保證每個隊列固定的帶寬。
WFQ加權公平隊列為使帶寬分配更加公平，不再像WRR那樣以報文數為單位，而是以比特數為單位進行調度，從而防止長報文比短報文獲得更多帶寬，并減少大小報文共存時的時延抖動。
此外，為了實現更好的隔離性，滿足不同維度的隔離需求，還可以采用多級分層隊列，各級可采用不同的傳輸選擇算法，實現豐富的調度策略。比如近年來提出的分層核心無狀態公平隊列HCSFQ，以及異步流量整形器ATS。
2. 軟件隊列到硬件隊列
上面提到的隊列策略都屬于軟件隊列，流量首先通過802.1p/DSCP/IP等字段在分類器進行優先級映射，進入不同的軟件隊列，然后在調度器根據不同的調度策略進行出隊;出隊后進入到硬件隊列中，最后從接口發送傳輸到下一跳。實際上，軟件隊列中存放的并不是真實的數據包，而是數據包的指針，指針就好比是數據包的名字，真實的數據包依然在緩沖區中，所以數據包的大小并不影響隊列的長度，一個1500字節的數據包和一個10K的數據包在隊列里占用的隊列長度均為1，軟件隊列的總隊列長度可以用隊列管理工具調整[2]。
硬件隊列是Tx輸出隊列，里面傳輸的是真實的數據包，其采用先進先出FIFO的方式，實現在接口的ASIC芯片上。每個物理接口上都有且僅有一個硬件隊列,且不能被隊列管理工具管理。硬件隊列的深度一般只有2-3個包，當硬件隊列沒有被充滿或者為空時，說明接口沒有發生擁塞，一般數據不會經過軟件隊列，而會被直接放入硬件隊列進行傳輸。
3. 軟件定義隊列與可編程隊列
一方面，當前商用交換機里的隊列調度策略都是選配的，即只支持諸如在某個端口關閉SP隊列、開啟WFQ隊列之類的操作，無法靈活地定制特定的隊列調度策略，因此軟件定義隊列的想法被提出。其借鑒軟件定義網絡中通過OpenFlow南向接口下發流表來實時改變轉發行為的思想，希望在控制器中實現諸如OpenQueue[3]的接口，定義入隊、調度、出隊等基本原語，從而能夠實時的進行添加隊列、刪除隊列、改變優先級、改變調度算法等操作。理論上可以在每個端口定義65000[4]個虛擬隊列，并采用不同的調度算法。
另一方面，P4等可編程交換機的興起，激發了人們在可編程交換機中創新隊列調度算法的設想。可編程隊列中的可編程主要作用在流量管理器(TM, Traffic Manager)中的調度器上，通過改變數據結構、改變硬件設計等方式，針對特定場景實現更高效的隊列算法。在2016年的SIGCOMM大會上MIT首次利用可編程PIFO隊列[5]實現了WFQ等調度算法的調度器，并支持10Gbps的線速轉發能力;Sharma提出可編程日歷隊列(Calendar Queues)調度器[6]來實現公平隊列、pFabric等各種調度算法;近來SP-PIFO[7]調度器使用SP嚴格優先級隊列實現了近似PIFO壓入先出隊列的調度效果，提升了隊列在應對海量流量時的可擴展性。
4. 隊列調度的粒度
隊列調度的粒度是眾多調度算法的兵家必爭之地，由粗粒度到細粒度大致可分為每端口、每用戶、每業務類、每隊列、每流、每包。
每端口粒度的調度基本只能在出隊時做端口限速，沒有調度算法;每用戶調度可以在邊緣側流量接入時保證用戶業務間的良好隔離性;在入隊映射時，用戶的多種業務流可能被分類進不同的優先級隊列;每隊列調度即如嚴格優先級調度般的以隊列間的調度順序為最小調度單位;每流調度可以識別流ID，從而在不同流出隊時進行每流粒度的限速和整形;每包調度是最細的調度粒度，比如PIFO隊列，其能改變一個包在單個隊列中的排隊順序。
調度粒度越細，網絡服務質量越好，但所需要的開銷也越大，比如每流調度往往需要維護每流的狀態，缺少可擴展性，當有成千上萬條流需要調度時，調度性能會變得很低。不同的調度粒度可以通過分層的多級隊列調度來綜合，比如下圖的HQOS (Hierarchical Quality of Service)[8]技術。
下一節將介紹確定性網絡中的隊列增強機制，更多內容請看下回分解。
