M. Shreedhar
Abstract
Fair queuing is a technique that allows each flow passing through a network device to have a fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement: specifically, the work required to process a packet in these schemes was O(log(n)), where n is the number of active flows. This is expensive at high speeds. On the other hand, cheaper approximations of fair queuing that have been reported in the literature exhibit unfair behavior. In this paper, we describe a new approximation of fair queuing, that we call Deficit Round Robin. Our scheme achieves nearly perfect fairness in terms of throughput, requires only O(1) work to process a packet, and is simple enough to implement in hardware. Deficit Round Robin is also applicable to other scheduling problems where servicing cannot be broken up into smaller units, and to distributed queues.
- APV95 H. Adiseshu, G. Parulkar, and G. Varghese. Reliable FIFO Load Balancing over Multiple FIFO Channels. Washington University Technical Report 95-11, available by FTP.Google Scholar
- CLR90 T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press/McGraw-Hill, 1990. Google ScholarDigital Library
- DKS89 A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Proc. Slgcomm '89, 19(4):1-12, September 1989. Google ScholarDigital Library
- Flo93a S. Floyd. Notes on guaranteed service in resource management. Unpublished note. 1993.Google Scholar
- Flo93b S. Floyd. Personal communication. 1993.Google Scholar
- GM90 A. Greenberg and N. Madras. How fair is fair queueing. In Proc. Performance '90, 1990.Google Scholar
- Gol94 S. Goiestani. A self clocked fair queueing scheme for broadband applications. In Proc. {EEE Infocomm '9d, 1994.Google Scholar
- JR86 R. Jain and S. Routhier. Packet trains measurement and a new model for computer netwoek traffic. IEEE Journal on Selected Areas ~n Communications, Sept. 1986.Google ScholarDigital Library
- Kes91 S. Keshav. On the efficient implementation of fair queueing. In Internetworking: Research and Experzence Vol. 2, 15%173, September 1991.Google Scholar
- McK91 P. McKenney. Stochastic fairness queueing. In Internetworking: Research and Experience Vol.2, 113-131, January 1991.Google Scholar
- Nag87 John Nagle. On packet switches with infinite storage. IEEE Trans. on Comm., COM-35(4), April 1987.Google ScholarCross Ref
- PG93 A.K. Parekh and R. G. Gallagher. A generalized processor sharing approach to flow control in integrated services networks. In Proc. IEEE Infocomm '93. Google ScholarDigital Library
- SA94 D. Saha and M. Saksena and S. Mukherjee and S. Tripathi. On Guaranteed Delivery of Time- Critical Messages in DQDB. In Proc. IEEE Infocomm '9d.Google Scholar
- ST85 D.D. Slea{or and R.E. Tarjan. Amortized efficiency of list update and paging rules. Comm. ACM, 28(2):202-208, 1985. Google ScholarDigital Library
- Zha91 L. Zhang. Virtual clock: A new traffic control algorithm for packet switched networks. A CM Trans. on Computer Systems, 9(2):101-125, May 1991. Google ScholarDigital Library
Index Terms
- Efficient fair queueing using deficit round robin
Recommendations
Efficient fair queueing using deficit round robin
SIGCOMM '95: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communicationFair queuing is a technique that allows each flow passing through a network device to have a fair share of network resources. Previous schemes for fair queuing that achieved nearly perfect fairness were expensive to implement: specifically, the work ...
Fair Queuing with Round Robin: A New Packet Scheduling Algorithm for Routers
ISCC '02: Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02)In the last few years several queuing policies have been proposed to ensure fairness between competing requests at a service point. Fair Queuing (FQ) algorithm due to Demers, Keshav and Shenkar is a queuing technique that attains near perfect fairness, ...
Fair Round-Robin: A Low Complexity Packet Schduler with Proportional and Worst-Case Fairness
Round robin based packet schedulers generally have a low complexity and provide long-term fairness. The main limitation of such schemes is that they do not support short-term fairness. In this paper, we propose a new low complexity round robin scheduler,...
Comments