Technical Report LPCR9305

Title: HOT-POTATOE WORM ROUTING is \small{almost} \normalsize as easy as STORE-AND-FORWARD PACKET ROUTING.
Authors: I. Newman and A. Schuster

The theory of worm routing (rather than packet routing recently attracted an increased attention as an abstraction of the underlying communication mechanisms in many parallel machines. Routing the worms in the hot-potato style is a desired form of communication in high-speed optical interconnection networks. In this work we develop a simple method for the design of parallel hot-potato worm routing algorithms. Our basic approach is to apply known packet routing algorithms, so that in each step worms are moved around instead of packets. For hot-potato permutation routing of worms of size k we have the following results. We get a O(k^{2.5} n) algorithm for the n \times n mesh, and a O(k^{1.5} n) algorithm for the corresponding offline problem. For the 2^n-nodes hypercube we get a O(k^3 n \log^2 n) deterministic algorithm, and a O(k^3 n) randomized algorithm. Although the results are given for permutation routing on the mesh and the hypercube, the general method can be applied to many other networks and to more general communication patterns as well. Moreover, once better routing algorithms are found for the underlying network, the worm routing algorithm improves too.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the LPCR technical reports of 1993
To the main CS technical reports page

Computer science department, Technion