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

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

doi:10.11999/JEIT151485

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

doi: 10.11999/JEIT151485

1.
(国家计算机网络应急技术处理协调中心北京 100029) ②(清华大学电子工程系北京 100084)

基金项目:

国家高技术研究与发展计划(2012AA012801)

计量
- 文章访问数: 1418
- HTML全文浏览量: 116
- PDF下载量: 378
- 被引次数: 0
出版历程
- 收稿日期: 2015-12-29
- 修回日期: 2016-05-26
- 刊出日期: 2016-10-19

Dynamical Weighted Scheduling Algorithm Supporting Fair Bandwidth Allocation of Virtual Networks

1.
(National Computer Network Emergency Response Technical Team, Beijing 100029, China)

Funds:

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

摘要

摘要: 网络虚拟化被广泛用于网络实验平台和数据中心等场景中。作为虚拟化网络中的核心组网设备，虚拟路由器可以在同一物理底层上构建多个虚拟路由器实例来承载多个虚拟网。其核心调度问题在于如何根据不同虚拟网对带宽的不同需求，将网络数据包调度到不同的实例中。该文针对该问题对虚拟化场景下的队列调度问题进行建模，提出了基于动态配额的队列调度算法，与miDRR等算法相比，该文算法在虚拟网带宽分配的有效性和公平性上有明显优势。
- 网络虚拟化 /
- 虚拟路由器 /
- 软件定义网络 /
- 队列调度算法 /
- 公平性
Abstract: 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

HTML全文

参考文献(21)

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

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

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

KOPONEN T, AMIDON K, BALLAND P, et al. 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.

刘中金, 李勇, 杨懋, 等. 基于可编程硬件的虚拟路由器数据平面设计与实现[J]. 电子学报, 2013, 41(7): 1268-1272. doi: 10.3969/j.issn.0372-2112.2013.07.004.

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

刘中金, 李勇, 苏厉, 等. 弹性协议可定制的网络数据平面结构及其映射算法[J]. 电子与信息学报, 2014, 36(7): 1713-1719. doi: 10.3724/SP.J.1146.2013.01151.

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

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

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.

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

BLANQUER J M andZDEN B. Fair queuing for aggregated multiple links[J]. ACM SIGCOMM Computer Communication Review, 2001, 31(4): 189-197. doi: 10.1145/383059.383074.

高先明, 张晓哲, 王宝生, 等. 面向虚拟路由器的基于历史转发开销的资源调度算法[J]. 电子与信息学报, 2015, 37(3): 686-692. doi: 10.11999/JEIT140491.

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

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

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

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

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.

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

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.

LOCKWOOD J W, MCKEOWN N, WATSON G, et al. NetFPGAan 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.

施引文献

资源附件(0)

访问统计