A Delay-Constrained Many-to-Many Multicast Routing Heuristic Algorithm
一种时延约束的多点到多点组播路由启发式算法

Many-to-many multicast routing is an important problem in multicast research fields. In some cases, when the delay constraint value of a multicast session is sufficiently small, a single shared multicast tree may not be able to satisfy this constraint. However, constructing multiple shared trees can increase managing overhead. The objective is to construct the minimum number of shared trees necessary to satisfy the delay constraint. The Delay-Constrained Multiple-Shared Multicast Tree problem (DCMSMT)is known to be NP-complete. In this paper, a heuristic algo- rithm named DCMMHA is proposed to solve DCMSMT problem. The algorithm generates an ordered list of candidate centers according to specific criterion. Then the sources and destinations attempt to join one of the shared trees, with- out violating the delay constraint. Finally, algorithm updates the selected centers. A large number of simulations demonstrate that DCMMHA algorithm has the best performance of the number of multicast centers compared to the other four algorithms, and reduces total overhead for managing these shared trees.