基于多級隊(duì)列調(diào)度模型的研究

王 琳，吉 萌

(1.光纖通信技術(shù)和網(wǎng)絡(luò)國家重點(diǎn)實(shí)驗(yàn)室，湖北武漢430074;2.武漢烽火網(wǎng)絡(luò)有限責(zé)任公司，湖北武漢430074)

隨著用戶數(shù)量的持續(xù)增長和網(wǎng)絡(luò)業(yè)務(wù)的豐富化，傳統(tǒng)的QoS已無法保證每個用戶的業(yè)務(wù)質(zhì)量。而層次化QoS(Hierarchy QoS)，通過建立多級的調(diào)度器，把多個端口的QoS通過樹形結(jié)構(gòu)來進(jìn)行調(diào)度，可實(shí)現(xiàn)多業(yè)務(wù)多用戶的靈活調(diào)度，提供更加精細(xì)的服務(wù)。本文以某高端路由器為背景，研究以太網(wǎng)多級隊(duì)列調(diào)度的模型和算法。

1 多級隊(duì)列調(diào)度原理

1.1 分級調(diào)度依據(jù)

層次化QoS的核心指導(dǎo)思想是QoS處理能真實(shí)體現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和業(yè)務(wù)轉(zhuǎn)發(fā)路徑［1］。根據(jù)DSL論壇的TR-059協(xié)議定義的層次化QoS的基本模型，調(diào)度器的層次可分為五層:Session Scheduler→VC Scheduler→VC Group Scheduler→VP Scheduler→ Physical Port Scheduler［2］。調(diào)度的根節(jié)點(diǎn)為Physical Port Scheduler，是流量的匯聚點(diǎn)，葉子節(jié)點(diǎn)為Session Scheduler的調(diào)度隊(duì)列，功能是確定輸出端口在下一個時刻，從哪個隊(duì)列中輸出數(shù)據(jù)包［3］。分支節(jié)點(diǎn)為中間的各級調(diào)度器。TM(Traffic Management)調(diào)度器的作用是決定數(shù)據(jù)包將從哪一個隊(duì)列中傳送，調(diào)度節(jié)點(diǎn)是其一個重要的模塊。父調(diào)度節(jié)點(diǎn)和其所屬的子節(jié)點(diǎn)為一個調(diào)度單元，作用是完成調(diào)度的配置及策略。分層依據(jù)包括端口(LAN、WAN)、VLAN、服務(wù)(邏輯概念)、COS/DSCP/TOS、ETH Type、IP 地址、TCP/UDP 端口號等［4］。

1.2 調(diào)度節(jié)點(diǎn)

調(diào)度節(jié)點(diǎn)的處理包括調(diào)度邏輯和狀態(tài)計(jì)算。調(diào)度邏輯可以通過改寫該調(diào)度節(jié)點(diǎn)的寄存器和子調(diào)度節(jié)點(diǎn)的寄存器進(jìn)行配置。狀態(tài)計(jì)算邏輯輸入包括整形器的狀態(tài)、所選擇的子調(diào)度節(jié)點(diǎn)(winner節(jié)點(diǎn))和本地的配置，可將輸入轉(zhuǎn)換成從當(dāng)前的調(diào)度節(jié)點(diǎn)傳遞到其父調(diào)度節(jié)點(diǎn)的調(diào)度參數(shù)。狀態(tài)計(jì)算邏輯的輸出有節(jié)點(diǎn)的可利用性、調(diào)度的優(yōu)先級和傳播的優(yōu)先級。節(jié)點(diǎn)的可利用性是指該節(jié)點(diǎn)可用來傳輸數(shù)據(jù);調(diào)度的優(yōu)先級是指父調(diào)度節(jié)點(diǎn)調(diào)度優(yōu)先級，即使用哪個調(diào)度器的調(diào)度邏輯，根據(jù)其選擇子調(diào)度節(jié)點(diǎn)。傳播的優(yōu)先級是指一旦一個子調(diào)度節(jié)點(diǎn)被當(dāng)前的調(diào)度節(jié)點(diǎn)的調(diào)度邏輯選擇，子調(diào)度節(jié)點(diǎn)將優(yōu)先級水平傳播到父調(diào)度節(jié)點(diǎn)。傳播優(yōu)先級也是處理用戶調(diào)度層(subscriber)時延敏感數(shù)據(jù)流量的一種方法。

1.3 調(diào)度單元

調(diào)度單元包括狀態(tài)寄存器、配置寄存器和子隊(duì)列寄存器。調(diào)度單元的隊(duì)列狀態(tài)和調(diào)度狀態(tài)存放在狀態(tài)寄存器中。隊(duì)列狀態(tài)是指當(dāng)前各個隊(duì)列的數(shù)據(jù)情況，即在調(diào)度過程中隊(duì)列中有無數(shù)據(jù)或者有多少數(shù)據(jù);調(diào)度狀態(tài)的作用可以根據(jù)上一次調(diào)度策略的結(jié)果作為本次調(diào)度的依據(jù)。如配置了調(diào)度策略RR后，可將上一次輪詢后的隊(duì)列狀態(tài)作為這次調(diào)度的依據(jù)。配置寄存器可以配置調(diào)度策略為SP、RR、WRR，以及調(diào)度權(quán)重weight的值。

1.4 轉(zhuǎn)發(fā)類

轉(zhuǎn)發(fā)類(ForwardingClass)是調(diào)度策略樹中的一個調(diào)度實(shí)體，對應(yīng)于樹中的葉子節(jié)點(diǎn)。一個轉(zhuǎn)發(fā)類與一個調(diào)度隊(duì)列相對應(yīng)。根據(jù)設(shè)置的映射關(guān)系，報(bào)文會進(jìn)入不同的調(diào)度隊(duì)列。系統(tǒng)共有4 種預(yù)定義轉(zhuǎn)發(fā)類，即 BE，AF，EF，NC［4］，與該 4 種轉(zhuǎn)發(fā)類對應(yīng)的參數(shù)信息將決定調(diào)度隊(duì)列的行為。BE(BestEffort)對應(yīng)的業(yè)務(wù)類型是盡力而為的業(yè)務(wù)，如普通網(wǎng)頁瀏覽;AF(AssuredForwarding)對應(yīng)傳輸質(zhì)量有保障的業(yè)務(wù)，如VPN、數(shù)據(jù)報(bào)文的傳輸;EF(ExpeditedForwarding)對應(yīng)對延時/抖動敏感的業(yè)務(wù)，如IP語音、IPTV報(bào)文的傳輸;NC(NetworkControl)表示轉(zhuǎn)發(fā)業(yè)務(wù)具有最高優(yōu)先級，如網(wǎng)絡(luò)控制報(bào)文的傳輸。

2 多級隊(duì)列調(diào)度模型及流程

2.1 多級隊(duì)列調(diào)度模型

以五級調(diào)度為例，如圖1所示，數(shù)據(jù)包存儲在大小為64×103的FIFO隊(duì)列，即session隊(duì)列中，大小為64×103的session隊(duì)列映射到16×103的A級節(jié)點(diǎn)，1×103～16×103的A級節(jié)點(diǎn)映射到4×103的B級節(jié)點(diǎn)，1×103～4×103的B級節(jié)點(diǎn)將映射到512個C級節(jié)點(diǎn)，1～512個C級節(jié)點(diǎn)映射到56個端口，即根節(jié)點(diǎn)。對于每個根節(jié)點(diǎn)端口，B和C級節(jié)點(diǎn)對應(yīng)于邏輯接口和服務(wù)，A級節(jié)點(diǎn)對應(yīng)于用戶，隊(duì)列對應(yīng)于各種服務(wù)應(yīng)用。調(diào)度器的層次決定了HQOS能否應(yīng)用到拓?fù)浣Y(jié)構(gòu)更復(fù)雜的情況，層次越多，可以應(yīng)用的場合越多，可提供的服務(wù)越精細(xì)。對于調(diào)度層次不需要五級的調(diào)度，A級和B級可以配置成透明的虛節(jié)點(diǎn)，即通過禁用需要設(shè)置成透明節(jié)點(diǎn)的所有整形和調(diào)度特征，并連接父節(jié)點(diǎn)和孩子層節(jié)點(diǎn)到透明節(jié)點(diǎn)。

調(diào)度節(jié)點(diǎn)在子節(jié)點(diǎn)中執(zhí)行調(diào)度，一個或多個子節(jié)點(diǎn)可以映射到一個父節(jié)點(diǎn)。子節(jié)點(diǎn)到父節(jié)點(diǎn)之間的映射是靈活的。整個的調(diào)度過程從隊(duì)列級別的調(diào)度開始，隊(duì)列級的調(diào)度可以獲取隊(duì)列的狀態(tài)，確定配置的三重信息(資格、調(diào)度優(yōu)先級和傳播的優(yōu)先級)，并將配置信息傳播到其父調(diào)度節(jié)點(diǎn)(A級節(jié)點(diǎn))。

圖1 五級調(diào)度模型結(jié)構(gòu)

通過配置某一層節(jié)點(diǎn)的寄存器到子節(jié)點(diǎn)和父節(jié)點(diǎn)可完成調(diào)度樹分層的配置，只有一系列連續(xù)的節(jié)點(diǎn)才可以映射到父調(diào)度節(jié)點(diǎn)。有兩種類型的映射關(guān)系:

1)從上到下的映射，通過定義映射的范圍，在子節(jié)點(diǎn)層定義開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)來完成。

2)從下到上的映射，通過一對一的映射，子節(jié)點(diǎn)層被映射到父節(jié)點(diǎn)層。

為了保持分層數(shù)據(jù)庫的一致性，根據(jù)節(jié)點(diǎn)配置的子節(jié)點(diǎn)映射范圍，所有的子節(jié)點(diǎn)應(yīng)該指向它們屬于的同一個父節(jié)點(diǎn)。

調(diào)度樹的多層結(jié)構(gòu)使得具有嵌套關(guān)系的父子節(jié)點(diǎn)得以存在。所以在子節(jié)點(diǎn)對流量進(jìn)行分類和調(diào)度后，從下一級匯聚的流量將會由父節(jié)點(diǎn)上配置的分類規(guī)則和控制參數(shù)進(jìn)行再一次的流量管理。節(jié)點(diǎn)可以針對不同的分類需求(如用戶、業(yè)務(wù)、流量類型等)配置分類規(guī)則和控制參數(shù)，并且在不同的節(jié)點(diǎn)上還可以對流量進(jìn)行不同的操作處理，從而可實(shí)現(xiàn)多層次、多業(yè)務(wù)、多用戶的流量管理［5］。

2.2 多級調(diào)度流程

對于一個五級調(diào)度的模型，可以采用流水作業(yè)機(jī)制進(jìn)行調(diào)度。每級的調(diào)度都是相互獨(dú)立并且類似的。每級調(diào)度之間的通信通過先進(jìn)先出FIFO(FirstInFirstOut)機(jī)制完成［6］。假設(shè)有N個數(shù)據(jù)流量需要處理，需要在queues、A級、B級、C級和Port五級調(diào)度器組成的流水線完成流量處理，流量處理的順序?yàn)閺淖蟮接?。五級調(diào)度可同時進(jìn)行操作，保證了調(diào)度的效率。每級的調(diào)度流程如圖2所示。

1)讀取上一級的FIFO接口中存儲的隊(duì)列調(diào)度的隊(duì)列信息，如隊(duì)列ID到本級的調(diào)度器。

2)通過讀取隊(duì)列信息，可得到其作為父調(diào)度器的信息和調(diào)度單元的信息，包括配置信息和狀態(tài)信息，根據(jù)配置信息中的調(diào)度算法和隊(duì)列的狀態(tài)進(jìn)行下一輪的調(diào)度，同時可獲取隊(duì)列的優(yōu)先級傳播到下一個調(diào)度節(jié)點(diǎn)。

根據(jù)調(diào)度單元中狀態(tài)信息和配置信息，隊(duì)列的優(yōu)先級信息，以及令牌桶的狀態(tài)整形以及調(diào)度，然后在下一級的FIFO接口中寫入調(diào)度結(jié)果并傳遞給下級調(diào)度模塊。

圖2 某一級調(diào)度機(jī)制

3 以太網(wǎng)接口的多級調(diào)度實(shí)驗(yàn)仿真及分析

3.1 以太網(wǎng)接口多級調(diào)度的實(shí)驗(yàn)仿真

將該多級調(diào)度模型用于以太網(wǎng)接口二級調(diào)度，測試拓?fù)淙鐖D3所示，測試儀表為Spirent TestCenter，選擇端口GE3/1/1，GE3/1/2，GE3/1/3作為測試端口，儀表發(fā)包給端口GE3/1/1和GE3/1/2，儀表從端口GE3/1/3收包。該模型在出端口限速500 Mbit/s，以VLAN來區(qū)分不同的用戶群，每個用戶的多種業(yè)務(wù)都在一個VLAN內(nèi)承載。接入網(wǎng)絡(luò)設(shè)備的用戶分為個人用戶和企業(yè)用戶。對于企業(yè)網(wǎng)用戶數(shù)據(jù)不區(qū)分?jǐn)?shù)據(jù)類型，都要求優(yōu)先發(fā)送;而對于個人用戶數(shù)據(jù)則要根據(jù)報(bào)文優(yōu)先級進(jìn)行調(diào)度，因此需要采用HQoS功能來實(shí)現(xiàn)需求。

圖3 以太網(wǎng)接口二級調(diào)度測試拓?fù)鋱D

承載個人用戶群A的Service VLAN ID范圍是100～299，業(yè)務(wù)類型分為以下4種:VoIP業(yè)務(wù)，具有最高優(yōu)先級，優(yōu)先級為6的流量最小帶寬保證為20 Mbit/s，優(yōu)先級為7的流量最小帶寬保證為30 Mbit/s;VoD業(yè)務(wù)，具有較高優(yōu)先級，IEEE802.1p優(yōu)先級為4、5;VPN業(yè)務(wù)，具有普通優(yōu)先級，IEEE802.1p優(yōu)先級為 2、3;HTTP瀏覽業(yè)務(wù)，最低優(yōu)先級，IEEE802.1p優(yōu)先級為0、1。承載企業(yè)用戶群的Service VLAN ID范圍為500～506，501～503為A組企業(yè)用戶，504～506為B組企業(yè)用戶。企業(yè)用戶群總流量要求限速100 Mbit/s，最小帶寬保證為50 Mbit/s。

在調(diào)度處理中，需要首先先調(diào)度企業(yè)網(wǎng)的數(shù)據(jù)，完成后再調(diào)度個人用戶的數(shù)據(jù)。在調(diào)度企業(yè)網(wǎng)的數(shù)據(jù)時，按照2∶1的比例對A組企業(yè)用戶和B組企業(yè)用戶進(jìn)行調(diào)度。在調(diào)度個人用戶數(shù)據(jù)時，首先調(diào)度VoIP業(yè)務(wù)的數(shù)據(jù)，完成后再輪詢調(diào)度VoD、VPN、HTTP 的流量，調(diào)度比例為 3∶2∶1(調(diào)度 3 個VoD報(bào)文后，調(diào)度2個PN報(bào)文，再調(diào)度1個HTTP報(bào)文)。

在建立調(diào)度樹模型的過程中，對于企業(yè)網(wǎng)用戶的流量，可以將其配置為父轉(zhuǎn)發(fā)組，其中嵌套6個子轉(zhuǎn)發(fā)組，分別對應(yīng)A組和B組企業(yè)用戶的共6個VLAN的數(shù)據(jù)，然后為分屬不同用戶的轉(zhuǎn)發(fā)組配置 WRR調(diào)度權(quán)重，實(shí)現(xiàn)按比例進(jìn)行調(diào)度的需求。最后，為父轉(zhuǎn)發(fā)組關(guān)聯(lián)SP轉(zhuǎn)發(fā)策略，使企業(yè)網(wǎng)用戶流量得到優(yōu)先調(diào)度，并通過流量整形和最小帶寬保證實(shí)現(xiàn)流量速率的控制。對個人用戶的各種流量，根據(jù)其IEEE802.1p優(yōu)先級映射到不同的本地優(yōu)先級，并匹配到8個轉(zhuǎn)發(fā)組中。為VoIP業(yè)務(wù)的轉(zhuǎn)發(fā)組關(guān)聯(lián) SP轉(zhuǎn)發(fā)策略、配置最小帶寬保證，使其優(yōu)先被調(diào)度。其余隊(duì)列則采用WRR隊(duì)列調(diào)度，并配置相應(yīng)的權(quán)重值，實(shí)現(xiàn)不同的調(diào)度比例。根據(jù)以上思路，建立的一個二層調(diào)度樹模型如圖4所示。

圖4 二層調(diào)度樹模型

在建立完調(diào)度模型后，在出端口應(yīng)用該多級調(diào)度模型。通過測試儀表向端口打流來測試HQoS性能。個人用戶和企業(yè)用戶調(diào)度測試結(jié)果分別如表1和表2所示。

表1 個人用戶業(yè)務(wù)調(diào)度測試情況 Mbit/s

表2 企業(yè)用戶業(yè)務(wù)調(diào)度測試情況 Mbit/s

3.2 以太網(wǎng)接口多級調(diào)度的實(shí)驗(yàn)仿真分析

從測試結(jié)果來看，在網(wǎng)絡(luò)擁塞的情況下，首先要保證企業(yè)網(wǎng)用戶200 Mbit/s的最小帶寬。然后進(jìn)行企業(yè)網(wǎng)用戶組的調(diào)度，根據(jù)所配置的權(quán)重和WRR算法進(jìn)行調(diào)度，并根據(jù)配置的CIR限速值對企業(yè)網(wǎng)總的數(shù)據(jù)流進(jìn)行整形處理。企業(yè)網(wǎng)用戶數(shù)據(jù)處理完后，接著處理個人用戶的業(yè)務(wù)數(shù)據(jù)。在調(diào)度中，對于個人用戶的實(shí)時業(yè)務(wù)VoIP按最高優(yōu)先級處理，在保證其最小帶寬的情況下可實(shí)現(xiàn)語音數(shù)據(jù)快速轉(zhuǎn)發(fā)，從而保證IP語音通信的質(zhì)量。VoD，VPN和HTTP業(yè)務(wù)根據(jù)配置權(quán)重按照WRR算法進(jìn)行調(diào)度，可使較高優(yōu)先級的業(yè)務(wù)得到較大的帶寬，使得VoD業(yè)務(wù)能得到較多的流量，從而保證視頻業(yè)務(wù)的質(zhì)量，而優(yōu)先級最低的HTTP業(yè)務(wù)也不會因?yàn)閮?yōu)先級低導(dǎo)致“餓死”現(xiàn)象的發(fā)生。

由上可知，每級調(diào)度可以采用不同的調(diào)度算法，調(diào)度級數(shù)也可靈活多變，可以根據(jù)隊(duì)列需求選擇調(diào)度級數(shù)［7］。多級調(diào)度模型可對不同用戶的不同業(yè)務(wù)流量進(jìn)行有效的限速、帶寬管理等控制操作，且在保證高優(yōu)先級業(yè)務(wù)的前提下，可充分地利用帶寬資源。

4 小結(jié)

一個靈活映射、靈活配置的多級調(diào)度樹可用于實(shí)現(xiàn)多用戶、多業(yè)務(wù)的流量管理。配置調(diào)度節(jié)點(diǎn)和調(diào)度單元的屬性可以配置調(diào)度算法、整形器以及權(quán)重。通過一個FIFO多級流水作業(yè)機(jī)制來實(shí)現(xiàn)調(diào)度過程，每級調(diào)度相互獨(dú)立，同一時刻多級調(diào)度同時進(jìn)行。從上一級FIFO接口中獲取上一級隊(duì)列調(diào)度的隊(duì)列信息，在調(diào)度操作完成后寫入FIFO接口，確保了調(diào)度的靈活與高效。根據(jù)不同的應(yīng)用需求，應(yīng)用該調(diào)度模型在用戶類別和業(yè)務(wù)類型較多的場合，可有效保證每種業(yè)務(wù)以及每個用戶或用戶組的服務(wù)質(zhì)量。

［1］劉辰.基于DiffServ模型的層次化QoS研究［D］.南京:南京航天航空大學(xué)，2008.

［2］楊宏亮.層次化QoS流量控制技術(shù)在PTN傳輸網(wǎng)絡(luò)中的研究與應(yīng)用［D］.銀川:寧夏大學(xué)，2013.

［3］俊超，王愛國.流量管理中隊(duì)列調(diào)度算法研［J］.電視技術(shù)，2013，37(17):102-105.

［4］肖恒杰.家庭網(wǎng)關(guān)中分層服務(wù)質(zhì)量管理功能的設(shè)計(jì)與實(shí)現(xiàn)［D］.武漢:華中科技大學(xué)，2010.

［5］黎曉亮，陳曉梅.DiffServ網(wǎng)絡(luò)中的分層流量整形及改進(jìn)［C］//2010通信理論與技術(shù)新發(fā)展——第十五屆全國青年通信學(xué)術(shù)會議論文集(下冊).［出版地不詳］:中國通信學(xué)會青年工作委員會，2010:265-269.

［6］謝延婷.一種基于分布式系統(tǒng)的隊(duì)列多級調(diào)度算法［J］.貴陽學(xué)院學(xué)報(bào)，2012，7(3):33-36.

［7］張蕾，戴錦友，基于交換芯片的3級調(diào)度算法的研究與實(shí)現(xiàn)［J］.電視技術(shù)，2012，36(9):117-119.

［8］劉陽，季新生.一種支持實(shí)時業(yè)務(wù)QoS的跨層分組調(diào)度方案［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(5):1810-1813.