{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:30Z","timestamp":1740109290832,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T00:00:00Z","timestamp":1520208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"European Research Council","award":["307696"],"award-info":[{"award-number":["307696"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-018-0421-x","type":"journal-article","created":{"date-parts":[[2018,3,5]],"date-time":"2018-03-05T18:15:41Z","timestamp":1520273741000},"page":"3861-3888","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Packet Scheduling for CIOQ and Buffered Crossbar Switches"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9381-5414","authenticated-orcid":false,"given":"Kamal","family":"Al-Bawani","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Englert","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Westermann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,5]]},"reference":[{"issue":"1","key":"421_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1435375.1435378","volume":"5","author":"W Aiello","year":"2008","unstructured":"Aiello, W., Kesselman, A., Mansour, Y.: Competitive buffer management for shared-memory switches. ACM Trans. Algorithms 5(1), 3 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"421_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.ipl.2012.12.014","volume":"113","author":"K Al-Bawani","year":"2013","unstructured":"Al-Bawani, K., Souza, A.: Buffer overflow management with class segregation. Inf. Process. Lett. 113(4), 145\u2013150 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"421_CR3","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1137\/S0097539704446268","volume":"35","author":"S Albers","year":"2006","unstructured":"Albers, S., Schmidt, M.: On the performance of greedy algorithms in packet buffering. SIAM J. Comput. 35(2), 278\u2013304 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"421_CR4","doi-asserted-by":"publisher","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)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Azar, Y., Richter, Y.: The zero-one principle for switching networks. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 64\u201371 (2004)","key":"421_CR5","DOI":"10.1145\/1007352.1007369"},{"key":"421_CR6","doi-asserted-by":"publisher","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, 81\u201396 (2005)","journal-title":"Algorithmica"},{"issue":"2","key":"421_CR7","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1145\/1150334.1150342","volume":"2","author":"Y Azar","year":"2006","unstructured":"Azar, Y., Richter, Y.: An improved algorithm for CIOQ switches. ACM Trans. Algorithms 2(2), 282\u2013295 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"421_CR8","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/s00453-012-9677-8","volume":"68","author":"M Bienkowski","year":"2014","unstructured":"Bienkowski, M.: An optimal lower bound for buffer management in multi-queue switches. Algorithmica 68(2), 426\u2013447 (2014)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","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 Symposium on Theoretical Informatics (LATIN), pp. 252\u2013263 (2008)","key":"421_CR9","DOI":"10.1007\/978-3-540-78773-0_22"},{"key":"421_CR10","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1109\/49.772430","volume":"17","author":"S-T Chuang","year":"1999","unstructured":"Chuang, S.-T., Goel, A., McKeown, N., Prabhakar, B.: Matching output queueing with a combined input output queued switch. IEEE J. Sel. Areas Commun. 17, 1030\u20131039 (1999)","journal-title":"IEEE J. Sel. Areas Commun."},{"unstructured":"Chuang, S.-T., Iyer, S., McKeown, N.: Practical algorithms for performance guarantees in buffered crossbars. In: Proceedings of the 24th IEEE Conference on Computer Communications (INFOCOM), pp. 981\u2013991 (2005)","key":"421_CR11"},{"issue":"4","key":"421_CR12","doi-asserted-by":"publisher","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)","journal-title":"Algorithmica"},{"issue":"5","key":"421_CR13","doi-asserted-by":"publisher","first-page":"1166","DOI":"10.1137\/110856745","volume":"41","author":"M Englert","year":"2012","unstructured":"Englert, M., Westermann, M.: Considering suppressed packets improves buffer management in QoS switches. SIAM J. Comput. 41(5), 1166\u20131192 (2012)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"421_CR14","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/1027914.1027930","volume":"35","author":"L Epstein","year":"2004","unstructured":"Epstein, L., van Stee, R.: Buffer management problems. SIGACT News 35(3), 58\u201366 (2004)","journal-title":"SIGACT News"},{"key":"421_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-319-25258-2_5","volume-title":"Structural Information and Communication Complexity","author":"Patrick Eugster","year":"2015","unstructured":"Eugster, P., Kesselman, A., Kogan, K., Nikolenko, S.I., Sirotkin, A.: Essential traffic parameters for shared memory switch performance. In: Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 61\u201375 (2015)"},{"doi-asserted-by":"crossref","unstructured":"Eugster, P., Kogan, K., Nikolenko, S.I., Sirotkin, A.: Shared memory buffer management for heterogeneous packet processing. In: Proceedings of the 34th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 471\u2013480 (2014)","key":"421_CR16","DOI":"10.1109\/ICDCS.2014.55"},{"key":"421_CR17","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1145\/1753171.1753195","volume":"41","author":"MH Goldwasser","year":"2010","unstructured":"Goldwasser, M.H.: A survey of buffer management policies for packet switches. SIGACT News 41, 100\u2013128 (2010)","journal-title":"SIGACT News"},{"issue":"5","key":"421_CR18","doi-asserted-by":"publisher","first-page":"1186","DOI":"10.1093\/ietfec\/e89-a.5.1186","volume":"E89-A","author":"T. ITOH","year":"2006","unstructured":"Itoh, T., Takahashi, N.: Competitive analysis of multi-queue preemptive QoS algorithms for general priorities. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E89-A(5), 1186\u20131197 (2006)","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"issue":"1","key":"421_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2390176.2390181","volume":"9","author":"\u0141 Je\u017c","year":"2012","unstructured":"Je\u017c, \u0141., Li, F., Sethuraman, J., Stein, C.: Online scheduling of packets with agreeable deadlines. ACM Trans. Algorithms 9(1), 5 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"421_CR20","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00446-010-0114-4","volume":"23","author":"A Kesselman","year":"2010","unstructured":"Kesselman, A., Kogan, K., Segal, M.: Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing. Distrib. Comput. 23(3), 163\u2013175 (2010)","journal-title":"Distrib. Comput."},{"issue":"5","key":"421_CR21","first-page":"1","volume":"2012","author":"A Kesselman","year":"2012","unstructured":"Kesselman, A., Kogan, K., Segal, M.: Best effort and priority queuing policies for buffered crossbar switches. Chic. J. Theor. Comput. Sci. 2012(5), 1\u201314 (2012)","journal-title":"Chic. J. Theor. Comput. Sci."},{"issue":"1\u20132","key":"421_CR22","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00453-011-9539-9","volume":"63","author":"A Kesselman","year":"2012","unstructured":"Kesselman, A., Kogan, K., Segal, M.: Improved competitive performance bounds for CIOQ switches. Algorithmica 63(1\u20132), 411\u2013424 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"421_CR23","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.jalgor.2004.09.003","volume":"60","author":"A Kesselman","year":"2006","unstructured":"Kesselman, A., Ros\u00e9n, A.: Scheduling policies for CIOQ switches. J. Algorithms 60(1), 60\u201383 (2006)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"421_CR24","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1142\/S0219265908002151","volume":"9","author":"A Kesselman","year":"2008","unstructured":"Kesselman, A., Ros\u00e9n, A.: Controlling CIOQ switches with priority queuing and in multistage interconnection networks. J. Interconnect. Netw. 9(1\u20132), 53\u201372 (2008)","journal-title":"J. Interconnect. Netw."},{"issue":"12","key":"421_CR25","doi-asserted-by":"publisher","first-page":"2757","DOI":"10.1093\/ietisy\/e91-d.12.2757","volume":"91\u2013D","author":"KM Kobayashi","year":"2008","unstructured":"Kobayashi, K.M., Miyazaki, S., Okabe, Y.: A tight upper bound on online buffer management for multi-queue switches with bicodal buffers. IEICE Trans. 91\u2013D(12), 2757\u20132769 (2008)","journal-title":"IEICE Trans."},{"key":"421_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2017.02.014","volume":"675","author":"KM Kobayashi","year":"2017","unstructured":"Kobayashi, K.M., Miyazaki, S., Okabe, Y.: Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms. Theor. Comput. Sci. 675, 27\u201342 (2017)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Li, F., Sethuraman, J., Stein, C.: Better online buffer management. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 199\u2013208 (2007)","key":"421_CR27"},{"key":"421_CR28","doi-asserted-by":"publisher","first-page":"1988","DOI":"10.1007\/978-1-4939-2864-4_535","volume-title":"Encyclopedia of Algorithms","author":"Sergey I. Nikolenko","year":"2016","unstructured":"Nikolenko, S.I., Kogan, K.: Single and multiple buffer processing. In: Encyclopedia of Algorithms, pp. 1\u20139 (2014). \n                    https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_535"},{"issue":"3","key":"421_CR29","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1109\/90.392383","volume":"3","author":"V Paxson","year":"1995","unstructured":"Paxson, V., Floyd, S.: Wide-area traffic: the failure of Poisson modeling. IEEE\/ACM Trans. Netw. 3(3), 226\u2013244 (1995)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"421_CR30","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-540-31856-9_24","volume-title":"STACS 2005","author":"Markus Schmidt","year":"2005","unstructured":"Schmidt, M.: Packet buffering: randomization beats deterministic algorithms. In: Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 293\u2013304 (2005)"},{"issue":"2","key":"421_CR31","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Veres, A., Boda, M.: The chaotic nature of TCP congestion control. In: Proceedings of the 19th IEEE Conference on Computer Communications (INFOCOM), pp. 1715\u20131723 (2000)","key":"421_CR32","DOI":"10.1109\/INFCOM.2000.832571"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0421-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0421-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0421-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T03:17:49Z","timestamp":1589858269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0421-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,5]]},"references-count":32,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["421"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0421-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,3,5]]},"assertion":[{"value":"17 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}