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

?

一種基于動態(tài)配額的虛擬網(wǎng)帶寬公平調度算法

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

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

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

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

1 引言

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

隊列調度算法已經(jīng)得到了廣泛而深入的研究，算法從原理上可以分為兩大類：基于虛擬時間的算法，如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]等。

然而，虛擬化網(wǎng)絡環(huán)境中的隊列調度問題與傳統(tǒng)場景不同，它具有如下3個特點：

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

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

(3)虛擬網(wǎng)業(yè)務流在數(shù)據(jù)平面中的處理具有選擇性。受限于虛擬轉發(fā)實例的處理類型，不同種類的業(yè)務流必須在不同種類的虛擬轉發(fā)實例中處理。

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

2 虛擬化場景建模

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

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

3 基于動態(tài)配額的隊列調度算法

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

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

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

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

表2基于動態(tài)配額的隊列調度算法

表3流選擇算法

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

表4動態(tài)配額更新算法

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

4 性能評估

4.1 實驗設計

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

4.2 算法有效性測試

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

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

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

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

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

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

圖3 DRR, miDRR和本文算法在業(yè)務流及虛擬網(wǎng)總體帶寬分配情況

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

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

4.3 算法公平性測試

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

5 結束語

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

參考文獻

[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] 劉中金, 李勇, 楊懋, 等. 基于可編程硬件的虛擬路由器數(shù)據(jù)平面設計與實現(xiàn)[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] 劉中金, 李勇, 蘇厲, 等. 彈性協(xié)議可定制的網(wǎng)絡數(shù)據(jù)平面結構及其映射算法[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] 高先明, 張曉哲, 王寶生, 等. 面向虛擬路由器的基于歷史轉發(fā)開銷的資源調度算法[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；網(wǎng)絡出版：2016-07-15

何躍鷹 hyy@cert.org.cn

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

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

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

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

何躍鷹： 男，1975年生，高級工程師，研究方向為大數(shù)據(jù)分析、網(wǎng)絡安全.

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

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

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

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