Separator-Based Strategies for Efficient Message Routing (Preliminary Version)

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.

Authors

• Greg N. Frederickson
• Ravi Janardan

Keywords

• Routing
• Particle separators
• Costs
• Network topology
• Encoding
• Computer science
• Equations
• Labeling
• Item Information
• Routing Information
• N Log N
• Routing Table
• Common Ancestor
• Shortest Path
• Pair Of Nodes
• Previous Strategies
• Routing Algorithm
• Core Nodes
• Planar Graphs
• Inner Nodes
• Additional Bits