计算机科学 ›› 2016, Vol. 43 ›› Issue (1): 122-127.doi: 10.11896/j.issn.1002-137X.2016.01.028
郭子荣,曾华燊,窦军
GUO Zi-rong, ZENG Hua-xin and DOU Jun
摘要: 根据通用处理器共享的公平排队思想,针对数据包或信元交换,提出了一种将数据流的预订速率作为时隙分配的权值来构建动态调度树的公平轮转调度算法。其主要思路是:当有新数据流到达时,将各数据流按其权值均匀分布到完全二叉树的叶子节点上,在每个时隙开始时轮转调度算法负责从叶子节点中依次取出数据流号,发送该数据流的信元,调度复杂度为O(1)。与其他经典的公平调度算法引比,所提出的公平轮转调度算法实现简单。理论分析和仿真结果都表明,这种简单的平滑公平轮转调度算法(SSFRR)具有良好的公平性,对源端为漏桶控制的数据流能够提供端到端的有界时延,且能够提供基于数据流的QoS保证。
[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! |
|