Solving Multi-Objective Multicast Routing Problem Using a New Hybrid Approach

Solving Multi-Objective Multicast Routing Problem Using a New Hybrid Approach

Mohammed Mahseur (University of Sciences and Technology Houari Boumediene, Algeria), Abdelmadjid Boukra (University of Sciences and Technology Houari Boumediene, Algeria) and Yassine Meraihi (University of M'Hamed Bougara Boumerdes, Algeria)
Copyright: © 2018 |Pages: 15
DOI: 10.4018/IJAEC.2018100102


Multicast routing is the problem of finding the spanning tree of a set of destinations whose roots are the source node and its leaves are the set of destination nodes by optimizing a set of quality of service parameters and satisfying a set of transmission constraints. This article proposes a new hybrid multicast algorithm called Hybrid Multi-objective Multicast Algorithm (HMMA) based on the Strength Pareto Evolutionary Algorithm (SPEA) to evaluate and classify the population in dominated solutions and non-dominated solutions. Dominated solutions are evolved by the Bat Algorithm, and non-dominated solutions are evolved by the Firefly Algorithm. Old and weak solutions are replaced by new random solutions by a process of mutation. The simulation results demonstrate that the proposed algorithm is able to find good Pareto optimal solutions compared to other algorithms.
Article Preview

2. Background

The multi-objective multicast routing problem is a topical issue that has been the subject of very important research, this kind of optimization problems has attracted the attention of researchers in computer communication and operational research. Several meta-heuristics have been developed around this topic including Genetic Algorithms, Tabu Search, Variable Neighborhood Search, Simulated Annealing, Immune Systems, Particle Swarm Optimization, Ant Colonies…

Cui et al. (Cui, Lin, & Wei, 2003) proposed a routing approach based on a genetic algorithm and Pareto dominance, their approach optimizes three qualities of service parameters. The simulations show that the used modeling can found a set of non-dominated multicast trees with a good quality to approximate the Pareto front.

Crichingo and Barán (Crichigno & Barán, 2004) proposed a new multicast algorithm based on the SPEA algorithm optimizing simultaneously the cost of the tree, the maximum end-to-end delay, and the average delay. They used an evolutionary population (P) and a Pareto set (Pnd), their proposed algorithm starts with a random population (P), individuals evolve to optimal solutions, and these are included in (Pnd).

They proposed also other multi-objective multicast routing algorithm (MMA) based on SPEA that simultaneously optimizes the maximum link utilization, the cost of the multicast tree, the end-to-end delay, and the average time (Crichigno & Barán, 2004). In the MMA1 algorithm, they used the binary tournament selection; in the MMA2 algorithm, they used the roulette selection.

Koyama et al. (Koyama, Barolli, Matsumoto, & Apduhan, 2004) have proposed a multi-objective genetic algorithm optimizing the cost and delay of the routing tree, their proposed approach is a source-based routing method and has a flexible and adaptive behavior. The experimentations demonstrate the performance of their proposed solution

Donoso et al. (Donoso, Fabregat, & Marzo, 2004) proposed a new a multi-objective traffic engineering scheme using different distribution trees to multicast several flows by combining into a single aggregated metric the different objective functions of multicast routing.

Fabregat et al. (Fabregat, Donoso, Baran, Solano, & Marzo, 2005) proposed a new traffic engineering load balancing taxonomy, they developed a new algorithm inspired by the SPEA Algorithm.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing