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 -