{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T14:52:12Z","timestamp":1675349532829},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9677-8","type":"journal-article","created":{"date-parts":[[2012,8,9]],"date-time":"2012-08-09T14:12:34Z","timestamp":1344521554000},"page":"426-447","source":"Crossref","is-referenced-by-count":7,"title":["An Optimal Lower Bound for Buffer Management in Multi-Queue Switches"],"prefix":"10.1007","volume":"68","author":[{"given":"Marcin","family":"Bienkowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,10]]},"reference":[{"issue":"2","key":"9677_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.jalgor.2004.04.004","volume":"55","author":"W. Aiello","year":"2005","unstructured":"Aiello, W., Mansour, Y., Rajagopolan, S., Ros\u00e9n, A.: Competitive queue policies for differentiated services. J. Algorithms 55(2), 113\u2013141 (2005). Also appeared in proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp.\u00a0431\u2013440 (2000)","journal-title":"J. Algorithms"},{"issue":"4","key":"9677_CR2","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1007\/s00453-008-9230-y","volume":"57","author":"S. Albers","year":"2010","unstructured":"Albers, S., Jacobs, T.: An experimental study of new and known online packet buffering algorithms. Algorithmica 57(4), 725\u2013746 (2010). Also appeared in proceedings of the\u00a015th European Symposium on Algorithms (ESA), pp.\u00a0754\u2013765 (2007)","journal-title":"Algorithmica"},{"issue":"2","key":"9677_CR3","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1137\/S0097539704446268","volume":"35","author":"S. Albers","year":"2005","unstructured":"Albers, S., Schmidt, M.: On the performance of greedy algorithms in packet buffering. SIAM J. Comput. 35(2), 278\u2013304 (2005). Also appeared in proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 35\u201344 (2004)","journal-title":"SIAM J. Comput."},{"key":"9677_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1073970.1073972","volume-title":"Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"N. Andelman","year":"2005","unstructured":"Andelman, N.: Randomized queue management for DiffServ. In: Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 1\u201310 (2005)"},{"key":"9677_CR5","first-page":"166","volume-title":"Proceedings of the 17th International Symposium on Distributed Computing (DISC)","author":"N. Andelman","year":"2003","unstructured":"Andelman, N., Mansour, Y.: Competitive management of non-preemptive queues with multiple values. In: Proceedings of the 17th International Symposium on Distributed Computing (DISC), pp.\u00a0166\u2013180 (2003)"},{"key":"9677_CR6","first-page":"761","volume-title":"Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"N. Andelman","year":"2003","unstructured":"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\u2013770 (2003)"},{"issue":"1","key":"9677_CR7","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s00453-005-1190-x","volume":"45","author":"Y. Azar","year":"2006","unstructured":"Azar, Y., Litichevskey, A.: Maximizing throughput in multi-queue switches. Algorithmica 45(1), 69\u201390 (2006). Also appeared in proceedings of the 12th European Symposium on Algorithms (ESA), pp.\u00a053\u201364 (2004)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"9677_CR8","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00453-005-1159-9","volume":"43","author":"Y. Azar","year":"2005","unstructured":"Azar, Y., Richter, Y.: Management of multi-queue switches in QoS networks. Algorithmica 43(1\u20132), 81\u201396 (2005). Also appeared in proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pp.\u00a082\u201389 (2003)","journal-title":"Algorithmica"},{"key":"9677_CR9","doi-asserted-by":"crossref","first-page":"1126","DOI":"10.1137\/1.9781611973068.122","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Bienkowski","year":"2009","unstructured":"Bienkowski, M., Chrobak, M., D\u00fcrr, C., Hurand, M., Je\u017c, A., Je\u017c, \u0141., Stachowiak, G.: Collecting weighted items from a dynamic queue. In: Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a01126\u20131135 (2009)"},{"issue":"39","key":"9677_CR10","doi-asserted-by":"crossref","first-page":"5121","DOI":"10.1016\/j.tcs.2011.05.015","volume":"412","author":"M. Bienkowski","year":"2011","unstructured":"Bienkowski, M., Chrobak, M., Je\u017c, \u0141.: Randomized competitive algorithms for online buffer management in the adaptive adversary model. Theory Comput. Sci. 412(39), 5121\u20135131 (2011). Also appeared as Randomized Algorithms for Buffer Management with 2-Bounded Delay in proceedings of the 6th Workshop on Approximation and Online Algorithms (WAOA), pp. 92\u2013104 (2008)","journal-title":"Theory Comput. Sci."},{"key":"9677_CR11","first-page":"252","volume-title":"Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN)","author":"M. Bienkowski","year":"2008","unstructured":"Bienkowski, M., Madry, A.: Geometric aspects of online packet buffering: an optimal randomized algorithm for two buffers. In: Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN), pp. 252\u2013263 (2008)"},{"key":"9677_CR12","volume-title":"Online Computation and Competitive Analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"2","key":"9677_CR13","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.jda.2005.03.005","volume":"4","author":"F.Y.L. Chin","year":"2006","unstructured":"Chin, F.Y.L., Chrobak, M., Fung, S.P.Y., Jawor, W., Sgall, J., Tich\u00fd, T.: Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms 4(2), 255\u2013276 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"9677_CR14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s00453-003-1025-6","volume":"37","author":"F.Y.L. Chin","year":"2003","unstructured":"Chin, F.Y.L., Fung, S.P.Y.: Online scheduling for partial job values: does timesharing or randomization help? Algorithmica 37, 149\u2013164 (2003)","journal-title":"Algorithmica"},{"key":"9677_CR15","first-page":"209","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Englert","year":"2007","unstructured":"Englert, M., Westermann, M.: Considering suppressed packets improves buffer management in QoS switches. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 209\u2013218 (2007)"},{"issue":"4","key":"9677_CR16","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/s00453-008-9236-5","volume":"53","author":"M. Englert","year":"2009","unstructured":"Englert, M., Westermann, M.: Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica 53(4), 523\u2013548 (2009). Also appeared in proceedings of the 14th European Symposium on Algorithms (ESA), pp. 352\u2013363 (2006)","journal-title":"Algorithmica"},{"issue":"1","key":"9677_CR17","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1145\/1753171.1753195","volume":"41","author":"M. Goldwasser","year":"2010","unstructured":"Goldwasser, M.: A survey of buffer management policies for packet switches. SIGACT News 41(1), 100\u2013128 (2010)","journal-title":"SIGACT News"},{"key":"9677_CR18","first-page":"434","volume-title":"Conference in Information Sciences and Systems","author":"B. Hajek","year":"2001","unstructured":"Hajek, B.: On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In: Conference in Information Sciences and Systems, pp. 434\u2013438 (2001)"},{"key":"9677_CR19","first-page":"489","volume-title":"Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS)","author":"\u0141. Je\u017c","year":"2010","unstructured":"Je\u017c, \u0141.: Randomized algorithm for agreeable deadlines packet scheduling. In: Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS), pp. 489\u2013500 (2010)"},{"key":"9677_CR20","first-page":"239","volume-title":"Proceedings of the 19th European Symposium on Algorithms (ESA)","author":"\u0141. Je\u017c","year":"2011","unstructured":"Je\u017c, \u0141.: One to rule them all: a general randomized algorithm for buffer management with bounded delay. In: Proceedings of the 19th European Symposium on Algorithms (ESA), pp. 239\u2013250 (2011)"},{"issue":"3","key":"9677_CR21","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/S0097539701399666","volume":"33","author":"A. Kesselman","year":"2004","unstructured":"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\u2013583 (2004). Also appeared in proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), pp. 520\u2013529 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9677_CR22","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0196-6774(02)00270-5","volume":"46","author":"A. Kesselman","year":"2003","unstructured":"Kesselman, A., Mansour, Y.: Loss-bounded analysis for differentiated services. J. Algorithms 46(1), 79\u201395 (2003). Also appeared in proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 591\u2013600 (2001)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"9677_CR23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s00453-005-1158-x","volume":"43","author":"A. Kesselman","year":"2005","unstructured":"Kesselman, A., Mansour, Y., van Stee, R.: Improved competitive guarantees for QoS buffering. Algorithmica 43(1\u20132), 63\u201380 (2005). Also appeared in proceedings of the 11th European Symposium on Algorithms (ESA), pp. 361\u2013372 (2003)","journal-title":"Algorithmica"},{"issue":"12","key":"9677_CR24","doi-asserted-by":"crossref","first-page":"2757","DOI":"10.1093\/ietisy\/e91-d.12.2757","volume":"91-D","author":"K. Kobayashi","year":"2008","unstructured":"Kobayashi, K., Miyazaki, S., Okabe, Y.: A tight upper bound on online buffer management for multi-queue switches with bicodal buffers. IEICE Trans. Inf. Syst. 91-D(12), 2757\u20132769 (2008)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"1","key":"9677_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/90.282603","volume":"2","author":"W.E. Leland","year":"1994","unstructured":"Leland, W.E., Taqqu, M.S., Willinger, W., Wilson, D.V.: On the self-similar nature of ethernet traffic. IEEE\/ACM Trans. Netw. 2(1), 1\u201315 (1994). Also appeared in proceedings of the ACM SIGCOMM Conference on Communications Architectures, Protocols and Applications, pp.\u00a0183\u2013193 (1993)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"9677_CR26","first-page":"801","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"F. Li","year":"2005","unstructured":"Li, F., Sethuraman, J., Stein, C.: An optimal online algorithm for packet scheduling with agreeable deadlines. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 801\u2013802 (2005)"},{"key":"9677_CR27","first-page":"199","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"F. Li","year":"2007","unstructured":"Li, F., Sethuraman, J., Stein, C.: Better online buffer management. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 199\u2013208 (2007)"},{"issue":"1","key":"9677_CR28","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/S1389-1286(03)00197-X","volume":"42","author":"Z. Lotker","year":"2003","unstructured":"Lotker, Z., Patt-Shamir, B.: Nearly optimal FIFO buffer management for two packet classes. Comput. Netw. 42(1), 481\u2013492 (2003). Also appeared as Nearly optimal FIFO buffer management for DiffServ in proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a0202\u2013214 (2002)","journal-title":"Comput. Netw."},{"issue":"1","key":"9677_CR29","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/s00446-003-0101-0","volume":"17","author":"Y. Mansour","year":"2004","unstructured":"Mansour, Y., Patt-Shamir, B., Lapid, O.: Optimal smoothing schedules for real-time streams. Distrib. Comput. 17(1), 77\u201389 (2004). Also appeared in proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC), pp.\u00a021\u201329 (2000)","journal-title":"Distrib. Comput."},{"key":"9677_CR30","first-page":"293","volume-title":"Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)","author":"M. Schmidt","year":"2005","unstructured":"Schmidt, M.: Packet buffering: randomization beats deterministic algorithms. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), pp. 293\u2013304 (2005)"},{"issue":"2","key":"9677_CR31","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jalgor.2004.04.007","volume":"53","author":"A. Zhu","year":"2004","unstructured":"Zhu, A.: Analysis of queueing policies in QoS switches. J. Algorithms 53(2), 137\u2013168 (2004)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9677-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T18:40:33Z","timestamp":1497984033000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9677-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,10]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9677"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9677-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,10]]}}}