Randomized Single-Target Hot-Potato Routing

Acampora, 1991, Multihop lightwave networks: A comparison of store-and-forward and hot-potato routing A. Bar-Noy, P. Raghavan, B. Schieber, H. Tamaki, Fast deflection routing for packets and worms, Proc. 12th Symp. on Principles Of Distributed Computing, ACM, 1993, 75, 86 Baran, 1964, On distributed communications networks, IEEE Trans. Comm., 12, 1, 10.1109/TCOM.1964.1088883 I. Ben-Aroya, D. D. Chinn, A. Schuster, May 1994, A CLT-Type Lower Bound for Nearly Minimal Adaptive and Hot Potato Algorithms, C.S. Dept. Technion I. Ben-Aroya, I. Newman, A. Schuster, Randomized single target hot potato routing, J. Algorithms Ben-Aroya, 1995, Greedy hot-potato routing on the two-dimensional mesh, Distrib. Comput., 9, 3, 10.1007/BF01784239 A. Ben-Dor, S. Halevi, A. Schuster, Potential function analysis of greedy hot-potato routing, Proc. 13th symp. on Principles of Distributed Computing, Los Angeles, Aug. 1994, 225, 234, ACM Borodin, 1985, Routing, merging, and sorting on parallel models of computation, J. Comput. Syst. Sci., 30, 130, 10.1016/0022-0000(85)90008-X A. Borodin, Y. Rabani, B. Schieber, 1995, Deterministic Many-to-Many Hot Potato Routing J. T. Brassil, R. L. Cruz, Bounds on maximum delay in networks with deflection routing, Proc. 29th Allerton conf. on Communication, Control and Computing, 1991, 571, 580 Chernoff, 1952, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observation, Ann. Math. Stat., 23, 493, 10.1214/aoms/1177729330 U. Feige, Observations on hot potato routing, Proc. 3rd Israeli symp. on Theory of Computing and Systems, Jan. 1995, 30, 39 U. Feige, P. Raghavan, Nov. 1992, Exact analysis of hot-potato routing, Proc. 33rd Symp. on of Foundations of Computer Science, 553, 562, IEEE Greenberg, 1986, Sharp approximate models of adaptive routing in mesh networks Greenberg, 1992, Deflection routing in hypercube networks, IEEE Trans. Comm., 10.1109/26.142797 Hajek, 1991, Bounds on evacuation time for deflection routing, Distrib. Comput., 5, 1, 10.1007/BF02311228 C. Kaklamanis, D. Krizanc, Satish, Rao, 1993, Hot-potato routing on processor arrays, Proc. 5th Symp. on Parallel Algorithms and Architectures, 273, 282, ACM M. Kaufmann, H. Lauer, H. Schröder, 1994, Fast deterministic hot-potato routing on meshes, Proc. 5th Symp. on Algorithms and Computation (ISAAC), number 834 in LNCS, 333, 341, Springer-Verlag Maxemchuk, 1989, Comparison of deflection and store and forward techniques in the manhattan street and shuffle exchange networks I. Newman, A. Schuster, November 1992, Hot-potato algorithms for permutation routing, Technical Report PCL Report #9201, CS dept. Technion Ngai, 1989, A framework for adaptive routing in multicomputer networks R. Prager, 1986, An algorithm for routing in hypercube networks, Computer Science Department, University of Toronto C. L. Seitz, June 1992, The Caltech Mosaic C: an experimental, fine-grain multicomputer, 4th Symp. on Parallel Algorithms and Architectures, ACM, San Diego B. Smith, 1981, Architecture and applications of the HEP multiprocessor computer system, Proc. (SPIE) Real Time Signal Processing IV, 241, 248 T. Szymanski, 1990, An analysis of hot potato routing in a fiber optic packet switched hypercube, Proc. IEEE INFOCOM, 918, 926 Z. Zhang, A. S. Acampora, 1991, Performance analysis of multihop lightwave networks with hot potato routing and distance age priorities, Proc. IEEE INFOCOM, 1012, 1021