|
 ABSTRACT
We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. A fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
DEC87a
|
R. Jain and K. K. Ramakrishnan, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part I-Concepts, Goals, and Alternatives", DEC Technical Report TR-507, Digital Equipment Corporation, April 1987.
|
| |
DEC87b
|
K. K. Ramakrishnan and R. Jain, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part I{-An Explicit Binary Feedback Scheme", DEC Technical Report TR-508, Digital Equipment Corporation, April 1987.
|
| |
DEC87c
|
D.-M. Chiu and R. Jain, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part {II- Analysis of Increase and Decrease Algorithms", DEC Technical Report TR-509, Digital Equipment Corporation, April 1987.
|
| |
DEC87d
|
K. K. Ramakrishnan, D.-M. Chiu, and R. Jain "Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part IV-A Selective Binary Feedback Scheme for General Topologies", DEC Technical Report TR-510, Digital Equipment Corporation, November 1987.
|
| |
Fra84
|
A. Fraser and S. Morgan, "Queueing and Framing Disciplines for a Mixture of Data Traffic Types", AT&T Bell Laboratories Technical Journal, Volume 63, No. 6, pp 1061-1087, 1984.
|
| |
Gaf84
|
E. Gafni and D. Bertsekas, "Dynamic Control of Session Input Rates in Communication Networks", IEEE Transactions on Automatic Control, Volume 29, No. 10, pp 1009-1016, 1984.
|
| |
Ger80
|
M. Gerla and L. Kleinrock, "Flow Control: A Comparative Survey", {EEE Transactions on Communications, Volume 28, pp 553-574, 1980.
|
| |
Gre89
|
A. Greenberg and N. Madras, private communication, 1989.
|
| |
Hah86
|
E. Hahne, "Round Robin Scheduling for Fair Flow Control in Data Communication Networks", Report LIDS-TH-1631, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts. December, 1986.
|
| |
Has89
|
E. Hashem, private communication. 1989.
|
| |
Hey89
|
A. Heybey and C. Davin, private communication, 1989.
|
| |
ISO86
|
International Organization for Standardization (ISO), "Protocol for Providing the Connectionless Mode Network Service", Draft International Standard 8473, 1986.
|
 |
Jac88a
|
|
| |
Jac88b
|
V. Jacobson, private communication, 1988.
|
| |
Jai86
|
R. Jain, "Divergence of Timeout Algorithms for Packet Retransmission", Proceedings of the Fifth Annual International Phoenix Conference on Computers and Communications, pp 1162-1167, 1987.
|
| |
Kar87
|
|
| |
Kat87
|
M. Katevenis, "Fast Switching and Fair Control of Congested Flow in Broadband Networks", IEEE Journal on Selected Areas in Communications, Volume 5, No. 8, pp 1315-1327, 1987.
|
| |
Lo87
|
C.-Y. Lo, "Performance Analysis and Application of a Two-Priority Packet Queue", AT&T Technical Journal, Volume 66, No. 3, pp 83-99, 1987.
|
| |
Lua88
|
D. Luan and D. Lucantoni, "Throughput Analysis of an Adaptive Window-Based Flow Control Subject to Bandwidth Management", Proceedings of the International Teletraffic Conference, 1988.
|
| |
Man89
|
A. Mankin and K. Thompson, "Limiting Factors in the Performance of the Slostart TCP Algorithms", preprint.
|
| |
Mor89
|
S. Morgan, "Queueing Disciplines and Passive Congestion Control in Byte- Stream Networks", IEEE INFOCOM '89 Proceedings, pp 711-720, 1989.
|
| |
Mil87
|
|
| |
Mil88
|
|
| |
Nag84
|
|
| |
Nag85
|
J. Nagle, "On Packet Switches with Infinite Storage", RFC 896 1985.
|
| |
Nag87
|
J. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Volume 35, pp 435-438, 1987.
|
| |
Nes88
|
D. Bacon, A. Dupuy, J. Schwartz, and Y. Yemini, "Nest: A Network Simulation and Prototyping Tool", Dallas Winter 1988 Usenix Conference Proceedings, pp. 71-78, 1988.
|
| |
Per89
|
IETF Performance and Congestion Control Working Group, "Gateway Congestion Control Policies", draft, 1989.
|
| |
Pos81
|
J. Postel, "Internet Protocol", RFC 791 1981.
|
| |
Pru88
|
W. Prue and J. Postel, "A Queueing Algorithm to Provide Type-of-Service for IP Links", RFC1046, 1988.
|
| |
She89a
|
S. Shenker, "Game-Theoretic Analysis of Gateway Algorithms", in preparation, 1989.
|
| |
She89b
|
S. Shenker, "Comments on the IETF Performance and Congestion Control Working Group Draft on Gateway Congestion Control Policies", unpublished, 1989.
|
| |
Stu88
|
H. Sturgis, private communication, 1988.
|
| |
USC81
|
USC Information Science Institute, "Transmission Control Protocol", RFC 793, 1981.
|
| |
Xer81
|
Xerox Corporation, "Internet Transport Protoco Is", XSIS 028112, 1981.
|
| |
Zha89
|
L. Zhang, "A New Architecture for Packet Switching Network Protocols", MIT Ph.D. Thesis, forthcoming, 1989.
|
CITED BY 255
|
|
Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Timo Hamalainen , Jarmo Siltanen , Ari Viinikainen , Jyrki Joutsensalo, Adaptive tuning of scheduling parameters, Proceedings of the 2nd WSEAS International Conference on Electronics, Control and Signal Processing, p.1-4, December 07-09, 2003, Singapore
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Subhash Suri , George Varghese , Girish Chandranmenon, Leap forward virtual clock: a new fair queuing scheme with guaranteed delays and throughput fairness, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.281, August 21-24, 1997, Santa Barbara, California, United States
|
|
|
|
|
|
|
|
|
John Bruno , Eran Gabber , Banu Özden , Abraham Silberschatz, Move-to-rear list scheduling: a new scheduling algorithm for providing QoS guarantees, Proceedings of the fifth ACM international conference on Multimedia, p.63-73, November 09-13, 1997, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thyagarajan Nandagopal , Songwu Lu , Vaduvur Bharghavan, A unified architecture for the design and evaluation of wireless fair queueing algorithms, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.132-142, August 15-19, 1999, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P. Lin , B. Bensaou , Q. L. Ding , K. C. Chua, A wireless fair scheduling algorithm for error-prone wireless channels, Proceedings of the 3rd ACM international workshop on Wireless mobile multimedia, p.11-20, August 11-11, 2000, Boston, Massachusetts, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Bruno , Eran Gabber , Banu Özden , Abraham Silberschatz, The eclipse operating system: providing quality of service via reservation domains, Proceedings of the Annual Technical Conference on USENIX Annual Technical Conference, 1998, p.20-20, June 15-19, 1998, New Orleans, Louisiana
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vijay Sundaram , Abhishek Chandra , Pawan Goyal , Prashant Shenoy , Jasleen Sahni , Harrick Vin, Application performance in the QLinux multimedia operating system, Proceedings of the eighth ACM international conference on Multimedia, p.127-136, October 2000, Marina del Rey, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Abhishek Chandra , Micah Adler , Pawan Goyal , Prashant Shenoy, Surplus fair scheduling: a proportional-share CPU scheduling algorithm for symmetric multiprocessors, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.4-4, October 22-25, 2000, San Diego, California
|
|
|
|
|
|
|
|
|
Jennifer Howell , Ming Shu , Robert Wohlfarth, An object oriented application/programmer interface for network programming, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.437-444, February 14-16, 1993, Indianapolis, Indiana, United States
|
|
|
Prashant Shenoy , Pawan Goyal , Harrick M. Vin, Architectural considerations for next generation file systems, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.457-467, October 30-November 05, 1999, Orlando, Florida, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ratul Mahajan , Steven M. Bellovin , Sally Floyd , John Ioannidis , Vern Paxson , Scott Shenker, Controlling high bandwidth aggregates in the network, ACM SIGCOMM Computer Communication Review, v.32 n.3, p.62-73, July 2002
|
|
|
|
|
|
|
|
|
|
|
|
Abdesselem Kortebi , Luca Muscariello , Sara Oueslati , James Roberts, Minimizing the overhead in implementing flow-aware networking, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
|
|
|
Bogdan Caprita , Jason Nieh , Clifford Stein, Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dan Twining , Matthew M. Williamson , Miranda J. F. Mowbray , Maher Rahmouni, Email prioritization: reducing delays on legitimate mail caused by junk mail, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.4-4, June 27-July 02, 2004, Boston, MA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Pdf