Computer Science ›› 2013, Vol. 40 ›› Issue (8): 72-78.

Previous Articles     Next Articles

RQRR:A New Fair and Efficient Packet Scheduling Algorithm

LIU Gui-kai and GAO Lei   

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

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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!