Multicast Routing for Energy Minimization Using Speed Scaling
Multicast Routing for Energy Minimization Using Speed Scaling
复制标题
使用速度缩放实现能量最小化的多播路由
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Cliff Stein
中科院分区：
文献类型：
--
作者：
N. Bansal;Anupam Gupta;Ravishankar Krishnaswamy;V. Nagarajan;K. Pruhs;Cliff Stein
我们认为虚拟电路组播路由的网络中的链接是速度可扩展的。我们假设负载为f的链路使用功率σ+fα，其中σ是静态功率，α>1是某个常数。我们假设一个链接如果不使用可能会被关闭。响应于客户端i到达顶点ti，必须建立将固定源s连接到宿ti的路由路径（虚拟电路）Pi。目标是最小化所有链路使用的总功率。
在所有链路的幂函数相同的情况下，给出了一个多项式时间的O（α）近似的离线算法。如果每个链接可以有一个不同的功率函数，我们证明了这个问题是APX困难的。如果此外，边缘可能是直接的，那么我们表明，没有多对数近似是可能的，在多项式时间下，标准的复杂性假设。这些是第一个结果在速度可扩展的网络中的算法文献组播路由。
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 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.