Constructing delay-bounded multicast tree with optimal delay variation

Cheng Hui, Cao Jiannong, Wang Xingwei

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)


Strict QoS requirements on delay and delay variation are required for many time-sensitive applications. For real-time multicast communications, a multicast tree satisfying both end-to-end delay and delay variation constraints often needs to be determined. Such a problem is called the DVBMT problem, and proved to be NP-complete [1]. Several algorithms have been developed to solve the problem based on a simple heuristic, the 'CBT+SP' heuristic, which uses the CBT (Core Based Tree) with the SP (Shortest Path). But this heuristic has several drawbacks, which can bring serious problems to algorithms based on it. Although attempt [2] has been made to overcome the problems, it actually has fatal drawbacks. In this paper, we first analyze the drawbacks of the heuristic, and explain why the improvement attempt does not work. Then we propose an efficient algorithm, also based on the 'CBT+SP' heuristic but with drawbacks completely removed. Experimental results show that, with the same time complexity, our algorithm outperforms the most efficient existing algorithm for the DVBMT problem in terms of multicast delay variation under multicast end-to-end delay constraint.
Original languageEnglish
Title of host publication2006 IEEE International Conference on Communications, ICC 2006
Number of pages6
Publication statusPublished - 1 Dec 2006
Event2006 IEEE International Conference on Communications, ICC 2006 - Istanbul, Turkey
Duration: 11 Jul 200615 Jul 2006


Conference2006 IEEE International Conference on Communications, ICC 2006


  • Core based tree
  • Delay and delay variation
  • Multicast tree
  • Shortest path

ASJC Scopus subject areas

  • Media Technology

Cite this