Exact analysis of hot-potato routing
Authors:
- U. FeigeUFU. Feige
- P. RaghavanPRP. Raghavan
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 553-562
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 11 references indexed in Scilit:
- Sharp approximate models of deflection routing in mesh networksIEEE Transactions on Communications, 1993
- Deflection routing in hypercube networksIEEE Transactions on Communications, 1992
- Simple algorithms for routing on butterfly networks with bounded queues1992
- A theory of wormhole routing in parallel computers1992
- Bounds on evacuation time for deflection routingDistributed Computing, 1991
- Performance analysis of multihop lightwave networks with hot potato routing and distance-age-priorities1991
- 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
- On Distributed Communications NetworksIEEE Transactions on Communications, 1964