首页> 外文会议>Design and analysis of algorithms >Multicast Routing for Energy Minimization Using Speed Scaling
【24h】

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.
机译:我们考虑在速度可伸缩的链路网络中进行虚拟电路多播路由。我们假设有负载的链路使用功率σ+ f〜α,其中σ是静态功率,而α> 1是某个常数。我们假定如果不使用链接,则可能会关闭它。响应于客户端i到达顶点t_i,必须建立将固定源s连接到宿t_i的路由路径(虚拟电路)P_i。目的是最小化所有链路使用的总功率。如果所有链接的幂函数都相同,我们给出了一个多对数竞争在线算法,以及一个多项式时间O(α)近似离线算法。如果每个链路可以具有不同的幂函数,则表明问题出在APX上。如果另外地,可以指示边缘,那么我们表明在标准复杂性假设下,多项式时间内不可能进行多对数近似。这些是算法文献中有关速度可扩展网络中多播路由的第一个结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号