Multicast routing for energy minimization using speed scaling

N. Bansal, Anupam Gupta, R. Krishnaswamy, V. Nagarajan, K.R. Pruhs, C. Stein

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

83 Citations (Scopus)

Abstract

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 s¿+¿fa, where s is the static power, and a¿>¿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 polynomial-time O(a)-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.
Original languageEnglish
Title of host publicationDesign and Analysis of Algorithms (First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings)
EditorsG. Even, D. Rawitz
Place of PublicationBerlin
PublisherSpringer
Pages37-51
ISBN (Print)978-3-642-34861-7
DOIs
Publication statusPublished - 2012
Eventconference; First Mediterranean Conference on Algorithms; 2012-12-03; 2012-12-05 -
Duration: 3 Dec 20125 Dec 2012

Publication series

NameLecture Notes in Computer Science
Volume7659
ISSN (Print)0302-9743

Conference

Conferenceconference; First Mediterranean Conference on Algorithms; 2012-12-03; 2012-12-05
Period3/12/125/12/12
OtherFirst Mediterranean Conference on Algorithms

Fingerprint Dive into the research topics of 'Multicast routing for energy minimization using speed scaling'. Together they form a unique fingerprint.

  • Cite this

    Bansal, N., Gupta, A., Krishnaswamy, R., Nagarajan, V., Pruhs, K. R., & Stein, C. (2012). Multicast routing for energy minimization using speed scaling. In G. Even, & D. Rawitz (Eds.), Design and Analysis of Algorithms (First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proceedings) (pp. 37-51). (Lecture Notes in Computer Science; Vol. 7659). Springer. https://doi.org/10.1007/978-3-642-34862-4_3