Optimizing multicast routing tree on application layer via an encoding-free non-dominated sorting genetic algorithm

摘要

The task of Application Layer Multicast (ALM) routing is to establish a proper routing tree on application layer network, which transmits data packages from a source to multiple destinations. ALM routing tree is instable due to the end-hosts’ departure or failure. In view of this, we formulated the ALM routing as a multi-objective optimization problem, where the aim is to optimize the ALM routing tree’s topological structure for minimizing its transmission delay and instability simultaneously. A novel encoding-free non-dominated sorting genetic algorithm is proposed for solving our formulated optimization problem. For achieving encoding-free, genotypes are directly represented as tree-like phenotypes in our proposed algorithm. Accordingly, the genetic operators acting on genotypes, like crossover and mutation, need to be redesigned to adapt the tree-like genotypes. The worst-case time complexity of the proposed algorithm is theoretically analyzed and exhaustive simulation results manifest that our proposed algorithm is capable of obtaining high-quality Pareto front. Besides, several interesting issues, such as how to select the final solution out of the obtained Pareto front and the reason why GP is not used, are also discussed.