Research Of Network Multicast Routing Technology Based On Genetic Algorithm

With the development of Internet and the advent of various multimedia applications, multicasting technology is widely applied. Multicast routing constructs paths along with data packets from a source are distributed to reach many, but not all, destinations in a communication network. Tree construction is a commonly used approach in solving the multicast routing problem. One advantage of multicast tree is that data are distributed to different multicasting destinations along the branches in parallel, which reduces the delay. The other is that message need only be replicated at forking nodes, which minimizes the data replication, spares the network bandwidth, reduces the network load and lessens the congestion. Thus multicasting is mostly researched and utilized at present. Multicast routing algorithms are used to compute multicast trees that satisfy quality of service requirement.Firstly, this paper analyses and summarizes the routing technology, including unicast routing, multicast routing and multicast routing based on genetic algorithm, presents the research of quality of service multicast routing will be focused on simplicity, generality, extensibility, hierarchical routing and routing with imprecise state information.Then, the paper analyses the principle of multicast and multicast routing technology. Commonly multicast routing algorithms use heuristic technology, either too complex to solve problems, or too time-consuming to be applied, and genetic algorithm is simple and effective, suitable for multicast routing. Subsequently the paper introduces the basic idea, the process and the mathematical fundament of genetic algorithm, analyses and summarizes the basic element design technology and the improvement methods of genetic algorithm.On the above, to overcome the pre-maturity and low speed of search in the late phase of multicast routing algorithm based on genetic algorithm, the author gives the multi-population parallel annealing genetic multicast routing algorithm to solve the bandwidth, delay, delay jitter and packet loss constrained least-cost multicast routing problem, which combines themulti-population parallel technology and annealing technology, adopts tree-like coding approach. In addition, the author verifies the correction of the algorithm theoretically and experimentally, and analyzes the time complexity and the space complexity, points out the worst time complexity is (max(e+n㏒+k ,n2)) and the worst space complexity is (kn2), which are polynomial solutions and indicate the algorithm is effective.