Construction of Scalable Application Layer Multicast Tree Based on Genetic Algorithms
Zhijun Zhao · Journal of Chinese Computer Systems · 2007
Generally, genetic algorithm and heuristic algorithm are used to reduce the path latency in application layer multicast (ALM). But when there are massive end system nodes, the convergence time is long if applying genetic algorithms and an optimization solution is hard to get if applying heuristic algorithms. For solving the scalable problem and getting optimization solution, we propose the GA-MWPL-DC-ST algorithm which aims at resolving minimum weighted path latency degree-constrained spanning tree (MWPL-DC-ST) based on the two layers ALM model. As the two layers multicast sub trees (TMT and BMTs) can be constructed in the distributed way, the high payload for computing is distributed to super nodes. The GA-MWPL-DC-ST algorithm adopts the heuristic algorithms in phases of initialization, crossover and mutation, and applies adaptive parameter according to different evolving generations which accelerates convergence speed. The experiments show that two layers ALM model and the GA-MWPL-DC-ST algorithm can get better optimization solution than heuristic algorithms, and reduce the convergence time significantly, and solve the scalable problem of using genetic algorithms to compute a large-scale ALM tree.