Algorithms of Spanning Tree Based on the Stability Probability and Contribution Link of Nodes for Application Layer Multicast

Application layer multicast (ALM) which relys on independent terminal hosts to relay multicast data, has emerged as a viable solution to most problems associated with IP multicast. However, the application layer multicast faces new challenges, for instance, the stability of ALM system, the minimum delay spanning tree of ALM, etc. In this paper, the research focuses on the algorithms of the high stability and minimum delay spanning tree for application layer multicast. Firstly, the paper analyzes the influencing factors of ALM stability and delay, and attributes them to the stability probability of terminal hosts, the degree constraints of terminal hosts and the unicast cost between two terminal hosts. The problem of the high stability and minimum delay spanning tree is modeled into a spanning tree based on stability probability, degree-constrained, and edge-weighted for application layer multicast (T-SDE). We propose a theorem of stability degree under the T-SDE, and show that T-SDE is NP-hard. Secondly, through analyzing the contribution of nodes to application layer multicast in stability and delay, three algorithms of spanning tree are given based on the stability probability and contribution link of nodes. Finally, from the experiment, the spanning trees of these algorithms are approved to have a great advantage in the average delay, the maximum delay, and the stability degree.