{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T04:02:29Z","timestamp":1746244949362,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642544224"},{"type":"electronic","value":"9783642544231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54423-1_53","type":"book-chapter","created":{"date-parts":[[2014,3,25]],"date-time":"2014-03-25T03:02:27Z","timestamp":1395716547000},"page":"610-621","source":"Crossref","is-referenced-by-count":3,"title":["Packet Forwarding Algorithms in a Line Network"],"prefix":"10.1007","author":[{"given":"Antonios","family":"Antoniadis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neal","family":"Barcelo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Cole","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyle","family":"Fox","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Nugent","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"53_CR1","doi-asserted-by":"crossref","unstructured":"Kowalski, D., Nussbaum, E., Segal, M., Milyeykovsky, V.: Scheduling problems in transportation networks of line topology. Optimization Letters (2013) (to appear)","DOI":"10.1007\/s11590-013-0613-x"},{"issue":"3","key":"53_CR2","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1006\/jcss.1999.1681","volume":"60","author":"W. Aiello","year":"2000","unstructured":"Aiello, W., Kushilevitz, E., Ostrovsky, R., Ros\u00e9n, A.: Adaptive packet routing for bursty adversarial traffic. J. Comput. Syst. Sci.\u00a060(3), 482\u2013509 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"53_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/363647.363677","volume":"48","author":"M. Andrews","year":"2001","unstructured":"Andrews, M., Awerbuch, B., Fern\u00e1ndez, A., Leighton, F.T., Liu, Z., Kleinberg, J.M.: Universal-stability results and performance bounds for greedy contention-resolution protocols. J. ACM\u00a048(1), 39\u201369 (2001)","journal-title":"J. ACM"},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"Andrews, M.: Instability of FIFO in the permanent sessions model at arbitrarily small network loads. ACM Transactions on Algorithms\u00a05(3) (2009)","DOI":"10.1145\/1541885.1541894"},{"issue":"3","key":"53_CR5","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1137\/S0097539702417225","volume":"33","author":"M. Andrews","year":"2004","unstructured":"Andrews, M., Zhang, L.: The effects of temporary sessions on network performance. SIAM J. Comput.\u00a033(3), 659\u2013673 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"53_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/363647.363659","volume":"48","author":"A. Borodin","year":"2001","unstructured":"Borodin, A., Kleinberg, J.M., Raghavan, P., Sudan, M., Williamson, D.P.: Adversarial queuing theory. J. ACM\u00a048(1), 13\u201338 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"53_CR7","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/375827.375849","volume":"48","author":"A.Z. Broder","year":"2001","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: A general approach to dynamic packet routing with bounded buffers. J. ACM\u00a048(2), 324\u2013349 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"53_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"F.T. Leighton","year":"1994","unstructured":"Leighton, F.T., Maggs, B.M., Rao, S.: Packet routing and job-shop scheduling in O(Congestion + Dilation) steps. Combinatorica\u00a014(2), 167\u2013186 (1994)","journal-title":"Combinatorica"},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y.: Universal O(Congestion + Dilation + log1\u2009+\u2009epsilon N) local control packet switching algorithms. In: STOC, pp. 644\u2013653 (1997)","DOI":"10.1145\/258533.258659"},{"key":"53_CR10","doi-asserted-by":"crossref","unstructured":"Rabani, Y., Tardos, \u00c9.: Distributed packet switching in arbitrary networks. In: STOC, pp. 366\u2013375 (1996)","DOI":"10.1145\/237814.237983"},{"issue":"1","key":"53_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2071379.2071384","volume":"8","author":"B.S. Chlebus","year":"2012","unstructured":"Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Adversarial queuing on the multiple access channel. ACM Transactions on Algorithms\u00a08(1), 5 (2012)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"53_CR12","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/S0097539700369168","volume":"32","author":"D. Gamarnik","year":"2003","unstructured":"Gamarnik, D.: Stability of adaptive and nonadaptive packet routing policies in adversarial queueing networks. SIAM J. Comput.\u00a032(2), 371\u2013385 (2003)","journal-title":"SIAM J. Comput."},{"key":"53_CR13","doi-asserted-by":"crossref","unstructured":"D\u00edaz, J., Koukopoulos, D., Nikoletseas, S.E., Serna, M.J., Spirakis, P.G., Thilikos, D.M.: Stability and non-stability of the FIFO protocol. In: SPAA, pp. 48\u201352 (2001)","DOI":"10.1145\/378580.378588"},{"issue":"6","key":"53_CR14","doi-asserted-by":"publisher","first-page":"2051","DOI":"10.1137\/S0097539798335596","volume":"30","author":"A. Srinivasan","year":"2000","unstructured":"Srinivasan, A., Teo, C.P.: A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM J. Comput.\u00a030(6), 2051\u20132068 (2000)","journal-title":"SIAM J. Comput."},{"key":"53_CR15","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: FOCS, pp. 32\u201340 (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"issue":"1-2","key":"53_CR16","doi-asserted-by":"publisher","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\u00a043(1-2), 63\u201380 (2005)","journal-title":"Algorithmica"},{"key":"53_CR17","unstructured":"Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies for QoS switches. In: SODA, pp. 761\u2013770 (2003)"},{"key":"53_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/11561071_44","volume-title":"Algorithms \u2013 ESA 2005","author":"Y. Azar","year":"2005","unstructured":"Azar, Y., Zachut, R.: Packet routing and information gathering in lines, rings and trees. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 484\u2013495. Springer, Heidelberg (2005)"},{"issue":"1","key":"53_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s00453-007-9143-1","volume":"55","author":"S. Angelov","year":"2009","unstructured":"Angelov, S., Khanna, S., Kunal, K.: The network as a storage device: Dynamic routing with bounded buffers. Algorithmica\u00a055(1), 71\u201394 (2009)","journal-title":"Algorithmica"},{"issue":"6","key":"53_CR20","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/s00224-002-1001-6","volume":"35","author":"M. Adler","year":"2002","unstructured":"Adler, M., Rosenberg, A.L., Sitaraman, R.K., Unger, W.: Scheduling time-constrained communication in linear networks. Theory Comput. Syst.\u00a035(6), 599\u2013623 (2002)","journal-title":"Theory Comput. Syst."},{"key":"53_CR21","doi-asserted-by":"crossref","unstructured":"Gordon, E., Ros\u00e9n, A.: Competitive weighted throughput analysis of greedy protocols on DAGs. ACM Transactions on Algorithms\u00a06(3) (2010)","DOI":"10.1145\/1798596.1798603"},{"key":"53_CR22","unstructured":"Aiello, W., Ostrovsky, R., Kushilevitz, E., Ros\u00e9n, A.: Dynamic routing on networks with fixed-size buffers. In: SODA, pp. 771\u2013780 (2003)"},{"issue":"2","key":"53_CR23","doi-asserted-by":"publisher","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\u00a04(2), 255\u2013276 (2006)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"53_CR24","doi-asserted-by":"publisher","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.\u00a033(3), 563\u2013583 (2004)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"53_CR25","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/1978782.1978787","volume":"7","author":"A. Ros\u00e9n","year":"2011","unstructured":"Ros\u00e9n, A., Scalosub, G.: Rate vs. buffer size-greedy information gathering on the line. ACM Transactions on Algorithms\u00a07(3), 32 (2011)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2-3","key":"53_CR26","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.tcs.2004.05.014","volume":"324","author":"A. Kesselman","year":"2004","unstructured":"Kesselman, A., Mansour, Y.: Harmonic buffer management policy for shared memory switches. Theor. Comput. Sci.\u00a0324(2-3), 161\u2013182 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"53_CR27","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2229163.2229172","volume":"8","author":"J. Edmonds","year":"2012","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms\u00a08(3), 28 (2012)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"53_CR28","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/1998037.1998058","volume":"42","author":"S. Im","year":"2011","unstructured":"Im, S., Moseley, B., Pruhs, K.: A tutorial on amortized local competitiveness in online scheduling. SIGACT News\u00a042(2), 83\u201397 (2011)","journal-title":"SIGACT News"}],"container-title":["Lecture Notes in Computer Science","LATIN 2014: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54423-1_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:23:09Z","timestamp":1746159789000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54423-1_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642544224","9783642544231"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54423-1_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}