Thumbnail
Access Restriction
Subscribed

Author Varghese, George ♦ Shreedhar, M.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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.
Description Affiliation: Microsoft Corporation (Shreedhar, M.) || Washington University in St. Louis. (Varghese, George)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1993-07-01
Publisher Place New York
Journal ACM SIGCOMM Computer Communication Review (CCRV)
Volume Number 25
Issue Number 4
Page Count 12
Starting Page 231
Ending Page 242


Open content in new tab

   Open content in new tab
Source: ACM Digital Library