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.
|Name||Lecture Notes in Computer Science|
|Conference||conference; First Mediterranean Conference on Algorithms; 2012-12-03; 2012-12-05|
|Period||3/12/12 → 5/12/12|
|Other||First Mediterranean Conference on Algorithms|