The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Efficient fair queueing using deficit round robin
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Analysis and simulation of a fair queueing algorithm
Demers, A., Keshav, S., & Shenker, S. (1989) · ACM SIGCOMM Computer Communication Review · doi:10.1145/75247.75248 · Cited by 2,614
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
Packet Trains--Measurements and a New Model for Computer Network Traffic
Jain, R. K., & Routhier, S. (1986) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.1986.1146410 · Cited by 549
VirtualClock: a new traffic control algorithm for packet-switched networks
Zhang, L. (1991) · ACM Transactions on Computer Systems · doi:10.1145/103720.103721 · Cited by 509
On Packet Switches with Infinite Storage
Nagle, J. (1987) · IEEE Transactions on Communications · doi:10.1109/tcom.1987.1096782 · Cited by 384
McKenney, P. E. (2002) · Proceedings. IEEE INFOCOM '90: Ninth Annual Joint Conference of the IEEE Computer and Communications Societies@m_The Multiple Facets of Integration · doi:10.1109/infcom.1990.91316 · Cited by 273
(1990)
Cited by
Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers
Nichols, K., Blake, S., Baker, F., & Black, D. (1998) · doi:10.17487/rfc2474 · Cited by 1,530
Efficient fair queuing using deficit round-robin
Shreedhar, M., & Varghese, G. (1996) · IEEE/ACM Transactions on Networking · doi:10.1109/90.502236 · Cited by 1,399
Self-citationEfficient fair queueing using deficit round robin
Shreedhar, M., & Varghese, G. (1995) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/217382.217453 · Cited by 542
Self-citationHierarchical packet fair queueing algorithms
Bennett, J. C. R., & Zhang, H. (1997) · IEEE/ACM Transactions on Networking · doi:10.1109/90.649568 · Cited by 422
Metadata
- Authors
- Shreedhar, M., & Varghese, G.
- Venue
- ACM SIGCOMM Computer Communication Review
- Published
- 1995-10
- Volume
- 25
- Issue
- 4
- Pages
- 231-242
- ISSN
- 0146-4833 (ISSN-L)
- OpenAlex
- W3143248510
- Cited by
- 347
- References
- 8
- FWCI
- 7.84
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Efficient fair queueing using deficit round robin. https://app.cochat.ai/papers/10.1145/217391.217453
- The paper
- Shreedhar, M., & Varghese, G. (1995). Efficient fair queueing using deficit round robin. ACM SIGCOMM Computer Communication Review. https://doi.org/10.1145/217391.217453
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.