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 -