基于不定叉树的应用层组播协议
摘 要 本文提出了一个适合小规模、低时延，基于不定叉树的 应用 层组播协议，重点讲
述了协议的设计思想、节点故障修补算法和性能优化 方法 。协议已被成功应用到一个视
频会议系统中，结果表明，这样的一个协议能很好的适应 目前 Internet 上小规模多媒体应
用层组播系统。 关键词 应用层组播；不定叉树；源指定树；路由树调整 1 概述 自
应用层组播的概念提出以来，已有很多各具特点的解决方案被提出。各个不同的应用层组
播系统具有不同的设计目标及系统结构。如，ESM(End-System Multicast)[1]和 ALMI[2]适
合时延要求不高的小规模多对多通信，而 Scattercast[3]和 Overcasts[4]则支持大规模的数
据递送系统。在系统结构方面，根据建立应用层组播拓扑结构时采用的方案，将这些系统
分为两种：网优先(Mesh First)和树优先(Tree First)，网优先的系统会首先为覆盖节点建立
一个网状的拓扑结构，然后按照某种路由协议来生成数据路由树，如 ESM 的 Narada 协议
，会先构建一个网，然后通过修改后的 DVMRP 协议完成路由树的生成；而树优先的系统
则是直接建立数据路由树，ALMI、 Overcast、 Host Multicastis[5]均属于这种系统。一般
来说，网优先的系统稳定性更好，不会形成回路，树优先的系统则在效率上占优势。 在
多源的应用层组播方案中，根据数据路由树的使用和维持，可以分为 Shared Tree 和
Source-specific Tree 两种。Shared Tree，就是所有的源使用同一棵树；Source-specific
Tree，就是每个源维持一棵树，前者不能保证每个源都能获得较好的传输延迟。 本协议
根据视频会议系统的应用特点，采用效率较高的树优先的拓扑结构，使用 Source-specific
Tree 数据路由树策略。树的生成、维持由根(源)负责，集中点(RP)不参与，这点类似 Host
Multicast 的做法，Host Multicast 是分布的方式，每个组的数据路由树都有一个根节点，
每个新的组成员加入时，都要从该根节点开始依次协商，直到找到一个距离最近的节点为
止。2 基于不定叉树的应用层组播协议 协议设计思想 我们的思路是，建立一个全
分布的，支持多组、多源，低时延的，基于不定叉源指定树(Source-specific Tree)的 Tree-
First 应用层组播协议平台。 由于目前 Internet 终端多数是以 xDSL 方式接入的，考虑到
这些终端具有的极限带宽是上传 512kbps(部分是 1Mbps)，下载 5Mbps(其余接入方式的
终端一般具有更高的带宽)，假定每个源每秒产生的实时数据流量为 150kbps(如视频会议)
，按照 90%极限上传带宽的可利用率，一个节点可以为 3 个节点实现分发任务；再假定组
的规模控制在 100 个节点内，如果按照三叉树的组织结构，这样的树将不超过 4 层，经
过 4 个节点的转发，其时延基本可以控制在 5 秒内。 基于以上的假设，我们将在组应
用开始前建立 n 棵 Source-specific Tree，n 等于组的节点数，每个节点负责生成一棵以它
为根的满三叉树。我们又知道，有的节点的上传能力可能不到 3 个，有的节点则可能超过
3 个，而且这种能力可能是变动的。由此，这些树必须根据 网络 的实际状态进行调整，
节点的分发孩子个数视其能力变动而定，分发能力的判断，则通过孩子节点反馈 RTCP 信
息包来 计算 丢包率。也就是说，满三叉树在应用预运行或运行后成为动态调整的不定叉
树。 节点加入 节点必须清楚自己属于哪个组，然后加入到合适的组中。 RP(集中
点)为节点提供加入服务。任一个节点加入时，必须向 RP 报到，RP 将新节点加入到组的
节点列表中，然后将已加入的节点列表发给新节点，同时，向所有节点通告单个节点加入
消息。 满三叉树的生成 “距离”与“距离”计算 节点一旦成功加入，马上与列表
中的同组节点通信，估算节点之间的“距离”。所谓的“距离”，指的是节点间的传输延迟和
带宽加权后的值，我们采取简单做法，就是测试 1K UDP 包来回所需的时间。我们采取如
下算法计算 NodeA 和 NodeB 节点间的“距离”：TimeAS= Current Time of NodeANodeA
Send 1K bytes to NodeB by UDP with TimeASNodeB Recvive packet from NodeA TimeBR=
Time when NodeB Recvives the packetTimeBS= Current Time of NodeBNodeB Send 1K
bytes to A by UDP with TimeAS, TimeBR and TimeBS Node A Recvive packet from
NodeBTimeAR= Time when NodeA Recvives the packetDistanceAB=TimeAR- TimeAS-
(TimeBS -TimeBR) 树生成 开始时，每个源生成一棵不超过 4 层(源，即根，为 0
层)的满三叉数据路由树，树的生成依据这样的原则，在树中，离源较近的节点与源有更
近的“距离”，而第 2 层的节点即与其第 1 层的父亲节点有更近的“距离” ，依此类推。 首
先，根选择 3 个最合适的节点作为它的第一层子节点，然后，根分别通知这 3 个子节点，
去寻找它们合适的孩子节点，过程不断重复，直到所有的节点都加入到树中。树的生成是
由覆盖网中的所有节点协同完成的，因此其生成算法是分布的，算法如下：
OnRecEiveCreateTree (void *packet){ //根收到建树命令,每个节点都需要生成一棵以其为
根的树 按”距离”大小选择 3 个孩子节点; 向选择好的节点发送邀请其成为我的孩子节
点的请求包(以’我’为根的树);}OnRecEIveInviteTobeChildReq(void * packet){//收到 i 邀请为
其孩子的请求(j 为根的树) if(我还没加入到以 j 为根的树)发送接受邀请的回应包; else
发送拒绝邀请的回应包;}OnReceiveToBeChildReply(void * packet){//收到节点 i 对我邀请
的回应(j 为根的树)if(i 接受我的邀请){ 将 i 置为 以 j 为根的树中的’我’的孩子; 将 i 加入到
本地以 j 为根的树已入树节点列表; if(我是 j)修改树结构;//根维持整棵树的结构描述,树生
成后,分发给所有孩子}else { 将 i 加入到本地在建以 j 为根的树中拒绝我的节点列表; if(
重新选择一个节点成功) 向被选择的节点发送邀请其成为我的孩子节点的请求包(以 j 为
根的树);}if( (孩子数==3 ) || (已入树节点数+拒绝我的节点数==组节点数)){// 以 j 为根的树
if((我是 j){ 将孩子节点列表打包; 向被选中的孩子节点发送选择孩子的命令; }else
将孩子节点列表打包,发送给根; } }OnReceiveSelectChildrenOrder(void * packet){//
收到根的选择孩子节点的命令 将包中已入树的节点列表复制到本地; for(int i=0;
i<3;i++){ if(选择一个节点成功)向其发送邀请其成为孩子的请求; else break; }}
树生成的算法是由分布在网络上的多个节点机共同执行的，为避免多个节点同时选择一
个节点为其孩子，因此，我们采用了应答制。 性能优化--不定叉树的调整 前面讲到
，在生成树时，并没有过多考虑树的上传能力，只是基于经验及网络的一般现状，假设每
节点有能力完成对 3 个节点的视音频数据转发。但，实际情况可能是，有的节点的分发能
力超过 3，有的节点则不足 3。这样，在应用预运行后，必须尽快对树进行调整。
