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

?

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

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

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

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

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

1 引言

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

隊列調(diào)度算法已經(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)境中的隊列調(diào)度問題與傳統(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)支持異構(gòu)網(wǎng)絡的數(shù)據(jù)平面虛擬化。在虛擬化的網(wǎng)絡數(shù)據(jù)平面中，物理設備被虛擬化為多個虛擬轉(zhuǎn)發(fā)實例。為了支持不同種類的業(yè)務，這些虛擬轉(zhuǎn)發(fā)實例會被配置成不同的轉(zhuǎn)發(fā)功能，處理不同格式的數(shù)據(jù)包。

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

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

2 虛擬化場景建模

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

圖1 虛擬化場景中隊列調(diào)度模型

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

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

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

表1隊列調(diào)度算法中所需符號意義

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

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

表3流選擇算法

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

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

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

4 性能評估

4.1 實驗設計

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

4.2 算法有效性測試

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

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

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

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

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

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

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

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

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

4.3 算法公平性測試

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

5 結(jié)束語

針對虛擬化環(huán)境中虛擬網(wǎng)之間帶寬分配的問題，本文對虛擬路由器的隊列調(diào)度問題進行了建模，并提出了基于動態(tài)配額的隊列調(diào)度算法。本文算法能夠以虛擬網(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ù)平面結(jié)構(gòu)及其映射算法[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] 高先明, 張曉哲, 王寶生, 等. 面向虛擬路由器的基于歷史轉(zhuǎn)發(fā)開銷的資源調(diào)度算法[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)絡體系結(jié)構(gòu)、移動容遲網(wǎng)絡、網(wǎng)絡虛擬化等.

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

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

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