Article Preview
Top1. Introduction
In recent years, we are witnessing the spread of many and various modern multimedia multicast applications in networks. These applications connect a transmitter of data packets to a group of receivers. The nature of these applications requires a large bandwidth with a reasonable period of transmission, a low jitter value and a low loss rate to avoid the degradation of audio and video playback quality.
These applications, therefore, require a high level of network resources quality, which needs to resolve the network quality of service optimization problem.
The multicast routing module is a cornerstone in the development and optimization of the quality of service. This later is a NP-hard problem (Wang & Crowcroft, 1996), which cannot be resolved with exact methods for large problem size. Thus, the use of metaheuristics is unavoidable.
Our problem, called Multi-Constrained Least Cost (MCLC) consists in minimizing the cost of multicast routing tree under multiple constraints such as delay, delay-jitter, bandwidth, and packet loss rate.
In recent years, many efficient metaheuristics, such as Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), Greedy Randomized Adaptive Search Procedure (GRASP), Ant Colony Optimization (ACO), Path Relinking Algorithm (PRA), Harmony Search (HS), Particle Swarm Optimization (PSO), Bat Algorithm (BA), and Optimization Based on Biogeography (BBO) have been applied to solve the multicast routing problem with delay constraint DCLC (Delay Constrained Least Cost) or with multiple constraints MCLC.
Wang Zheng Ying &al (Zhengying, Bingxin, & Erdun, 2001) applied the reproduction principle of GA (selection, crossover, and mutation) for the construction of new solutions. Haghighat et al. (Haghighat, Faez, Dehghan, Mowlaei, & Ghahremani, 2004) proposed new representations of genotype and new heuristics to mutation and crossover of individuals. Koyama et al. (Koyama, Nishie, Arai, & Barolli, 2008) propose a new QoS multicast routing protocol, in which new genetic operations are introduced.
Youssef H et al. (Youssef, Al-Mulhim, M. Sait, & Tahir, 2002) present a TS algorithm to build the near optimal solution, their algorithm starts with an initial feasible solution and builds a tree of the sink for each destination with the shortest path of Dijkstra algorithm, in a given iteration the algorithm refines the tree at a lower cost. Skorin-Kapov and Kos (Skorin-Kapov & Kos, 2003) proposed an algorithm based on TS called Tabu search–constrained Steiner tree (TS-CST). The neighboring solutions include all the solutions for which the binary representation is a little different. A movement in the TS-CST is to choose the best new neighbor solution on the Tabu list. TS-CST stops after a predefined number of iterations without improvement. Wang et al. (Wang, Fang, Wang & Sun, 2004) added in the search algorithm of Tabu the ‘flexible memory’ to adjust the size of the Tabu list and the generation of neighborhood structure based on a “switching path” operation. Ghaboosi and Haghighat (Ghaboosi & Haghighat, 2007) proposed different movements in the Tabu list and have modified the movements proposed in (Wang, Fang, Wang, & Sun, 2004) and (Youssef, Al-Mulhim, Sait & Tahir, 2002) in order to accelerate the search process. Armaghan and Haghighat (Armaghan & Haghighat, 2009) proposed a new algorithm based on TS with a strategy of the list of candidates who can produce faster good solutions than other algorithms based on the traditional simple TS.
Wang and Jiang (Wang & Jiang, 2004) proposed SA algorithm for multicast routing problem, compared with GA; they found that SA algorithm is able to converge to the near optimal solution in a shorter time.
Skorin-Kapov and Kos (Skorin-Kapov & Kos, 2006) used GRASP for this problem; GRASP is an iterative algorithm such that each iteration consists of two phases: construction and local search. In the first phase, one feasible solution is constructed with GRASP, and it is improved by performing a local search algorithm in the second phase. After the execution of several iterations, the best solution found in all iterations is kept as a final solution.