Computer Science ›› 2016, Vol. 43 ›› Issue (1): 122-127.doi: 10.11896/j.issn.1002-137X.2016.01.028

Previous Articles     Next Articles

Simple and Smoothed Fair Round Robin Scheduling Algorithm

GUO Zi-rong, ZENG Hua-xin and DOU Jun   

  • Online:2018-12-01 Published:2018-12-01

Abstract: A simple and smoothed fair round-robin(SSFRR) scheduling algorithm for packet or cell switching was proposed based on the idea of packet generalized processor sharing(GPS) service discipline.The algorithm uses the reserved rates of active flows as their weights to build scheduling tree for allocating slots.The basic idea of SSFRR is to distribute all flow IDs over the leaf nodes of a complete binary tree according to the weight of each flow by scanning the weight matrix when a new flow arrives.At each time slot,SSFRR visits next leaf node of the binary tree in sequence from left to right,takes out the flow ID from the current leaf node and schedules the cell of this flow.SSFRR scheduling algorithm has O(1) scheduling time complexity.Compared with other classical fairness round robin scheduler,SSFRR algorithm is simpler to implement.Analysis and simulation show that SSFRR scheduling algorithm has good fairness property,and can provide end-to-end delay bounds for those flows which are token-bucket regulated by sources.SSFRR can provide flow-based QoS guarantees.

Key words: Smoothed fairness round robin scheduling,QoS guarantees,End-to-end delay,Slots allocation

[1] Demers A,Keshav S,Shenker S.Analysis and Simulation of aFair Queuing Algorithm[C]∥Proc.ACM SIGCOMM.1989:1-13
[2] Parekh A,Gallager R.A Generalized Processor Sharing Ap-proach to Flow Control in Integrated Services Networks:The Single Node Case[J].IEEE/ACM Trans.Networking,1993,1(3):344-357
[3] Bennett J,Zhang H.WF2Q:Worst Case Fair Weighted FairQueuing[C]∥Proc.IEEE INFOCOM.1996:120-128
[4] Bennett J,Zhang H.Hierarchical Packet Fair Queueing Algo-rithms[J].ACM/IEEE Trans.Networking,1997,5(5):675-689
[5] Zhang L.Virtual Clock:A New Traffic Control Scheme forPacket Switching Networks[C]∥Proc.ACM SIGCOMM.1990:19-29
[6] Golestani S.A self-clocked fair queueing scheme for broadband applications[C]∥Proc.IEEE INFOCOM’94.Toronto,ON,Canada,1994:636-646
[7] Shreedhar M,Varghese G.Efficient Fair Queuing Using Deficit Round Robin[C]∥Proc.ACM SIGCOMM.1995:231-242
[8] Katevenis S S M,Courcoubeti C.Weighted round robin cell multiplexing in a general purpose ATM switch chip[J].IEEE Journal on Selected Areas of Communications,1991,9:1265-1279
[9] Saha D,Mukherjee S,Tripathi S.Carry-over round robin:a simple cell scheduling mechanism for ATM networks[J].IEEE/ACM Trans.Networking,1998,6:779-796
[10] Garg Ra-hul,Chen Xiao-qiang.RRR:Recursive round robinscheduler[J].Computer Networks,1999,31(18):1951-1966
[11] Guo Chuan-xiong.SRR:An O(1) time complexity packet scheduler for flows in multi-service packet networks[J].IEEE/ACM trans.Networking,2004,12(6):1144-1155
[12] Guo Chuan-xiong.G-3:An O(1) time complexity packet scheduler that provides bounded end-to-end delay[C]∥Proc.Infocom.2007:1109-1117
[13] Guo Chuan-xiong.Improved Smoothed Round Robin Schedulers for High-Speed Packet Networks[C]∥IEEE INFOCOM 2008 Proceedings.2008:1579-1587
[14] Yuan Xin,Duan Zhen-hai.Fair Round-Robin:A Low-Complexity Packet Scheduler with Proportional and Worst-Case Fairness[J].IEEE Transaction on Computers,2009,58(3):365-379
[15] Ramabhadran S,Pasquale J.The Stratified Round Robin Scheduler:Design,Analysis,and Implementation[J].IEEE/ACM Trans.Networking,2006,14(6):1362-1373
[16] Wittevrongel S,De Vuyst S,Sys C,et al.A reservation-basedscheduling mechanism for fair QoS provisioning in packet-based networks[C]∥2014 26th International Teletraffic Congress (ITC).2014,1(8):9-11
[17] Checconi F,Rizzo L,Valente P.QFQ:Efficient Packet Scheduling With Tight Guarantees[J].IEEE/ACM Transactions on Networking,2013,21(3):802-816
[18] Chang G,Lee C C.Fair queueing without per-flow queues:AVirtual Queueing Machine[C]∥2014 International Conference on Computing,Networking and Communications (ICNC).2014 :124-130

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!