TY - JOUR
T1 - Efficient message routing in planar networks
AU - Frederickson, Greg N.
AU - Janardan, Ravi
PY - 1989
Y1 - 1989
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 the class of planar networks. Both schemes use the separator property of planar networks in assigning the node names and performing the routings. For an n-node network, the first scheme uses O(log n)-bit names and a total of O(n4/3) items of routing information, each O(log n) bits long, to generate routings that are only three times longer than corresponding shortest routings in worst case. For any constant ε, 0 < ε < 1/3, the second scheme achieves the better space bound of O(n1+ε) items, each O((1/ε)log n) bits long, but at the expense of O((1/ε)log n)-bit node names and a worst-case bound of 7 on the routings.
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 the class of planar networks. Both schemes use the separator property of planar networks in assigning the node names and performing the routings. For an n-node network, the first scheme uses O(log n)-bit names and a total of O(n4/3) items of routing information, each O(log n) bits long, to generate routings that are only three times longer than corresponding shortest routings in worst case. For any constant ε, 0 < ε < 1/3, the second scheme achieves the better space bound of O(n1+ε) items, each O((1/ε)log n) bits long, but at the expense of O((1/ε)log n)-bit node names and a worst-case bound of 7 on the routings.
UR - http://www.scopus.com/inward/record.url?scp=0024716011&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024716011&partnerID=8YFLogxK
U2 - 10.1137/0218058
DO - 10.1137/0218058
M3 - Article
AN - SCOPUS:0024716011
SN - 0097-5397
VL - 18
SP - 843
EP - 857
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 4
ER -