TY - GEN

T1 - Multicast Routing for Energy Minimization Using Speed Scaling

AU - Bansal, Nikhil

AU - Gupta, Anupam

AU - Krishnaswamy, Ravishankar

AU - Nagarajan, Viswanath

AU - Pruhs, Kirk

AU - Stein, Cliff

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2012.

PY - 2012

Y1 - 2012

N2 - We consider virtual circuit multicast routing in a network of links that are speed scalable. We assume that a link with load f uses power σ + fα,whereσ is the static power, and α>1 is some constant. We assume that a link may be shutdown if not in use. In response to the arrival of client i at vertex ti a routing path (the virtual circuit) Pi connecting a fixed source s to sink ti must be established. The objective is to minimize the aggregate power used by all links. We give a polylog-competitive online algorithm, and a polynomialtime O(α)-approximation offline algorithm if the power functions of all links are the same. If each link can have a different power function, we show that the problem is APX-hard. If additionally, the edges may be directed, then we show that no poly-log approximation is possible in polynomial time under standard complexity assumptions. These are the first results on multicast routing in speed scalable networks in the algorithmic literature.

AB - We consider virtual circuit multicast routing in a network of links that are speed scalable. We assume that a link with load f uses power σ + fα,whereσ is the static power, and α>1 is some constant. We assume that a link may be shutdown if not in use. In response to the arrival of client i at vertex ti a routing path (the virtual circuit) Pi connecting a fixed source s to sink ti must be established. The objective is to minimize the aggregate power used by all links. We give a polylog-competitive online algorithm, and a polynomialtime O(α)-approximation offline algorithm if the power functions of all links are the same. If each link can have a different power function, we show that the problem is APX-hard. If additionally, the edges may be directed, then we show that no poly-log approximation is possible in polynomial time under standard complexity assumptions. These are the first results on multicast routing in speed scalable networks in the algorithmic literature.

UR - http://www.scopus.com/inward/record.url?scp=84902120010&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902120010&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-34862-4_3

DO - 10.1007/978-3-642-34862-4_3

M3 - Conference contribution

AN - SCOPUS:84902120010

SN - 9783642348617

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 37

EP - 51

BT - Design and Analysis of Algorithms - 1st Mediterranean Conference on Algorithms, MedAlg 2012, Proceedings

A2 - Even, Guy

A2 - Rawitz, Dror

PB - Springer Science and Business Media Deutschland GmbH

T2 - 1st Mediterranean Conference on Algorithms, MedAlg 2012

Y2 - 3 December 2012 through 5 December 2012

ER -