A Fair Round Robin Scheduling Algorithm with Low Latency

Yang Fan; Liu Zeng-ji; Qiu Zhi-liang; Liu Huan-feng

doi:10.3724/SP.J.1146.2006.00152

Volume 29 Issue 4

Jan. 2011

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2007 > 29(4): 785-788

Yang Fan, Liu Zeng-ji, Qiu Zhi-liang, Liu Huan-feng. A Fair Round Robin Scheduling Algorithm with Low Latency[J]. Journal of Electronics & Information Technology, 2007, 29(4): 785-788. doi: 10.3724/SP.J.1146.2006.00152

Citation:

Yang Fan, Liu Zeng-ji, Qiu Zhi-liang, Liu Huan-feng. A Fair Round Robin Scheduling Algorithm with Low Latency[J]. Journal of Electronics & Information Technology, 2007, 29(4): 785-788. doi: 10.3724/SP.J.1146.2006.00152

Citation:

PDF( 280 KB)

A Fair Round Robin Scheduling Algorithm with Low Latency

doi: 10.3724/SP.J.1146.2006.00152

Received Date: 2006-02-16
Rev Recd Date: 2006-08-14
Publish Date: 2007-04-19

Abstract

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.

FullText(HTML)

References(1)

References

[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

Relative Articles

Supplements(0)

Cited By

Proportional views