Technical Report LPCR9320

Authors: I. Ben-Aroya and A. Schuster
PDFNot Available

We propose hot-potato (or deflection) packet routing algorithms on the two-dimensional mesh. The algorithms are strongly greedy in the sense that they attempt to send packets in good directions whenever possible. Furthermore, the routing operations are simple and independent of the time that has elapsed. These two features suggest that the algorithms are practical and may also be used for continuous routing. The first algorithm gives the best evacuation time known for delivering all the packets to their destinations. A batch of k packets with maximal source-to-destination distance d_{\max} is delivered in 2(k-1)+d_{\max}. The second algorithm improves this bound to k+d_{\max} when all packets are destined to the same node. This also implies a new bound for the multi-target case, which is the first to take into account the number of in-edges of a node. The third algorithm is designed for routing permutations in which the maximal source-to-destination distance is small. In particular, when routing permutations for which d_{\max}=3, the algorithm terminates in at most seven steps. We also show a lower bound of five steps for this problem.

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