| TR#: | CS0881 |
| Class: | CS |
| Title: | A Lower Bound for Linear Interval Routing |
| Authors: | T. Eilam, S. Moran and S. Zaks |
| CS0881.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1996/CS/CS0881), 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