一种具有低时延的分组公平循环调度
doi: 10.3724/SP.J.1146.2006.00152
A Fair Round Robin Scheduling Algorithm with Low Latency
-
摘要: 本文提出了一种新的分组循环调度算法LFRR(Large weight First Round Robin)。为了具有良好的时延特性和较低的实现复杂度，LFRR采取了以下方法：(1)在调度表中为流分配时隙时，LFRR以时隙完全均匀分布为参照，确保分配给一个流的时隙不会过早或过晚地出现在调度表中。(2)LFRR算法中采用了等权值流合并的技术，把权值大于1且权值相等的流合并成一个虚流，以虚流为处理对象，使算法需要处理的对象数目大为减小。(3)当一个时隙适合分配给多个虚流时，LFRR采用了简单的权值大的虚流优先占用时隙的原则。本文对LFRR进行了理论分析和计算机仿真，结果表明LFRR算法的时延性能比WRR(Weighted Round Robin)有了很大提高，同时LFRR算法的公平性也有保证。
-
关键词:
- 分组调度;时延;实现复杂度;公平性
Abstract: A new round robin scheduling algorithm named LFRR(Large weight First Round Robin) is proposed in this paper. In order to achieve good delay property and low implementation complexity, several methods are taken in LFRR. Firstly, when slots are allocated for flows in the schedule table, LFRR refers to the ideal situation where the slots of each flow are uniformly distributed in the schedule table to prevent flows slots from appearing too early or too late. Secondly, in LFRR system flows which weights are the same and larger than 1 are aggregated into a virtual flow. LFRR deals with virtual flows instead of actual flows. This deceases the flow number that scheduling algorithm deals with. Thirdly, when a slot can be allocated to several virtual flows, flows with larger weight have high priority to posses this slot. Theoretical and simulation results show the delay property of LFRR is much better than that of WRR(Weighted Round Robin) and the fairness of LFRR can be guaranteed. -
[1] Parekh A and Gallager R. A generalized processor sharing approach to flow control: The single node case[J].IEEE/ACM Trans. on Networking.1993, 1(3):344-357 [2] Katevenis M and Sidiropoulos S. Weighted round-robin cell multiplexing in a general purpose ATM switch chip[J].IEEE Journal on Selected Areas on Communication.1991, 9(8):1265-1279 [3] Matsufuru N and Aibara R. Efficient fair queueing for ATM networks using uniform round robin. In Proc. IEEE INFOCOM 1999, New York: 389-397. [4] Saha D and Mukherjee S. Carry-over round robin : A simple cell scheduling mechanism for ATM networks[J].IEEE/ACM Trans. on Networking.1998, 6(6):779-795 [5] Onur, Yukio, and Teruaki. Urgency-based round robin: A new scheduling discipline for packet switching networks. in Proc. IEEE INFOCOM 1998, San Francisco: 1179-1184. [6] Dimitrios Stiliadis and Nnujan Varma. Latency-rate servers: A general model for analysis of traffic scheduling algorithms[J].IEEE/ACM Trans. on Networking.1998, 6(5):611-624 -
计量
- 文章访问数: 3353
- HTML全文浏览量: 77
- PDF下载量: 776
- 被引次数: 0
下载:
