Genetic algorithm based efficient routing scheme for multicast networks

Abstract

Due to the advent of many new multimedia applications in high speed networks, the issue of multicast routing has become more and more important. The multicast routing problem in computer networks is also known as the Steiner tree problem, which has been shown to be NP-complete. In this paper, we propose a new multicast routing scheme based on genetic algorithms (GA). To apply this algorithm to real networks, we also propose several methods for reducing the computational complexity. Computer simulations are conducted on a random graph to evaluate the performance of the proposed algorithm. Our numerical results show that the proposed algorithm is able to find a better solution than the conventional routing schemes. A very promising heuristic algorithm for the Steiner tree problem was proposed by Raywar-Smith. Finally, since many multimedia applications require multiple QoS constraints, such as delay, jitter, and packet loss, we extend the proposed algorithm to obtain a multi-constrained multicast tree.