基于优先级的应用层平衡多播树算法研究.pdfVIP

电子发烧友 电子技术论坛 基于优先级的应用层平衡多播树算法研究 许建真 周佩 岳静 卢瑞玲 Priority-based Balanced Tree Building Algorithm for ALM XU Jianzhen, ZHOU Pei, YUE Jing , and LU Ruilin (College of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing, 210003) Abstract This paper proposes a Priority-based Balanced Tree Building Algorithm for ALM. The algorithm constructs balanced tree by computing nodes ’priority, it guarntees a method to confirm leaders which have the best priority, and ensures the overload in an ideal state. The simulation validates mathematicial model combined with the algorithm based on Optimizing resource usage for building ALM tree, the result shows that the model can impove the construction of multicast tree efficiently. Keywords Application-Layer Multicast; Balance Tree; Priority 摘要 本文提出了一种基于优先级的平衡应用层多播树算法PBTA。该算法根据节点优先级的大小来确定多 播树的构建，提出了一种迅速找到最高优先级成员，并使多播域中主节点的负载处于理想状态的方法。通 过仿真试验对此算法的数学模型进行验证，根据多播树的吞吐量和稳定性分析，并与其他多种多播树构建 算法进行比较。实验结果表明基于此多播算法进行树的构建更加快速和有效。 关键字：应用层多播；优先级；平衡树 中图法分类号 TP39 文献标识码： A 1. 引言 随着网络技术的不断发展，多播作为一点对多点的通信，是节省网络带宽的有效方法 [1] 之一，已成为引人瞩目的技术 。 多播树的稳定性问题可分为两类，一类是由于多播成员的动态变化引起；另一类是在多 播成员不变的情况下由于其他原因引起，如网络拥塞等。单点失效(single point of failure) 问 题会导致 ALM 树结构分割，引起 ALM 多播树的重构。稳定的多播树是数据正常传输的重 要保障，虽然研究者们设计了诸多应用层多播协议，但其中却很少有保障多播树稳定性的有 效措施。因此多播树的健壮性问题一直是多播领域的一个重要研究课题。 目前通用的应用层多播树的构建算法[2]主要可以分为随机组播算法、最短路径树算法、 最大带宽算法的等几种。 为提高应用层多播树的健壮性，本文从优先级入手，提出基于优先级的应用层平衡多 播树算法，使得网络尽快收敛，网络更稳定的方法。 2. 健壮性分析 在应用层多播组中，多播树下游的节点数目越多，用来维护孩子节点的开销就越大。那 么数据的复制、转发等的开销就会随之增大，网络利用率越低。在 ALM 多播树中，若没有 采取适当的保护措施，节点离开时会导致其下游节点全部离开，当树中的多个节点频繁的加 入和退出多播组时，会引起多播树结构较大的变化，尤其是非正常退出节点出度较大时，由 此节点产生的管理开销会激增，而使用出度为 K 的平衡树能有效的减少管理节点上的开销。 图 1 K 为 4 的平衡树 电子发烧友 电子技术论坛 为讨论方便，我们定义以下概念： 定义 1：应用层多播树中，多播树的深度定义为 D ，成员节点所处的高度定义为 H ，出 度定义为 K 。 定义 2 ：应用层多播树中，成员节