A Heuristic Genetic Algorithm for Distributed Multicast Routing

Abstract

Multicast (MC) routing algorithms capable of satisfying the quality of services (QoS) requirements of real-time applications will be essential for future high-speed networks. Genetic Algorithms (GA) are stochastic search optimisation methods used in combinatorial optimisation and parameter tuning applications. In this paper, a shared-tree routing protocol based on distributed Genetic Algorithms(Gas) is presented, including building and dynamic maintenance of multicast routing tree in package exchange network. The algorithm has the following characteristics: (1) the preprocessing mechanism, (2) the tree structure coding method, (3) the heuristic crossover technique, and (4) the instructional mutation process. Simulation results over random networks show that the genetic algorithms are capable of successfully constructing MC trees which satisfy the QoS requiremnets of real time traffic. GA heuristic constucts low cost trees to solve the minimal multicast tree with delay constraint. As a result, the algorithm is efficient and effective.