首页 | 本学科首页   官方微博 | 高级检索  
     


A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology
Authors:Guoliang Xue  Wei Xiao
Affiliation:(1) Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287-5406, USA;(2) Department of Computer Science, University of Vermont, Burlington, VT 05405, USA
Abstract:This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.
Keywords:Computer communications  Minimum cost delay-constrained network under a Steiner topology  Fully polynomial time approximation scheme  Quality of service
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号