Abstract
We study packet buffering, a basic problem occurring in network switches. We construct an optimal 16/13-competitive randomized online algorithm 
for the case of two input buffers of arbitrary sizes. Our proof is based on geometrical transformations which allow to identify the set of sequences incurring extremal competitive ratios. Later we may analyze the performance of 
on these sequences only.
Extended abstract. The full version of this paper is available online. Research supported by MNiSW grant number N206 001 31/0436, 2006–2008, MNiSW grant number N206 1723 33, 2007–2010, and by an Akamai Presidential Fellowship.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albers, S., Schmidt, M.: On the performance of greedy algorithms in packet buffering. In: Proc. of the 36th ACM Symp. on Theory of Computing (STOC), pp. 35–44 (2004)
Azar, Y., Richter, Y.: Management of multi-queue switches in QoS networks. In: Proc. of the 35th ACM Symp. on Theory of Computing (STOC), pp. 82–89 (2003)
Chrobak, M., Larmore, L.L., Reingold, N., Westbrook, J.: Page migration algorithms using work functions. Journal of Algorithms 24(1), 406–415 (1993) In: Proc. of the 4th ISAAC, pp. 406–415 (1993)
Englert, M., Westermann, M.: Lower and upper bounds on FIFO buffer management in QoS switches. In: Proc. of the 14th European Symp. on Algorithms (ESA), pp. 352–363 (2006)
Englert, M., Westermann, M.: Considering suppressed packets improves buffer management in QoS switches. In: Proc. of the 18th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 209–218 (2007)
Kesselman, A., Mansour, Y., van Stee, R.: Improved competitive guarantees for QoS buffering. Algorithmica 43(1–2), 63–80 (2005) In: Proc. of the 11th ESA, pp. 361–372 (2003)
Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. Journal of the ACM 42(5), 971–983 (1995) In: Proc. of the 26th STOC, pp. 507–511 (1994)
Leland, W.E., Taqqu, M.S., Willinger, W., Wilson, D.V.: On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Transactions on Networking 2(1), 1–15 (1994)
May, M., Bolot, J., Jean-Marie, A., Diot, C.: Simple performance models of differentiated services schemes for the internet. In: Proc. of the IEEE INFOCOM, pp. 1385–1394 (1999)
Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365–374 (1987)
Schmidt, M.: Packet buffering: Randomization beats deterministic algorithms. In: Proc. of the 22nd Symp. on Theoretical Aspects of Computer Science (STACS), pp. 293–304 (2005)
Schmidt, M.: Online Packet Buffering. PhD thesis, Albert-Ludwigs-Universität Freiburg (2006)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202–208 (1985)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bienkowski, M., Mądry, A. (2008). Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-78773-0_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78772-3
Online ISBN: 978-3-540-78773-0
eBook Packages: Computer ScienceComputer Science (R0)