Genetic algorithm approach for constrained multicast routing in computer networks.

摘要

Multicast communication has become a key requirement for many applications where one source transmits the same information simultenously to many destinations. The problem of finding a route from the source to other group members is referred to as multicast routing. The main objective of multicast routing is to find a route shaped tree that either has the least total cost, which is known as the Steiner tree, or has the least cost for every path from source to each destination, which is known as the shortest path tree. Due to the fast evolution of real time and multimedia applications such as audio/video conferencing, interactive distributed games and real time remote control systems, some quality of services, QoS, need to be guaranteed in the underlying network. Multicast routing algorithms should support the required QoS. This thesis presents a constrained multicast routing scheme based on genetic algorithm (GA) by constructing a multicast tree that satisfies two quality of service (QoS) requirements: (i) End-to-End delay and (ii) Delay variation among path delays. The proposed scheme constructs a multicast tree by using a simple mapping technique that does not require a complex transformation in order to obtain a feasible multicast tree, and also scales well for large size networks. A new multicast routing algorithm with constraints based on genetic algorithm, called Genetic Algorithm With Delay and Delay Variations GADVM, is proposed and discussed in depth with the flowcharts and pseudo codes of its main subroutines. The proposed algorithm is applied to the problem of multicast routing with delay and delay-variation constraints. The delay variation constraint is a bound on the delay difference between any two destinations. The problem is formulated as one of the shortest path routing under delay and delay variation constraints which is know to be NP-complete. A large number of simulation experiments have been done to analyze the performance of the proposed GADVM algorithm and compare it to some other known multicast algorithms.