Name
Abstract | ||
|---|---|---|
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 shut down when idle. We assume the standard model for component power: the power consumed by a component with load (speed) s is sigma + s(alpha), where sigma is the static power and the exponent alpha > 1. We obtain a very simple O(log(alpha) k)-approximation algorithm for multicommodity routing, where k is the number of demand pairs. This improves upon previous results by several logarithmic factors. The key step in our algorithm is a random sampling technique that we call hallucination, which is reminiscent of the sample-augment framework for buy-at-bulk problems, and sampling in cut-sparsification algorithms. We also consider the online setting of the problem, where demand pairs arrive over time. We show that our offline algorithm naturally extends to the online setting, and obtain a randomized competitive ratio of O(log(3 alpha+1) k), which is the first nontrivial bound. The analysis of this algorithm involves the study of priority multicommodity flows, where edges and demand-pairs have priorities and each demand-pair must route its flow only on edges of lower priority. We establish a polylogarithmic flow-cut gap for these priority flows, which we believe is of independent interest. Finally, we show how our technique can be used to achieve a randomized (O(log m), O(log(2) m)) bicriteria competitive algorithm for the uniform capacitated network design problem, where m is the number of edges. Here, every edge has a cost c(e) and uniform capacity (q), and the goal is to choose the minimum cost subgraph that can support the given multicommodity demand. This is the first online algorithm for this problem. In fact, our approach also improves prior results in the offline setting by several logarithmic factors. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/18M1228591 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
network design,approximation algorithms,online algorithms,energy efficiency | Online algorithm,Discrete mathematics,Approximation algorithm,Network planning and design,Virtual circuit routing,Efficient energy use,Idle,Computer network,Mathematics,Scalability | Journal |
Volume | Issue | ISSN |
49 | 1 | 0097-5397 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Antonios Antoniadis | 1 | 127 | 13.81 |
| Sungjin Im | 2 | 353 | 33.73 |
| Ravishankar Krishnaswamy | 3 | 322 | 25.01 |
| Benjamin Moseley | 4 | 554 | 50.11 |
| VISWANATH NAGARAJAN | 5 | 642 | 46.44 |
| Kirk Pruhs | 6 | 2286 | 192.78 |
| C Stein | 7 | 1207 | 125.21 |