A FAST SCALABLE EVOLUTIONARY ALGORITHM FOR THE QOS MULTICAST ROUTING PROBLEM

摘要

The increasing demand of real-time multimedia services makes of quality of service based routing a serious challenge for next-generation networks. The complexity of this NP-complete problem significantly increases with the size of the network. A new evolutionary-based multicast routing algorithm is presented in this paper. It is based on computational intelligence techniques that integrate in an efficient manner the merits of genetic algorithms and the concepts of competitive learning in the area of artificial neural networks. Population-based incremental learning algorithm is utilized, among other techniques, to construct a delay bounded multicast tree. The proposed algorithm is capable of simultaneously satisfying several key quality of service requirements that are necessary for real-time multimedia applications. The main objective of the algorithm is to construct a multicast tree that is characterized by a minimum cost and a bounded end-to-end delay and residual bandwidth. It is shown through a series of extensive experimental studies that the proposed algorithm outperforms several other popular heuristic based routing algorithms in terms of execution time as well as the quality of the generated solution, for various network sizes, multicast tree sizes, and delay bounds. It is also shown that the performance of the algorithm becomes significantly superior to others as the network size increases, which confirms its high scalability.