Distributed multicast routing, with end-to-end delay and delay variation constraints

✍ Scribed by C.P. Low; Y.J. Lee

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 737 KB
• Volume: 23
• Category: Article
• ISSN: 0140-3664
• DOI: 10.1016/s0140-3664(00)00165-1

✦ Synopsis

We study the problem of constructing multicast trees for high-bandwidth delay-sensitive applications in a point-to-point communication network. This problem arise in real time multimedia applications, which often requires bounded end-to-end delay along paths from the source to each destination and bounded variations among the delays along these paths to ensure that data packets reaches the destinations without exceeding certain delay, failing which the user will experience jitters effect.

This problem can be formulated as that of finding a minimum cost Steiner tree which satisfy the above-mentioned constraints and is known to be computationally intractable, being NP-complete. In this paper, we propose a new distributed algorithm, called the Distributed Delay and Delay Variation Bounded Multicast (DDVBM) algorithm for the problem. Empirical studies shows that our proposed algorithm performs very well in terms of cost and inter-destination delay variations of the solutions that it generates as compared to some existing algorithms.