一种混合的基于分区策略的应用层组播恢复算法

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

应用层组播技术由于依靠终端主机转发组播数据,任意中间节点的退出,都将导致其下游节点中断组播数据的接收,因此构建高效的组播恢复算法是提高组播效率的重要措施之一.针对该问题,该文在充分考虑节点性能异构性的基础上,提出了一种混合的基于分区策略的应用层组播恢复算法HPLR,在该算法中,将节点的服务能力定义为其子孙节点的数目与其根路径长度的比值,再根据节点的服务能力将组播树划分成中心区域和边缘区域,并分别提出了相应的组播恢复算法,以在系统的计算开销和时间开销方面达到平衡.位于中心区域的节点服务能力较强,一旦离开将会造成大面积的节点失联情况的发生.因此,针对中心区域节点失效的情况,该文提出了一种前向式的组播树重构策略HPLR-CD算法,在节点失效之前为其孩子节点寻找备份父节点,受影响节点通过与备份父节点联系以恢复数据传输,避免了在节点失联之后仍需计算备份父节点所产生的时间开销,能够快速进行组播树重构,提高组播的效率和性能.位于边缘区域的节点服务能力较弱,针对边缘区域的节点失效情况,该文提出了一种后向式的组播树重构策略HPLR-MD算法,当节点失效后,受影响节点通过与祖父节点联系以恢复组播连接,以此避免了为所有节点都计算备份父节点所产生的计算开销,并将节点离开事件对组播树所造成的拓扑结构的变化限制在局部范围.仿真实验表明,HPLR算法的累计百分比在同一重加入时延内均大于对比算法NICE以及BFN,并当累计百分比达到100%时,HPLR算法平均所需的重加入时延比BFN算法小0.16s、比NICE协议小0.24s.HPLR算法的平均重加入时延分布在1.05s至1.4s之间,随着组播规模的增加其波动范围较小,并且在同一组播规模下其值均小于NICE协议和BFN算法.此外,HPLR算法由于采用混合式恢复策略,其在同一规模下维护组播树所需的控制数据包总量均比对比算法Yang小约50KB.

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 averagely 0.16 s less than that of BFN algorithm,and 0.24 s less than the NICE protocol.The mean rejoin delay distribution of HPLR algorithm is between 1.05 s and 1.4 s,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 50 KB less than the Yang algorithm.