Scalable QoS provision through buffer management

ABSTRACT

In recent years, a number of link scheduling algorithms have been proposed that greatly improve upon traditional FIFO scheduling in being able to assure rate and delay bounds for individual sessions. However, they cannot be easily deployed in a backbone environment with thousands of sessions, as their complexity increases with the number of sessions. In this paper, we propose and analyze an approach that uses a simple buffer management scheme to provide rate guarantees to individual flows (or to a set of flows) multiplexed into a common FIFO queue. We establish the buffer allocation requirements to achieve these rate guarantees and study the trade-off between the achievable link utilization and the buffer size required with the proposed scheme. The aspect of fair access to excess bandwidth is also addressed, and its mapping onto a buffer allocation rule is investigated. Numerical examples are provided that illustrate the performance of the proposed schemes. Finally, a scalable architecture for QoS provisioning is presented that integrates the proposed buffer management scheme with WFQ scheduling that uses a small number of queues.

REFERENCES

• 1: A. K. Choudhury and E. L. Hahne. Dynamic queue length thrcsholds in a shared memory ATM switch. In Proceedings of INFOCOM, pages 679-687, San Francisco, CA, April 1996.
• 2: Israel Cidon , Roch Guérin , Asad Khamisy, On protective buffer policies, IEEE/ACM Transactions on Networking (TON), v.2 n.3, p.240-246, June 1994 [doi>10.1109/90.311616]
• 3: 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]
• 4: Leonidas Georgiadis , Roch Guérin , Vinod Peris , Kumar N. Sivarajan, Efficient network QoS provisioning based on per node traffic shaping, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.482-501, Aug. 1996 [doi>10.1109/90.532860]
• 5: 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
• 6: A. K. J. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. PhD thesis, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1992. No. LIDS-TH-2089.
• 7: A. Romanow and S. Floyd. Dynamics of TCP traffic over ATM networks. IEEE dl Sel. Areas Commun., 13(4):633-641, May 1995.
• 8: Subhash Suri , George Varghese , Girish Chandranmenon, Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delay and Throughput Fairness, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.557, April 09-11, 1997
• 9: J. Turner. Maintaining high throughput during overload in ATM switches. In Proceedings of lNFOCOM, pages 287- 295, San Francisco, CA, April 1996.
• 10: Dallas E. Wrege Jörg Liebeherr, A Near-Optimal Packet Scheduler for QoS Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.576, April 09-11, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Performance

Keywords:
buffer management, fairness, rate guarantees, scheduling, sharing