一種基于動態配額的虛擬網帶寬公平調度算法

劉中金 卓子寒 何躍鷹 李 勇 蘇 厲 金德鵬 曾烈光

?

一種基于動態配額的虛擬網帶寬公平調度算法

劉中金①卓子寒①何躍鷹*①李 勇②蘇 厲②金德鵬②曾烈光②

①(國家計算機網絡應急技術處理協調中心 北京 100029)②(清華大學電子工程系 北京 100084)

網絡虛擬化被廣泛用于網絡實驗平臺和數據中心等場景中。作為虛擬化網絡中的核心組網設備，虛擬路由器可以在同一物理底層上構建多個虛擬路由器實例來承載多個虛擬網。其核心調度問題在于如何根據不同虛擬網對帶寬的不同需求，將網絡數據包調度到不同的實例中。該文針對該問題對虛擬化場景下的隊列調度問題進行建模，提出了基于動態配額的隊列調度算法，與miDRR等算法相比，該文算法在虛擬網帶寬分配的有效性和公平性上有明顯優勢。

網絡虛擬化；虛擬路由器；軟件定義網絡；隊列調度算法；公平性

1 引言

軟件定義網絡(Software Defined Networking, SDN)[1], VXLAN[2]等新協議不斷涌現，為了支持這些應用的部署，研究人員引入了網絡虛擬化的機制對網絡進行隔離。在實驗平臺中，管理員通過劃分虛擬網實現不同協議、轉發機制以及服務質量的分配和隔離[3]；在數據中心中，管理員將不同租戶劃分到不同的虛擬網，以進行隔離和服務質量區分[4]。在這些場景中，虛擬路由器作為核心的組網設備，可以在同一物理底層上構建多個虛擬路由器實例來承載多個虛擬網[5,6]，因此，管理員需要保證路由器能夠按照虛擬網的服務質量要求對數據包進行隊列調度。

隊列調度算法已經得到了廣泛而深入的研究，算法從原理上可以分為兩大類：基于虛擬時間的算法，如WFQ(Weighted Fair Queuing)[7], WF2Q (Worst-case Fair Queuing)[8], STFQ(Start Time Fair Queuing)[9], MS-PGPS[10]和HFOB_RSA[11]等算法和基于輪詢的算法，如差額輪詢算法(Deficit Round Robin, DRR)[12], SRR[13], PDRR[14]和miDRR(Multi-interface Deficit Round Robin)[15]等。

然而，虛擬化網絡環境中的隊列調度問題與傳統場景不同，它具有如下3個特點：

(1)虛擬網業務具有差異性。一個物理網絡承載了多張并行的虛擬網，這些虛擬網通常屬于不同的用戶。用戶會在虛擬網中部署自己的業務，使得不同虛擬網承載不同種類、不同數量的業務流。例如在實驗平臺和數據中心中，既有基于IP協議的業務，也會有基于NDN[16], OSA[17], Avalanche[18]等新協議的業務。

(2)支持異構網絡的數據平面虛擬化。在虛擬化的網絡數據平面中，物理設備被虛擬化為多個虛擬轉發實例。為了支持不同種類的業務，這些虛擬轉發實例會被配置成不同的轉發功能，處理不同格式的數據包。

(3)虛擬網業務流在數據平面中的處理具有選擇性。受限于虛擬轉發實例的處理類型，不同種類的業務流必須在不同種類的虛擬轉發實例中處理。

當流與虛擬轉發實例具有選擇性時，虛擬完成時間將取決于虛擬轉發實例上業務流的到達情況，不能僅通過當前時刻的隊列狀態決定數據包調度的先后順序，因此基于虛擬完成時間的調度算法不適用于上述場景；在虛擬網和虛擬轉發實例具有選擇性的情況下，分布式的DRR的調度方案難以滿足全局的業務流帶寬分配需求；同時，以流為單位的max-min公平調度難以滿足虛擬網的帶寬分配要求。因此需要研究適用于虛擬網的調度算法，使得虛擬網之間的帶寬得到公平分配。

2 虛擬化場景建模

本節根據虛擬化場景的特點對隊列調度算法進行建模。如圖1所示，不失一般性，考慮物理網絡中的一個路由器，它被虛擬化為個虛擬轉發實例。物理設備上承載了個業務流，這些業務流屬于個虛擬網。業務流與虛擬網的歸屬關系用表示，如果流屬于虛擬網，那么，否則。虛擬網與虛擬轉發實例之間的選擇關系用流選擇矩陣來表示，如果虛擬網可以在虛擬路由器中處理，則，否則。

圖1 虛擬化場景中隊列調度模型

3 基于動態配額的隊列調度算法

在虛擬化網絡中，虛擬網帶寬max-min帶寬公平是指：若要增加一個高帶寬虛擬網的帶寬，必須要降低一個低帶寬虛擬網的帶寬，即max-min公平分配保證了低帶寬虛擬網所分配的帶寬盡可能高。

本節根據上節所述的隊列調度模型，提出基于動態配額的隊列調度算法。下文將調度算法分為3部分進行描述，算法1是所提出算法的框架，算法2和算法3是調度算法的子算法，分別實現流選擇和配額更新的功能。如圖1所示，每個虛擬轉發實例入口處部署一個調度器，在每個調度器上不斷循環運行算法1中的基于動態配額的隊列調度算法。算法所用到符號及意義在表1中列出。

表1隊列調度算法中所需符號意義

因此，算法1(表2)的每次循環至多發送一個數據包，每發送一次進行判斷，如果仍然有差額計數器大于隊頭的數據包長度，指針保持不變，并進入下一次循環發送數據包，直到小于隊頭的數據包長度。經過多次循環，調度器指針可以將所有可服務的隊列遍歷一遍，稱為一輪調度。

表2基于動態配額的隊列調度算法

表3流選擇算法

在已有算法中調度器以流為單位進行隊列調度，流的配額是一成不變的。算法3(表4)考慮了流與虛擬網的歸屬關系，根據虛擬網中活躍業務流的數目在每一輪調度中更新所有流的配額，使得虛擬網內的各條業務流則按照比例對配額進行調整，同時每輪調度中每個虛擬網的總配額保持不變。

表4動態配額更新算法

可以證明基于算法1的調度器滿足速率集簇特性，因此該調度器能夠實現虛擬網之間帶寬的max-min公平調度。

4 性能評估

4.1 實驗設計

為了評估本文所提隊列調度算法的有效性和公平性，我們基于NetFPGA硬件板卡進行了驗證[19]。我們在單個NetFPGA板卡上創建了2個虛擬轉發實例和，二者的處理容量都為1000 Mbps。通過流量產生器發送3個TCP業務流,,到板卡上，其中和屬于虛擬網，可以在和中處理；屬于虛擬網，僅能在中處理。虛擬網的帶寬權重為，業務流的帶寬權重為。作為比較，在和的調度器中分別部署了miDRR和算法1，為了能夠反映調度算法的動態特征，在和中統計了10 s的流量，其中和持續了10 s,持續了4 s，下面對實驗結果進行分析。

4.2 算法有效性測試

在所設計實驗條件場景下，DRR, SRR和PDRR調度算法為各個數據流分配的帶寬是一致的，其主要區別在于算法復雜度和調度延時上。

圖2(a1)和圖2(a2)分別示出了在上述3種算法下和內業務流的帶寬分配情況。由于和的調度過程相互獨立，前4 s,中和兩個流的占比為1:3，在中,和的比例為1:3:1；在4~6 s間，到6 s后，隊列不再有數據包排隊，在中只處理，而在中，和按照的比例進行分配。

圖2 DRR, miDRR和本文算法在虛擬轉發實例中的帶寬分配情況

圖2(b1)和圖2(b2)分別示出了在miDRR算法下和內業務流的帶寬分配情況。從圖2(b1)可以看出，在前4 s,和會被交替調度到和中，則嚴格地在中處理；在4~6 s間，由于停止到達，因此會處理隊列中剩余的數據包，其處理速率也逐漸下降；在6 s后，隊列不再有數據包排隊，和分別在和中滿速率處理，符合的比例。

圖2(c1)和圖2(c2)分別示出了在本文算法下和內業務流的帶寬分配情況。可以看到，前4 s,和仍然在兩個虛擬實例中處理；在6 s后，隊列空置，可以看出，和對和的配額進行調整，的配額不變。因此，在和中的帶寬分別增長到1000 Mbps和500 Mbps,的帶寬保持不變。

圖3(a1)和圖3(a2) 顯示了DRR, SRR和PDRR調度算法下，3個流和虛擬網的總體帶寬的分配情況。從圖3(a1)中可以看出：前4s, 3條流的帶寬分配分別為450 Mbps, 1350 Mbps和200 Mbps，不符合預期的1:3:1的流權重分配。從圖3(a2)中可以看出，與的帶寬比例為9:1，未按照預定的虛擬網權重進行調度。從第6 s開始，不再有數據包排隊，其配額變為0,與的帶寬比例變為3:1，也未能按照虛擬網權重進行調度。

圖3 DRR, miDRR和本文算法在業務流及虛擬網總體帶寬分配情況

圖3(b1)和圖3(b2)顯示了miDRR調度算法下，3個流和虛擬網的總體帶寬的分配情況。從圖3(b1)中可以看出：前4 s, 3條流的帶寬分配分別為400 Mbps, 1200 Mbps和400 Mbps，符合預期的1:3:1的流權重分配。從圖3(b2)中可以看出，與的帶寬比例為4:1，未按照預定的虛擬網權重進行調度。從第6 s開始，不再有數據包排隊，其配額變為0，因此，和按照比例分別在和中處理，與的帶寬比例也是1:1，也未能按照虛擬網權重進行調度。

圖3(c1)和圖3(c2)顯示了在本文所提調度算法下，3個流和虛擬網的總體帶寬的分配情況。在前4 s, 3條流的速率分別為370 Mbps, 1130 Mbps和500 Mbps,與的帶寬比例為3:1，與預期權重相同，同時，在內部，和保持了1:3的比例。4 s后，當的帶寬下降時，調度器調整的配額，使得的帶寬分配迅速增加并保持在1500 Mbps，從而保證了虛擬網與的帶寬維持在3:1。說明本文算法能夠以虛擬網為單位調度業務流。

4.3 算法公平性測試

圖4 不同虛擬網帶寬比例設置下的帶寬實際分配情況

5 結束語

針對虛擬化環境中虛擬網之間帶寬分配的問題，本文對虛擬路由器的隊列調度問題進行了建模，并提出了基于動態配額的隊列調度算法。本文算法能夠以虛擬網為單位進行帶寬資源的分配，與DRR, SRR和miDRR等算法相比，本文算法在虛擬網帶寬分配的有效性和公平性上有顯著優勢。

參考文獻

[1] KREUTZ D, RAMOS F M V, ESTEVES V P,Software-defined networking: A comprehensive survey[J]., 2015, 103(1): 14-76. doi: 10.1109/ JPROC.2014.2371999.

[2] MAHALINGAM M, DUTT D, DUDA K,Virtual extensible local area network (VXLAN): a framework for overlaying virtualized layer 2 networks over layer 3 networks [R]. 2014.

[3] BERMAN M, CHASE J S, LANDWEBER L,GENI: a federated testbed for innovative network experiments[J]., 2014, 61: 5-23. doi: 10.1016/j.bjp. 2013.12.037.

[4] KOPONEN T, AMIDON K, BALLAND P,Network virtualization in multi-tenant data centers[C]. Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation,Seattle, USA, 2014: 203-216.

[5] 劉中金, 李勇, 楊懋, 等. 基于可編程硬件的虛擬路由器數據平面設計與實現[J]. 電子學報, 2013, 41(7): 1268-1272. doi: 10.3969/j.issn.0372-2112.2013.07.004.

LIU Zhongjin, LI Yong, YANG Mao,Design on data plane of programmable hardware-based virtual router[J]., 2013, 41(7): 1268-1272. doi: 10.3969/ j.issn.0372-2112.2013.07.004.

[6] 劉中金, 李勇, 蘇厲, 等. 彈性協議可定制的網絡數據平面結構及其映射算法[J]. 電子與信息學報, 2014, 36(7): 1713-1719.doi: 10.3724/SP.J.1146.2013.01151.

LIU Zhongjin, LI Yong, SU Li,Design on the elastic protocol customizable data plane and its mapping algorithm[J].&, 2014, 36(7): 1713-1719.doi: 10.3724/SP.J.1146.2013.01151.

[7] PAREKH A K and GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks: the single-node case[J]./, 1993, 1(3): 344-357. doi: 10.1109/INFCOM.1992.263509.

[8] BENNETT J C R and ZHANG H. WF2Q: worst-case fair weighted fair queueing[C]. P roceedings of IEEE INFOCOM'96, 1996, Vol. 1: 120-128. doi: 10.1109/INFCOM.1996.497885.

[9] GOVAL P, VIN H M, and CHENG H. Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks[J]./, 1997, 5(5): 690-704.

[10] BLANQUER J M and ?ZDEN B. Fair queuing for aggregated multiple links[J]., 2001, 31(4): 189-197. doi: 10.1145/383059.383074.

[11] 高先明, 張曉哲, 王寶生, 等. 面向虛擬路由器的基于歷史轉發開銷的資源調度算法[J]. 電子與信息學報, 2015, 37(3): 686-692.doi: 10.11999/JEIT140491.

GAO Xianming, ZHANG Xiaozhe, WANG Baosheng,Historical forwarding overhead based the resource scheduling algorithm for the virtual router[J].&, 2015, 37(3): 686-692. doi: 10.11999/ JEIT140491.

[12] SHREEDHAR M and VARGHESE G. Efficient fair queuing using deficit round-robin[J]./, 1996, 4(3): 375-385. doi: 10.1109/90.502236.

[13] GUO C. SRR: an O (1) time complexity packet scheduler for flows in multi-service packet networks[J]., 2001, 31(4): 211-222. doi: 10.1109/TNET.2004.838601.

[14] TSAO S C and LIN Y D. Pre-order deficit round robin: a new scheduling algorithm for packet-switched networks[J]., 2001, 35(2): 287-305. doi: 10.1016/ S1389-1286(00)00172-9.

[15] YAP K K, SANDEEP Y Y, and KATTI K S. Scheduling packets over multiple interfaces while respecting user preferences[C]. Proceedings of the Ninth ACM Conference on Emerging Networking Experiments and Technologies. Santa Barbara, 2013: 109-120.doi: 10.1145/2535372.2535387.

[16] VAN J, PATRICK C, ZHANG L,Named data networking[OL]. http://www.named-data.net/, 2015, 12.

[17] CHEN K, SINGLA A, SINGH A,OSA: an optical switching architecture for data center networks with unprecedented flexibility[J]./, 2014, 22(2): 498-511.

[18] IYER A, KUMAR P, and MANN V. Avalanche: data center multicast using software defined networking[C]. Proceedings of IEEE Sixth International Conference on Communication Systems and Networks (COMSNETS), Bangalore, India, 2014: 1-8. doi: 10.1109/COMSNETS.2014.6734903.

[19] LOCKWOOD J W, MCKEOWN N, WATSON G,. NetFPGA—an open platform for gigabit-rate network switching and routing[C]. Proceedings of the IEEE International Conference on Microelectronic Systems Education, San Diego, USA, 2007: 160-161. doi: 10.1109/MSE.2007.69.

Dynamical Weighted Scheduling Algorithm Supporting Fair Bandwidth Allocation of Virtual Networks

LIU Zhongjin①ZHUO Zihan①HE Yueying①LI Yong②SU Li②JIN Depeng②ZENG Lieguang②

①(,100029,)②(,,100084,)

Network virtualization is widely deployed in network experiment platforms and data center networks. As a key networking equipment in virtualized environment, the virtual router can build many virtual router instances to run different virtual networks. The key problem for a virtual router lies in how to schedule the packets into different virtual instances according to the virtual networks’ bandwidth requirement. In this article, a model is given to the scheduling problem and a dynamical weighted scheduling algorithm is proposed. The experimental results show that the proposed algorithm has superiority over miDRR algorithm in terms of the efficiency and the fairness.

Network virtualization; Virtual router; Software Defined Networking (SDN); Queue scheduling algorithm; Fairness

TP393.1

A

1009-5896(2016)10-2654-06

10.11999/JEIT151485

2015-12-29；改回日期：2016-05-26；網絡出版：2016-07-15

何躍鷹 hyy@cert.org.cn

國家高技術研究與發展計劃(2012AA012801)

The National High Technology Research and Development Program of China (2012AA012801)

劉中金： 男，1988年生，博士，研究方向為計算機網絡安全、軟件定義網絡、數據中心網絡、可編程虛擬化路由器等.

卓子寒： 男，1987年生，博士，研究方向為計算機網絡安全、網絡測量、圖像處理等.

何躍鷹： 男，1975年生，高級工程師，研究方向為大數據分析、網絡安全.

李 勇： 男，1985年生，講師，研究方向為軟件定義網絡、下一代IP網絡體系結構、移動容遲網絡、網絡虛擬化等.

蘇 厲： 男，1976年生，講師，研究方向為片上網絡、軟件定義網絡、短距離無線通信等.

金德鵬： 男，1972年生，教授，研究方向為軟件定義網絡、片上網絡、短距離無線通訊等.

曾烈光： 男，1947年生，教授，研究方向為通信網、ASIC設計、片上網絡、下一代網絡體系架構等.