Core-stateless fair queueing: achieving approximately fair bandwidth allocations in high speed networks

ABSTRACT

Router mechanisms designed to achieve fair bandwidth allocations, like Fair Queueing, have many desirable properties for congestion control in the Internet. However, such mechanisms usually need to maintain state, manage buffers, and/or perform packet scheduling on a per flow basis, and this complexity may prevent them from being cost-effectively implemented and widely deployed. In this paper, we propose an architecture that significantly reduces this implementation complexity yet still achieves approximately fair bandwidth allocations. We apply this approach to an island of routers --- that is, a contiguous region of the network --- and we distinguish between edge routers and core routers. Edge routers maintain per flow state; they estimate the incoming rate of each flow and insert a label into each packet header based on this estimate. Core routers maintain no per flow state; they use FIFO packet scheduling augmented by a probabilistic dropping algorithm that uses the packet labels and an estimate of the aggregate traffic at the router. We call the scheme Core-Stateless Fair Queueing. We present simulations and analysis on the performance of this approach, and discuss an alternate approach.

REFERENCES

• 1: J. C. R. Bennett , D. C. Stephens , Hui Zhang, High speed, scalable, and accurate implementation of packet fair queueing algorithms in ATM networks, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.7, October 28-31, 1997
• 2: J.C.R. Bennett and H. Zhang. WF2Q: Worst-case fair weighted fair queueing. In Proceedings o/ {EEE {NFO- COM'96, pages 120-:128, San Francisco, CA, March 1996.
• 3: B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K. K. Ramakrishnan, S. Shenker, and J. Wroclawski. Recommendations on queue management and congestion avoidance in the internet, January 1998. Internet Draft,
• 4: R. Callon, P. Doolan, N. Feldman, A. Fredette, G. Swallow, and A. Viswanathan. A Framework for Multiprotocol Label Switching, November 1997. Internet Draft.
• 5: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.160-169, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 6: R. L. Cruz. SCED+: Efficient Management of Quality of Service Guarantees. In Proceedings of INFOCOM'98, pages 625--642, San Francisco, CA, 1998.
• 7: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 8: S. Floyd and K. Fall. Router mechanisms to support endto-end congestion control, February 1997. LBL Technical Report.
• 9: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 10: S. Colestanl. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE INFOCOM'9J, pages 636-646, Toronto, CA, June 1994.
• 11: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 12: J. Jaffe. Bottleneck flow control. IEEE Transactions on Communications, 7(29):954-962, July 1980.
• 13: Srinivasan Keshav, A control-theoretic approach to flow control, Proceedings of the conference on Communications architecture & protocols, p.3-15, September 03-06, 1991, Zurich, Switzerland
• 14: Dong Lin , Robert Morris, Dynamics of random early detection, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.127-137, September 14-18, 1997, Cannes, France
• 15: Steven Ray Mccanne , Martin Vetterli, Scalable compression and transmission of internet multicast video, 1996
• 16: J Nagle. On packet switches with infinite storage. IEEE Trans. On Uommunications, 35(4):435-438, April 1987.
• 17: Ucb/lbnl/vint network simulator- ns (version 2).
• 18: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks—the single node case, Proceedings of the eleventh annual joint conference of the IEEE computer and communications societies on One world through communications (Vol. 2), p.915-924, May 1992, Florence, Italy
• 19: Scott Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, Proceedings of the conference on Communications architectures, protocols and applications, p.47-57, August 31-September 02, 1994, London, United Kingdom
• 20: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 21: Dimitrios Stiliadis , Anujan Varma, Efficient fair queueing algorithms for packet-switched networks, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.175-185, April 1998 [doi>10.1109/90.664266]
• 22: I. Stoica, S. Shenker, and H. Zhang. Core-stateless fair queueing: Achieving approximately fair banwidth allocations in high speed nteworks, June 1998. Technical Report CMU-CS-98-136, Carnegie Mellon University.
• 23: I. Stoica and H. Zhang. LIRA: A model for service differentiation in the internet. In Proceedings of NOSSDAV'98, London, UK, july 1998.
• 24: Z. Wang. User-share differentiation (USD) scalable bandwidth allocation for differentiated services, May 1998. Internet Draft.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

General Terms:
Design, Performance