{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:01Z","timestamp":1742596801769,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_230","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:05:37Z","timestamp":1330257937000},"page":"14-25","source":"Crossref","is-referenced-by-count":1,"title":["Towards a better understanding of pure packet routing"],"prefix":"10.1007","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"R. Aleliunas. Randomized parallel communication. In Proc. ACM-SIGOPS Symposium on Principles of Distributed Systems, 60\u201372, 1982.","DOI":"10.1145\/800220.806683"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, P. Raghavan, B. Schieber, and H. Tamaki. Fast deflection routing for packets and worms. To appear in 1993 ACM PODC Conference.","DOI":"10.1145\/164051.164062"},{"key":"2_CR3","first-page":"64","volume":"9","author":"L.A. Bassalygo","year":"1974","unstructured":"L.A. Bassalygo and M.S. Pinsker. Complexity of an optimum non-blocking switching network without reconnections. Problems of Information Transmission, 9:64\u201366, 1974.","journal-title":"Problems of Information Transmission"},{"issue":"1","key":"2_CR4","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(85)90008-X","volume":"30","author":"A. Borodin","year":"1985","unstructured":"A. Borodin and J. Hopcroft. Routing, merging, and sorting on parallel models of computation. Journal of Computer and System Sciences, 30(1):130\u2013145, 1985.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"A. Borodin, P. Raghavan, B. Schieber, and E. Upfal. How much can hardware help routing? In Proc. 25th Annual ACM Symposium on Theory of Computing, 573\u2013582, 1993.","DOI":"10.1145\/167088.167237"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"R. Cypher and G. Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. In Proc. 22nd Annual ACM Symposium on Theory of Computing, 193\u2013203, 1990.","DOI":"10.1145\/100216.100240"},{"key":"2_CR7","first-page":"140","volume-title":"VLSI and Parallel Computation","author":"W. Dally","year":"1990","unstructured":"W. Dally. Network and processor architecture for message-driven computers. In Robert Suaya and Graham Birtwhistle, editors, VLSI and Parallel Computation, chapter 3, 140\u2013222. Morgan Kaufman Publishers, San Mateo, CA, 1990."},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"U. Feige and P. Raghavan. Exact analysis of hot-potato routing. In Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science, 553\u2013562, 1992.","DOI":"10.1109\/SFCS.1992.267796"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02311228","volume":"5","author":"B. Hajek","year":"1991","unstructured":"B. Hajek. Bounds on evacuation time for deflection routing. Distributed Computing, 5:1\u20136, 1991.","journal-title":"Distributed Computing"},{"key":"2_CR10","unstructured":"T. Han and D. Stanat. \u201cMove and smooth\u201d routing algorithms on mesh-connected computers. In Proc. 28th Allerton Conference, 236\u2013245, 1990."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"C. Kaklamanis, D. Krizanc and S. Rao. Simple path selection for optimal routing on processor arrays. SPAA 92, 23\u201330.","DOI":"10.1145\/140901.140904"},{"key":"2_CR12","unstructured":"C. Kaklamanis, D. Krizanc and S. Rao. Improved hot potato routing for processor arrays. SPAA 93, to appear."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF02090400","volume":"10","author":"C. Kaklamanis","year":"1991","unstructured":"C. Kaklamanis, D. Krizanc, and T. Tsantilas. Tight bounds for oblivious routing in the hypercube. Math. Systems Theory, 10:223\u2013232, 1991.","journal-title":"Math. Systems Theory"},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0022-0000(91)90017-Y","volume":"43","author":"D. Krizanc","year":"1991","unstructured":"D. Krizanc. Oblivious routing with limited buffer capacity. Journal of Computer and System Sciences, 43:317\u2013327, 1991.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"2_CR15","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1109\/TC.1985.5009385","volume":"C-34","author":"F.T. Leighton","year":"1985","unstructured":"F.T. Leighton. Tight bounds on the complexity of parallel sorting. IEEE Transactions on Computers, C-34(4):344\u2013354, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"F.T. Leighton. Average case analysis of greedy routing algorithms on arrays. In Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 2\u201310, 1990.","DOI":"10.1145\/97444.97448"},{"key":"2_CR17","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufman Publishers, San Mateo, CA, 1992."},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"F.T. Leighton. Methods for message routing in parallel machines. In Proc. 24th Annual ACM Symposium on Theory of Computing, 77\u201396, 1992.","DOI":"10.1145\/129712.129721"},{"key":"2_CR19","unstructured":"F.T. Leighton. Personal communication."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"F.T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proc. 29th IEEE Symposium on Foundations of Computer Science, 256\u2013269, 1988.","DOI":"10.21236\/ADA204273"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1109\/5.92038","volume":"79","author":"H. Li","year":"1991","unstructured":"H. Li and Q. Stout. Reconfigurable SIMD massively parallel computers. In Proc. IEEE, 79:429\u2013443, 1991.","journal-title":"Proc. IEEE"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"B. Maggs and R. Sitaraman. Simple algorithms for routing on butterfly networks with bounded queues. In Proc. 24th Annual ACM Symposium on Theory of Computing, 150\u2013161, 1992.","DOI":"10.1145\/129712.129728"},{"key":"2_CR23","volume-title":"Technical Report #9201","author":"I. Newman","year":"1992","unstructured":"I. Newman and A. Schuster. Hot-potato algorithms for permutation routing. Technical Report #9201, CS Department, Technion, Israel, 1992."},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"N. Pippenger. Parallel communication with limited buffers. In Proc. 25th Annual IEEE Symposium on Foundations of Computer Science, 127\u2013136, 1984.","DOI":"10.1109\/SFCS.1984.715909"},{"key":"2_CR25","first-page":"805","volume-title":"Handbook of Theoretical Computer Science, Vol. A: Algorithms, and Complexity","author":"N. Pippenger","year":"1990","unstructured":"N. Pippenger. Communication networks. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. A: Algorithms, and Complexity, 805\u2013834. MIT Press, Cambridge, 1990."},{"key":"2_CR26","unstructured":"R. Prager. An algorithm for routing in hypercube networks. M.Sc. thesis, University of Toronto, 1986."},{"issue":"2","key":"2_CR27","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1145\/62044.62050","volume":"36","author":"M. Rabin","year":"1989","unstructured":"M. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335\u2013348, 1989.","journal-title":"Journal of the ACM"},{"key":"2_CR28","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01758834","volume":"8","author":"S. Rajasekaran","year":"1992","unstructured":"S. Rajasekaran, and T. Tsantilas. Optimal routing algorithms for mesh-connected processor arrays. Algorithmica, 8:21\u201338, 1992.","journal-title":"Algorithmica"},{"issue":"3","key":"2_CR29","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0022-0000(91)90005-P","volume":"42","author":"A. Ranade","year":"1991","unstructured":"A. Ranade. How to emulate shared memory. Journal of Computer and System Sciences, 42(3):307\u2013326, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1145\/828.1892","volume":"31","author":"E. Upfal","year":"1984","unstructured":"E. Upfal. Efficient schemes for parallel communication. Journal of the ACM, 31:507\u2013517, 1984.","journal-title":"Journal of the ACM"},{"issue":"2","key":"2_CR31","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1137\/0211027","volume":"11","author":"L. Valiant","year":"1982","unstructured":"L. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2):350\u2013361, 1982.","journal-title":"SIAM Journal on Computing"},{"issue":"9","key":"2_CR32","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1109\/TC.1983.1676335","volume":"C-32","author":"L. Valiant","year":"1983","unstructured":"L. Valiant. Optimality of a two-phase strategy for routing in interconnection networks. IEEE Transactions on Computers, C-32(9):861\u2013863, 1983.","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR33","first-page":"943","volume-title":"Handbook of Theoretical Computer Science, Vol. A: Algorithms, and Complexity","author":"L. Valiant","year":"1990","unstructured":"L. Valiant. General purpose parallel architectures. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, Vol. A: Algorithms, and Complexity, 943\u2013972. MIT Press, Cambridge, 1990."},{"key":"2_CR34","unstructured":"L. Valiant. Personal communication."},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"L. Valiant and G. Brebner. Universal schemes for parallel communication. In Proc. 13th Annual ACM Symposium on Theory of Computing, 263\u2013277, 1981.","DOI":"10.1145\/800076.802479"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_230.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:00:15Z","timestamp":1742594415000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_230","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}