Compact routing schemes with low stretch factor (extended abstract)

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.