基于不定叉树的应用层组播协议

1、基于不定叉树的应用层组播协议摘要本文提出了一个合适小规模、低时延，基于不定叉树的应用层组播协议，重点讲述了协议的设计思想、节点故障修补算法和性能优化方法。协议已被成功应用到一个视频会议系统中，结果说明，这样的一个协议能很好的适应目前Internet上小规模多媒体应用层组播系统。关键词应用层组播；不定叉树；源指定树；路由树调整自应用层组播的概念提出以来，已有很多各具特点的解决方案被提出。各个不同的应用层组播系统具有不同的设计目的及系统构造。如，ES(End-Systeultiast)1和ALI2合适时延要求不高的小规模多对多通信，而Satterast3和verasts4那么支持大规模的数据递送系

2、统。在系统构造方面，根据建立应用层组播拓扑构造时采用的方案，将这些系统分为两种：网优先(eshFirst)和树优先(TreeFirst)，网优先的系统会首先为覆盖节点建立一个网状的拓扑构造，然后按照某种路由协议来生成数据路由树，如ES的Narada协议，会先构建一个网，然后通过修改后的DVRP协议完成路由树的生成；而树优先的系统那么是直接建立数据路由树，ALI、verast、Hstultiastis5均属于这种系统。一般来说，网优先的系统稳定性更好，不会形成回路，树优先的系统那么在效率上占优势。在多源的应用层组播方案中，根据数据路由树的使用和维持，可以分为SharedTree和Sure-spe

3、ifiTree两种。SharedTree，就是所有的源使用同一棵树；Sure-speifiTree，就是每个源维持一棵树，前者不能保证每个源都能获得较好的传输延迟。本协议根据视频会议系统的应用特点，采用效率较高的树优先的拓扑构造，使用Sure-speifiTree数据路由树策略。树的生成、维持由根(源)负责，集中点(RP)不参与，这点类似Hstultiast的做法，Hstultiast是分布的方式，每个组的数据路由树都有一个根节点，每个新的组成员参加时，都要从该根节点开场依次协商，直到找到一个间隔 最近的节点为止。2.1协议设计思想我们的思路是，建立一个全分布的，支持多组、多源，低时延的，基于

4、不定叉源指定树(Sure-speifiTree)的Tree-First应用层组播协议平台。由于目前Internet终端多数是以xDSL方式接入的，考虑到这些终端具有的极限带宽是上传512kbps(部分是1bps)，下载5bps(其余接入方式的终端一般具有更高的带宽)，假定每个源每秒产生的实时数据流量为150kbps(如视频会议)，按照90%极限上传带宽的可利用率，一个节点可以为3个节点实现分发任务；再假定组的规模控制在100个节点内，假如按照三叉树的组织构造，这样的树将不超过4层，经过4个节点的转发，其时延根本可以控制在5秒内。基于以上的假设，我们将在组应用开场前建立n棵Sure-speifi

5、Tree，n等于组的节点数，每个节点负责生成一棵以它为根的满三叉树。我们又知道，有的节点的上传才能可能不到3个，有的节点那么可能超过3个，而且这种才能可能是变动的。由此，这些树必须根据网络的实际状态进展调整，节点的分发孩子个数视其才能变动而定，分发才能的判断，那么通过孩子节点反应RTP信息包来计算丢包率。也就是说，满三叉树在应用预运行或运行后成为动态调整的不定叉树。2.2节点参加节点必须清楚自己属于哪个组，然后参加到适宜的组中。RP(集中点)为节点提供参加效劳。任一个节点参加时，必须向RP报到，RP将新节点参加到组的节点列表中，然后将已参加的节点列表发给新节点，同时，向所有节点通告单个节点参加

6、消息。2.3满三叉树的生成2.3.1“间隔 与“间隔 计算节点一旦成功参加，马上与列表中的同组节点通信，估算节点之间的“间隔 。所谓的“间隔 ，指的是节点间的传输延迟和带宽加权后的值，我们采取简单做法，就是测试1KUDP包来回所需的时间。我们采取如下算法计算NdeA和NdeB节点间的“间隔 ：TieAS=urrentTiefNdeANdeASend1KbytestNdeBbyUDPithTieASNdeBRevivepaketfrNdeATieBR=TiehenNdeBRevivesthepaketTieBS=urrentTiefNdeBNdeBSend1KbytestAbyUDPithTie

7、AS,TieBRandTieBSNdeARevivepaketfrNdeBTieAR=TiehenNdeARevivesthepaketDistaneAB=TieAR-TieAS-(TieBS-TieBR)2.3.2树生成开场时，每个源生成一棵不超过4层(源，即根，为0层)的满三叉数据路由树，树的生成根据这样的原那么，在树中，离源较近的节点与源有更近的“间隔 ，而第2层的节点即与其第1层的父亲节点有更近的“间隔 ，依此类推。首先，根选择3个最适宜的节点作为它的第一层子节点，然后，根分别通知这3个子节点，去寻找它们适宜的孩子节点，过程不断重复，直到所有的节点都参加到树中。树的生成是由覆盖网中的所

8、有节点协同完成的，因此其生成算法是分布的，算法如下：nReEivereateTree(vid*paket)/根收到建树命令,每个节点都需要生成一棵以其为根的树按间隔 大小选择3个孩子节点;向选择好的节点发送邀请其成为我的孩子节点的恳求包(以我为根的树);nReeiveInviteTbehildReq(vid*paket)/收到i邀请为其孩子的恳求(j为根的树)if(我还没参加到以j为根的树)发送承受邀请的回应包;else发送回绝邀请的回应包;nReeiveTBehildReply(vid*paket)/收到节点i对我邀请的回应(j为根的树)if(i承受我的邀请)将i置为以j为根的树中的我的孩子

9、;将i参加到本地以j为根的树已入树节点列表;if(我是j)修改树构造;/根维持整棵树的构造描绘,树生成后,分发给所有孩子else将i参加到本地在建以j为根的树中回绝我的节点列表;if(重新选择一个节点成功)向被选择的节点发送邀请其成为我的孩子节点的恳求包(以j为根的树);if(孩子数=3)|(已入树节点数+回绝我的节点数=组节点数)/以j为根的树if(我是j)将孩子节点列表打包;向被选中的孩子节点发送选择孩子的命令;else将孩子节点列表打包,发送给根;nReeiveSelethildrenrder(vid*paket)/收到根的选择孩子节点的命令将包中已入树的节点列表复制到本地;fr(int

10、i=0;i3;i+)if(选择一个节点成功)向其发送邀请其成为孩子的恳求;elsebreak;树生成的算法是由分布在网络上的多个节点机共同执行的，为防止多个节点同时选择一个节点为其孩子，因此，我们采用了应答制。2.4性能优化-不定叉树的调整前面讲到，在生成树时，并没有过多考虑树的上传才能，只是基于经历及网络的一般现状，假设每节点有才能完成对3个节点的视音频数据转发。但，实际情况可能是，有的节点的分发才能超过3，有的节点那么缺乏3。这样，在应用预运行后，必须尽快对树进展调整。我们使用UDP协议进展应用数据的传输，父亲在向孩子节点发送应用数据包时，统计单位时间已向孩子节点发送了多少数据包，每隔3秒

11、钟，孩子节点向父亲发送一个RTP包，告诉父亲，最近3秒，已接收其发送的数据包数量，父亲节点据此计算单链路的丢包率，并根据所有链路的丢包率，结合帧率，估算其带宽，然后通告带宽。为将问题简单化，并基于Internet现状(xDSL节点是上传才能缺乏，非下载才能缺乏)，我们规定，当一定时间内，丢包率超过一定程度时，总假定是父亲节点上传才能缺乏。当父亲节点认为其上传才能缺乏时，希望移交孩子节点，父亲节点会选择带宽较高的节点发送移交恳求。收到移交恳求的节点检查其自身上传才能，回应承受恳求或不承受恳求，发送移交恳求的节点会一直尝试，直到有节点同意移交，此外，上传才能缺乏的节点可以启用选帧，降低对带宽的需求

12、，这属于应用层QS的任务，不在这里详述。目前多数的AL协议，对底层网络变动的适应普遍采取整体变动的方法，这样的代价相当大，如NARADA，节点状态的变化将导致网esh的重构，从而导致所有sure-speifiTree的重构，这个过程需要较长的收敛时间。我们采取部分变化的对策以适应verlayNetrk的变化。图1节点转移实现优化2.5树的修补有边相连的节点，互相为邻居。节点每3秒钟向邻居发送“心跳信息。“心跳信息可以简单到是一个不断增长的序列号。当节点在30秒钟收不到邻居的“心跳信息后，节点认为邻居已经出现故障。故障处理：1).为防止多个节点同时尝试修补树，我们规定，只允许上层节点对下层节点进

13、展修补。假如根节点故障，树的修补失去意义。2).后备选择从故障节点的最左边的子孙节点逐级往上提升，最左的节点不存在，那么往右选择。3).叶子节点故障将不修补。4).树修补算法如图2:i发现其儿子节点j故障后,执行如下算法:1.向组内所有节点通告j的故障2.j是叶子节点吗?2.1是，算法完毕2.2否，转33.j有适宜的孩子吗？3.1有，转43.2没有，算法完毕4.选择适宜的孩子，向其发送接替j的通知5.T:=j图2树的修补任何节点k收到l发送给自己，要求自己接替节点j的通知，执行如下算法：1.k是否叶子1.1是，向l发送jk、k0的通知1.2否，选择适宜的儿子，向其发送接替k的通知，T:=j,T

14、1:=l任何节点k收到确认接替的通知，执行如下算法：1.接替串的第一个节点是自己吗？1.1是，接替串:=Tk+接替串，向T1发送接替串1.2否，根据接替串交换树，将新树向所有节点发送本协议合适小规模、时延要求高的应用层组播系统，我们在协议的根底上开发了一个视频会议系统，经试验，在网络状态变动不是太频繁的前提下，系统能很好工作。协议对很多复杂问题做了简化，这些简化对协议的实现带来很大的便利，但同时也使得协议的适应才能存在着一定的问题，我们将在树的优化、修补上进展改造，以使得协议具有更广阔的适应才能。1huY,RaS,ZhangH.AasefrEndSysteultiast.ASIGETRIS,20002PendarakisD.ALI:AnAppliatinLevelu