TY - JOUR

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

AU - Ahn, Sanghyun

AU - Du, David H C

PY - 1996/12/1

Y1 - 1996/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030382846&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030382846&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0030382846

SN - 0742-1303

SP - 172

EP - 181

JO - Conference on Local Computer Networks

JF - Conference on Local Computer Networks

T2 - Proceedings of the 1996 21st Conference on Local Computer Networks

Y2 - 13 October 1996 through 16 October 1996

ER -