Analyzing the effects of neighborhood crossover in multiobjective multicast flow routing problem

Multicast transmission corresponds to send data to several destinations, often involving requirements of Quality of Service (QoS) and Traffic Engineering (TE). These multiple requirements lead to the need of optimizing a set of conflicting objectives subject to constraints. We investigate algorithms to perform the calculus of multicast routes while minimizing five objectives - mean link utilization, maximum link utilization, total cost, maximum end-to-end delay and hops count - attending a link capacity constraint. New multiobjective evolutionary models to tackle multicast routing are discussed here based on SPEA2 and NSGA-II. The key investigation performed here is about the incorporation of Neighborhood Crossover (NC) as the mating selection of parent pairs. Two variations of NC with different shuffling strategies are discussed here. The incorporation of both NC methods to the routing environments leaded to significant improvements mainly on convergence, while maintaining a compromise on diversity. Our results indicate that the evolutionary model based on SPEA2 using a shuffle procedure, in which after sorting the population according to a focused objective, an individual can cross over with a neighbor around a small range (10%), had returned the better results. A comparison of the results obtained by the aforementioned evolutionary model with the traditional Dijkstra´s (Shortest Path Tree) and Takahashi-Matsuyama algorithms shows that the our proposal is a very competitive multicast routing model.