Hallucination helps: energy efficient virtual circuit routing
Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk R. Pruhs, Clifford Stein · 2014
We consider virtual circuit routing protocols, with an objective of minimizing energy, in a network of components that are speed scalable, and that may be shutdown when idle. We assume that the speed s of the router is proportional to its load, and assume the standard model for component power, namely that the power is some constant static power plus sα, where typically α ∈ [1.1, 3]. We give a polynomial-time offline algorithm that is the combination of three natural combinatorial algorithms, and show that for any fixed α the algorithm has approximation ratio O(logα k), where k is the number of demand pairs. The algorithm extends rather naturally to a randomized online algorithm, which we show has competitive ratio Õ(log3α+1 k). This is the first online result for the problem. We also show that this online algorithm has competitive ratio Õ(logα+1 k) for the case that all connections have a common source. 1