Round-robin scheduling for max-min fairness in data networks
- 1 September 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 9 (7), 1024-1039
- https://doi.org/10.1109/49.103550
Abstract
The author studies a simple strategy, proposed independently by E.L. Hahne and R.G. Gallager (1986) and M.G.H. Katevenis (1987), for fairly allocating link capacity in a point-to-point packet network with virtual circuit routing. Each link offers its packet transmission slots to its user sessions by polling them in round-robin order. In addition, window flow control is used to prevent excessive packet queues at the network nodes. As the window size increases, the session throughput rates are shown to approach limits that are perfectly fair in the max-min sense. If each session has periodic input (perhaps with jitter) or has such heavy demand that packets are always waiting to enter the network, then a finite window size suffices to produce perfectly fair throughput rates. The results suggest that the transmission capacity not used by the small window session will be approximately fairly divided among the large window sessions. The focus is on the worst-case performance of round-robin scheduling with windows.Keywords
This publication has 30 references indexed in Scilit:
- Golden ratio scheduling for low delay flow control in computer networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Rate controlled servers for very high-speed networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A simulation study of fair queueing and policy enforcementACM SIGCOMM Computer Communication Review, 1990
- Analysis and simulation of a fair queueing algorithmPublished by Association for Computing Machinery (ACM) ,1989
- Queueing disciplines and passive congestion control in byte-stream networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Window flow control on a trunked byte-stream virtual circuitIEEE Transactions on Communications, 1988
- Fast switching and fair control of congested flow in broadband networksIEEE Journal on Selected Areas in Communications, 1987
- Towards a Universal Data Transport SystemIEEE Journal on Selected Areas in Communications, 1983
- State-of-the-Art—Networks of Queues—A Survey of Equilibrium AnalysisManagement Science, 1977
- Open, Closed, and Mixed Networks of Queues with Different Classes of CustomersJournal of the ACM, 1975