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 / 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 t_i a routing path (the virtual circuit) P_i connecting a fixed source s to sink t_i 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(α)-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.