Efficient Fair Queueing using Deficit Round Robin

Authors

George Varghese, Washington University in St Louis
M. Shreedhar, Washington University in St Louis

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-17.PDF

Technical Report Number

WUCS-94-17

Abstract

Fair queuing is a technique that allows each flow passing through a network device to have 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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7513WG9

Recommended Citation

Varghese, George and Shreedhar, M., "Efficient Fair Queueing using Deficit Round Robin" Report Number: WUCS-94-17 (1994). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/339