{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T21:26:47Z","timestamp":1765142807001,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:p>We consider the following buffer management problem arising in QoS networks: Packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. Packets not forwarded before their deadlines are lost. The main result of the article is an online 64\/33 \u2248 1.939-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. For the 2-uniform case we give an algorithm with ratio \u2248 1.377 and a matching lower bound.<\/jats:p>","DOI":"10.1145\/1290672.1290687","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Improved online algorithms for buffer management in QoS switches"],"prefix":"10.1145","volume":"3","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Jawor","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[{"name":"Academy of Sciences of the Czech Republic, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom\u00e1\u0161","family":"Tich\u00fd","sequence":"additional","affiliation":[{"name":"Academy of Sciences of the Czech Republic, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), 761--770","author":"Andelman N.","key":"e_1_2_1_1_1","unstructured":"Andelman , N. , Mansour , Y. , and Zhu , A . 2003. Competitive queueing policies in QoS switches . In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), 761--770 . Andelman, N., Mansour, Y., and Zhu, A. 2003. Competitive queueing policies in QoS switches. In Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), 761--770."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science","volume":"3142","author":"Bansal N.","unstructured":"Bansal , N. , Fleischer , L. , Kimbrel , T. , Mahdian , M. , Schieber , B. , and Sviridenko , M . 2004. Further improvements in competitive guarantees for QoS buffering . In Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science , vol. 3142 . Springer, 196--207. Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., and Sviridenko, M. 2004. Further improvements in competitive guarantees for QoS buffering. In Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 3142. Springer, 196--207."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science","volume":"2996","author":"Bartal Y.","unstructured":"Bartal , Y. , Chin , F. Y. L. , Chrobak , M. , Fung , S. P. Y. , Jawor , W. , Lavi , R. , Sgall , J. , and Tich\u00fd , T . 2004. Online competitive algorithms for maximizing weighted throughput of unit jobs . In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science , vol. 2996 . Springer, 187--198. Bartal, Y., Chin, F. Y. L., Chrobak, M., Fung, S. P. Y., Jawor, W., Lavi, R., Sgall, J., and Tich\u00fd, T. 2004. Online competitive algorithms for maximizing weighted throughput of unit jobs. In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 2996. Springer, 187--198."},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","key":"e_1_2_1_4_1","unstructured":"Borodin , A. , and El-Yaniv , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press , New York . Borodin, A., and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.03.005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Chin F. Y. L. and Fung S. P. Y. 2003. Online scheduling for partial job values: Does timesharing or randomization help&quest; Algorithmica 37 149--164.  Chin F. Y. L. and Fung S. P. Y. 2003. Online scheduling for partial job values: Does timesharing or randomization help&quest; Algorithmica 37 149--164.","DOI":"10.1007\/s00453-003-1025-6"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 12th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science","volume":"3221","author":"Chrobak M.","unstructured":"Chrobak , M. , Jawor , W. , Sgall , J. , and Tich\u00fd , T . 2004. Improved online algorithms for buffer management in QoS switches . In Proceedings of the 12th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science , vol. 3221 . Springer, 204--215. Chrobak, M., Jawor, W., Sgall, J., and Tich\u00fd, T. 2004. Improved online algorithms for buffer management in QoS switches. In Proceedings of the 12th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 3221. Springer, 204--215."},{"volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 209--218","author":"Englert M.","key":"e_1_2_1_8_1","unstructured":"Englert , M. , and Westerman , M . 2007. Considering suppressed packets improves buffer management in QoS switches . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 209--218 . Englert, M., and Westerman, M. 2007. Considering suppressed packets improves buffer management in QoS switches. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 209--218."},{"key":"e_1_2_1_9_1","volume-title":"Conference in Information Sciences and Systems, 434--438","author":"Hajek B.","year":"2001","unstructured":"Hajek , B. 2001 . On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time . In Conference in Information Sciences and Systems, 434--438 . Hajek, B. 2001. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Conference in Information Sciences and Systems, 434--438."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380847"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701399666"},{"key":"e_1_2_1_12_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 11th European Symposium on Algorithms (ESA)","author":"Kesselman A.","unstructured":"Kesselman , A. , Mansour , Y. , and van Stee , R. 2003. Improved competitive guarantees for QoS buffering . In Proceedings of the 11th European Symposium on Algorithms (ESA) . Lecture Notes in Computer Science , vol. 2832 . Springer , 361--372. Kesselman, A., Mansour, Y., and van Stee, R. 2003. Improved competitive guarantees for QoS buffering. In Proceedings of the 11th European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2832. Springer, 361--372."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1158-x"},{"volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 801--802","author":"Li F.","key":"e_1_2_1_14_1","unstructured":"Li , F. , Sethuraman , J. , and Stein , C . 2005. An optimal online algorithm for packet scheduling with agreeable deadlines . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 801--802 . Li, F., Sethuraman, J., and Stein, C. 2005. An optimal online algorithm for packet scheduling with agreeable deadlines. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 801--802."},{"volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 199--208","author":"Li F.","key":"e_1_2_1_15_1","unstructured":"Li , F. , Sethuraman , J. , and Stein , C . 2007. Better online buffer management . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 199--208 . Li, F., Sethuraman, J., and Stein, C. 2007. Better online buffer management. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 199--208."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290687","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1290672.1290687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:25Z","timestamp":1750258345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1290672.1290687"],"URL":"https:\/\/doi.org\/10.1145\/1290672.1290687","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}