TITLE: Compact Routing Schemes With Low Stretch Factor
(Extended Abstract) AUTHORS: Tamar Eilam, Cyril Gavoille and David Peleg ABSTRACT: This paper presents a routing strategy called {\em Pivot Interval Routing (PIR)}, which allows message routing on every weighted $n$-node network along paths whose {\em stretch} (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at most three, with routing tables of size $O(n^{3/2}\log^{3/2}{n})$ bits in total. A similar routing strategy for unweighted networks which guarantees the same bounds on the stretch factor and in addition a bound of $\ceil{1.5D}$ on the route lengths, where $D$ is the diameter of the network, is also presented. Moreover, it is shown that the PIR strategy can be implemented so that the generated scheme is in the form of an {\em interval routing scheme (IRS)}, using at most $2\sqrt{n(1+\ln{n})}$ intervals per link in the first case and $3\sqrt{n(1+\ln{n})}$ in the second case. As a result, the schemes are simpler than previous ones and they imply that paths of messages are loop-free. Finally, it is shown that there is no {\em loop-free\/} routing strategy guaranteeing a memory bound of $\sqrt{n}$ bits per router for all networks, regardless of the route lengths.