Quality of Service (QoS) Optimization in a Multicast Routing: A Hybrid Solution

Quality of Service (QoS) Optimization in a Multicast Routing: A Hybrid Solution

Mohammed Mahseur (University of Algiers 3, Ibrahim, Algeria) and Abdelmadjid Boukra (University of Sciences and Technology Houari Boumediene, Bab Ezzouar, Algeria)
Copyright: © 2019 |Pages: 28
DOI: 10.4018/IJAMC.2019040102


Optimizing the QoS of multicast routing with multiple constraints is a NP-hard problem. Thus, the use of approximate methods is unavoidable. This article proposes to modify Bat Algorithm (BA) to solve such problem. BA is a metaheuristic that has been applied to several issues of various fields and has given good results, which has owned him a good reputation in terms of robustness and performance. Like any metaheuristic, BA can be trapped in a local optimum. In order to avoid such problem, the authors propose to hybridize BA with the quantum principle and introduce the chaotic map in the calculation of parameters leading to more diversification. The authors chose to adopt a quantum representation for the solutions. The approach, named quantum Bat Algorithm with Chaotic Map (CBAQEA), was experimented and compared with other well-known methods. The experimental results reveal the efficiency and the superiority of the proposed algorithm in terms of multicast routing cost with a good trade-off between intensification and diversification without premature convergence compared to other algorithms in the literature.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2020): Forthcoming, Available for Pre-Order
Volume 10: 4 Issues (2019): 2 Released, 2 Forthcoming
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