A. Demers
S. Keshav
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.
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
- 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.]]Google ScholarCross Ref
- Ger80.M. Gerla and L. Kleinrock, "Flow Control: A Comparative Survey", {EEE Transactions on Communications, Volume 28, pp 553-574, 1980.]]Google ScholarCross Ref
- Gre89.A. Greenberg and N. Madras, private communication, 1989.]]Google Scholar
- 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.]]Google Scholar
- Has89.E. Hashem, private communication. 1989.]]Google Scholar
- Hey89.A. Heybey and C. Davin, private communication, 1989.]]Google Scholar
- ISO86.International Organization for Standardization (ISO), "Protocol for Providing the Connectionless Mode Network Service", Draft International Standard 8473, 1986.]] Google ScholarDigital Library
- Jac88a.V. Jacobson, "Congestion Avoidance and Control", ACM SigComm Proceedings, pp 314-329, 1988.]] Google ScholarDigital Library
- Jac88b.V. Jacobson, private communication, 1988.]]Google Scholar
- 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.]]Google Scholar
- Kar87.P. Karn and C. Partridge, "Improving Round-Trip Time Estimates in Reliable Transport Protocols", ACM SigComm Proceedings, pp 2-7, 1987.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- Man89.A. Mankin and K. Thompson, "Limiting Factors in the Performance of the Slostart TCP Algorithms", preprint.]]Google Scholar
- Mor89.S. Morgan, "Queueing Disciplines and Passive Congestion Control in Byte- Stream Networks", IEEE INFOCOM '89 Proceedings, pp 711-720, 1989.]]Google Scholar
- Mil87.D. Mills and W.-W. Braun, "The NSFNET Backbone Network", ACM SigComm Proceedings, pp 191-196, 1987.]] Google ScholarDigital Library
- Mil88.D. Mills, "The Fuzzball", ACM SigComm Proceedings, pp 115-122. 1988.]] Google ScholarDigital Library
- Nag84.J. Nagle, "Congestion Control in IP/TCP Networks, Computer Communication Review, Vol 14, No. 4, pp 11-17, 1984.]] Google ScholarDigital Library
- Nag85.J. Nagle, "On Packet Switches with Infinite Storage", RFC 896 1985.]]Google Scholar
- Nag87.J. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Volume 35, pp 435-438, 1987.]]Google ScholarCross Ref
- 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.]]Google Scholar
- Per89.IETF Performance and Congestion Control Working Group, "Gateway Congestion Control Policies", draft, 1989.]]Google Scholar
- Pos81.J. Postel, "Internet Protocol", RFC 791 1981.]]Google Scholar
- Pru88.W. Prue and J. Postel, "A Queueing Algorithm to Provide Type-of-Service for IP Links", RFC1046, 1988.]] Google ScholarDigital Library
- She89a.S. Shenker, "Game-Theoretic Analysis of Gateway Algorithms", in preparation, 1989.]]Google Scholar
- She89b.S. Shenker, "Comments on the IETF Performance and Congestion Control Working Group Draft on Gateway Congestion Control Policies", unpublished, 1989.]]Google Scholar
- Stu88.H. Sturgis, private communication, 1988.]]Google Scholar
- USC81.USC Information Science Institute, "Transmission Control Protocol", RFC 793, 1981.]]Google Scholar
- Xer81.Xerox Corporation, "Internet Transport Protoco Is", XSIS 028112, 1981.]]Google Scholar
- Zha89.L. Zhang, "A New Architecture for Packet Switching Network Protocols", MIT Ph.D. Thesis, forthcoming, 1989.]]Google Scholar
Index Terms
- Analysis and simulation of a fair queueing algorithm
Recommendations
Analysis and simulation of a fair queueing algorithm
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 ...
Rainbow fair queueing: theory and applications
Fair bandwidth sharing at routers has several advantages, including protection of well-behaved flows and possible simplification of end-to-end congestion control mechanisms. Traditional mechanisms to achieve fair sharing (e.g., Weighted Fair Queueing, ...
Dynamic Fair Queuing (DFQ): A Novel Fair Scheduler Improving Wireless Transmission over Hybrid LANs
ISCC '03: Proceedings of the Eighth IEEE International Symposium on Computers and CommunicationsLocal area network (LAN) will be a hybrid networkthat includes wired and wireless links together.Nonetheless, the wired hosts always take the mostbandwidth and bring about the bandwidth allocationunfairness. This problem is caused by the flow ...
Comments