Abstract
We consider the management of FIFO buffers for network switches providing differentiated services. In each time step, an arbitrary number of packets arrive and only one packet can be sent. The buffer can store a limited number of packets and, due to the FIFO property, the sequence of sent packets has to be a subsequence of the arriving packets. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy can drop packets, and the goal is to maximize the sum of the values of sent packets.
For only two different packet values, we introduce the account strategy and prove that this strategy achieves an optimal competitive ratio of \(\sqrt{2}-(\sqrt{5+4\sqrt{2}}-3)/2\approx 1.282\) if the buffer size tends to infinity and an optimal competitive ratio of \((\sqrt{13}-1)/2\approx 1.303\) for arbitrary buffer sizes. For general packet values, the simple preemptive greedy strategy (PG) is studied. We show that PG achieves a competitive ratio of \(\sqrt{3}\approx 1.732\) which is the best known upper bound on the competitive ratio of this problem. In addition, we give a lower bound of \(1+1/\sqrt{2}\approx 1.707\) on the competitive ratio of PG which improves the previously known lower bound. As a consequence, the competitive ratio of PG cannot be further improved significantly.
Similar content being viewed by others
References
Aiello, W., Mansour, Y., Rajagopolan, S., Rosen, A.: Competitive queue policies for differentiated services. J. Algorithms 55(2), 113–141 (2005)
Andelman, N.: Randomized queue management for DiffServ. In: Proceedings of the 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 1–10 (2005)
Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies for QoS switches. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 761–770 (2003)
Azar, Y., Richter, Y.: Management of multi-queue switches in QoS networks. Algorithmica 43(1–2), 81–96 (2005)
Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., Sviridenko, M.: Further improvements in competitive guarantees for QoS buffering. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 196–207 (2004)
Jawor, W.: Three dozen papers on online algorithms. SIGACT News 36(1), 71–85 (2005)
Kesselman, A., Lotker, Z., Mansour, Y., Patt-Shamir, B., Schieber, B., Sviridenko, M.: Buffer overflow management in QoS switches. SIAM J. Comput. 33(3), 563–583 (2004)
Kesselman, A., Mansour, Y.: Loss-bounded analysis for differentiated services. J. Algorithms 46(1), 79–95 (2003)
Kesselman, A., Mansour, Y., van Stee, R.: Improved competitive guarantees for QoS buffering. Algorithmica 43(1–2), 63–80 (2005)
Lotker, Z., Patt-Shamir, B.: Nearly optimal FIFO buffer management for two packet classes. Comput. Networks 42(4), 481–492 (2003)
Mansour, Y., Patt-Shamir, B., Lapid, O.: Optimal smoothing schedules for real-time streams. Distrib. Comput. 17(1), 77–89 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the DFG grant WE 2842/1. A preliminary version of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms (ESA), 2006.
Rights and permissions
About this article
Cite this article
Englert, M., Westermann, M. Lower and Upper Bounds on FIFO Buffer Management in QoS Switches. Algorithmica 53, 523–548 (2009). https://doi.org/10.1007/s00453-008-9236-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-008-9236-5