Technical Report CS0881

Title: A Lower Bound for Linear Interval Routing
Authors: T. Eilam, S. Moran and S. Zaks
Abstract: Linear Interval Routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of Interval Routing where the routing range associated with every link is represented by an interval with no wrap-around. A common way to measure the efficienty of such routing methods is in terms of the maximal length of a path a message traverses. For Interval Routing the upper bound and lower bound on this quantity are 2D and 1.75D-1, respectively, where D is the diameter of the network. We mprove a lower bound of $\Omega (D^2)$ on the length of a path a message traverses under Linear Interval Routing.
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 CS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion