Shorter Labels for Routing in Trees

A routing labeling scheme assigns a binary string, called a label, to each node in a network, and chooses a distinct port number from 1, . . . , d for every edge outgoing from a node of degree d. Then, given the labels of u and w and no other information about the network, it should be possible to determine the port number corresponding to the first edge on the shortest path from u to w. In their seminal paper, Thorup and Zwick [SPAA 2001] designed several routing methods for general weighted networks. An important technical ingredient in their paper that according to the authors "may be of independent practical and theoretical interest" is a routing labeling scheme for trees of arbitrary degrees. For a tree on n nodes, their scheme constructs labels consisting of (1 + o(1)) log n bits such that the sought port number can be computed in constant time. Looking closer at their construction, the labels consist of log n + O(log n • log log log n/ log log n) bits. Given that the only known lower bound is log n + Ω(log log n), a natural question that has been asked for other labeling problems in trees is to determine the asymptotics of the smaller-order term.

We make the first (and significant) progress in 19 years on determining the correct second-order term for the length of a label in a routing labeling scheme for trees on n nodes. We design such a scheme with labels of length log n + O((log log n) 2 ). Furthermore, we modify the scheme to allow for computing the port number in constant time at the expense of slightly increasing the length to log n + O((log log n) 3 ).