基于多級隊列調度模型的研究

王 琳，吉 萌

(1.光纖通信技術和網絡國家重點實驗室，湖北武漢430074;2.武漢烽火網絡有限責任公司，湖北武漢430074)

隨著用戶數量的持續增長和網絡業務的豐富化，傳統的QoS已無法保證每個用戶的業務質量。而層次化QoS(Hierarchy QoS)，通過建立多級的調度器，把多個端口的QoS通過樹形結構來進行調度，可實現多業務多用戶的靈活調度，提供更加精細的服務。本文以某高端路由器為背景，研究以太網多級隊列調度的模型和算法。

1 多級隊列調度原理

1.1 分級調度依據

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

1.2 調度節點

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

1.3 調度單元

調度單元包括狀態寄存器、配置寄存器和子隊列寄存器。調度單元的隊列狀態和調度狀態存放在狀態寄存器中。隊列狀態是指當前各個隊列的數據情況，即在調度過程中隊列中有無數據或者有多少數據;調度狀態的作用可以根據上一次調度策略的結果作為本次調度的依據。如配置了調度策略RR后，可將上一次輪詢后的隊列狀態作為這次調度的依據。配置寄存器可以配置調度策略為SP、RR、WRR，以及調度權重weight的值。

1.4 轉發類

轉發類(ForwardingClass)是調度策略樹中的一個調度實體，對應于樹中的葉子節點。一個轉發類與一個調度隊列相對應。根據設置的映射關系，報文會進入不同的調度隊列。系統共有4 種預定義轉發類，即 BE，AF，EF，NC［4］，與該 4 種轉發類對應的參數信息將決定調度隊列的行為。BE(BestEffort)對應的業務類型是盡力而為的業務，如普通網頁瀏覽;AF(AssuredForwarding)對應傳輸質量有保障的業務，如VPN、數據報文的傳輸;EF(ExpeditedForwarding)對應對延時/抖動敏感的業務，如IP語音、IPTV報文的傳輸;NC(NetworkControl)表示轉發業務具有最高優先級，如網絡控制報文的傳輸。

2 多級隊列調度模型及流程

2.1 多級隊列調度模型

以五級調度為例，如圖1所示，數據包存儲在大小為64×103的FIFO隊列，即session隊列中，大小為64×103的session隊列映射到16×103的A級節點，1×103～16×103的A級節點映射到4×103的B級節點，1×103～4×103的B級節點將映射到512個C級節點，1～512個C級節點映射到56個端口，即根節點。對于每個根節點端口，B和C級節點對應于邏輯接口和服務，A級節點對應于用戶，隊列對應于各種服務應用。調度器的層次決定了HQOS能否應用到拓撲結構更復雜的情況，層次越多，可以應用的場合越多，可提供的服務越精細。對于調度層次不需要五級的調度，A級和B級可以配置成透明的虛節點，即通過禁用需要設置成透明節點的所有整形和調度特征，并連接父節點和孩子層節點到透明節點。

調度節點在子節點中執行調度，一個或多個子節點可以映射到一個父節點。子節點到父節點之間的映射是靈活的。整個的調度過程從隊列級別的調度開始，隊列級的調度可以獲取隊列的狀態，確定配置的三重信息(資格、調度優先級和傳播的優先級)，并將配置信息傳播到其父調度節點(A級節點)。

圖1 五級調度模型結構

通過配置某一層節點的寄存器到子節點和父節點可完成調度樹分層的配置，只有一系列連續的節點才可以映射到父調度節點。有兩種類型的映射關系:

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

2)從下到上的映射，通過一對一的映射，子節點層被映射到父節點層。

為了保持分層數據庫的一致性，根據節點配置的子節點映射范圍，所有的子節點應該指向它們屬于的同一個父節點。

調度樹的多層結構使得具有嵌套關系的父子節點得以存在。所以在子節點對流量進行分類和調度后，從下一級匯聚的流量將會由父節點上配置的分類規則和控制參數進行再一次的流量管理。節點可以針對不同的分類需求(如用戶、業務、流量類型等)配置分類規則和控制參數，并且在不同的節點上還可以對流量進行不同的操作處理，從而可實現多層次、多業務、多用戶的流量管理［5］。

2.2 多級調度流程

對于一個五級調度的模型，可以采用流水作業機制進行調度。每級的調度都是相互獨立并且類似的。每級調度之間的通信通過先進先出FIFO(FirstInFirstOut)機制完成［6］。假設有N個數據流量需要處理，需要在queues、A級、B級、C級和Port五級調度器組成的流水線完成流量處理，流量處理的順序為從左到右。五級調度可同時進行操作，保證了調度的效率。每級的調度流程如圖2所示。

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

2)通過讀取隊列信息，可得到其作為父調度器的信息和調度單元的信息，包括配置信息和狀態信息，根據配置信息中的調度算法和隊列的狀態進行下一輪的調度，同時可獲取隊列的優先級傳播到下一個調度節點。

根據調度單元中狀態信息和配置信息，隊列的優先級信息，以及令牌桶的狀態整形以及調度，然后在下一級的FIFO接口中寫入調度結果并傳遞給下級調度模塊。

圖2 某一級調度機制

3 以太網接口的多級調度實驗仿真及分析

3.1 以太網接口多級調度的實驗仿真

將該多級調度模型用于以太網接口二級調度，測試拓撲如圖3所示，測試儀表為Spirent TestCenter，選擇端口GE3/1/1，GE3/1/2，GE3/1/3作為測試端口，儀表發包給端口GE3/1/1和GE3/1/2，儀表從端口GE3/1/3收包。該模型在出端口限速500 Mbit/s，以VLAN來區分不同的用戶群，每個用戶的多種業務都在一個VLAN內承載。接入網絡設備的用戶分為個人用戶和企業用戶。對于企業網用戶數據不區分數據類型，都要求優先發送;而對于個人用戶數據則要根據報文優先級進行調度，因此需要采用HQoS功能來實現需求。

圖3 以太網接口二級調度測試拓撲圖

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

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

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

圖4 二層調度樹模型

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

表1 個人用戶業務調度測試情況 Mbit/s

表2 企業用戶業務調度測試情況 Mbit/s

3.2 以太網接口多級調度的實驗仿真分析

從測試結果來看，在網絡擁塞的情況下，首先要保證企業網用戶200 Mbit/s的最小帶寬。然后進行企業網用戶組的調度，根據所配置的權重和WRR算法進行調度，并根據配置的CIR限速值對企業網總的數據流進行整形處理。企業網用戶數據處理完后，接著處理個人用戶的業務數據。在調度中，對于個人用戶的實時業務VoIP按最高優先級處理，在保證其最小帶寬的情況下可實現語音數據快速轉發，從而保證IP語音通信的質量。VoD，VPN和HTTP業務根據配置權重按照WRR算法進行調度，可使較高優先級的業務得到較大的帶寬，使得VoD業務能得到較多的流量，從而保證視頻業務的質量，而優先級最低的HTTP業務也不會因為優先級低導致“餓死”現象的發生。

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

4 小結

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

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

［2］楊宏亮.層次化QoS流量控制技術在PTN傳輸網絡中的研究與應用［D］.銀川:寧夏大學，2013.

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

［4］肖恒杰.家庭網關中分層服務質量管理功能的設計與實現［D］.武漢:華中科技大學，2010.

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

［6］謝延婷.一種基于分布式系統的隊列多級調度算法［J］.貴陽學院學報，2012，7(3):33-36.

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

［8］劉陽，季新生.一種支持實時業務QoS的跨層分組調度方案［J］.計算機應用研究，2011，28(5):1810-1813.