Multicast routing for energy minimization using speed scaling

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