隊(duì)列指的是在緩存中對(duì)報(bào)文進(jìn)行排序的邏輯。當(dāng)流量的速率超過(guò)接口帶寬或超過(guò)為該流量設(shè)置的帶寬時(shí)，報(bào)文就以隊(duì)列的形式暫存在緩存中。報(bào)文離開(kāi)隊(duì)列的時(shí)間、順序，以及各個(gè)隊(duì)列之間報(bào)文離開(kāi)的相互關(guān)系由隊(duì)列調(diào)度算法決定。

華為交換機(jī)設(shè)備的每個(gè)端口上都有 8 個(gè)下行隊(duì)列，稱為CQ（Class Queue）隊(duì)列，也叫 端口隊(duì)列（Port-queue），在交換機(jī)內(nèi)部與前文提到的 8 個(gè)PHB一一對(duì)應(yīng)，分別為BE、 AF1、AF2、AF3、AF4、EF、CS6 和CS7。單個(gè)隊(duì)列的報(bào)文采用 FIFO（First In First Out）原則入隊(duì)和出隊(duì)。

• PQ（Priority Queuing）調(diào)度

PQ（Priority Queuing）調(diào)度，就是嚴(yán)格按照隊(duì)列優(yōu)先級(jí)的高低順序進(jìn)行調(diào)度。只有 高優(yōu)先級(jí)隊(duì)列中的報(bào)文全部調(diào)度完畢后，低優(yōu)先級(jí)隊(duì)列才有調(diào)度機(jī)會(huì)。 采用PQ 調(diào)度方式，將延遲敏感的關(guān)鍵業(yè)務(wù)放入高優(yōu)先級(jí)隊(duì)列，將非關(guān)鍵業(yè)務(wù)放入 低優(yōu)先級(jí)隊(duì)列，從而確保關(guān)鍵業(yè)務(wù)被優(yōu)先發(fā)送。 PQ調(diào)度的缺點(diǎn)是：擁塞發(fā)生時(shí)，如果較高優(yōu)先級(jí)隊(duì)列中長(zhǎng)時(shí)間有分組存在，那么 低優(yōu)先級(jí)隊(duì)列中的報(bào)文就會(huì)由于得不到服務(wù)而“餓死”。

假設(shè)端口有 3 個(gè)采用PQ調(diào)度的隊(duì)列，分別為高優(yōu)先（High）隊(duì)列、中優(yōu)先（Medium） 隊(duì)列、和低優(yōu)先（Low）隊(duì)列，它們的優(yōu)先級(jí)依次降低。如圖，其中報(bào)文編號(hào)表示報(bào)文到達(dá)順序。

圖1 PQ調(diào)度

• RR（Round Robin）調(diào)度

RR調(diào)度采用輪詢的方式，對(duì)多個(gè)隊(duì)列進(jìn)行調(diào)度。RR以環(huán)形的方式輪詢多個(gè)隊(duì)列。 如果輪詢的隊(duì)列不為空，則從該隊(duì)列取走一個(gè)報(bào)文；如果該隊(duì)列為空，則直接跳過(guò)該隊(duì)列，調(diào)度器不等待。

圖2 RR調(diào)度

RR調(diào)度各個(gè)隊(duì)列之間沒(méi)有優(yōu)先級(jí)之分，都能夠有相等的概率得到調(diào)度。RR調(diào)度的缺點(diǎn)是：所有隊(duì)列無(wú)法體現(xiàn)優(yōu)先級(jí)，對(duì)于延遲敏感的關(guān)鍵業(yè)務(wù)和非關(guān)鍵業(yè)務(wù)無(wú)法得到區(qū)別對(duì)待，使得關(guān)鍵業(yè)務(wù)無(wú)法及時(shí)得到處理

• WRR（Weighted Round Robin）調(diào)度

加權(quán)輪詢WRR（Weighted Round Robin）調(diào)度主要解決RR不能設(shè)置權(quán)重的不足。 在輪詢的時(shí)候，WRR每個(gè)隊(duì)列享受的調(diào)度機(jī)會(huì)和該隊(duì)列的權(quán)重成比例。RR調(diào)度相當(dāng)于權(quán)值為 1 的WRR調(diào)度。 WRR的實(shí)現(xiàn)方法是為每個(gè)隊(duì)列設(shè)置一個(gè)計(jì)數(shù)器 Count，根據(jù)權(quán)重進(jìn)行初始化。每次 輪詢到一個(gè)隊(duì)列時(shí)，該隊(duì)列輸出一個(gè)報(bào)文且計(jì)數(shù)器減一。當(dāng)計(jì)數(shù)器為 0 時(shí)停止調(diào)度該隊(duì)列，但繼續(xù)調(diào)度其他計(jì)數(shù)器不為 0 的隊(duì)列。當(dāng)所有隊(duì)列的計(jì)數(shù)器都為 0 時(shí)，所有計(jì)數(shù)器重新根據(jù)權(quán)重初始化，開(kāi)始新一輪調(diào)度。在一個(gè)循環(huán)中，權(quán)重大的隊(duì)列被多次調(diào)度。

圖3 WRR調(diào)度

假設(shè)某端口有3個(gè)隊(duì)列采用WRR調(diào)度，為每個(gè)隊(duì)列配置一個(gè)權(quán)值，依次為50%、 25%、25%，詳細(xì)的調(diào)度過(guò)程如下： 首先計(jì)數(shù)器初始化：Count[1]=2，Count[2]=1，Count[3]= 1。

? 第 1 個(gè)輪詢： 從隊(duì)列 1 取出報(bào)文 1 發(fā)送，Count[1]=1；從隊(duì)列 2 取出報(bào)文 5 發(fā)送，Count[2]=0； 從隊(duì)列 3 取出報(bào)文 8 發(fā)送，Count[3]=0。
? 第 2 個(gè)輪詢： 從隊(duì)列 1 取出報(bào)文 2 發(fā)送，Count[1]=0；由于Count[2]=0，Count[3]=0，隊(duì)列 2 和隊(duì)列 3 不參與此輪調(diào)度。 此時(shí)，Count[1]=0，Count[2]=0，Count[3]=0，將計(jì)數(shù)器重新初始化：Count[1]=2， Count[2]=1，Count[3]= 1。
? 第 3 個(gè)輪詢：從隊(duì)列 1 取出報(bào)文 3 發(fā)送，Count[1]=1；從隊(duì)列 2 取出報(bào)文 6 發(fā)送，Count[2]=0； 從隊(duì)列 3 取出報(bào)文 9 發(fā)送，Count[3]=0。
? 第 4 個(gè)輪詢： 從隊(duì)列 1 取出報(bào)文 4 發(fā)送，Count[1]=0；由于Count[2]=0，Count[3]=0，隊(duì)列 2 和隊(duì)列 3 不參與此輪調(diào)度。 此時(shí)，Count[1]=0，Count[2]=0，Count[3]=0，將計(jì)數(shù)器重新初始化：Count[1]=2， Count[2]=1，Count[3]= 1。

從統(tǒng)計(jì)上看，各隊(duì)列中的報(bào)文流被調(diào)度的次數(shù)與該隊(duì)列的權(quán)值成正比，權(quán)值越大被調(diào)度的次數(shù)相對(duì)越多。如果該端口為100Mbps，則可以保證最低權(quán)重的隊(duì)列至少獲得25Mbit/s帶寬，避免了采用PQ調(diào)度時(shí)低優(yōu)先級(jí)隊(duì)列中的報(bào)文可能長(zhǎng)時(shí)間得不到服務(wù)的缺點(diǎn)。WRR對(duì)于空的隊(duì)列直接跳過(guò)，循環(huán)調(diào)度的周期變短，因此當(dāng)某個(gè)隊(duì)列流量小的時(shí)候，剩余帶寬能夠被其他隊(duì)列按照比例占用。

WRR調(diào)度有兩個(gè)缺點(diǎn)：

1. WRR調(diào)度按照?qǐng)?bào)文個(gè)數(shù)進(jìn)行調(diào)度，因此每個(gè)隊(duì)列沒(méi)有固定的帶寬，同等調(diào)度機(jī) 會(huì)下大尺寸報(bào)文獲得的實(shí)際帶寬要大于小尺寸報(bào)文獲得的帶寬。而用戶一般關(guān) 心的是帶寬。當(dāng)每個(gè)隊(duì)列的平均報(bào)文長(zhǎng)度相等或已知時(shí)，通過(guò)配置WRR權(quán)重， 用戶能夠獲得想要的帶寬；但是，當(dāng)隊(duì)列的平均報(bào)文長(zhǎng)度變化時(shí)，用戶就不能 通過(guò)配置WRR權(quán)重獲取想要的帶寬。
2. 低延時(shí)需求業(yè)務(wù)（如語(yǔ)音）得不到及時(shí)調(diào)度。

• DRR（Deficit Round Robin）調(diào)度

差分輪詢DRR（Deficit Round Robin）調(diào)度實(shí)現(xiàn)原理與RR調(diào)度基本相同。DRR與RR的區(qū)別是：RR調(diào)度是按照?qǐng)?bào)文個(gè)數(shù)進(jìn)行調(diào)度，而DRR是按照?qǐng)?bào)文長(zhǎng)度進(jìn)行調(diào)度。

DRR為每個(gè)隊(duì)列設(shè)置一個(gè)計(jì)數(shù)器Deficit，Deficit 初始化為一次調(diào)度允許的最大字節(jié)數(shù)， 一般為接口MTU。每次輪詢到一個(gè)隊(duì)列時(shí)，該隊(duì)列輸出一個(gè)報(bào)文且計(jì)數(shù)器Deficit 減去報(bào)文長(zhǎng)度。如果報(bào)文長(zhǎng)度超過(guò)了隊(duì)列的調(diào)度能力，DRR調(diào)度允許Deficit 出現(xiàn)負(fù)值，以保證長(zhǎng)報(bào)文也能夠得到調(diào)度。但下次輪循調(diào)度時(shí)該隊(duì)列將不會(huì)被調(diào)度。當(dāng)計(jì)數(shù)器為 0 或 負(fù)數(shù)時(shí)停止調(diào)度該隊(duì)列，但繼續(xù)調(diào)度其他計(jì)數(shù)器為正數(shù)的隊(duì)列。當(dāng)所有隊(duì)列的Deficit 都為 0 或負(fù)數(shù)時(shí)，將所有隊(duì)列的Deficit 計(jì)數(shù)器加上初始值，開(kāi)始新一輪調(diào)度。

假設(shè)某端口MTU=150Bytes，有 2 個(gè)隊(duì)列Q1和Q2采用DRR調(diào)度，Q1 隊(duì)列中有多個(gè) 200Bytes 的長(zhǎng)報(bào)文，Q2隊(duì)列中有多個(gè)100Bytes 的端報(bào)文，則調(diào)度過(guò)程如圖 4 所示。

圖4 DRR調(diào)度

由圖4可以看出，經(jīng)過(guò)第 1~6 輪DRR調(diào)度，Q1隊(duì)列被調(diào)出了3個(gè)200Bytes 的報(bào)文， Q2隊(duì)列被調(diào)出了6個(gè)100Bytes 的報(bào)文。從長(zhǎng)期的統(tǒng)計(jì)看，Q1和 Q2 的實(shí)際輸出帶寬比 是 1:1，為公平的比例。DRR調(diào)度避免了采用PQ調(diào)度時(shí)低優(yōu)先級(jí)隊(duì)列中的報(bào)文可能長(zhǎng)時(shí)間得不到服務(wù)的缺點(diǎn)。 但是，DRR調(diào)度不能設(shè)置權(quán)重，且也具有低延時(shí)需求業(yè)務(wù)（如語(yǔ)音）得不到及時(shí)調(diào)度的缺點(diǎn)。

• DWRR（Deficit Weighted Round Robin）調(diào)度

差分加權(quán)輪詢DWRR（Deficit Weighted Round Robin）調(diào)度主要解決DRR不能設(shè)置權(quán)重的不足。DRR調(diào)度相當(dāng)于權(quán)值為 1 的DWRR調(diào)度。 DWRR為每個(gè)隊(duì)列設(shè)置一個(gè)計(jì)數(shù)器Deficit，Deficit 初始化為Weight * MTU。每次輪詢到一個(gè)隊(duì)列時(shí)，該隊(duì)列輸出一個(gè)報(bào)文且計(jì)數(shù)器Deficit 減去報(bào)文長(zhǎng)度。當(dāng)計(jì)數(shù)器為 0 時(shí)停止調(diào)度該隊(duì)列，但繼續(xù)調(diào)度其他計(jì)數(shù)器不為 0 的隊(duì)列。當(dāng)所有隊(duì)列的計(jì)數(shù)器都為 0 時(shí)，所有計(jì)數(shù)器的Deficit 都加上Weight*MTU，開(kāi)始新一輪調(diào)度。

圖5 DWRR調(diào)度

假設(shè)某端口MTU=150Bytes，有 2 個(gè)隊(duì)列Q1和Q2采用DRR調(diào)度，Q1 隊(duì)列中有 多個(gè) 200Bytes 的長(zhǎng)報(bào)文，Q2隊(duì)列中有多個(gè) 100Bytes 的端報(bào)文，Q1和Q2配置權(quán)重 比為weight1:weight2=2:1。則DWRR調(diào)度過(guò)程如圖 2-37。

1. 第一輪調(diào)度 Deficit[1] =weight1* MTU=300，Deficit[2] = weight2* MTU=150Bytes，從 Q1 隊(duì) 列取出 200Bytes 報(bào)文發(fā)送，從Q2隊(duì)列取出 100Bytes 發(fā)送；發(fā)送后，Deficit[1] = 100，Deficit[2] =50。
2. 第二輪調(diào)度
   從 Q1 隊(duì)列取出 200Bytes 報(bào)文發(fā)送，從Q2隊(duì)列取出 100Bytes 發(fā)送；發(fā)送后， Deficit[1] = -100，Deficit[2] =-50。
3. 第三輪調(diào)度
   此時(shí)兩個(gè)隊(duì)列都為負(fù)，因此，Deficit[1] = Deficit[1]+weight1* MTU=-100+2150=200，Deficit[2] = Deficit[2]+weight2 MTU=-50+1*150=100。
   從 Q1 隊(duì)列取出 200Bytes 報(bào)文發(fā)送，從Q2隊(duì)列取出 100Bytes 發(fā)送；發(fā)送后， Deficit [1] = 0，Deficit[2] = 0。

由上圖可以看出，經(jīng)過(guò)第 1~3 輪DWRR調(diào)度，Q1隊(duì)列被調(diào)出了3個(gè)200Bytes 的 報(bào)文，Q2 隊(duì)列被調(diào)出了3個(gè)100Bytes 的報(bào)文。從長(zhǎng)期的統(tǒng)計(jì)看，Q1和Q2的實(shí)際 輸出帶寬比是 2:1，與權(quán)重比相符。

DWRR調(diào)度避免了采用PQ調(diào)度時(shí)低優(yōu)先級(jí)隊(duì)列中的報(bào)文可能長(zhǎng)時(shí)間得不到服務(wù)的缺點(diǎn)，也避免了各隊(duì)列報(bào)文長(zhǎng)度不等或變化較大時(shí)，WRR調(diào)度不能按配置比例分 配帶寬資源的缺點(diǎn)。但是，DWRR調(diào)度也具有低延時(shí)需求業(yè)務(wù)（如語(yǔ)音）得不到及時(shí)調(diào)度的缺點(diǎn)。

• WFQ（Weighted Fair Queuing）調(diào)度

加權(quán)公平隊(duì)列WFQ（Weighted Fair Queuing）調(diào)度是按隊(duì)列權(quán)重來(lái)分配每個(gè)流應(yīng)占有出口的帶寬。同時(shí)，為了使得帶寬分配更加“公平”，WFQ 以 bit 為單位進(jìn)行調(diào)度，類(lèi)似于圖 6的 bit-by-bit 調(diào)度模型

圖6 WFQ調(diào)度

Bit-by-bit 調(diào)度模型可以完全按照權(quán)重分配帶寬，防止長(zhǎng)報(bào)文比短報(bào)文獲得更多帶寬，從 而減少大小報(bào)文共存時(shí)的時(shí)延抖動(dòng)。但Bit-by-bit 調(diào)度模型只是理想化的模型，實(shí)際上，華為交換機(jī)實(shí)現(xiàn)的WFQ是按照一定的粒度，例如 256B、1KB，或其他粒度，具體按何種粒度，與單板類(lèi)型相關(guān)。
WFQ的優(yōu)點(diǎn)主要有以下幾點(diǎn)：

• 不同的隊(duì)列獲得公平的調(diào)度機(jī)會(huì)，從總體上均衡各個(gè)流的延遲。
• 短報(bào)文和長(zhǎng)報(bào)文獲得公平的調(diào)度：如果不同隊(duì)列間同時(shí)存在多個(gè)長(zhǎng)報(bào)文和短報(bào)文等 待發(fā)送，讓短報(bào)文優(yōu)先獲得調(diào)度，從而在總體上減少各個(gè)流的報(bào)文間的抖動(dòng)。
• 從統(tǒng)計(jì)上看，權(quán)重越小，所分得的帶寬越少。權(quán)重越大，所分得的帶寬越多。