Space-Efficient Message Routing inc-Decomposable Networks
Authors:
- Greg N. FredericksonGFGreg N. Frederickson
- Ravi JanardanRJRavi Janardan
- 1 February 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (1) , 164-181
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 \geqslant 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.l 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 to $(2 / \alpha) + 1$, where $\alpha, 1 < \alpha \leq 2$, is the root of the equation $\alpha ^{\lceil (c+1) / 2\rceil } - \alpha - 2 = 0$. For both schemes, the node names and the routing information can be determined efficiently.
Keywords
This publication has 16 references indexed in Scilit:
- Efficient Message Routing in Planar NetworksSIAM Journal on Computing, 1989
- Designing networks with compact routing tablesAlgorithmica, 1988
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- Efficient Algorithms for Optimization and Selection on Series-Parallel GraphsSIAM Journal on Algebraic Discrete Methods, 1986
- Finding small simple cycle separators for 2-connected planar graphsJournal of Computer and System Sciences, 1986
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Hierarchical routing for large networks Performance evaluation and optimizationComputer Networks (1976), 1977
- Efficient Algorithms for Shortest Paths in Sparse NetworksJournal of the ACM, 1977
- GRAPH THEORY1969
- Topology of series-parallel networksJournal of Mathematical Analysis and Applications, 1965