Randomized oblivious integral routing for minimizing power cost

• Original study on energy saving in oblivious integral routing.
• An Ω(|E|α−1α+1) lower bound on competitive ratio.
• A random oblivious integral routing algorithm with polylog-tight competitive ratio.
• A general framework to design and analyze oblivious integral routing algorithms.
• Polylog bound on competitive ratio for expanders and hypercubes.

Given an undirected network G(V,E)G(V,E) and a set of traffic requests RR, the minimum power-cost routing problem requires that each Rk∈RRk∈R be routed along a single path to minimize ∑e∈E(le)α∑e∈E(le)α, where lele is the traffic load on edge e and α   is a constant greater than 1. Typically, α∈(1,3]α∈(1,3]. This problem is important in optimizing the energy consumption of networks.To address this problem, we propose a randomized oblivious routing algorithm. An oblivious routing algorithm makes decisions independently of the current traffic in the network. This feature enables the efficient implementation of our algorithm in a distributed manner, which is desirable for large-scale high-capacity networks.An important feature of our work is that our algorithm can satisfy the integral constraint, which requires that each traffic request RkRk should follow a single path. We prove that, given this constraint, no randomized oblivious routing algorithm can guarantee a competitive ratio bounded by o(|E|α−1α+1). By contrast, our approach provides a competitive ratio of O(|E|α−1α+1log2αα+1⁡|V|⋅logα−1⁡D), where D   is the maximum demand of traffic requests. Furthermore, our results also hold for a more general case where the objective is to minimize ∑e(le)p∑e(le)p, where p≥1p≥1 is an arbitrary unknown parameter with a given upper bound α>1α>1.The theoretical results established in proving these bounds can be further generalized to a framework of designing and analyzing oblivious integral routing algorithms, which is significant for research on minimizing ∑e(le)α∑e(le)α in specific scenarios with simplified problem settings. For instance, we prove that this framework can generate an oblivious integral routing algorithm whose competitive ratio can be bounded by O(logα⁡|V|⋅logα−1⁡D)O(logα⁡|V|⋅logα−1⁡D) and O(log3α⁡|V|⋅logα−1⁡D)O(log3α⁡|V|⋅logα−1⁡D) on expanders and hypercubes, respectively.