Abstract
We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when k = 2. They also introduced an “order-respecting” variant of k-FTM, called k-OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most \(\frac{ 2kB }{ \lfloor B/k \rfloor } + k\) for any B ≥ k, where B is the size of the buffer. They also gave a lower bound of \(\frac{ B }{ \lfloor 2B/k \rfloor }\) for deterministic online algorithms when 2B ≥ k and k is a power of 2.
In this paper, we improve upper and lower bounds on the competitive ratio of k-OFTM. Our main result is to improve an upper bound of O(k 2) by Kesselman et al. to \(\frac{5B + \lfloor B/k \rfloor - 4}{\lfloor B/2k \rfloor} = O(k)\) for B ≥ 2k. Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al. is Ω(k). We also give two lower bounds. First we give a lower bound of \(\frac{2B}{\lfloor{B/(k-1)} \rfloor} + 1\) on the competitive ratio of deterministic online algorithms for any k ≥ 2 and any B ≥ k − 1, which improves the previous lower bound of \(\frac{B}{ \lfloor 2B/k \rfloor }\) by a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of k − 1 against an oblivious adversary for any k ≥ 3 and any B. Since a deterministic algorithm, as mentioned above, achieves an upper bound of about 10k, this indicates that randomization does not help too much.
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Mansour, Y., Rajagopolan, S., Rosén, A.: Competitive queue policies for differentiated services. Journal of Algorithms 55(2), 113–141 (2005)
Albers, S., Schmidt, M.: On the performance of greedy algorithms in packet buffering. SIAM Journal on Computing 35(2), 278–304 (2005)
Andelman, N.: Randomized queue management for DiffServ. In: In Proc. of the 17th ACM Symposium on Parallel Algorithms and Architectures, pp. 1–10 (2005)
Andelman, N., Mansour, Y.: Competitive management of non-preemptive queues with multiple values. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 166–180. Springer, Heidelberg (2003)
Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies for QoS switches. In: Proc. of the 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 761–770 (2003)
Azar, Y., Litichevskey, A.: Maximizing throughput in multi-queue switches. Algorithmica 45(1), 69–90 (2006)
Azar, Y., Richter, Y.: Management of multi-queue switches in QoS networks. Algorithmica 43(1-2), 81–96 (2005)
Azar, Y., Richter, Y.: An improved algorithm for CIOQ switches. ACM Transactions on Algorithms 2(2), 282–295 (2006)
Bienkowski, M.: An optimal lower bound for buffer management in multi-queue switches. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1295–1305 (2010)
Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)
Emek, Y., Halldórsson, M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing and competitive scheduling of multi-part tasks. In: Proc. of the 29th ACM Symposium on Principles of Distributed Computing, pp. 440–449 (2010)
Englert, M., Westermann, M.: Lower and upper bounds on FIFO buffer management in QoS switches. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 352–363. Springer, Heidelberg (2006)
Goldwasser, M.: A survey of buffer management policies for packet switches. ACM SIGACT News 41(1), 100–128 (2010)
Hahne, E., Kesselman, A., Mansour, Y.: Competitive buffer management for shared-memory switches. In: Proc. of the 13th ACM Symposium on Parallel Algorithms and Architectures, pp. 53–58 (2001)
Halldórsson, M., Patt-Shamir, B., Rawitz, D.: Online Scheduling with Interval Conflicts. In: Proc. of the 28th Symposium on Theoretical Aspects of Computer Science, pp. 472–483 (2011)
Kawahara, J., Kobayashi, K.M.: Optimal Buffer Management for 2-Frame Throughput Maximization. In: Proc. of the 20th International Colloquium on Structural Information and Communication Complexity (2013)
Kawahara, J., Kobayashi, K.M., Miyazaki, S.: Better Bounds for Online k-Frame Throughput Maximization in Network Switches. arXiv:1309.4919 [cs.DS] (2013)
Kesselman, A., Lotker, Z., Mansour, Y., Patt-Shamir, B., Schieber, B., Sviridenko, M.: Buffer overflow management in QoS switches. SIAM Journal on Computing 33(3), 563–583 (2004)
Kesselman, A., Mansour, Y.: Harmonic buffer management policy for shared memory switches. Theoretical Computer Science 324(2-3), 161–182 (2004)
Kesselman, A., Mansour, Y., van Stee, R.: Improved competitive guarantees for QoS buffering. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 361–372. Springer, Heidelberg (2003)
Kesselman, A., Rosén, A.: Scheduling policies for CIOQ switches. Journal of Algorithms 60(1), 60–83 (2006)
Kesselman, A., Rosén, A.: Controlling CIOQ switches with priority queuing and in multistage interconnection networks. Journal of Interconnection Networks 9(1/2), 53–72 (2008)
Kesselman, A., Kogan, K., Segal, M.: Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing. In: Proc. of the 27th ACM Symposium on Principles of Distributed Computing, pp. 335–344 (2008)
Kesselman, A., Kogan, K., Segal, M.: Best effort and priority queuing policies for buffered crossbar switches. In: Shvartsman, A.A., Felber, P. (eds.) SIROCCO 2008. LNCS, vol. 5058, pp. 170–184. Springer, Heidelberg (2008)
Kesselman, A., Kogan, K., Segal, M.: Improved competitive performance bounds for CIOQ switches. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 577–588. Springer, Heidelberg (2008)
Kesselman, A., Patt-Shamir, B., Scalosub, G.: Competitive buffer management with packet dependencies. In: Proc. of the 23rd IEEE International Parallel and Distributed Processing Symposium, pp. 1–12 (2009)
Kobayashi, K., Miyazaki, S., Okabe, Y.: A tight bound on online buffer management for two-port shared-memory switches. In: Proc. of the 19th ACM Symposium on Parallel Algorithms and Architectures, pp. 358–364 (2007)
Kobayashi, K., Miyazaki, S., Okabe, Y.: Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms. In: Proc. of the 21st ACM Symposium on Parallel Algorithms and Architectures, pp. 328–336 (2009)
Mansour, Y., Patt-Shamir, B., Rawitz, D.: Overflow management with multipart packets. In: Proc. of the 31st IEEE Conference on Computer Communications, pp. 2606–2614 (2011)
Mansour, Y., Patt-Shamir, B., Rawitz, D.: Competitive router scheduling with structured data. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 219–232. Springer, Heidelberg (2012)
Scalosub, G., Marbach, P., Liebeherr, J.: Buffer management for aggregated streaming data with packet dependencies. In: Proc. of the 29th IEEE Conference on Computer Communications, pp. 1–5 (2010)
Sleator, D., Tarjan, R.: Amortized efficiency of list update and paging rules. Communications of the ACM 28(2), 202–208 (1985)
Sviridenko, M.: A lower bound for online algorithms in the FIFO model (2001) (unpublished manuscript)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kawahara, J., Kobayashi, K.M., Miyazaki, S. (2013). Better Bounds for Online k-Frame Throughput Maximization in Network Switches. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)