DBMISD-D: A distributed algorithm for constructing and maintaining high stability application-layer multicast tree

摘要

Both IP multicast and Application-Layer Multicast (ALM) use tree structure as data delivery path, but the adaptiveness to the dynamic behaviors of member nodes in ALM trees is weaker than that of IP multicast trees. In ALM tree, when a parent node leaves or fails, all its descendent nodes must adjust their positions resulting in the interruption of multicast connections. This phenomenon is called stability problem of ALM trees which may degrade the continuity of multicast data transmission. In this paper, we analyze the stability problem of ALM trees and propose the Instantaneous Stability Degree Model (ISDM). An approach that takes advantage of the statistical properties of member's join-leave behavior is proposed to estimate the Relative Leave-Probabilities of ALM nodes. Furthermore, this paper proposes the Degree-Bounded Maximum Instantaneous Stability Degree spanning tree problem (DBMISD) based on the ISDM. The DBMISD problem is proved to be NP-hard and a distributed algorithm, namely DBMISD-D, is proposed to solve it. Finally, the simulation results show that the proposed algorithm works better than the Minimum-Depth, Longest-First, Relaxed BO, Relaxed TO and ROST algorithm in general.