Group multicast routing problem: A genetic algorithms based approach

To save network resources, multicast transmissions are more and more adopted by the operators when the same content has to reach several destinations in parallel, such as in IPTV services, radio broadcast and video-clip streaming. Though, with respect to unicast transmissions, multicast sessions make the routing problem more complex with huge sets of trees to be evaluated. Additionally, since in the real world several multicast sessions occur simultaneously, the suitable trees for more sessions have to be found concurrently. This problem is addressed in this paper, which proposes the use of the genetic algorithms (GA) to reduce the number of solutions to be evaluated. Firstly, a heuristic procedure is employed to generate a set of possible trees for each session in isolation; secondly, the GA are applied to find the appropriate combination of the trees to comply with the bandwidth needs of the group of multicast sessions simultaneously. The goodness of each solution is assessed by means of an expression that weights both network bandwidth allocation and one-way delay. Some key parameters are also introduced that allow the operator to find the desired balance between quality of service and network resource utilization. Experimental results are provided to show the performance of the proposed algorithm compared with alternative solutions in terms of bandwidth utilization and transmission delay and to illustrate the influence of the selection and crossover procedures configuration. (C) 2007 Elsevier B.V. All rights reserved.