Lower bounds for linear interval routing

Linear interval routing is a space-efficient routing method for point-to-po int communication networks. It is a restricted variant of interval routing where the routing range associated with every link is represented by an int erval with no wraparound. A common way to measure the efficiency of such ro uting methods is in terms of the maximal length of a path a message travers es. 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 Omega(D-2) on the length of a path a message traver ses under linear interval routing. We further extend the result by showing a connection between the efficiency of linear interval routing and the tota l(2)-diameter (defined in Section 4) of the network, and by presenting a fa mily of graphs for which this lower bound is tight. (C) 1999 John Wiley & S ons, Inc. Networks 34: 37-46, 1999.