关键词: 应用层组播, 遗传算法, 约束松弛, 多目标优化

Abstract: In Application Layer Multicast（ALM） system, the end-hosts undertaking the task of forwarding data have no wire-speed forwarding capability. Heavy forwarding load can result in congestion occurring on the end-host, thus causing that the sub-routing tree rooted at the congested end-host losses connection. In order to address the issue of poor stability of ALM resulted from congestion, the process of constructing the optimal multicast routing tree is formulated as the degree-constrained least-cost Steiner tree problem. A Genetic Algorithm（GA） for constructing node-forwarding-capability-restricted ALM routing tree is proposed. The proposed GA encodes a multicast routing tree by using the predecessor of each tree-node, which is convenient for measuring the out-degree of nodes. In order to make the genetic manipulation applicable to the predecessor-based routing tree representation, the conception of  “gene-pool” is introduced to implement the operation of crossover and mutation. Aiming at the production of infeasible solutions caused by the degree-constraint, a new optimization objective is proposed to treat the excess that a multicast routing tree violates the degree-constraint as the 2nd minimization goal such that the multicast routing tree being satisfied with the degree-constraint can be chosen from the Pareto front, which avoids the risk of obtaining infeasible solution by using the penalty function-based method. Simulation experiments show that the proposed GA is capable of constructing the node-forwarding-capability-restricted ALM routing tree of the least transmission delay and possesses good reliability on problem-solving.

Key words: application layer multicast, genetic algorithm, constraint-relaxation, multi-objective optimization