کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435666 | 689924 | 2015 | 26 صفحه PDF | دانلود رایگان |
• 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α−1D), 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α−1D)O(logα|V|⋅logα−1D) and O(log3α|V|⋅logα−1D)O(log3α|V|⋅logα−1D) on expanders and hypercubes, respectively.
Journal: Theoretical Computer Science - Volume 607, Part 2, 23 November 2015, Pages 221–246