Space-efficient message routing in c-decomposable networks

Greg N. Frederickson, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)164-181
Number of pages18
JournalSIAM Journal on Computing
Volume19
Issue number1
DOIs
StatePublished - 1990

Fingerprint Dive into the research topics of 'Space-efficient message routing in c-decomposable networks'. Together they form a unique fingerprint.

Cite this