Compact routing schemes with low stretch factor (extended abstract)
Tamar Eilam, Cyril Gavoille, David Peleg · 1998
This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows inessage routing on every weighted n-node network along paths whose stretch (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at inost three, with routing tables of size O(n3/" log3/' 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 r1.501 on the route lengths, where D is the dianreter 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 forin of an interval routing scheme (IRS), using at most 2dm intervals per link in the first case and 3,/m in the second case.As a result, the scheines are siinpler than previous ones and they imply that paths of messages are loop-free.Finally, it is showu that there is no loop-free routing strategy guaranteeing a inemory bound of J5i bits per router for all networks, regardless of the route lengths.