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
ss and
pp destination vertices
t1, t2, ¼, tpt_1, t_2, \ldots, t_p together with
pp corresponding nonnegative delay
constraints
d1, d2, ¼, dpd_1, d_2, \ldots, d_p,
many QoS multicast problems seek a minimum cost multicast tree in which
the delay along the unique
ss--
tit_i path is no more than
did_i for
1 £ i £ p1 \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.
Computer communications - Minimum cost delay-constrained network under a Steiner topology - Fully polynomial time approximation scheme - Quality of service