Lower bounds for linear interval routing
Tamar Eilam, Shlomo Moran, Shmuel Zaks · Networks · 1999
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 wraparound. A common way to measure the efficiency 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 2D − 3, respectively, where D is the diameter of the network. We prove a lower bound of Ω(D2) on the length of a path a message traverses under linear interval routing. We further extend the result by showing a connection between the efficiency of linear interval routing and the total2-diameter (defined in Section 4) of the network, and by presenting a family of graphs for which this lower bound is tight. © 1999 John Wiley & Sons, Inc. Networks 34: 37–46, 1999