Separator-based strategies for efficient message routing
- 1 October 1986
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Message routing strategies are given for networks with certain separator properties. These strategies use considerably less space than complete routing tables, keep node names to O(log n) bits, and still route along near-shortest paths. For any network with separators of size at most a small constant c, a total of O(n log n) items of routing information is stored, and any message is routed along a path of length at most (2/α) + 1 times the length of an optimal path, where α ≫ 1 is the positive root of the equation α⌈(c+1)/2⌉ - α - 2 = 0. For planar networks, O(n1+ε) items are stored, for any constant ε, 0 ≪ ε ≪ 1/3, and the length of any message path is at most 7 times that of an optimal path.Keywords
This publication has 5 references indexed in Scilit:
- Optimal message routing without complete routing tablesPublished by Association for Computing Machinery (ACM) ,1986
- Labelling and Implicit Routing in NetworksThe Computer Journal, 1985
- Finding small simple cycle separators for 2-connected planar graphs.Published by Association for Computing Machinery (ACM) ,1984
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Topology of series-parallel networksJournal of Mathematical Analysis and Applications, 1965