Competitive buffer management for shared-memory switches

ABSTRACT

We consider buffer management policies for shared memory switches. We study the case of overloads resulting in packet loss, where the constraint is the limited shared memory capacity. The goal of the buffer management policy is that of maximizing the number of packets transmitted. The problem is online in nature, and thus we use competitive analysis to measure the performance of the buffer management policies. Our main result is to show that the well-known preemptive Longest Queue Drop (LQD) policy is at most 2-competitive and at least &sqrt;2-competitive. We also demonstrate a general lower bound of 4/3 on the performance of any deterministic online policy. Finally, we consider some other popular non-preemptive policies including Complete Partition, Complete Sharing, Static Threshold and Dynamic Threshold and derive almost tight bounds on their performance.

REFERENCES

• 1: William A. Aiello , Yishay Mansour , S. Rajagopolan , Adi Rosén, Competitive queue policies for differentiated services, Journal of Algorithms, v.55 n.2, p.113-141, May 2005 [doi>10.1016/j.jalgor.2004.04.004]
• 2: Susanne Albers , Markus Schmidt, On the Performance of Greedy Algorithms in Packet Buffering, SIAM Journal on Computing, v.35 n.2, p.278-304, 2005 [doi>10.1137/S0097539704446268]
• 3: Nir Andelman , Yishay Mansour , An Zhu, Competitive queueing policies for QoS switches, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: Arpaci, M., and Copeland, J. A. 2000. Buffer management for shared-memory atm switches. IEEE Commun. Surv. 3, 1, 2--10.
• 5: Yossi Azar , Arik Litichevskey, Maximizing throughput in multi-queue switches, Algorithmica, v.45 n.1, p.69-90, April 2006 [doi>10.1007/s00453-005-1190-x]
• 6: Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007369]
• 7: Azar, Y., and Richter, Y. 2005. Management of multi-queue switches in qos networks. Algorithmica 43, 1-2, 81--96.
• 8: Yossi Azar , Yossi Richter, An improved algorithm for CIOQ switches, ACM Transactions on Algorithms (TALG), v.2 n.2, p.282-295, April 2006 [doi>10.1145/1150334.1150342]
• 9: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 10: Abhijit K. Choudhury , Ellen L. Hahne, Dynamic queue length thresholds for shared-memory packet switches, IEEE/ACM Transactions on Networking (TON), v.6 n.2, p.130-140, April 1998 [doi>10.1109/90.664262]
• 11: Marek Chrobak, SIGACT news online algorithms column 4, ACM SIGACT News, v.35 n.3, September 2004 [doi>10.1145/1027914.1027930]
• 12: Irland, M. 1978. Buffer management in a packet switch. IEEE Trans. Commun. COM-26, 3 (Mar.), 328--337.
• 13: Kamoun, F., and Kleinrock, L. 1980. Analysis of shared finite storage in a computer network node environment under general traffic conditions. IEEE Trans. Commun. COM-28, 7 (July), 992--1003.
• 14: Alexander Kesselman , Yishay Mansour, Harmonic buffer management policy for shared memory switches, Theoretical Computer Science, v.324 n.2-3, p.161-182, 20 September 2004 [doi>10.1016/j.tcs.2004.05.014]
• 15: Alex Kesselman , Adi Rosén, Scheduling policies for CIOQ switches, Journal of Algorithms, v.60 n.1, p.60-83, July 2006 [doi>10.1016/j.jalgor.2004.09.003]
• 16: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer Overflow Management in QoS Switches, SIAM Journal on Computing, v.33 n.3, p.563-583, 2004 [doi>10.1137/S0097539701399666]
• 17: Kroner, H. 1990. Comparative peformance study of space priority mechanisms for atm networks. In Proceedings of IEEE INFOCOM 1990. IEEE Computer Society Press, Los Alamitos, CA, 1136--1143.
• 18: 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]
• 19: Thareja, A. K., and Agrawala, A. K. 1984. On the design of optimal policy for sharing finite buffers. IEEE Trans. Communications COM-32, 6 (June), 737--740.
• 20: Wei, S. X., Coyle, E. J., and Hsiao, M. T. 1991. An optimal buffer management policy for high-performance packet switching. In Proceedings of IEEE GLOBECOM 1991. IEEE Computer Society Press, Los Alamitos, CA, 924--928.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory

Keywords:
Buffer management, competitive analysis, shared memory