基于弹性定额值的分组轮询调度算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (8): 72-78.

基于弹性定额值的分组轮询调度算法

刘桂开,高蕾

湖南科技大学计算机科学与工程学院湘潭411201;湖南科技大学计算机科学与工程学院湘潭411201

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受湖南省科技厅科技计划项目(2010GK3045),湖南省教育厅科研项目(10C0687)资助

RQRR:A New Fair and Efficient Packet Scheduling Algorithm

LIU Gui-kai and GAO Lei

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 提出了一种新的适用于变长分组的调度算法——弹性定额值轮询调度算法(Resilient Quantum Round Robin,RQRR),与现有算法不同,该算法中每个数据流的定额值不是固定不变的,定额值的生成依赖于前一个轮次中各个数据流的发送情况。理论分析表明,RQRR可以保证数据流之间具有较好的公平性,它的公平性度量具有上界值7Max－1,其中Max为分组的最大长度。RQRR对每个分组的处理复杂度为O(1),易于实现、适用于高速网络。

关键词: 分组调度,轮询,弹性定额值,公平性,实现复杂度

Abstract: Aiming at variable length packet queues,a new packet scheduling algorithm named Resilient Quantum Round Robin(RQRR)was presented．Different from existent algorithms,the quantum given to each of the flows in a round is not fixed and is calculated depending on the transmission situation of all the flows in the previous round．The theoretical analyses show that the relative fairness measure of RQRR has an upper bound of 7Max－1,where Max is the largest size of the packets．RQRR takes O(1)processing complexity per packet and is simple to implement at high-speed networks.

Key words: Packet scheduling,Round robin,Resilient quantum,Fairness,Implementation complexity

刘桂开,高蕾. 基于弹性定额值的分组轮询调度算法[J]. 计算机科学, 2013, 40(8): 72-78. https://doi.org/

LIU Gui-kai and GAO Lei. RQRR:A New Fair and Efficient Packet Scheduling Algorithm[J]. Computer Science, 2013, 40(8): 72-78. https://doi.org/

参考文献

[1] Demers A,Keshav S,Shenker S．Analysis and simulation of a fair queueing algorithm[J]．Proc．SIGCOMM ’89,1989,19(4) :1-12
[2] Keshav S．On the efficient implementation of fair queuing[J]．Journal of Internetworking Research and Experience,1991,2(3):1-20
[3] Bennett J C R,Zhang H．WF2Q:Worst-case fair weighted fair queueing[C]∥INFOCOM ’96．San Fran-ciso,California,Mar．1996:120-128
[4] Zhang L．Virtual clock:A new traffic control algorithm for packet switching networks[C]∥Proceedings of ACM SIGCOMM．Philadelphia,September 1990:19-29
[5] Golestani S．A self-clocked fair queueing scheme for broadband applications[C]∥INFOCOM’94．June 1994:636-646
[6] Parekh A．A generalized processor sharing approach to flow control in integrated services network[D]．Dept．Elect．Eng．and Comput．Sci.,M.I.T.,Feb．1992
[7] Shreedhar M,Varghese G．Efficient Fair Queuing Using Deficit Round Robin[J]．IEEE/ACM Transaction on Networking(S1063-6692),1996,4(3):375-385
[8] Sivakumar G,Ramprasad A V.Analysis of FiWi networks toimprove TCP Performance[C]∥2012International Conference on Computing,Communication and Applications(ICCCA)．2012:1-6
[9] Ayaz S,Hoffmann F,German R,et al.Analysis of deficit round robin scheduling for future aeronautical data link[C]∥2011IEEE 22nd International Symposium on Personal Indoor and Mobile Radio Communications(PIMRC)．2011:1809-1814
[10] Sleem M Y,ElBadawy H M,Abo-El-Seoud M S．Two layerchannel aware scheduling for QoS support in IEEE 802.16/WiMAX networks[C]∥2011Eighth International Conference on Wireless and Optical Communications Networks(WOCN)．2011:1-5
[11] Mansy A,Ammar M,Zegura E.Deficit Round-Robin BasedMessage Ferry Routing[C]∥Global Telecommunications Conference(GLOBECOM 2011)．2011:1-5
[12] 简贵宵,葛宁,冯重熙．具有优先服务机制的嵌套式DRR算法[J]．电子与信息学报,2005,27(1):123-126
[13] 高斐,张原,杨百战．差额轮循的平滑输出算法研究[J]．西北工业大学学报,2011,29(1):49-53
[14] Kumar D,Priyameenal V.Adaptive packet scheduling algorithm for real-time services in Wi-MAX networks[C]∥2011International Conference on Recent Trends in Information Technology(ICRTIT)．2011:342-347
[15] 张博,汪斌强,王珊珊,等．基于Crossbar的可重构网络输入排队分域调度研究[J]．通信学报,2012,33(9):105-115
[16] Yang Shu-qing,Peng Jin-ye．QoS Multi-users Packet Scheduling Algorithm in IEEE 802.16e System[C]∥2011International Conference on Computer and Automation Engineering(ICCAE 2011)．IPCSIT vol．44,2012:112-116
[17] Yu Hua,Liu Xue．Scheduling Heterogeneous Flows with Delay-Aware Deduplication for Avionics Applications[J]．IEEE Tran-sactions on Parallel and Distributed Systems,2012,23(9):1790-1802

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed