Nearly optimal FIFO buffer management for DiffServ

ABSTRACT

We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output stream rate is bounded, so overflows may occur. Motivated by DiffServ, we assume that each packet has value either 1 or α, for some α > 1. The buffer management task is to decide which packets to drop so as to minimize the total value of lost packets, subject to the buffer space bound, and to the FIFO order of sent packets. We consider push-out buffers, where the algorithm may eject packets from anywhere in the buffer. The best lower bound on the competitive ratio of on-line algorithms for buffer management is approximately 1.28. In this paper we present an on-line algorithm whose competitive ratio is approximately 1.30 for the worst case α. The best previous general upper bound was about 1.888.

REFERENCES

• 1: W. Aiello, Y. Mansour, S. Rajagopolan, and A. Rosen. Competitive queue policies for diffrentiated services. In Proc. IEEE INFOCOM, 2000.
• 2: D. Black, S. Blake, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An architecture for differentiated services. Internet RFC 2475, December 1998.
• 3: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 4: D. Clark and J. Wroclawski. An approach to service allocation in the Internet. Internet draft, 1997. Available from diffserv.lcs.mit.edu.
• 5: R. Cruz. A calculus for network delay part I: Network elements in isolation. IEEE Trans. Info. Theory, 37(1):114-131, Jan. 1991.
• 6: 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]
• 7: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer overflow management in QoS switches, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.520-529, July 2001, Hersonissos, Greece [doi>10.1145/380752.380847]
• 8: Alexander Kesselman , Yishay Mansour, Loss-bounded analysis for differentiated services, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.591-600, January 07-09, 2001, Washington, D.C., United States
• 9: M. A. Labrador and S. Banerjee. Packet dropping policies for ATM and IP networks. IEEE Communications Surveys, 2(3), 1999.
• 10: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 11: Z. Lotker. Personal Communication, October 2000.
• 12: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]
• 13: M. May, J.-C. Bolot, A. Jean-Marie, and C. Diot. Simple performance models of differentiated services for the Internet. In Proc. IEEE INFOCOM, 1998.
• 14: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 15: M. Sviridenko. A lower bound for on-line algorithms in the FIFO model. Unpublished manuscruipt, Apr. 2001.
• 16: The ATM Forum Technical Committee. Traffic management specification version 4.0, Apr. 1996. Available from www.atmforum.com.
• 17: A. Veres and M. Boda. The chaotic nature of TCP congestion control. In Proc. IEEE INFOCOM, pages 1715-1723, 2000.