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

?

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

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

①(國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心 北京 100029)②(清華大學(xué)電子工程系 北京 100084)

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

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

1 引言

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

隊(duì)列調(diào)度算法已經(jīng)得到了廣泛而深入的研究，算法從原理上可以分為兩大類：基于虛擬時(shí)間的算法，如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)絡(luò)環(huán)境中的隊(duì)列調(diào)度問(wèn)題與傳統(tǒng)場(chǎng)景不同，它具有如下3個(gè)特點(diǎn)：

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

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

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

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

2 虛擬化場(chǎng)景建模

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

圖1 虛擬化場(chǎng)景中隊(duì)列調(diào)度模型

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

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

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

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

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

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

表3流選擇算法

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

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

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

4 性能評(píng)估

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

4.2 算法有效性測(cè)試

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

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

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

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

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

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

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

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

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

4.3 算法公平性測(cè)試

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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ù)平面設(shè)計(jì)與實(shí)現(xiàn)[J]. 電子學(xué)報(bào), 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)絡(luò)數(shù)據(jù)平面結(jié)構(gòu)及其映射算法[J]. 電子與信息學(xué)報(bào), 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ā)開(kāi)銷的資源調(diào)度算法[J]. 電子與信息學(xué)報(bào), 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)絡(luò)出版：2016-07-15

何躍鷹 hyy@cert.org.cn

國(guó)家高技術(shù)研究與發(fā)展計(jì)劃(2012AA012801)

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

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

卓子寒： 男，1987年生，博士，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全、網(wǎng)絡(luò)測(cè)量、圖像處理等.

何躍鷹： 男，1975年生，高級(jí)工程師，研究方向?yàn)榇髷?shù)據(jù)分析、網(wǎng)絡(luò)安全.

李 勇： 男，1985年生，講師，研究方向?yàn)檐浖x網(wǎng)絡(luò)、下一代IP網(wǎng)絡(luò)體系結(jié)構(gòu)、移動(dòng)容遲網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化等.

蘇 厲： 男，1976年生，講師，研究方向?yàn)槠暇W(wǎng)絡(luò)、軟件定義網(wǎng)絡(luò)、短距離無(wú)線通信等.

金德鵬： 男，1972年生，教授，研究方向?yàn)檐浖x網(wǎng)絡(luò)、片上網(wǎng)絡(luò)、短距離無(wú)線通訊等.

曾烈光： 男，1947年生，教授，研究方向?yàn)橥ㄐ啪W(wǎng)、ASIC設(shè)計(jì)、片上網(wǎng)絡(luò)、下一代網(wǎng)絡(luò)體系架構(gòu)等.