Hop-constrained oblivious routing
Mohsen Ghaffari, Bernhard Haeupler, Goran Žužić
Abstract
We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing.
Topics & Concepts
Computer scienceDilation (metric space)Routing (electronic design automation)Scheme (mathematics)Multipath routingStatic routingComputer networkTheoretical computer scienceRouting protocolMathematicsCombinatoricsMathematical analysisComplexity and Algorithms in GraphsOptimization and Search ProblemsCryptography and Data Security