一个基于应用层的单源组播协议设计
朱坤华
(河南科技学院 计算机科学系，河南 新乡 453003）
摘 要：由于IP组播在实现过程中遭遇了很多困难，所以应用层组播就成了Internet应用研究的热点。本文在简单地论述了应用层组播的优缺点后，提出了一个基于应用层的单源组播协议ALSSMP。此协议设计的目的是能够实现大规模直播视频。在ALSSMP中采用树拓扑优先的方法来构造组播转发树。在组播树的维护方面，利用为转发树中每一个结点预先选择一个“备用父结点”以设置预留链路思想的PCP算法。该协议既继承了应用层组播的优点，又在一定程度上克服了应用层组播的不稳定性的特点，使组播树的稳定性和可靠性大大提高。
关键词：应用层组播；组播转发树；备用父结点；链路预留 中图分类号：TP393 文献标识码：A
Design 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. Analysis of the N ICE Application Layer Multicast Protocol[R ]. Technical report, UMIACSTR 2002260 and CS2TR 4380, Department of Computer Science University of Maryland, College Park, June 2002.
[6] 张金平，马旭东等.智能楼宇系统中的软件化网络视频监控服务器[J].微计算机信息，2004，20（11）:145.
[7] Suman Banerjee,Bobby Bhattacharjee,Christopher Kommareddy.Scalable Applicati- on Layer Multicast[C].In:ACM Sigcomm,2002-08
作者简介：
朱坤华，女，1974年9月出生，汉族，河南方城县人，讲师，硕士，计算机专业，现在主要从事计算机专业的教学和研究工作，主要研究方向：组播协议、计算机网络安全. e-mail: zwkh100@163.com
Author brief introduction:
ZHU kun-hua,female,1974.9, the Han nationality, Henan Province Fangcheng County person, instructor,the master,is mainly engaged in the teaching and study of computer network,the way of mostly studying:multicast protocal，computer network security
