On the space requirement of interval routing

Interval routing is a space-efficient method for point-to-point networks. It is based on labeling the edges of a network with intervals of vertex numbers (called interval labels). An M-label scheme allows up to M labels to be attached on an edge. For arbitrary graphs of size m, n the number of vertices, the problem is to determine the minimum RP necessary for achieving optimality in the length of the longest routing path. The longest routing path resulted from a labeling is an important indicator of the performance of any algorithm that runs on the network. We prove that there exists a graph with D=Ω(n^1/3) such that if M⩽n/18D-O(√n/D) the longest path is no shorter than D+Θ(D/√M). As a result, for any M-label 1RS, if the longest path is to be shorter than D+Θ(D/√M), at least M=Θ(n/D) labels per edge would be necessary