A Hybrid Partition Based Method for Loss Recovery in Application Layer Multicast

作者：Cui, Jian Qun; Chen, Ai Ling; Han, Jie; Chang, Ya Nan^*; Wu, Li Bing

来源：Chinese Journal of Computers, 2018, 41(9): 1990-2002.

DOI：10.11897/SP.J.1016.2018.01990

• Application-layer multicast
• Computational overheads
• Efficiency and performance
• HPLR
• Hybrid
• Loss recovery
• Multicast connections
• Recovery algorithms

Since application layer multicast (ALM) relies on the terminal hosts to forward multicast data, if the node fails or quits from the multicast tree, its descendants cannot receive the data any more. Thus, it is important to propose an efficient recovery algorithm for the ALM tree to improve the efficiency of data multicast. Aiming at this problem, this paper presents a hybrid partition-based method for ALM tree's recovery, named HPLR (a hybrid partition based method for loss recovery), which is based on the heterogeneity of node performance. In this algorithm, the service capability of nodes is defined as the ratio of the number of descendant nodes to the length of the root path. The multicast tree are divided into the center area and the marginal area according to the defined service capacity. Each of the two areas has its own recovery method so as to achieve a balance between computational overhead and time overhead. Since the nodes in the center area have stronger ability for forwarding data, the failure of such nodes will cause interruption for their descendants to receive data. Therefore, aiming at the failure of the center area node, this paper proposes a forward-based multicast tree reconstruction strategy HPLR-CD(a hybrid partition based method for loss recovery- core domain). In this strategy, the backup parent node has already designated for its child nodes before it fails, and the affected node contacts the backup parent node to recover the data transfer. The HPLR-CD algorithm avoids the time cost of the backup parent node when the node is lost, and can quickly reconstruct the multicast tree to improve the efficiency and performance of the multicast. Since the nodes in the margin area has weak ability for forwarding data, aiming at the failure of the margin area node, this paper proposes a backward multicast tree reconstruction strategy HPLR-MD (a hybrid partition based method for loss recovery- margin domain). When the node fails, the affected nodes are in contact with the grandfather node to restore the multicast connection. The HPLR-MD algorithm avoids calculating the computational overhead of the backup parent node for all nodes, and minimize the change of the topology caused by the node failture in ALM tree. The simulation results demonstrate that the cumulative percentage of HPLR algorithm is greater than that of contrast algorithm NICE and BFN in the same rejoin delay. When the cumulative percentage reaches 100%, the rejoin delay of HPLR algorithm is averagely0.16s less than that of BFN algorithm, and 0.24s less than the NICE protocol. The mean rejoin delay distribution of HPLR algorithm is between 1.05s and 1.4s, and its fluctuation range is smaller with the increase of multicast size. And the mean rejoin delay of HPLR algorithm is less than the contrast algorithm under the same multicast size. In addition, since HPLR algorithm adopts hybrid multicast recovery strategy, the total amount of control packets required to maintain the multicast tree in the same scale by the HPLR algorithm is about 50KB less than the Yang algorithm.

• 出版日期2018
• 单位华中师范大学