一种基于动态配额的虚拟网带宽公平调度算法

刘中金 卓子寒 何跃鹰 李 勇 苏 厉 金德鹏 曾烈光



一种基于动态配额的虚拟网带宽公平调度算法

刘中金①卓子寒①何跃鹰*①李 勇②苏 厉②金德鹏②曾烈光②

①(国家计算机网络应急技术处理协调中心 北京 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设计、片上网络、下一代网络体系架构等.