|
Warning: The download time has expired please click on the item to try again.
 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 288
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Charles R. Kalmanek , Srinivasan Keshav , William T. Marshall , Samuel P. Morgan , Robert C. Restrick, III, Xunet 2: lessons from an early wide-area ATM testbed, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.40-55, Feb. 1997
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
Takeshi Yoshimura , Yoshifumi Yonemoto , Tomoyuki Ohya , Minoru Etoh , Susie Wee, Mobile streaming media CDN enabled by dynamic SMIL, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Miklos Ajtai , James Aspnes , Moni Naor , Yuval Rabani , Leonard J. Schulman , Orli Waarts, Fairness in scheduling, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.477-485, January 22-24, 1995, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Haiyun Luo , Songwu Lu , Vaduvur Bharghavan, A new model for packet scheduling in multihop wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.76-86, August 06-11, 2000, Boston, Massachusetts, United States
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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, 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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sriram Ramabhadran , Joseph Pasquale, Stratified round Robin: a low complexity packet scheduler with bandwidth fairness and bounded delay, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Patrick Traynor , William Enck , Patrick McDaniel , Thomas La Porta, Mitigating attacks on open functionality in SMS-capable cellular networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ratul Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
Sean Rhea , Brighten Godfrey , Brad Karp , John Kubiatowicz , Sylvia Ratnasamy , Scott Shenker , Ion Stoica , Harlan Yu, OpenDHT: a public DHT service and its uses, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
|
|
|
|
|
|
|
|
|
Yuting Zhang , Azer Bestavros , Mina Guirguis , Ibrahim Matta , Richard West, Friendly virtual machines: leveraging a feedback-control model for application adaptation, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, 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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nikolaos Doulamis , Anastasios Doulamis , Antonios Litke , Athanasios Panagakis , Theodora Varvarigou , Emmanuel Varvarigos, Adjusted fair scheduling and non-linear workload prediction for QoS guarantees in grid computing, Computer Communications, v.30 n.3, p.499-515, February, 2007
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
Bogdan Caprita , Wong Chun Chan , Jason Nieh , Clifford Stein , Haoqiang Zheng, Group ratio round-robin: O(1) proportional share scheduling for uniprocessor and multiprocessor systems, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.36-36, April 10-15, 2005, Anaheim, CA
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
John Bruno , José Brustoloni , Eran Gabber , Banu Özden , Abraham Silberschatz, Retrofitting quality of service into a time-sharing operating system, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.2-2, June 06-11, 1999, Monterey, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
K. McLaughlin , S. Sezer , H. Blume , X. Yang , F. Kupzog , T. Noll, A scalable packet sorting circuit for high-speed WFQ packet scheduling, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.7, p.781-791, July 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pete Räsänen , Simo Lintunen , Riku Kuismanen , Jyrki Joutsensalo , Timo Hämäläinen, Gradient scheduling algorithm for fair delay guarantee in logarithmic pricing scenario, Proceedings of the 1st international conference on Simulation tools and techniques for communications, networks and systems & workshops, March 03-07, 2008, Marseille, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Khalid Al-Begain , Alexander Dudin , Arseniy Kazimirsky , Suleiman Yerima, Investigation of the M2/G2/1/∞,N queue with restricted admission of priority customers and its application to HSDPA mobile systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.8, p.1186-1201, June, 2009
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2