Exact analysis of hot-potato routing
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 553-562
- https://doi.org/10.1109/sfcs.1992.267796
Abstract
The authors consider a form of packet routing known as hot potato routing or deflection routing. Its striking feature is that there are no buffers at intermediate nodes. Thus packets are always moving (possibly in the 'wrong' direction), giving rise to the term 'hot potato'. They give a simple deterministic algorithm that on a n*n torus will route a random instance in 2n+O(log n) steps with high probability. They add random delays to this algorithm so that it solves the permutation routing problem on the torus in 9n steps with high probability, on every instance. On a hypercube with N=2/sup n/ nodes, they give a simple deterministic algorithm that will route a random instance in O(n) steps with high probability. Various other results are discussed.Keywords
This publication has 13 references indexed in Scilit:
- An analysis of 'hot-potato' routing in a fiber optic packet switched hypercubePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Bounds on maximum delay in networks with deflection routingIEEE Transactions on Parallel and Distributed Systems, 1995
- Sharp approximate models of deflection routing in mesh networksIEEE Transactions on Communications, 1993
- Simple algorithms for routing on butterfly networks with bounded queuesPublished by Association for Computing Machinery (ACM) ,1992
- A theory of wormhole routing in parallel computersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Bounds on evacuation time for deflection routingDistributed Computing, 1991
- Performance analysis of multihop lightwave networks with hot potato routing and distance-age-prioritiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Routing, merging, and sorting on parallel models of computationJournal of Computer and System Sciences, 1985
- A Scheme for Fast Parallel CommunicationSIAM Journal on Computing, 1982
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977