Document Open Access Logo

Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop

Authors Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, Pavel Veselý

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.17.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Author Details

Antonios Antoniadis
  • University of Twente, The Netherlands
Matthias Englert
  • University of Warwick, Coventry, UK
Nicolaos Matsakis
  • Athens, Greece
Pavel Veselý
  • Computer Science Institute of Charles University, Prague, Czech Republic

Funding

  • Antoniadis, Antonios: Work done in part while the author was at Saarland University and Max-Planck-Institute for Informatics and supported by DFG grant AN 1262/1-1.
  • Veselý, Pavel: Work done while the author was at University of Warwick. Partially supported by European Research Council grant ERC-2014-CoG 647557, by GA ČR project 19-27871X, and by Charles University project UNCE/SCI/004.

Cite AsGet BibTex

Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, and Pavel Veselý. Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.17

Abstract

We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably rejected. At the end of each time step, each output port transmits a packet in its queue and the goal is to maximize the number of transmitted packets. The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from the back of whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and is known to be 2-competitive since 2001. Although LQD remains the best known online algorithm for the problem and is of practical interest, determining its true competitiveness is a long-standing open problem. We show that LQD is 1.707-competitive, establishing the first (2-ε) upper bound for the competitive ratio of LQD, for a constant ε > 0.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • buffer management
  • online scheduling
  • online algorithms
  • longest queue drop

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. W. Aiello, A. Kesselman, and Y. Mansour. Competitive buffer management for shared-memory switches. ACM Transactions on Algorithms, 5(1):3:1-3:16, 2008. Google Scholar
  2. K. Al-Bawani, M. Englert, and M. Westermann. Online packet scheduling for CIOQ and buffered crossbar switches. Algorithmica, 80(12):3861-3888, 2018. Google Scholar
  3. S. Albers and M. Schmidt. On the performance of greedy algorithms in packet buffering. SIAM Journal on Computing, 35(2):278-304, 2005. Google Scholar
  4. N. Andelman, Y. Mansour, and A. Zhu. Competitive queueing policies for QoS switches. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 761-770, 2003. Google Scholar
  5. Y. Azar and A. Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69-90, 2006. Google Scholar
  6. Y. Azar and Y. Richter. Management of multi-queue switches in QoS networks. Algorithmica, 43(1-2):81-96, 2005. Google Scholar
  7. N. Bansal, L. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, and M. Sviridenko. Further improvements in competitive guarantees for QoS buffering. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pages 196-207, 2004. Google Scholar
  8. M. Bienkowski, M. Chrobak, and Ł Jeż. Randomized competitive algorithms for online buffer management in the adaptive adversary model. Theoretical Computer Science, 412(39):5121-5131, 2011. Google Scholar
  9. I. Bochkov, A. Davydow, N. Gaevoy, and S. I. Nikolenko. New competitiveness bounds for the shared memory switch. CoRR, abs/1907.04399, 2019. URL: http://arxiv.org/abs/1907.04399.
  10. J. L. Bruno, B. Özden, A. Silberschatz, and H. Saran. Early fair drop: a new buffer management policy. Multimedia Computing and Networking, 3654:148-161, 1998. Google Scholar
  11. S. Chamberland and B. Sansò. Overall design of reliable ip networks with performance guarantees. In Proceedings of the IEEE International Conference on Communications: Global Convergence Through Communications (ICC), pages 1145-1151, 2000. Google Scholar
  12. H. J. Chao and X. Guo. Quality of Service Control in High-Speed Networks. Wiley-IEEE Press, 2001. Google Scholar
  13. H. J. Chao and B. Liu. High Performance Switches and Routers. Wiley-IEEE Press, 2007. Google Scholar
  14. F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, and T. Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms, 4(2):255-276, 2006. Google Scholar
  15. F. Y. L. Chin and S. P. Y. Fung. Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica, 37(3):149-164, 2003. Google Scholar
  16. M. Chrobak, W Jawor, J. Sgall, and T. Tichý. Improved online algorithms for buffer management in QoS switches. ACM Transactions on Algorithms, 3(4):50, 2007. Google Scholar
  17. M. Englert and M. Westermann. Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica, 53(4):523-548, 2009. Google Scholar
  18. M. Englert and M. Westermann. Considering suppressed packets improves buffer management in quality of service switches. SIAM Journal on Computing, 41(5):1166-1192, 2012. Google Scholar
  19. P. Eugster, K. Kogan, S. Nikolenko, and A. Sirotkin. Shared memory buffer management for heterogeneous packet processing. In Proceedings of the 34th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 471-480, 2014. Google Scholar
  20. M. H. Goldwasser. A survey of buffer management policies for packet switches. SIGACT News, 41(1):100-128, 2010. Google Scholar
  21. E. L. Hahne, A. Kesselman, and Y. Mansour. Competitive buffer management for shared-memory switches. In Proceedings of the 13th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 53-58, 2001. Google Scholar
  22. B. Hajek. On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings of the 35th Conference on Information Sciences and Systems, pages 434-438, 2001. Google Scholar
  23. Ł. Jeż. A universal randomized packet scheduling algorithm. Algorithmica, 67(4):498-515, 2013. Google Scholar
  24. A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber, and M. Sviridenko. Buffer overflow management in QoS switches. SIAM Journal on Computing, 33(3):563-583, 2004. Google Scholar
  25. A. Kesselman and Y. Mansour. Harmonic buffer management policy for shared memory switches. Theoretical Computer Science, 324(2-3):161-182, 2004. Google Scholar
  26. A. Kesselman, Y. Mansour, and R. van Stee. Improved competitive guarantees for QoS buffering. Algorithmica, 43(1-2):63-80, 2005. Google Scholar
  27. A. Kesselman and A. Rosén. Scheduling policies for CIOQ switches. Journal of Algorithms, 60(1):60-83, 2006. Google Scholar
  28. K. M. Kobayashi, S. Miyazaki, and Y. Okabe. A tight bound on online buffer management for two-port shared-memory switches. In Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 358-364, 2007. Google Scholar
  29. F. Li, J. Sethuraman, and C. Stein. Better online buffer management. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 199-208, 2007. Google Scholar
  30. N. Matsakis. Approximation Algorithms for Packing and Buffering problems. PhD thesis, University of Warwick, UK, 2015. Google Scholar
  31. M. Nabeshima and K. Yata. Performance improvement of active queue management with per-flow scheduling. IEE Proceedings-Communications, 152(6):797-803, 2005. Google Scholar
  32. S. I. Nikolenko and K. Kogan. Single and multiple buffer processing. In Encyclopedia of Algorithms, pages 1988-1994. Springer, 2016. Google Scholar
  33. B. Suter, T. V. Lakshman, D. Stiliadis, and A. K. Choudhury. Design considerations for supporting TCP with per-flow queueing. In Proceedings of the 17th IEEE Conference on Computer Communications (INFOCOM), pages 299-306, 1998. Google Scholar
  34. P. Veselý, M. Chrobak, Ł. Jeż, and J. Sgall. A ϕ-competitive algorithm for scheduling packets with deadlines. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 123-142, 2019. Google Scholar
  35. S. X. Wei, E. J. Coyle, and M. T. Hsiao. An optimal buffer management policy for high-performance packet switching. In Proceedings of the Global Communication Conference (GLOBECOM), pages 924-928, 1991. Google Scholar
  36. A. Zhu. Analysis of queueing policies in QoS switches. Journal of Algorithms, 53(2):137-168, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact