On the performance of greedy algorithms in packet buffering

ABSTRACT

We study a basic buffer management problem that arises in network switches. Consider m input ports, each of which is equipped with a buffer (queue) of limited capacity. Data packets arrive online and can be stored in the buffers if space permits; otherwise packet loss occurs. In each time step the switch can transmit one packet from one of the buffers to the output port. The goal is to maximize the number of transmitted packets. Simple arguments show that any reasonable algorithm, which serves any non-empty buffer, is 2-competitive. Azar and Richter recently presented a randomized online algorithm and gave lower bounds for deterministic and randomized strategies.In practice greedy algorithms are very important because they are fast, use little extra memory and reduce packet loss by always serving a longest queue. In this paper we first settle the competitive performance of the entire family of greedy strategies. We prove that greedy algorithms are not better than 2-competitive no matter how ties are broken. Our lower bound proof uses a new recursive construction for building adversarial buffer configurations that may be of independent interest. We also give improved lower bounds for deterministic and randomized online algorithms.In the second part of the paper we present the first deterministic online algorithm that is better than 2-competitive. We develop a modified greedy algorithm, called Semi-Greedy, and prove that it achieves a competitive ratio of $17/9 ≅ 1. 89$. The new algorithm is simple, fast and uses little extra memory. Only when the risk of packet loss is low, it does not serve the longest queue. Additionally we study scenarios when an online algorithm is granted additional resources. We consider resource augmentation with respect to memory and speed, i. e. an online algorithm may be given larger buffers or higher transmission rates. We analyze greedy and other online strategies.

REFERENCES

• 1: W. Aiello, Y. Mansour, S. Rajagopolan and A. Rosen, Competitive queue policies for differentiated services. Proc. INFOCOM, 431--440, 2000.
• 2: 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
• 3: Yossi Azar , Yossi Richter, Management of multi-queue switches in QoS networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780556]
• 4: Adnan Aziz , Amit Prakash , Vijaya Ramachandra, A near optimal scheduler for switch-memory-switch routers, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777472]
• 5: Amotz Bar-Noy , Ari Freund , Shimon Landa , Joseph (Seffi) Naor, Competitive on-line switching policies, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.525-534, January 06-08, 2002, San Francisco, California
• 6: Ellen L. Hahne , Alexander Kesselman , Yishay Mansour, Competitve buffer management for shared-memory switches, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.53-58, July 2001, Crete Island, Greece [doi>10.1145/378580.378589]
• 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: A. Kesselman, Y. Mansour and R. van Stee. Improved competitive guarantees for QoS buffering Proc. 11th European Symp. on Algorithms, LNCS Vol. 2832, 361--372, 2003.
• 10: Alex Kesselman , Adi Rosén, Scheduling policies for CIOQ switches, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777473]
• 11: Hisashi Koga, Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness, Proceedings of the 12th International Symposium on Algorithms and Computation, p.61-73, December 19-21, 2001
• 12: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  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, competitive, greedy, network switch, online, packet, throughput