Space-efficient message routing in c-decomposable networks

The problem of routing messages along near-shortest paths in a distributed network without using complete routing tables is considered. It is assumed that the nodes of the network can be assigned suitable short names at the time the network is established. Two space-efficient near-shortest path routing schemes are given for any class of networks whose members can be decomposed recursively by a separator of size at most a constant c, where c ≥ 2. For an n-node network, the first scheme uses a total of O(cn log n) items of routing information, each O(log n) bits long, and O(log n) bit names, generated from a separator-based decomposition of the network, to achieve routings that are at most three times longer than shortest routings in worst case. The second scheme augments the node names with O(c log c log n) additional bits and uses this to reduce the bound on the routings. For both schemes, the node names and the routing information can be determined efficiently.