Technical Report LPCR9303

Authors: A. Ben-Dor, S. Halvei and A. Schuster
PDFNot Available

In greedy hot potato routing a packet always moves towards its destination unless some other packet is using the link in the desired direction. This routing style ensures that when no congestion appears the packet takes the shortest path to its destination. We propose three general techniques for the analysis of greedy hot potato routing schemes. Each of the methods uses a very weak (though necessary) restriction, and thus may be applied to a wide class of greedy algorithms. The methods are demonstrated for many-to-one problems on the n \times n two-dimensional mesh, where the total number of packets is initially k. The first method guarantees that each of the algorithms in some large collection terminates in 16 n \sqrt{k} steps (which is asymptotically optimal when k=n^2). The second, simpler method yields O(n^2 \log k) termination time for a narrower collection. The third one guarantees 2n+2k termination time (and 2n + n^2 termination time when k=n^2), for a different class of algorithms, including also a set of non-greedy algorithms.

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