الفهرس 
AbstractOnly 14 pages are availabe for public view
 |  | from | 103 |  |  |
| | | from | 103 | | |
Abstract
Due to rapid advances in the communication technologies and the increased demand for various kinds of communication services, many nowadays network applications require support of multicast communication. Therefore, the issue of multicast routing has become more and more important, especially with the emergence of distributed real-time multimedia applications, such as video conferencing, distance learning, and video on demand. These applications involve multiple users, with their own different quality of service (QoS) requirements in terms of throughput, reliability, and bounds on end-to-end delay, delay jitter, and packet loss ratio.
The main problem of QoS multicast routing (QMR) is to set up a least-cost multicast tree, i.e. a tree covering a group of destinations with the minimum total cost over all the links, which satisfies certain QoS constraints.
The QMR problem is known to be NP-Complete and for a large scale network with high real time response, it is expensive or even infeasible to find the optimal multicast trees. Hence, the problem is usually solved by methods based on computational intelligence, such as meta-heuristic algorithms that take polynomial time and produce near optimal solutions. Many meta-heuristic algorithms have been proposed for solving the QMR problem, such as genetic algorithm (GA), simulated annealing (SA), tabu search algorithm, ant colony optimization (ACO), particle swarm optimization (PSO), and hybrid GA-PSO based algorithms.
The work in this thesis is motivated by the need for developing efficient algorithms to solve the least-cost multicast problem with QoS constraints. The QoS constraints considered in this thesis are the end-to-end delay, the delay jitter and the bandwidth. So, the aim of the research work in this thesis is to study the use of some meta-heuristic algorithms: namely GA, PSO, ACO and Hybrid GA-PSO, to solve the multicast routing problem with the considered QoS constraints.
In order to achieve this aim, five algorithms have been proposed for solving the considered problem.
The first three are GA, PSO and hybrid GA-PSO based algorithms. In these algorithms, the representation of individuals (chromosomes in GA or particles in PSO algorithm) depends on the existence of a routing table for each destination. So, before applying any of the proposed algorithms, a routing table is constructed for each source-destination pair in the given network, such that each path in the routing table satisfies the bandwidth and delay constraints. Accordingly, a fitness function has been proposed, which depends only on the cost and the delay jitter constraint. During the evolution of individuals (solutions) in the three proposed algorithms, any generated individual that does not represent a multicast tree is discarded.
The forth algorithm is an ACO-based algorithm. In this algorithm, the ACO algorithm is used for finding the best path for each destination that satisfy the QoS constraints separately and then these best paths are combined to obtain the best multicast tree.
The fifth algorithm is called tree growth based ACO algorithm (TGACO). This algorithm generates a multicast tree in the way of tree growth. In the TGACO algorithm, during the construction of a multicast tree, we check only the bandwidth of the edge that has been chosen from the candidate edge set to be sure that it satisfies the bandwidth constraint, the other QoS constraints, i.e. delay and delay jitter, are included with the cost in the fitness function.
Experiments have been conducted to compare the performance of the proposed algorithms with each other and with some existing algorithms for solving the considered problem.