Compact routing with name independence
Marta Arias, Lenore Cowen, Kofi A. Laing, Rajmohan Rajaraman, Orjeta Taka · 2003
This paper is concerned with compact routing in the name independent model first introduced by Awerbuch et al. [1] for adaptive routing in dynamic networks. A compact routing scheme that uses local routing tables of size Õ(n1/2), O(log2 n)-sized packet headers, and stretch bounded by 5 is obtained. Alternative schemes reduce the packet header size to O(log n) at cost of either increasing the stretch to 7, or increasing the table size to Õ(n2/3). For smaller table-size requirements, the ideas in these schemes are generalized to a scheme that uses O(log2 n)-sized headers, Õ(k2n2/k)-sized tables, and achieves a stretch of min[1 + (k-1)(2k/2-2), 16k2+4k ], improving the best previously-known name-independent scheme due to Awerbuch and Peleg [3].