  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,\ldots,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\cdot \log\log\log n / \log\log n)$ bits. Given
that the only known lower bound is $\log n+\Omega(\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})$.
