Multicast Routing for Energy Minimization Using Speed Scaling

Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, Kirk Pruhs, Cliff Stein

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationDesign and Analysis of Algorithms - 1st Mediterranean Conference on Algorithms, MedAlg 2012, Proceedings
EditorsGuy Even, Dror Rawitz
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages15
ISBN (Print)9783642348617
StatePublished - 2012
Event1st Mediterranean Conference on Algorithms, MedAlg 2012 - Kibbutz Ein Gedi, Israel
Duration: Dec 3 2012Dec 5 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7659 LNNS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference1st Mediterranean Conference on Algorithms, MedAlg 2012
CityKibbutz Ein Gedi

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Multicast Routing for Energy Minimization Using Speed Scaling'. Together they form a unique fingerprint.

Cite this