TY - JOUR
T1 - Space-efficient message routing in c-decomposable networks
AU - Frederickson, Greg N.
AU - Janardan, Ravi
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 1990
Y1 - 1990
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0025384425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025384425&partnerID=8YFLogxK
U2 - 10.1137/0219011
DO - 10.1137/0219011
M3 - Article
AN - SCOPUS:0025384425
VL - 19
SP - 164
EP - 181
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
SN - 0097-5397
IS - 1
ER -