Multicast tree algorithm considering maximum delay bound for real-time applications

Sanghyun Ahn, David H C Du

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations

Abstract

For many multicast applications, especially those requiring real-time traffic, it is important that the maximum delay bound requirement between any pair of group members be satisfied. Most studies on multicast routing have been based on a single multicast tree (a shortest path tree or a minimal Steiner tree) approach. By using only a single multicast tree for a multicast group, satisfying the maximum delay bound requirement is nearly impossible. To fulfill these requirements, we adopt the multiple multicast tree concept whose disadvantage is the high tree maintenance cost. Since the tree maintenance cost is proportional to the number of multicast trees for a multicast group, it is necessary to minimize the number of multicast trees. In this paper, we formulate the Delay-Bounded Multicast Tree (DBMT) problem whose main objectives are to satisfy an application's maximum delay bound among the group members and to minimize the number of multicast trees needed for a group communication. We categorize the DBMT problem according to the application's needs into two subproblems, the Shortest Path Tree-based DBMT (SPT_DBMT) and the Minimal Steiner Tree-based DBMT (MST_DBMT) problems. For the DBMT subproblems, we prove the NP-hardness and propose heuristic algorithms. For the performance analysis, simulations were performed.

Original languageEnglish (US)
Pages (from-to)172-181
Number of pages10
JournalConference on Local Computer Networks
StatePublished - Dec 1 1996
EventProceedings of the 1996 21st Conference on Local Computer Networks - Minneapolis, MN, USA
Duration: Oct 13 1996Oct 16 1996

Fingerprint

Dive into the research topics of 'Multicast tree algorithm considering maximum delay bound for real-time applications'. Together they form a unique fingerprint.

Cite this