信息通信专业资料 基于拓扑结构的应用层组播综述（WORD版）

1、基于拓扑结构的应用层组播综述一、应用层组播的提出20世纪80年代末90年代初 Deering提出了IP组播的概念1。在IP组播中，与组播相关的功能都放在IP层即由路由器来实现。路由器负责记录组的存在和组成员的变化，并在组成员之间构造一棵组播发送树。数据源只需要向组内发送一份组播数据，由路由器在恰当的分支点复制数据，就可以让所有组成员收到数据。而任何一份数据包的拷贝只会在每个组播树的链路上出现一次。由于IP组播能够有效地利用网络资源并降低服务器的负荷，因此它被认为是解决组内通信的最理想的方式。然而到目前为止，经过十多年的研究，虽然IP组播在实验系统上比如Mbone,Internet2上得到了应用

2、，但是一直没有进入商业领域。概括地说，主要是由以下原因造成的。第一，IP组播需要路由器的支持，每个组播路由器需要为每个组地址甚至组播业务源保存组状态。由于组地址是动态分配的，不能够像单播地址那样得到有效会聚，需要路由器内保存大量组状态，这增加了路由器的开销和实现的复杂性。第二，IP组播目前缺乏有效的可靠传输和拥塞控制机制，对拥塞不响应的组播流会对正常的单播业务流造成伤害，组播的拥塞控制机制非常难解决，因此在没有可靠的拥塞控制机制以前，ISP不会在它们的网络中大规模配置组播业务。第三，目前还缺乏对组播流的合理的收费模型。以上几个原因导致了IP组播迟迟得不到大规模的应用。Simple Multic

3、ast,Express和Source Specific Multicast针对IP组播存在的问题进行了一些改进，简化了多播发送的地址分配和接入控制，但是大规模运行这些协议需要大规模改动目前的网络基础设施，并且同IP组播一样，这些组播方式对路由器有很大依赖2。应用层组播就是为解决上述问题出现的,应用层组播将对组播功能的支持从路由器转移到终端系统,在终端之间运用原来的单播方式进行传输,也就是说将数据的路由、复制和转发功能由成员主机完成，成员主机间建立一个叠加在IP网络之上的，实现组播业务的功能性网络。这样不必改变原有网络中基础设施,也不需要路由器维护组播组的路由表,可以比较容易地实现组播,加速了应

4、用。图1.1是应用层组播网的结构模型。图1.1应用层组播网模型应用层组播的基本思想和它与IP组播的对比可以用图1.2来说明。应用层组播树也需要在组成员之间建立一颗组播分发树。然而与IP组播不同的是应用层组播树中的分叉点必须是终端系统，也就是说组播数据的复制是在终端系统中实现的。从图1.2(b)可以看到在某些链路上如A-1同一份组播数据被发送了两次，而且从源到目的节点如A-C所经过的路径长度也大于IP组播中相同组成员所经历的路径长度。可见，应用层组播在网络资源的使用效率上不如IP组播。然而应用层组播的好处体现在首先它不需要路由器的支持，其次由于任何两个组成员之间在发送或接收数据时都可以使用单播流

5、量控制和差错控制协议，从而简化了IP组播繁杂的拥塞控制机制。因此应用层组播更有可能成为组播的实现方式。图1.2a IP组播示意图 图1.2b 应用层组播示意图二、应用层组播算法的分类3应用层组播协议在把组成员组织在一起时，在它们之间构造了两个拓扑即控制拓扑和数据拓扑。其中数据拓扑实际上就是一颗组播分发树，它定义了数据在组成员之间分发的路径。而控制拓扑则是一个网状结构，它的目的在于增加组成员之间的连通性以及健壮性。控制拓扑上互为邻居的对等点相互之间周期性的交换信息以识别组成员的动态变化(或者是主动离开，或者是意外崩溃)并恢复受到影响的数据拓扑。换句话说，控制拓扑起到了保护数据拓扑的作用。根据构建

6、控制拓扑和数据拓扑的顺序，我们可以把应用层组播协议采用的策略分为以下几类:基于Mesh优先的策略、基于树优先的策略和基于隐含组播转发拓扑结构的策略。在基于Mesh优先的策略中，组成员首先分布式地构造一个应用层的叠加网络，建立一个控制拓扑，在控制拓扑上成员与成员之间可以存在多条可达路径。每个成员都要参加分布式的路由协议，计算自己到其它节点的转发路径。在建立的控制拓扑上每个组成员随后再通过反向路径转发协议(RPF)构造从数据源到每个组成员的组播分发树，也就是数据拓扑。其代表性协议有Narada,Scattercast和Kudos等。所谓的叠加网络（也叫覆盖网络）其实就是位于应用层的主机自己构成的一

7、个实现特定功能的逻辑网络。叠加网络在现有的Internet传输网络之上构建一个完全位于应用层的网络系统，拓扑发现、路由等功能完全由应用层自己完成，不依赖网络层，是基于Internet网络的大规模的分布式应用技术。基于树优先的方式与网状优先恰好相反，组成员首先在它们之间构造组播分发树，随后每个组成员再通过相互之间交换信息发现其他非邻居成员，并建立与这些非邻居成员的连接，从而构造控制拓扑。这类协议主要有Yoid, Host Multicast, ALMI, Switch-trees等。隐含方式构造的控制拓扑需要满足一定的属性。数据的转发路径通过一定的分组转发规则隐含定义在这个控制拓扑中.也就是说隐

8、含方式在构建控制拓扑的同时也就同时定义了数据拓扑。代表协议有NICE, CAN-Multicast, Scribe等。本文从应用层组播树构成的拓扑结构入手，对每种策略选取了若干协议对其拓扑结构建立过程进行了比较详细地阐述。三、协议介绍1.基于Mesh优先的策略1.1 End System Multicast（ESM）12端系统组播(End System Multicast)是由卡耐基梅隆大学提出的一种应用层组播方案，也是最早提出的应用层组播方案之一。它的目的是采用应用层组播技术使Internet上的中小规模的交互式会议应用能够进一步实用化。端系统组播的核心是Narada协议。终端组播（End

9、System Multicast）利用终端来处理与功能相关的组播，如成员组织（membership management），包的复制等，这种支持从路由器到终端的组播存在潜在的解决IP组播问题的可能，关键存在模型方面的性能缺陷，尤其是终端组播要在物理链路上复制包，这导致了比IP组播更大的端到端的延迟。NARADA 思想它是基于以下思想来设计的l 自组织终端系统重叠网结构必须是全分布的方式,并且对组成员的动态变化具有鲁棒性l 重叠效率组织的树必须在网络和应用两方面都是有效的,从网络方面看,构造的重叠网必须确保在物理链路层上的冗余传输是最小的,但是不同的用户需求的重叠网具有不同的效率,交互式应用如音

10、频会议等需要较低的延迟,而视频会议等需要较大的带宽和较低的延迟;l 自我改善重叠网络应该具有随着网络不断收集信息而不断升级的机制,协议能够允许网络通过不断收集信息来促使其结构不断完善;阿l 适应网络动态性重叠网必须能够适应网络路径特征的长期变化(如带宽和延迟), 对这些测量的量发生错误时要有弹性;Mesh网的构建按照以下两个步骤来构造树.首先 构造一个网并且使这个网具有所要讨论的特性其次 Narada网的生成树,树的根为用通用算法所得到的对应的数据源节点 图3.1中ABCD 4个节点构成了Mesh网，而带箭头的虚线表示以A节点为根节点的一棵生成树。图3.1Narada采用基于Mesh网的策略主

11、要是为了更好地支持多个数据源的组播应用。单个共享树对中心点的故障比较敏感,并且不能使单个数据源最优化,相反Mesh可以使我们构造的树达到单个数据源的最优化,使我们对组的作用的管理更加抽象而不是通过组播树他们进行复制.在Narada中，数据转发树完全基于Mesh中的overlay链路构造，因此为了获得一个高质量的转发树，首先要构建一个高质量的Mesh网。高质量的Mesh网主要有以下两个特性：首先是任意成员节点对之间的路径质量应该与该节点对的单播路径质量相近，例如延时和带宽；另一个是每个成员节点应该具有有限的邻居节点数。Narada中的组管理 由于Narada的设计目标是不依赖于某个特定节点进行组

12、维护，因此组维护的任务就需要各个节点共同承担，在Narada中，每个节点都维护所有其它节点的信息。通过交换信息来获取其他成员的信息的位置，每个节点随机选择一些节点作为自己的邻居，邻居节点之间通过交换更新消息来维护信息mesh。l 成员加入当一个成员要加入组时，Narada假设该成员通过某种机制获取了其他成员的一个表，这个表并不需要很完善或很准确，只需要包含当前至少一个活动的组成员。要加入的成员随机选择一些组成员，并向他们发出请求作为邻居加入的消息。重复这个过程直到获得响应。接点成功加入后，它就可以通过其邻居接点来更新消息。l 成员离开或出现故障当一个成员离开组时，它向其邻居通报，并且通过网向其

13、他成员通报。当出现突然故障时，故障也能被正确检测出来并向其他成员通报。本文采取一种失败停止模型（fail-stop）。如图3.2，假设成员C死亡，他在MESH中的邻居A，G通过他来获得更新消息。A和G独立的发送多余的探测消息给C，这种消息丢失的概率非常小，如果A，G没有从C中获得响应，就认为C已经死亡，并通过MESH向其他成员通报。 图3.2l 修复分割节点维护一个超时节点队列，队列中是经过Tm时间仍然没有收到更新消息的节点节点将采用某种基于概率的策略，周期性地从队列头部取出一个节点并对该节点进行探测，探测的结果或者是该节点已经失效，或者是发现了一个分割检测到一个节点分割后，在被分割的两个节点

14、之间加入一条链路。MESH性能 构造的MESH可能不是最优的l 新节点加入Mesh时并没有考虑网络拓扑结构信息l 分割修复过程可能会同时增加多条不必要的链路l 组成员不断地发生动态变化l 底层网络条件，包括路由负载情况等也在不断发生变化根据网络状况进行性能优化l 根据网络状况动态的增加和删除MESH中的节点l 如果某链路利用率太低则删除，如果负荷过重则增加链路；Utility of a link算法Utility = 0For each member m (m not i) beginCL = current latency between i and m along meshNL = new

15、 latency between i and m along mesh if edge i-j were addedIf (NL < CL) then beginutility += ( CL NL) / CLEndEndReturn utility增加链路的过程l 每个节点周期性的选择不是自己的邻居节点进行探测，并对每个节点增加一条链路的效用进行评估l 当I探测到J时，J返回给I他的路由表，I利用这些信息计算如果在J之间增加一条链路，效用的增加值。l 如果增加一条链路效用的增加值超过某个阈值，则增加一条链路。这个阈值的选取依赖网的规模和I，J邻居节点数目l 还有其他某些特殊的增加链路的

16、原因，例如当重叠网要求延迟达到最优，IJ之间的物理延迟可能很底但是重叠延迟很高，IJ之间也需要增加链路 Cost of a link 算法Cost i-j = number of members for which i uses j as next hopt for forwarding packets. Cost j-i = number of members for which j uses i as next hop for forwarding packets.Cost = max(cost i-j, cost j-i)删除链路过程l 每个节点都周期性的计算与其邻居节点之间的COST，

17、（I，J之间的COST是指I以J作为下一跳所经过的成员数目）l 所计算的COST如果底于某个阈值就将这个节点丢掉。阈值的选取是按照组的规模和邻居节点的数目计算的。l 节点的丢掉还要考虑稳定性（Stability）和避免网络分割（Partition Avoidance）1.2Topology-Aware Hierachical Arrangement Graph（THAG）9THAG算法的基本思想是构造节点不重合（node-disjoint）的多树结构（表示从原到接收端的任意路径都没有重复的节点），以增加路径多样性。将传输内容分为多个部分，沿着不同的树进行传播。在THAG中，参与者将组成一些小的

18、AG，在每个AG中，嵌入了若干互不相关的组播树。然后将这些AG组成类似于树的层次结构。AG和树的构造：AG是一个规则的互联拓扑结构。在数学上，AG可以表示为，1kn-1，用表示从1,2，n中取k个值的排列数，表示为X=x1x2xk。定义为一个无向图，其中：图3.3 一个的拓扑图3.3表示了一个的拓扑。在一个中，共有n(n-1)个节点，以坐标(i,j)标记。任意两个坐标中只有一个数字不同的节点相互连接，则在中，每个节点的度为2(n-2)。AG表现出了顶点对称性和边对称性。在该算法中使用了作为组播节点的结构单元。在中最多有n-2个无关树，即每个节点最多只在一棵树中作为中间节点。AG拓扑有如下特点：

19、（1）无关树可以嵌入AG。每个节点在局部决定它在所有树中的父节点，所有父节点都是AG拓扑结构中的邻居节点；（2）除了两个全叶子节点，几乎所有节点都是中间节点；（3）AG是一个规则拓扑，节点可以在3跳内访问任何节点；（4）AG有弹性。如果一个节点离开，它的邻居可以发现，并在此位置建立一个虚拟节点。虚拟节点可以在以后被一个活动节点代替。AG的层次结构：由于AG的尺寸太小，因此需要将AG按层次结构连接。在父AG中选出节点作为子AG的源即可完成层次连接（见图3.4）。由于在父AG中作为某组播树T中间节点的节点为子AG中组播树T的源，因此仍然能保证多播树的无关性。AG中树间的切换：如果用来传递内容的树（

20、称为传递树）个数为s(s<n-2)，则有n-2-s棵树未被利用（称为未传递树）。这些未传递树可在中间节点离开时作为临时可选路径，以增强可靠性。当一个节点无法通过传递树的父节点收到数据时，它向一个未传递树的父节点请求该数据，这样，数据传递可以部分地切换到未传递树。节点加入：节点加入的基本思路是新节点沿着AG树自顶向下反复与AG入口通信。若当前AG没有填满，则接受新节点，并分配一个虚拟节点的位置给它。若AG已满，则入口将决定是否将一个已有节点进行替换。新节点或被替换节点则沿着AG树向下重复此过程，直到最终加入。1.3 ZIGZAG8ZIGZAG算法将接收节点组织为层次化的尺寸有限的集群（cl

21、uster），并在其上构建组播树。管理系统组织（控制拓扑）：一个管理系统的组织用来管理当前系统中的参与者。参与者按照一个多层的层次化集群结构进行组织，集群的递归定义如下：（1）第0层包含所有节点。（2）在j<H-1层的节点分入尺寸在k,3k的集群，在第H-1层（最高层）只有一个尺寸为2,3k的集群。（3）在j<H层的每一个集群选一个头节点。该头节点成为第j+1的成员。服务器S为其所属的所有集群的头节点。在以上的结构中H=(logkN)，N为所有节点的数目。并且，对于任何j>0的层中的节点，它一定是更低一层的所属集群的头节点。组播树：于NICE不同，在ZIGZAG中，控制拓扑并

22、不能表现数据传输的拓扑结构。在ZIGZAG中，节点的加入、离开、优化必须遵守一下规则：（1）一个节点除了在它的最高层，不能有任何连入或连出的连接。（2）一个在其最高层的节点，只能连接到它的相异下属节点（foreign subordinates，表示最该节点高层集群中的某同伴在低一层的下属节点）。只有服务器例外，它在最高层连接它的每个下属节点。（3）在j<H-1层，每个非头节点的成员不能从它们的头节点处得到内容，必须从相异头节点（foreign head，表示头节点在高一层集群中的同伴）处获得。图3.6 ZIGZAG的组播树控制协议：每个节点X都周期性地与最高层集群的同伴，组播树中的父节点

23、和子节点通信。对于同一集群的节点，交换信息为节点的度，当接收方为头节点时，X也发送一个列表L = X1, d1, X2, d2, .，Xi, di表示X转发内容到Xi的di个下属节点。若接收方为父节点，则发送一下信息：（1）Addable(X)：为真表示在组播树中存在从X到第0层的一个尺寸在k,3k-1的集群的路径；（2）Reachable(X)：为真表示在组播树中存在从X到第0层的一个节点的路径。节点加入：新客户P向服务器提交一个请求。若控制拓扑只有一层，则P直接与服务器相连，否则，加入请求沿着组播树向下传递，直到找到一个合适的节点加入。当节点X收到加入请求后，进行如下操作：（其中D(Y)表

24、示从服务器到节点Y的端到端延时；d(Y,P)表示Y到P的延时）If X为叶子节点将P加入X的集群将P作为X的父节点的新子节点ElseIf Addable(X)选择一个子节点YAddable(Y ) 并且 D(Y )+d(Y , P)最小转发加入请求到YElse选择一个子节点YReachable(Y ) 并且 D(Y )+d(Y , P)最小转发加入请求到Y当新节点加入后，若集群的尺寸超过了3k，则需要进行拆分。节点离开：若一个节点X离开，由于控制协议，使得X的父节点和子节点，和所有同一集群的节点都能发现。X的父节点将删除到X的连接。若X的最高层j>0，对于j-1层X的子节点所在集群，头节

25、点Y将在j层的集群同伴中为它们寻找一个度最小的节点Z作为它们新的父节点。并且，由于X为0j-1层集群的头节点，需要从第0层的X的下属中随机选出一个节点X替代X的位置，并且X出现在第j层接受X的父节点的连接。当节点离开使得集群尺寸过小时，还须与别的集群进行聚合。2. 基于树优先的策略2.1 Host Multicast Tree Protocol（HMTP）13University of California和University of Michigan提出结构在Host Multicast中，每个IP组播网络选出一个代表成员(Designated Member)来代表整个组播网络，代表成员组成

26、应用层组播网络，在它们之间构造共享组播树。Host Multicast体系结构可以支持任意规模的IP组播网络，包括单个主机，局域网，校园网等。所有成员节点都具有IP组播能力（目前大部分操作系统都支持IP组播）。在每一个IP组播网络中，使用IP组播接收和发送数据。每个IP组播网络中选举出一个代表成员（Designated Member）代表整个组播网络。不同的代表节点之间通过UDP隧道相连。所有的代表节点之间组成一棵共享树，也就是说，从根节点到每个节点都只有一条无循环的路径，称为根路径。每个组播组都需要一个汇集节点HMRP(Host Multicast Rendezvous Point)，汇集节

27、点的功能是为新节点提供组的成员信息。HMRP知道共享树的根节点信息，当新节点向它发出查询请求时，它会把根节点的地址返回给新节点。HMRP并不参加数据转发，因此HMM的位置并不会对转发性能产生任何影响。一个HMRP可以同时为多个组服务。图3.7树的构建节点加入算法如下1) 所有的成员被看作是潜在的有效双亲节点，用栈S来保存以前的潜在双亲节点2) 找出查询HMRP所得的根节点，把所得的根看作潜在的双亲节点3) 查询潜在的双亲节点来找出它的所有子节点，跟踪衡量双亲和它的子节点4) 找出潜在双亲和它所有子节点最近的成员，除了这些，其他节点都是无效的。果所有的节点都是无效的，将栈清空，并返回第三步5)

28、如果最近的成员不是目前潜在的双亲节点，则将目前潜在的双亲节点入栈，并将最近成员设成潜在的双亲节点，返回第三步6) 否则，给潜在双亲节点发送一个节点加入请求，如果被拒绝，则将潜在双亲节点设成无效并返回第四步，反之，发现双亲节点，建立通向他的隧道。例子如下Host Multicast中的成员自己在共享树中寻找父节点。一个新节点H采用下面的过程寻找自己的父节点。H首先通过询问HMRP获得共享树的根节点。如图18所示，H知道A是树的根节点，H将把A设置成可行的父节点，并要求A告诉自己A的子节点的信息。从A和A的子节点列表中，H选择一个离自己最近的成员，图中是D，作为自己的新的可行父节点。H重复这一过程

29、，又得到了下一个可行的父节点F。于是H向F发送加入请求，请求把F作为自己的父节点。F将根据自己的配置策略，带宽和负载情况来决定是否接收H的加入请求。如果F拒绝了H的加入请求，H将把F标记为不可行并回到上一层的D节点继续查找过程，最后将G节点作为父节点。成员维护自己的根路径上的所有成员的信息。每个成员周期性的通过向根路径上某个随机节点发出加入请求操作来寻找更好的父节点（之所以不直接向根节点发出请求是为了降低根节点的负担）。掌握整个根路径的信息可以使成员检测是否出现环路。Host Multicast使用的是循环检测机制而不是循环避免机制。Host Multicast并不创建Mesh，Host Mu

30、lticast中采用的机制是让每个成员周期性地发现并缓存树中其它一些节点的信息。当HMRP失效时而共享树又出现分割现象时，这些信息可以帮助恢复共享树。图3.8节点退出HMTP通过周期性的与邻居节点交换信息来更新状态，每个孩子发送更新消息给他的父母，父母通过发送回路消息来回应。父母发送的路径消息包含父母的根路径。通过把它添加到父母的根路径中，成员自己构建了根路径。每个成员必须维持它的孩子和根路径表的更新。根发送更新消息给HMRP，因此HMRP总能知道当前的根节点当一个成员离开组时，他通报给他的父母和孩子，父母简单的从他的孩子中将他删除。离开的孩子自己寻找新的父母节点。一个孩子通过下面的节点加入算

31、法的反过程来寻找它的父母。如果根节点离开，他的孩子经过一段时间的延迟再与HMRP联系，第一个与HMRP联系的成员将成为新的根节点。3.基于隐含组播转发3.1 NICE NICE 4是一种可扩展的应用层组播,主要针对大量接收者的低带宽、大规模网络中的数据流应用,它基于分层的结构,同时具有较小的控制负荷,有利于它的扩展性。NICE 的数据拓扑隐含在它的控制拓扑中,因而还可以支持不同源的数据分发树;并且由于它的分层结构,进行错误检测较为迅速。NICE 协议把组播组成员安排成层次型的拓扑结构,由于总有新成员加入或旧成员退出,协议的基本功能就是维护这一拓扑结构. 拓扑结构隐含了组播数据的转发路径, 而且

32、它也是确保NICE 协议具有良好可扩展性的关键因素。NICE 通过把组成员分配到不同的层次结构来创建层次型拓扑结构。从最低层开始顺序编号，最低层标号为0 ，用Layer 0 表示，依次类推。每个层次的节点都被分成多个节点集群,通常物理位置较近的节点位于同一个集群中。每个集群有一个领导节点，协议依据集群的拓扑结构选择中心的节点作为领导节点,即领导节点到其他节点的距离之和在这个集群的所有节点中最小. 集群领导的选择对新节点加入时经过很少的查询次数就可以在层次结构中找到合适的位置非常重要.协议按照下面的规则将成员分配到各层次中：所有成员都属于最低层次Layer 0 ,然后使用集群协议把Layer 0

33、 层的成员分成多个集群并选择出每个集群的领导节点,所有集群的领导节点便构成Layer 1层的成员,依次类推.如图所示：图3.9 层次结构示意图Layer 0的集群是A,B,C,DE,F,G,HJ,K,L,M,C,F,M分别为这三个集群的中心，由它们组成了Layer 1，Layer 1只包含一个集群C,F,M,而F又是这个集群的中心，出现在了Layer 2层，以此类推，最高则只有一个成员。归纳以上，可以用以下几条性质来描述：1) 一个数据成员在每一层只能属于一个集群。2) 如果某个成员出现在了Layer i层，那么它也一定会出现在Layer i-1,Layer i-2Layer 0层，实际上它也

34、是这些层所在集群的中心点。3) 如果某成员没有出现在Layer i层，那么它也不会出现在Layer j层其中j>i4) 每个集群的大小都限制在（k,3k-1）,k为常数，。其领导节点正是集群在图论中的中心点。5) 整个层次结构最多有层，且最高层只有一个成员在这个控制拓扑中，每个集群中的每个成员都保留着其所属集群中的其它成员的状态信息，并且互相间周期性地交换这些状态信息，来确保所有成员能够快速地对成员变化作出反应，并能够对一些拓扑结构的破坏进行快速地修复。当一个新的成员加入到这个组中时，它将会被最终分配到Layer 0层中离它最近的集群中去。以图为例，假设有一个节点RP了解所有成员的信息，

35、新成员H要加入到组播组中，首先，H询问RP,RP返回最高层的成员的信息C0，然后H去查询最高层的成员C0，得到它下一层的集群的所有成员（B0，B1，B2）的信息，找出距离它最近的成员，设为B2，然后查询B2得到其下一层集群的所有成员信息，A3将最终找到Layer 0层中离它最近的集群。当一个节点A 要离开组播组时,它向与它建立联系的所有集群发送移除消息. 这是理想的离开方式,但是,如果A 失效了,与A 建立联系的所有的集群成员将在指定周期内不能收到来自A更新消息,从而认为A 离开了. 如果A 节点是一个集群的领导节点, 该集群必须选择重新选择一个领导节点. 集群中的每个成员以距离度量为依据独立

36、地选择一个领导节点,这样,便有多个领导节点,这些领导节点通过发送常规消息来重新选择一个惟一的领导节点.图3.10（a）NICE二层拓扑结构示意图图3.10（b） 图3.10（c） 图3.10（d）为了避免数据循环传输，数据传输拓扑同样选择了树形结构。对于基于层次结构的应用层组播协议来说，其特定数据源的数据传输路径已经在控制拓扑中隐式地定义了。因此，在控制拓扑上系统只需要决定哪些成员需要转发数据：首先，数据源会把数据包发向它在控制拓扑上的所有邻接点成员。然后，对于成员h，假设其属于层Layer 0Layer j,，接收到来自于成员p的数据包，那么p，h一定属于同一层Layer i的同一集群。此时

37、，只有当h是Ck（Ck表示h在Layer k层所属的集群）的中心点时才需要把数据转发给其Ck的其它所有成员。例如，图3.10中的（b）、（c）、（d）子图分别为源点为A0,A7,C0时的数据传输树示意图。3.2 PRO(Peer-to-peer Receiver-driven Overlay) 7PRO算法的基本思路是每个节点都可以独立、自私地决定一种接入应用层网络的最佳方式以最大化自己的传输质量。基于非结构化的P2P网络，每个节点可以连接到应用层网络的多个节点作为父节点。该算法他们先前开放的一种分层流数据传输方式PAL共同工作。节点加入和维护：PRO包括了两个关键成分：（1）基于闲话（Gos

38、sip）的节点发现（简称为PD），（2）由接受端驱动的父节点选择（简称为PS）。PD：PRO使用了一种类似闲话的方法来发现节点。使用闲话作为发现有潜力的父节点的搜索机制有两个好处：（1）交换信息的大小可以控制；（2）基于闲话的信息交换can be customized 流言机制的工作方式如下：每个节点维护一个含有img_sz个记录的本地Image，其中，每个记录保存了一个应用层中已发现节点的以下信息：（1）IP地址，（2）GNP（全局网络位置）坐标，（3）收到的层数，（4）记录最后一次建立的时间戳，（5）输出链路带宽，（6）输入链路带宽。在最开始时，一个新的接受节点需要知道应用层网络中的少数其

39、它节点，这个信息可以从一个初始服务器（也成为集合点）获得。该服务器将运用一定的策略选出一些初始节点提供给新加入的接收节点。这个过程成为初始父节点选择机制。当一个节点知道它的初始节点组后，它开始周期性地从本地Image中随机取出一个节点（Pj）进行闲话。然后运用一个内容选择策略从它的本地Image中选出一些（gsm个）对Pj最有用的节点传给Pj，Pj收到后也按同样方法返回一个信息。当闲话信息到达节点后，将使用一个Image维持机制将心得节点整合到本地Image中。内容选择策略：节点对本地Image中所有节点为目标节点确定相对效用，按照效用设置被抽取概率并从中随机抽取gsm个节点作为闲话的内容。I

40、mage维持机制：当收到新的节点信息时，Image维持机制将符合以下条件之一的记录从Image中删除：（1）有较低效用的节点；（2）由于性能较差而被PS机制放弃的节点；（3）时间太老，超过一个阈值的节点。PS：PS机制实际上是在本地Image中寻找父节点的渐进式搜索。它的目标是：（1）最大化传输带宽；（2）最小化所有父节点到接收节点的总延时；（3）最大化到父节点路径的多样性。当这些目标冲突时，接收节点将按照优先级进行优化。每个接受节点的活动父节点数目应该在一个预先设置的范围内。每个接收节点都尝试着用最小的父节点数达到最大的传输带宽。若一定数目的父节点无法达到要求，则接收节点会逐渐增加父节点的数

41、目。3.3VRing 10VRing为环形拓扑结构，成员为自组织分布式结构。它的管理开销较小，带宽消耗较小，节点的度较小，但是有较高的路径伸展度和较高的链路强度。使用环形拓扑的原因有如下两个：（1）节点的度为O(1)，在应用层的邻居数目为一常数，并与组播组的大小无关。（2）通过使用含有顺序和流量控制信息的令牌可以有效地进行安全、可靠和有序的信息传递。由于环形拓扑可能会造成大的路由延时，因此在节点间还建立了备用环，数据同时通过原环和备用环进行转发。环的初始化：在VRing的初始连接阶段，进行连接的成分包含一下几类：（1）单独的成员；（2）至少有两个成员的环。每个连接成分都有一个领导节点（lead

42、er node），单独成员组的领导节点为本身。每个组成员都维护着它的前驱和后继节点的ID（单独成员的前驱和后继均为NULL），同时需要维护所在组的领导节点的ID。每个领导节点周期性地向集合点注册自己，当领导节点超过一定时间未刷新注册信息，则集合点认为该领导节点退休（retired）并删除其信息。当集合点收到注册信息后，将该领导节点信息加入全部领导信息的列表，并返回一个已注册的全部领导节点的列表。当领导节点知道其它领导节点后，会选择一个最近的发送JOIN消息进行两个环的合并，这里有四种情况，见图3.11。每个领导节点在某一时间只能与一个另外的领导节点通信，于是当某领导节点联系的目标正在与其它领导

43、节点联系时，JOIN请求会被拒绝，此时它会转向联系第二个最近的领导节点。当最后只剩下一个领导节点的时候，整个初始化过程结束。剩下的领导节点仍周期性地与RP联系，但是RP不会回应。当该领导节点没有收到RP回应超过一定时间，则认为初始化过程结束，开始备用环的生成过程。图3.11 四种环的合并方式环的维护：每个组成员周期性地发送HELLO消息到它的后继节点。当节点收到HELLO后，检查自己的前驱，若为NULL，则将发送方设为前驱。当前驱为NULL或和HELLO发送方相同时，向发送方回复HELLO_REPLY消息，并在消息中包含自己的后继，否则HELLO被丢弃。相似地，当节点收到HELLO_REPLY

44、时，检查自己的后继，为NULL则将回复方设为后继。当后继为NULL或为回复方时，当前节点记录下其后继节点的后继，否则丢弃HELLO_REPLY消息。这样做的作用有三方面：（1）每个节点都可以检测到它的后继是否还为一个成员，如果发送一定数目的HELLO消息仍未收到回复，则认为后继节点已失效；（2）可以使每个节点知道其后继节点的后继。这样，当其后继节点失效时，可以与后继的后继建立连接；（3）若该成员为领导节点，它将在HELLO_REPLY中指出，如果领导节点失效，则它的前驱成为新的领导节点。生成备用连接：为了减少路由延时，算法建立了一个备用环。当组成员的数目为N时，把组成员从领导节点开始赋予序号0

45、N。备用连接将在节点i和之间建立，见图3.12。图3.12 备用环示意成员离开和节点失效：将前驱节点成为上游，后继节点成为下游，则总是由上游通过HELLO消息进行失效检测，并在发现失效后向后继的后继发起修复过程（发送LINK_REPIAR消息）。当后继的后继收到后回复LINK REPAIR ACK消息。当同时会有多个相邻的节点失效的情况下，可以对HELLO消息进行一些修改，返回时存入后继节点列表。在这种情况下，领导节点需要以一个很低的频率周期性地向整个环发送消息来表明领导节点的有效。当领导节点失效后，则用一个选举算法选出新的领导节点。4混合型的拓扑结构4.1 HOMP（Hybrid Overl

46、ay Multicast Protocol）11HOMP使用混合形拓扑结构，将所有成员分为核心成员和附属成员，核心成员组成网状拓扑结构，附属成员组成附属树，树根节点为核心成员。该算法混合使用了Narada（核心成员）和HMTP协议（附属成员）的一些内容。核心成员使用类似DVMRP的路由算法；附属成员使用group-shared tree模型在附属树中传递信息。图3.13 混合拓扑，实心节点为核心成员，空心节点为附属成员节点加入：每个节点都需要通过集合点（RP）加入。第一个加入的成员成为第一个核心成员。当新成员加入时，它通过集合点找到一个已存在的成员x，然后向x请求一个存有所有核心成员的列表。如

47、果x是一个核心成员，则复制自己的核心列表发给新加入节点。如果x是一个附属成员，则将它们的根节点y的信息发给新成员，使新成员可以从y处得到核心列表。一个新成员按照以下方法决定是否成为核心成员：（1）当前的核心成员数C小于核心成员的期望值en；（2）成员的剩余的度不小于d，d表示了成为核心成员所需的剩余带宽。否则它将成为附属成员。如果新成员成为了核心成员，则它随机地从核心列表中选择一组成员，向它们发送消息加入核心网。如果新成员成为一个附属成员，它在一个现有成员列表的一部分中选择一个最近的成员作为父节点。目前HMOP使用往返时间（Round Trip Time）作为度量标准。节点离开与失效：当一个成

48、员离开组播组时，它将通知它的邻居。失效节点的发现由其邻居完成。如果离开（或失效）的节点为核心成员，组变化的信息将通过核心网传播到其它的核心成员。一旦附属成员发现它的父节点离开了组播组，它将寻找一个新的父节点活成为一个核心成员加入核心网。拓扑结构的改进：为了提高性能，需要对重叠层的网络进行优化。对核心网的优化与Narada协议类似，即增加“好”的连接，删除“坏”的连接。对于附属树的优化则为每个节点周期性地运行加入算法。由于成员的变化可能导致核心程序数目超过或远小于期望值en，需要动态对核心成员进行调整。在HOMP中选用一个领导节点来完成这个工作。当核心成员数超过阈值en+T1时，领导节点将选出一

49、些度最小或接口带宽最小的节点转为附属节点。当核心成员数小于阈值en-T2时，领导节点会随机选出一些附属树的叶子节点成为核心成员。四、应用层组播协议的评价评价组播协议一般用以下几种方式:(1) 数据分发路径的质量主要有下面三个指标5:强度(Stress) ：在一条物理链路中发送相同数据包的数量。伸展度(Stretch)：就是在覆盖网分发拓扑中从源到成员的延迟与利用单播直接传输的延迟的比例。资源利用率(Usage)：所有参加到数据传输中的成员,他们的延迟和强度的乘积的总和。这个指标用于评定传输过程中网络资源的利用情况。(2) 终端的性能失效后包丢失：单个节点突然失效后,平均的丢包数量。强调突发事件

50、发生的鲁棒性。收到第一个包的时间：当成员加入到组中,收到第一个包的时间。(3) 控制负荷(Control OverHead)指成员为了维护网络拓扑所要进行的控制信息交换所付出的代价。为了有效地利用网络资源,对每个成员的控制负荷必须尽量的小,这是能否很好扩展重要的指标。不同的文献所采用的评价参数也不完全相同。总的来说，基于Mesh网优先的策略比较适合应用与小规模的组播组，基于树优先的策略虽然不适合在实时性要求较高的场合应用，但却非常适合在高带宽的数据传输中应用。基于隐含组播转发拓扑结构的策略虽然对以上两个方面的缺点有所改进，但是也不可能达到完全的理想。五、总结应用层组播的优点(1) 应用层组播能

51、够很快就进入应用,不需要改变现有网络路由器。(2) 接入控制更容易实现。由于单播技术在这方面比较成熟,而应用层组播是通过终端系统之间单播来实现的,所以差错控制、流控制、拥塞控制容易实现。(3) 地址分配问题有相应的解决方案。应用层组播的缺点(1) 可靠性:终端系统的可靠性比路由器差。(2) 延迟比较大: IP 组播主要是链路上的延迟,而在应用层组播中,数据还要经过终端系统,因而延迟相对要大一点。(3) 传输效率不如IP 组播:应用层组播在数据传输过程中会产生数据冗余,因此它们比IP 组播的效率差。基于其优缺点，目前应用层组播的研究主要集中于视频会议系统、媒体流的分发系统（如视频广播）和订阅/分

52、发系统（Publish/Subscribe System）等。应用层组播的主要应用是实时的多媒体传输。一方面这利用了多媒体信息的性质，即在传输链路质量下降的情况下，用户仍然可以利用收到的低速率的或者不完整的信息，这适用于同一组播组中的多个用户可能接收能力不同的情况。而文件传输等可靠传输则没有这样的性质。另一方面也发挥了组播“时间上集中、空间上分布”的特点6。六、我们的一些想法应用层组播的一大特色就是充分利用了客户终端的软硬件资源，在计算机技术迅速发展的今天，终端的性能不断地提高，而随着网络在生活中的地位越来越重要，网络上传输的信息越来越多，路由器等网络设施处理信息的压力越来越大，应用层组播中终

53、端分担了部分原来路由器的任务减轻了路由器的压力，实现了资源的优化使用。我们或许能够将应用层组播技术和IP组播技术结合起来使用，在能够使用IP组播的区域（例如局部的小规模的支持IP组播的区域）使用IP组播技术，当出现网络拥塞时使用应用层组播技术采用单播的拥塞控制方式处理网络拥塞。另外由于IP层掌握了网络的拓扑结构信息，因此在应用层组播树建立时如果能够很好的利用IP层的网络拓扑信息的话就能建立起效率更高的组播树。网络安全是目前一个非常热门的话题，在应用层组播中，大部分终端收到的数据都是来自其它终端的，则终端就有机会借助应用层组播树在传递有用数据的同时传播计算机病毒或者对其它终端进行攻击，这也是一个很大的安全隐患。参考文献1S.E. Deering, D.R. Cheriton,Multicast routing in datagram internetworks and extended LANs, ACM Transactions on Computer Systems, 19902 Yeo