Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality
Bernhard Haeupler, Harald Räcke, Mohsen Ghaffari
Abstract
This paper studies the fundamental task of establishing routing paths in distributed networks. We prove the existence of compact routing tables that store in each network-node few simple forwarding rules tracing out hop-constrained and oblivious routing paths for any pair of nodes. For any collection of pairs the congestion of these paths is almost-optimal, i.e., competitive with the globally optimal solution up to a sub-polynomial factor.
Topics & Concepts
Computer scienceDistributed computingStatic routingRouting (electronic design automation)Equal-cost multi-path routingRouting tableMultipath routingSimple (philosophy)Computer networkDynamic Source RoutingRouting protocolEpistemologyPhilosophyComplexity and Algorithms in GraphsAdvanced Graph Theory ResearchOptimization and Search Problems