通信网络-一个基于应用层的单源组播协议设计.pdf

一个基于应用层的单源组播协议设计一个基于应用层的单源组播协议设计 朱坤华 河南科技学院 计算机科学系 河南 新乡 453003 摘 要 由于IP组播在实现过程中遭遇了很多困难 所以应用层组播就成了Internet应用 研究的热点 本文在简单地论述了应用层组播的优缺点后 提出了一个基于应用层的单源组 播协议ALSSMP 此协议设计的目的是能够实现大规模直播视频 在ALSSMP中采用树拓扑优 先的方法来构造组播转发树 在组播树的维护方面 利用为转发树中每一个结点预先选择一 个 备用父结点 以设置预留链路思想的PCP算法 该协议既继承了应用层组播的优点 又在 一定程度上克服了应用层组播的不稳定性的特点 使组播树的稳定性和可靠性大大提高 关键词 应用层组播 组播转发树 备用父结点 链路预留 中图分类号 TP393 文献标识码 A Design of a single source application layer multicast protocolDesign of a single source application layer multicast protocol ZHU kun hua Department of Computer Science Henan Institute of Science and Technology Xinxiang Henan 453003 China Abstrac Because of a great deal of pressure to implement IP multicast the application layer multicast has been invigorated in Internet application research After discussing the merits and demerits of application layer multicast simply we propose an ALSSMP protocol based on application layer in this article The objective of ALSSMP is to implement live video on a large scale In this research a tree topology first approach is presented to construct multicast transmit tree In the maintenance of multicast tree we use the PCP algorithm which selects a backup parent node for every non leaf node to a spare linker This protocol which inherits the merit of application layer multicast and overcomes the instability of application layer multicast greatly improves the stability and reliability of multicast tree Key words application layer multicast multicast transmit tree backup parent node spare linker 1 引言 组播概念自诞生以来一直是互联网应用研究的热点 人们把它作为解决由单播通信方式 所带来的严重带宽浪费和效率低下等问题的一剂良药 1988 年 Steve Deering 首先提出了利 用路由器在网络层实现组播的思想 即 IP 组播 在这个模型中 路由器负责维护组播树 当数据包从数据源发出后 数据包在不同的树结点路由器上进行复制 最后到达每个接收终 端 在 IP 组播架构中 通过合并重复信息传输来有效地减少数据包的复制 降低带宽浪费 和提高服务效率 所以 IP 组播一直以来被认为是最有效的 但是 经过十多年的研究 IP 组播终因其涉及的技术领域复杂 对其监控管理过于复杂 服务和计费模式缺少市场驱动及 客户需求而没有象预期的那样被广泛地应用到 Internet 中 正是由于这个原因 近几年组 播研究的重点转移到了应用层 应用层组播的数据在端系统上复制并转发 不需要路由器保持组播组的状态 改由端系 统负责组播组成员的管理 解决了业务的扩展性问题 同时 应用层组播可以随时部署 不 需要网络设备的升级和更新 虽然应用层组播对带宽的浪费比IP组播严重 但开发 部署起 来简单方便 所以具有较好的应用前景 应用层组播从总体上来说分为单源组播和多源组播两种模式 本文提出了一个单源的组 播协议ALSSMP Application Layer Single Source Multicast Protocol 算法设计 该协议 支持的是大规模用户流媒体的应用 2 ALSSMP的框架设计和特点 ALSSMP协议继承了应用层组播的思想 没有路由器的参与 不需要任何的网络底层改变 就能实现比较有效的组播传输 在应用上限制条件也大大减少 ALSSMP协议是针对单源应用 层组播的协议 即在一个特定的组播组中同时只能有一个发送者 这样在一定程度上降低了 协议的复杂度 协议的实现过程得到了大大的简化 因此有较好的性能 组内成员是以树状拓 扑优先的方式组织在一起 在此协议中 每一个成员结点既是服务器又是客户端 每一个结 点都必须实现三个功能 接收数据流 实施回放 转发数据流 因为流媒体应用一般会持续很长时间 而且需要稳定的带宽 所以本协议算法在维护应 用层组播转发树的可靠性方面提出了新的见解 3 ALSSMP的主要算法设计 协议中每个结点都被逻辑地分为两个拓扑结构 控制拓扑结构和数据传输拓扑结构 拓 扑图上的每条边都相当于一条单播连线 控制拓扑主要用来在端系统间周期性的交换控制信 息来维护组播转发树 增强协议的可靠性 数据拓扑主要用来表明组播数据包的传输路径 此协议首先建立起一个共享的数据传输拓扑树 每个想加入的结点的首要任务就是找到 合适于自己的父结点 然后 增加一些成员间的控制信息便可组成控制拓扑 下面根据成员 结点参与组播的过程 对ALSSMP中的主要算法进行描述说明 3 1 结点加入组播组 加入组的成员必须以某种方式知道要加入组的根的IP地址 当有新成员加入时 此成员 会从某一个RIP Reserve Information Point 此点会保留从根结点 自己的父结点 所有 孩子及其他一些邻接点的成员信息 获得有关根结点的信息 然后经过一系列的请求连接 发送询问 回应等动作 最后根据协议规定的评价指标选择自己的父结点 当某一个组内成 员成为这个新成员的父结点时 此结点就成功加入了这个组播组 在成功选择父结点的同时 还要经过某些计算找出自己的 备用父结点 父结点选择算法的步骤如下 假设成员结点A收到了新加入者生成的查询报文 查询要加入组的根的有关信息 结点A收到这个查询报文后 根据自己掌握的信息查找到根的地址和根对QOS 如延时 带 宽等 的限制条件后 生成回复报文 把查询结果返回给新加入者 加入者得到根的地址后 生成queryfather报文 将报文发送到根 根收到queryfather报文后 查询它维护的邻接点的信息 找出孩子数小于度的所有孩子结 点作为 可能父结点 PF Possible Father 如果这一层没有就继续往下找 直到找出树 中所有的PF 然后生成creat回复报文 将 可能父结点 集合 SPF Set of Possible Father 以及根结点等有关信息返回给加入者 加入者根据根的回复报文返回的结果 向每个PF发出探测报文 探测沿直接路径从加入者 到它之间的延时和带宽等 每一个PF把回应报文发送给加入者 返回探测结果 加入者陆续收到这些PF的回应报文后 根据延时最小时取最大带宽的原则 选择自己的父结点 再通过有关算法找到一个组成员结 点作为这个新成员结点的 备用父结点 以备发生突发情况时能够完成树的重构 加入者确定自己的父结点后 向父结点发送Subscribe 报文 父结点收到报文后 将加入 者加入自己维护的孩子列表中 这样加入者也就被加入到转发树中 加入动作完成后 父结点向加入者发送suceedJoin报文 表示成功加入 在该算法中 父结点的选取范围是整棵组播树 为新成员选择合适的父结点必须满足两 个条件 如果选中某结点作为新成员的父结点 组播树拓扑图上应不会出现循环 如果选新 成员做其子结点不会超过其度的要求 如果新成员找到了多个合适的父结点 那么它将根据 具体实际量度的要求来找出最合适的一个父结点 同时还要利用有关算法找到另一个成员结 点作为这个新成员的 备用父结点 3 2 组播报文的传输和多媒体流的回放 当结点加入组播树后 就能够收到从根结点发送的数据了 数据源点的多媒体流经过采 集 编码等过程后生成组播报文 将报文沿直接路径发送至根 再由根沿组播转发树自顶向下 到达叶子结点 每个结点从其父结点处接收数据报文后 把它转发给其所有的子结点 直至 叶子结点 若某结点收到的数据报不是发自父结点的 则丢弃该数据报文 在每一个结点在 接收 发送数据流的同时 再把收到的组播数据还原成多媒体流回放出来 传输数据时根据 上层应用的不同可以选择采用TCP或者UDP 若上层为文件分发系统 则可以采用可靠的TCP 协议 若为音频 视频广播系统 则可采用开销较小的UDP协议 3 3 组播成员结点的主动退出和意外失效时组播树的维护 应用层组播转发树中 结点的主动退出和意外失效引起的树的断裂 是不可回避的问题 因此 需要一个有效的机制 能够在结点退出或者失效后 快速地重构整个转发树 将数据 丢失控制到最小的范围和时间内 组播转发树重构时有两种方式 即后向式和前向式 后向 式是在结点失效后 再进行树的重构 这种事后补救的方法会花去不少时间 并且还会丢失 数据 所以在本算法中采用的是前向式 proactive approach 即在结点失效之前预先计算 好结点的新的父结点 一旦该结点的父结点退出 就可以根据预先计算的值快速地找到新父 结点 避免花太多的时间用于寻找新加入点 从而减少数据的丢失 为转发树中每一个结点预先选择一个 备用父结点 一旦该结点的父结点失效退出 则 可以立即启用 备用父结点 备用父结点 的选择采用一种 链路预留 思想的 PCP Pre Calculation Parent algorithm 算法进行 PCP 算法描述如下 设要选择 备用父结点 的结点为 n p 为指向某个结点的指针 procedure PCP n 算法开始 参数为结点 n 代表要计算的结点 p n parent 首先将指针指向 n 的父结点 p while p siblings is null 如果 p 没有兄弟结点 则沿着树往上走 do p p parent 将 p 指向原结点的父结点 if p dp 0 then return p end if 判断 p 是否有兄弟结点 until p null 如果 p 有预留链路 则 p 就是要找的结点 算法结束 如果 p 没有预留链路 但是 p 有兄弟结点 则循环结束 否则 继续往上游走 如果一直没有合适的结点 会一 直到达根结点 循环结束 寻找兄弟结点的目的是 结点 n 的 备用父结点 是优先选择 除了父结点的祖先结点 其次选择祖先结点的兄弟结点 在高于 n 的上层结点中只有 n 的父结点不能充当 备用父结点 其它的祖先结点都可以充当 n 的 备用父结点 if p siblings null then no link provided exit 如果一直找至根结点还没有找到合适的 p 则结束寻找过程 返回 0 else add queue item q p siblings end if 如果找到了合适的 p 则将 p 的兄弟结点信息 写入一个队列 q 队列 q 中存放着候选结点的列表 n 可以以先进先出的次序从队列 q 中取出结点 进行比较和 选择 while q null do 开始从队列 q 中依次取出候选结点 p get queue item q 将 p 指向从队列中取出的结点 if p dp 0 then return p 如果结点 p 的预留链路还有 则 p 就是要找的结点 跳出循环 else add queue item q p children loop 否则 将结点 p 的子女结点加入队列 q 中 回到循环体的开始 继续循环 return 0 如果没有找到合适的结点 返回 0 end procedure 算法结束 在利用上述算法找到备用父结点后 如果某些结点突然离开或失效 会立即启用备用父 结点 不至于使组播树断裂或崩溃 起到了很好的维护和预防作用 建立预留链路的算法步骤描述如下 1 假设要选择 备用父结点 的结点为 n 通过 PCP 算法计算出作为 备用父结点 的 结点 p 2 结点 n 发送一个 JOIN 报文给结点 p 3 结点 p 收到以后 发送 ACCEPT REFUSE 报文给结点 n 告诉 n 是否同意建立预留 链路 4 结点 n 收到后 将自己 备用父结点 指向 p 然后发送 ACKNOWLEGMENT 报文 给结点 p 5 结点 p 收到确认报文后 再修改自己的相关信息 建立起到 n 的预留链路 6 算法结束 需要说明的是 在备用链路的维护上 采用如下方法 在某个结点通过 PCP 算法找到自己的备用父结点之后 就需要备用父结点过一定的时 间发送 keepalive 报文 来维持双方的联系 一旦结点在一定时间内收不到 keepalive 报文 就可以认为备用父结点已经失效 这样就会触发 PCP 算法再次运行 以寻找新的备用父结 点 根据以上两个算法 在组播树重构策略中 成员结点也能够收到预留链路转发过来的数 据报文 那么许多结点会同时收到两个同样的数据报文 这时结点可以把来自预留链路的报 文丢弃 一旦某结点的父结点退出或失效 结点会向备用父结点发送一个数据传输请求 然 后开始利用预留链路传输数据 这样组播报文就不会因为某些结点的离开而丢失 4 结束语 ALSSMP 协议已经在实验室十台以内的机器上实验过 结果表明在小范围内此协议表 现良好 在实验的同时 我们还对协议中采用的 PCP 算法和链路预留算法与其他的一些应 用层组播协议中采用的组播树的维护及容错机制进行了比较 比较的结果是采用 PCP 算法 后 尽管转发树的结点平均延迟略有增加 但在维护应用层组播转发树的可靠性方面要比其 他算法优越 算法思想简单 实现起来比较容易 每次加入一个新结点时 这个结点就可以 自行启动 PCP 算法来寻找一条备用链路 而不必受自己的后代结点的影响 树的控制拓扑 和数据传输拓扑构建起来清晰 自然 但 ALSSMP 在大规模机器上的测试还没有完成 因 为本协议的主要目的就是实现基于应用层组播的大规模直播视频系统 所以能否真正在 Int ernet 上实现 协议的正确性和表现等还需要进一步的测试和验证 本文的创新点在于 提出了一个基于应用层的单源组播协议 ALSSMP 在此协议中 提 出的为转发树中每一个结点预先选择一个 备用父结点 以设置预留链路思想的 PCP 算法 使 该协议既继承了应用层组播的优点 又在一定程度上克服了应用层组播的不稳定性的特点 使组播树的稳定性和可靠性大大提高 参考文献 1 李伟 沈长宁 应用层组播协议的研究 J 计算机工程与应用 2004 24 157 158 2 李珺晟 余镇危等 应用层组播综述 J 计算机应用研究 2004 11 14 17 3 章淼 徐明伟 吴建平 应用层组播研究综述 J 电子学报 2004 32 12A 22 23 4 Pendarakis D Shi S VermaD et al ALMI AnApplicationLevel Multicast Infrastructure A Proceedings of 3rd USENIX Symposium on Internet Technologies and Systems C 2001 5 BANERJEE S BHATTACHARJEE B Ana