一種在大容量交換中可以保證QoS的隊(duì)列調(diào)度器設(shè)計(jì)與實(shí)現(xiàn)*

錢鵬飛，喬廬峰，陳慶華

（中國(guó)人民解放軍陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007）

0 引 言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)業(yè)務(wù)流量迅速增加，用戶對(duì)網(wǎng)絡(luò)帶寬的需求已經(jīng)遠(yuǎn)遠(yuǎn)超出了現(xiàn)有網(wǎng)絡(luò)的交換容量。交換機(jī)作為通信網(wǎng)絡(luò)中至關(guān)重要的設(shè)備，不僅需要進(jìn)行路由交換、網(wǎng)絡(luò)接入等工作，還要承載語(yǔ)音、多媒體通信等諸多數(shù)據(jù)容量較大的復(fù)雜通信業(yè)務(wù)?？梢哉f(shuō)，交換機(jī)的交換容量決定了整個(gè)通信網(wǎng)絡(luò)的性能。為了保證骨干網(wǎng)絡(luò)的正常運(yùn)行，“大容量”交換機(jī)的研究被提上日程[1]。

典型的數(shù)據(jù)交換模型主要由隊(duì)列管理器、隊(duì)列調(diào)度器及交換結(jié)構(gòu)組成，其中隊(duì)列調(diào)度器起著交通樞紐的作用。它的性能直接決定了整個(gè)通信過程的質(zhì)量。圖1是一種常見的大容量交換結(jié)構(gòu)。該交換結(jié)構(gòu)在輸入緩沖區(qū)建立VOQ隊(duì)列，以解決隊(duì)頭阻塞問題；在輸出緩沖區(qū)使用結(jié)構(gòu)較為簡(jiǎn)單的FIFO隊(duì)列。兩者之間采用大容量的Crossbar進(jìn)行定長(zhǎng)或變長(zhǎng)分組交換。通常采用光背板或高速串并/并串變換器（Serial-Deserial，SerDes）相連接，有利于實(shí)現(xiàn)高速片間互聯(lián)以及獲得較高的加速比，以提高系統(tǒng)吞吐率[2]。

圖1 大容量交換結(jié)構(gòu)模型

本文針對(duì)該交換結(jié)構(gòu)設(shè)計(jì)了一個(gè)調(diào)度器。該交換結(jié)構(gòu)將輸入緩沖區(qū)分為單/多播隊(duì)列，每個(gè)隊(duì)列各有16個(gè)VOQ且每個(gè)VOQ均劃分了8個(gè)優(yōu)先級(jí)（其中0為高優(yōu)先級(jí)隊(duì)列HP，1-7為低優(yōu)先級(jí)隊(duì)列LP），因此設(shè)計(jì)的調(diào)度器需要對(duì)這256個(gè)隊(duì)列進(jìn)行合理調(diào)度，并保證高優(yōu)先級(jí)隊(duì)列的服務(wù)質(zhì)量。整個(gè)交換結(jié)構(gòu)如圖2所示。

圖2 交換結(jié)構(gòu)

1 調(diào)度算法

為了給不同的業(yè)務(wù)流提供相應(yīng)的QoS保證，在設(shè)計(jì)調(diào)度器時(shí)，需要選擇合理的調(diào)度算法。在硬件實(shí)現(xiàn)過程中，不僅要求算法可以滿足功能需求，還要求簡(jiǎn)單高效。目前的調(diào)度算法可以分為以下幾類：基于靜態(tài)優(yōu)先級(jí)、基于輪循、基于廣義處理器共享模型、基于時(shí)延、基于服務(wù)曲線以及最大匹配類算法。其中，應(yīng)用最廣泛的是基于輪詢的調(diào)度算法，主要有以下幾種：公平輪詢（Round Robin，RR）、權(quán)重輪詢（Weighted Round Robin，WRR）和赤字輪詢（Deficit Round Robin，DRR）[3-5]。

1.1 RR算法

RR算法公平地對(duì)待每個(gè)隊(duì)列并為每個(gè)隊(duì)列平均分配鏈路帶寬。這在不考慮優(yōu)先級(jí)的情況下非常合理，但對(duì)于高優(yōu)先級(jí)業(yè)務(wù)的數(shù)據(jù)流則不能保證其服務(wù)質(zhì)量。

1.2 WRR算法

WRR算法給每個(gè)隊(duì)列賦予一個(gè)加權(quán)值wi和計(jì)數(shù)器Ci，如圖3所示。計(jì)數(shù)器的初始值就是加權(quán)值，代表一次完整循環(huán)隊(duì)列被服務(wù)的分組數(shù)。輪詢時(shí)，計(jì)數(shù)器不為零的隊(duì)列允許發(fā)送一個(gè)分組，并把計(jì)數(shù)器減1。當(dāng)所有隊(duì)列的計(jì)數(shù)器均為零時(shí)，將所有的計(jì)數(shù)器重置為加權(quán)值。這種算法可以為不同優(yōu)先級(jí)的隊(duì)列分配相應(yīng)的帶寬，既保證了高優(yōu)先級(jí)隊(duì)列的QoS，又能避免低優(yōu)先級(jí)隊(duì)列“餓死”現(xiàn)象。但是，這種方案存在分組長(zhǎng)度不同帶來(lái)的不公平，而且只能針對(duì)特定端口保證高優(yōu)先級(jí)隊(duì)列的QoS。

圖3 WRR算法

1.3 DRR算法

DRR算法以字節(jié)為單位為每個(gè)隊(duì)列分配帶寬配額和計(jì)數(shù)器，計(jì)數(shù)器的初始化值即為帶寬配額，該配額對(duì)應(yīng)隊(duì)列的服務(wù)速率。調(diào)度時(shí)，如果待發(fā)送分組的長(zhǎng)度小于或等于計(jì)數(shù)器值，允許發(fā)送，并把計(jì)數(shù)器減去此分組的長(zhǎng)度值；否則，不允許發(fā)送，并該計(jì)數(shù)器的值累計(jì)到下一次的循環(huán)。這種算法很大程度上解決了分組長(zhǎng)度帶來(lái)的不公平性，但不能很好地滿足業(yè)務(wù)的延時(shí)特性。

綜合以上幾種輪詢算法的優(yōu)缺點(diǎn)，本課題設(shè)計(jì)的隊(duì)列調(diào)度器采用一種改進(jìn)的WRR調(diào)度算法——全局動(dòng)態(tài)權(quán)重輪詢算法（Global Dynamic WRR，GDWRR）。該算法為每個(gè)隊(duì)列賦予了一個(gè)加權(quán)值wi和一個(gè)信用值Ci，同時(shí)還有一個(gè)全局的連接消耗值Cost，如圖4所示。調(diào)度時(shí)，如果某個(gè)隊(duì)列非空，則將該隊(duì)列的信用值Ci加上wi，然后與Cost進(jìn)行比較。如果Ci大于或等于Cost，則該隊(duì)列滿足發(fā)送條件，隊(duì)列i發(fā)送數(shù)據(jù)，同時(shí)Ci減去Cost；否則，Ci保持不變。Cost值是根據(jù)當(dāng)前所有非空隊(duì)列的最大加權(quán)值確定的，每次調(diào)度時(shí)都會(huì)根據(jù)當(dāng)前隊(duì)列狀態(tài)進(jìn)行更新，從而避免了某些隊(duì)列出現(xiàn)“餓死”現(xiàn)象，既在一定程度上保證了調(diào)度的公平性，又能保證高優(yōu)先級(jí)隊(duì)列的QoS，同時(shí)為保證全局QoS提供了可能。

圖4 GDWRR算法

2 調(diào)度器電路設(shè)計(jì)

整個(gè)調(diào)度器需要實(shí)現(xiàn)的功能如下。

（1）為每個(gè)VOQ中優(yōu)先級(jí)為0的高優(yōu)先級(jí)非空隊(duì)列發(fā)送連接請(qǐng)求HP_CRQ，按GDWRR算法，從每個(gè)VOQ中優(yōu)先級(jí)為1-7的低優(yōu)先級(jí)非空隊(duì)列選擇滿足要求的隊(duì)列，并發(fā)送連接請(qǐng)求LP_CRQ；

（2）中間級(jí)Crossbar單元對(duì)發(fā)送的連接請(qǐng)求進(jìn)行仲裁后返回HP_ACK和LP_ACK，由調(diào)度器對(duì)允許發(fā)送數(shù)據(jù)的VOQ進(jìn)行隊(duì)列選擇，并發(fā)出數(shù)據(jù)讀取請(qǐng)求dpram_rd_req。

圖5是隊(duì)列調(diào)度器的框架圖，主要由CPU接口模塊、單/多播隊(duì)列調(diào)度模塊和單多播帶寬分配模塊組成。

圖5 隊(duì)列調(diào)度器框架

2.1 CPU接口模塊

為了實(shí)現(xiàn)CPU對(duì)不同優(yōu)先級(jí)隊(duì)列的權(quán)重配置，調(diào)度器模塊中加入了CPU接口模塊。主要功能有：

（1）系統(tǒng)復(fù)位后，對(duì)各隊(duì)列的權(quán)重值進(jìn)行初始化；

（2）CPU發(fā)出指令后，對(duì)其指令進(jìn)行格式轉(zhuǎn)換與傳遞，以便權(quán)重分配模塊讀取配置信息。

CPU接口模塊與CPU之間采用異步總線連接，狀態(tài)機(jī)根據(jù)CPU寫進(jìn)來(lái)的地址進(jìn)行數(shù)據(jù)格式轉(zhuǎn)換后寫入內(nèi)部緩存區(qū)。內(nèi)部緩存分為權(quán)重信息緩存和指針緩存，分別用來(lái)存儲(chǔ)權(quán)重配置信息和與權(quán)重配置信息相對(duì)應(yīng)的長(zhǎng)度指針。

2.2 單/多播隊(duì)列模塊

單/多播隊(duì)列調(diào)度模塊的功能是用全局動(dòng)態(tài)輪詢調(diào)度算法GDWRR對(duì)隊(duì)列管理器中的128個(gè)VOQ隊(duì)列進(jìn)行調(diào)度。兩個(gè)模塊原理相同，下面僅對(duì)單播隊(duì)列模塊進(jìn)行說(shuō)明。模塊內(nèi)部主要包括權(quán)重分配模塊、連接請(qǐng)求模塊和隊(duì)列選擇模塊。各模塊功能如下：

（1）權(quán)重分配模塊：為不同的優(yōu)先級(jí)隊(duì)列分配調(diào)度所需的加權(quán)值，以提供不同的QoS保證；

（2）連接請(qǐng)求模塊：根據(jù)隊(duì)列管理器中的排隊(duì)規(guī)則，按照GDWRR算法進(jìn)行連接請(qǐng)求調(diào)度，得到調(diào)度結(jié)果后發(fā)往單多播帶寬分配模塊進(jìn)行帶寬分配；

（3）隊(duì)列選擇模塊：根據(jù)Crossbar交換單元仲裁的結(jié)果，在指定的VOQ內(nèi)進(jìn)行隊(duì)列選擇，然后將選擇結(jié)果發(fā)往存儲(chǔ)單元進(jìn)行數(shù)據(jù)提取。

2.2.1 權(quán)重分配模塊電路

該模塊按照CPU寫進(jìn)來(lái)的隊(duì)列權(quán)重配置信息對(duì)各個(gè)隊(duì)列進(jìn)行權(quán)重配置。系統(tǒng)復(fù)位后，權(quán)重分配模塊會(huì)對(duì)CPU接口模塊中的指針緩存進(jìn)行實(shí)時(shí)監(jiān)測(cè)。當(dāng)檢測(cè)到指針緩存區(qū)內(nèi)部有數(shù)據(jù)時(shí)，權(quán)重分配電路會(huì)讀出指針，并根據(jù)指針信息讀出相應(yīng)的數(shù)據(jù)；如果檢測(cè)不到數(shù)據(jù)，則繼續(xù)等待。讀出數(shù)據(jù)后，狀態(tài)機(jī)會(huì)檢索數(shù)據(jù)中隊(duì)列號(hào)字段的權(quán)重分配信息，從而完成隊(duì)列的權(quán)重分配。

2.2.2 連接請(qǐng)求模塊電路

根據(jù)隊(duì)列管理器的排隊(duì)規(guī)則，每個(gè)VOQ劃分了8個(gè)優(yōu)先級(jí)，其中0隊(duì)列為HP隊(duì)列，1-7隊(duì)列為不同等級(jí)的LP隊(duì)列。該模塊需要根據(jù)當(dāng)前隊(duì)列狀態(tài)信息進(jìn)行調(diào)度，產(chǎn)生連接請(qǐng)求。在進(jìn)行連接請(qǐng)求時(shí)，如果HP隊(duì)列中有數(shù)據(jù)，則發(fā)出高優(yōu)先級(jí)連接請(qǐng)求HP_CRQ；如果7個(gè)LP隊(duì)列中有排隊(duì)等待的數(shù)據(jù)，則采用GDWRR算法對(duì)其進(jìn)行調(diào)度選擇，判斷LP業(yè)務(wù)是否滿足發(fā)送請(qǐng)求的條件,如果滿足條件，則發(fā)送低優(yōu)先級(jí)連接請(qǐng)求LP_CRQ。根據(jù)隊(duì)列結(jié)構(gòu)可知，每個(gè)VOQ均會(huì)產(chǎn)生1個(gè)HP與1個(gè)LP連接請(qǐng)求，所以16個(gè)VOQ共產(chǎn)生16個(gè)HP_CRQ和16個(gè)LP_CRQ。

表1是連接請(qǐng)求調(diào)度的一個(gè)例子（加粗部分表示經(jīng)調(diào)度后選擇的VOQ隊(duì)列），調(diào)度算法中的關(guān)鍵變量如表1所示。

表1 連接請(qǐng)求模塊中GDWRR調(diào)度算法示例

（1）花銷（Cost）。這是一個(gè)全局變量，只有當(dāng)VOQ的信用值達(dá)到或超過該值時(shí)，連接請(qǐng)求才被允許。本設(shè)計(jì)將每個(gè)VOQ中非空LP隊(duì)列中的最大權(quán)重值設(shè)為該VOQ的Costi，所有VOQ中最大的Costi被設(shè)為該連接周期的全局Cost。這樣可以根據(jù)隊(duì)列的狀態(tài)實(shí)時(shí)更新門限值，保證隊(duì)列中排隊(duì)的數(shù)據(jù)能夠及時(shí)得到服務(wù)，并避免低優(yōu)先級(jí)隊(duì)列“餓死”。

（2）信用值（Credit）。每個(gè)VOQ都有一個(gè)動(dòng)態(tài)的信用值Crediti。在某個(gè)信元周期內(nèi)，如果Crediti值低于Cost，則進(jìn)行累加操作，累加量為該VOQ的Costi。一旦信用值超過了Cost門限，VOQ就可以發(fā)出連接請(qǐng)求，同時(shí)信用值會(huì)減去Cost。

（3）權(quán)重（w）。這是由CPU分配給每個(gè)LP隊(duì)列的靜態(tài)值，用于在不同的隊(duì)列間分配帶寬。

2.2.3 隊(duì)列選擇模塊電路

中間級(jí)Crossbar交換單元返回連接請(qǐng)求仲裁結(jié)果后，由隊(duì)列選擇模塊對(duì)指定的VOQ進(jìn)行隊(duì)列調(diào)度選擇。調(diào)度規(guī)則：如果HP隊(duì)列中有數(shù)據(jù)請(qǐng)求，則直接選擇HP隊(duì)列進(jìn)行數(shù)據(jù)發(fā)送；若HP隊(duì)列中沒有數(shù)據(jù)請(qǐng)求，則采用GDWRR調(diào)度算法從7個(gè)LP隊(duì)列中選擇一個(gè)隊(duì)列進(jìn)行數(shù)據(jù)發(fā)送。與連接請(qǐng)求模塊的區(qū)別是，該算法針對(duì)特定的VOQ進(jìn)行調(diào)度，因此每個(gè)LP隊(duì)列均有各自的信用值。表2是隊(duì)列選擇調(diào)度的一個(gè)例子（加粗部分表示經(jīng)調(diào)度后選擇的隊(duì)列）。

表2 隊(duì)列選擇模塊中GDWRR調(diào)度算法示例

2.3 單多播帶寬分配模塊電路

當(dāng)某個(gè)VOQ同時(shí)有單播和多播兩個(gè)連接請(qǐng)求時(shí)，需要按照預(yù)先配置的權(quán)重等級(jí)進(jìn)行帶寬分配，即每個(gè)VOQ只能發(fā)單播或多播信元。單、多播隊(duì)列調(diào)度模塊產(chǎn)生的32個(gè)HP_CRQ和32個(gè)LP_CRQ連接請(qǐng)求，最終變?yōu)?6個(gè)HP_CRQ和16個(gè)LP_CRQ，然后發(fā)往中間級(jí)crossbar進(jìn)行仲裁。權(quán)重等級(jí)可在0到31之間選擇，等級(jí)0表示配置單播絕對(duì)優(yōu)先于多播，等級(jí)31表示配置多播絕對(duì)優(yōu)先于單播。

3 仿真結(jié)果與分析

該調(diào)度器的實(shí)現(xiàn)選用Xilinx的xc6vlx240tFPGA，開發(fā)環(huán)境為ISE 14.7，電路模塊采用Verilog HDL編程，并用ModelSim SE 10.2c進(jìn)行仿真分析。關(guān)鍵電路模塊仿真圖如下所述。

3.1 連接請(qǐng)求模塊仿真分析

圖6是單播隊(duì)列調(diào)度模塊中的連接請(qǐng)求模塊仿真時(shí)序圖。單播隊(duì)列中共有16個(gè)VOQ隊(duì)列，每個(gè)隊(duì)列分為8個(gè)優(yōu)先級(jí)，所以需要對(duì)128個(gè)隊(duì)列的連接請(qǐng)求進(jìn)行調(diào)度。

圖6 連接請(qǐng)求仿真時(shí)序圖

仿真開始前，所有VOQ的Crediti與Costi經(jīng)初始化后均為0，VOQ中對(duì)應(yīng)7個(gè)低優(yōu)先級(jí)隊(duì)列LP0～LP6的權(quán)重w0～w6配置為7～1；信號(hào)i_reg位寬為128位，代表16個(gè)VOQ中128個(gè)單播隊(duì)列的非空狀態(tài)信息；信號(hào)i_reg_dv為1時(shí)表示數(shù)據(jù)有效，可以進(jìn)行連接請(qǐng)求調(diào)度。i_reg的輸入值為h0506，表示VOQ0的LP0、LP1以及VOQ1的HP、LP1需要進(jìn)行連接請(qǐng)求調(diào)度。由調(diào)度規(guī)則可知，VOQ1將保證HP隊(duì)列優(yōu)先調(diào)度，VOQ0則按照GDWRR算法對(duì)兩個(gè)LP隊(duì)列進(jìn)行選擇。最后，得到的仿真結(jié)果是給VOQ1發(fā)送一個(gè)高優(yōu)先級(jí)請(qǐng)求，給VOQ0發(fā)送一個(gè)低優(yōu)先級(jí)請(qǐng)求，滿足優(yōu)先保證高優(yōu)先級(jí)隊(duì)列的QoS的要求。

3.2 隊(duì)列選擇模塊仿真分析

隊(duì)列選擇模塊是在中間級(jí)交換單元給出仲裁結(jié)果后，在特定的VOQ中對(duì)單播業(yè)務(wù)的八個(gè)優(yōu)先級(jí)隊(duì)列進(jìn)行隊(duì)列選擇操作，圖7是該模塊的仿真時(shí)序圖。仿真開始前，所有的LP隊(duì)列的信用值初始化為0，信號(hào)ack_dv是調(diào)度開始的指示位。仿真輸入的激勵(lì)信號(hào)LP_ACK是1，表示VOQ0中的LP隊(duì)列可以進(jìn)行調(diào)度。由于該VOQ中有2個(gè)LP隊(duì)列請(qǐng)求調(diào)度，因此需要對(duì)這2個(gè)隊(duì)列用GDWRR算法進(jìn)行調(diào)度。最后，得到的仿真結(jié)果是選擇VOQ0的LP0進(jìn)行數(shù)據(jù)發(fā)送。

圖7 數(shù)據(jù)讀取仿真波形

4 結(jié) 語(yǔ)

本文針對(duì)大容量交換結(jié)構(gòu)設(shè)計(jì)了一個(gè)隊(duì)列調(diào)度器，給出了具體的結(jié)構(gòu)框圖和關(guān)鍵模塊的仿真分析。仿真結(jié)果表明，該電路實(shí)現(xiàn)了對(duì)單多播業(yè)務(wù)共256個(gè)隊(duì)列的有效調(diào)度，既保證了HP隊(duì)列的QoS，降低了關(guān)鍵業(yè)務(wù)的時(shí)延，又避免了LP隊(duì)列的“餓死”現(xiàn)象，同時(shí)為中間級(jí)模塊的全局調(diào)度提供了可能。下一步將結(jié)合前級(jí)隊(duì)列管理器和中間級(jí)crossbar做進(jìn)一步的仿真測(cè)試，檢驗(yàn)該隊(duì)列調(diào)度器，以保證不同業(yè)務(wù)QoS的能力。