Lower bounds for linear interval routing

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 BS 2D − 3, respectively, where D is the diameter of the network. We prove a lower bound of (D²) 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.