信息通信专业资料 应用层组播数据驱动构建重叠网络word版

1、应用层组播 数据驱动构建重叠网络 一 引言组播是网络研究的一个重要课题，IP组播模型是对Internet基本的“单播、尽力发送”模型的一个重要扩充，它把组播的主要功能放在路由器上实现。在IP组播体系结构中，网络中的路由器采用分布式算法构造一棵数据转发树。当组播分组沿着转发树进行转发时，在树的分支节点处，由路由器进行分组复制。IP组播是实现组播分组转发的最有效的方式，因为它可以使全网范围的分组复制数量达到最少，从而实现减少带宽浪费和降低服务器处理负担的目的。从提出IP组播模型到现在，IP组播并没有得到广泛应用，这是由于IP组播在传输技术和管理上存在严重的问题。首先，IP组播的可扩展性问题，IP组

2、播需要每个路由器为每个组维护状态，有时甚至需要为每个组播组中的源维护状态，和单播地址不同，组播地址很难聚合，这就增加了路由器的负担和实现的复杂性。其次，IP组播中实现可靠性和拥塞控制非常复杂，难以支持高层功能。第三，缺乏有效的网络管理和计费模型，这使得ISP迟迟不愿意在自己的路由器上实现IP组播。针对IP组播的部属实现困难，同时为了满足不断增长的组播应用需求，研究人员提出了应用层组播方案。在应用层组播中，组播功能是在应用层实现的。应用层组播的主要思想是通过保持Internet原有的“单播、尽力发送”模型，在尽量不改变原有网络体系结构的情况下，增加端系统的功能来实现组播的功能。由于对网络本身改变

3、很少，应用层组播具有很好的灵活性。图1给出了应用层和网络层组播示意图。在网络层组播中，分组由网络中的路内器进行复制，如果主机A向主机B、C和D发送分组，则分组在路由器1处进行复制。而在应用层组播中，分组在端系统处进行复制。端系统构成了逻辑上的重叠网络(Overlay Network)，应用层组播的目标就是为了便于进行数据传输，构造并维护高效率的重叠网络。由于应用层组播可能会在同一条链路上多次发送相同的分组，因此它的效率要低于网络层组播。图10(a) IP层组播图10(b) 应用层组播方案二 应用层组播分类应用层组播方案通常都按照两个拓扑结构组织组成员，一个是控制拓扑，另一个是数据拓扑。控制拓扑

4、中的组成员周期性的交互刷新消息以相互标识身份并从节点失效中恢复。而数据拓扑通常是控制拓扑的子集，它用于标识组播转发时使用的数据路径。数据拓扑一般是树状结构，而控制拓扑则具有网状结构。根据构造控制拓扑和数据拓扑的顺序，我们可以把应用层组播方案分为3类：基于Mesh网优先建立的方案（Mesh-First）、基于树优先建立的方案（Tree-First based Approach）和基于隐含组播转发拓扑结构的方案。基于Mesh网优先建立的方案（Mesh-First）：首先，组成员构造一个基于应用层的重叠网络作为自己的控制拓扑。其次，在重叠网上使用标准的组播路由协议例如DVMRP (Distance

5、Vector Multicast Routing Protocol) 生成基于源的组播树(数据拓扑)。典型方法有ESM、ScatterCast等。 在基于树优先的方案中，首先直接采用分布式算法构造数据转发树；然后各个组成员通过主动探测，发现该组播树中的其它节点（不一定是自己邻居节点），并和这些节点保持控制连接。在基于树优先的方案中，数据转发树加上这些额外的连接就构成了控制拓扑。这类方案的典型例子是Yoid、Host Multicast、ALMI等。在基于隐含组播转发拓扑结构的方案中，使用面向大规模对等网络的路由机制创建带有某些特殊属性的控制拓扑。在控制拓扑中就隐含定义了数据转发路径，因此在这类

6、方案中，Mesh和转发树是同时根据应用层网络路由机制创建的，组成员之间并不需要进行额外的信息交互。这种方式的应用层组播协议通常可以支持规模相当大的组播组，具有良好的可扩展性。这类方案包括：NICE、CAN、Bayeux等。在本研究报告中，我们将重点介绍基于数据驱动来构建拓扑结构（Data-Driven Overlay Network）方案。该方案的特点是：1）构建了非结构化的，每个节点（peer）拥有多个父节点的重叠网络；2）采用了一种节点发现机制，使得每个节点能够发现对自己最有利的多个父节点。这种数据为中心的设计更适应组播组中节点的动态的加入和退出。典型的方案有：CoolStreaming，

7、PRO，GnuStream等。在具体介绍这些方案之前，我们先简要介绍与应用层组播的相关的媒体编码传送技术。三 应用层组播相关技术3.1 媒体编码传送技术媒体编码传送技术对应用层组播，特别是实时的视频流业务影响很大。目前的媒体编码传送技术方案主要有：1） 信息重复的单速率方案：发送端对相同的媒体内容生成重复的，不同速率的数据流由接收端的情况决定使用某个数据流。2） 累积的分层方案：媒体被编码成一个基本层和若干个增强层。基本层是必须的，增强层可以根据接收端的状况选择增加，可以提高媒体质量。例如现有的FGS（Fine Granularity Scalability）编码.3） 非累积的分层方案：媒体

8、被编码成若干个具有相同优先级的媒体流。MDC（Multiple Description Coding）编码属于这种方案。采用FGS编码和MDC编码比单速率具有优势，它们可以根据用户的要求调整速率。分层编码可以与数据驱动的方案很好的结合，前面提到的PRO就是采用了分层编码。分层编码的缺点：1）编码和解码的计算开销比较大；2）在FGS方案中，只有完全接收到某层的信息才能获得相应的质量提高，这要求尽量减少高优先级数据的丢失；3）在同等质量下，要比单速率方案多消耗2040的带宽。3.2 流言协议（Gossip）Gossip算法广泛应用于组播信息分发，典型的Gossip算法实际上是一种泛洪机制，其流程如

9、下：一个新节点向随机选的一组节点发送新产生的信息。接收到该消息的节点在下一次发送时段重复上面的过程，这个过程不断重复，直到组播组中每个节点都收到该信息。它有以下显著特点：1）发送对象是在组播组中随机选择出来，这更能适应组播组中节点的动态性；2）节点之间的交互消息的大小是可以控制的，也就是开销是可以控制在适度范围。我们将要介绍的PRO中就采用了Gossip协议来寻找潜在的父亲节点。四 数据驱动重叠网络PRO（Peer-to-Peer Receiver-driven Overlay）是一种典型的数据驱动重叠网络，也称接收端驱动方式构建重叠网络。其核心观点是：允许每个节点独立的选择自己的接入方式和父

10、亲节点，以达到最大化自己的传输带宽，每个节点可能拥有多个父节点。按照这种规则，组播组的节点构成了一个非结构化的重叠网络。由于每个节点拥有多个父节点，从而能够有效地协调带宽地异构性和不对称性，更好的适应网络中由于节点加入和退出引起地波动。PRO不仅具有前面提到的数据驱动重叠网络的一般特点，为了能够支持实时的视频业务，这就要求它能够对所有的发送节点进行协调，譬如对采用了分层编码的视频流，它必须能够很好的协调每个父节点该传输那些数据包，并确保数据包能够及时的达到。PRO由两大模块构成：1）基于流言（Gossip）的节点发现模块（Parent Discover）；每个节点周期性的与组播组中已知的节点交

11、互信息，来了解未知节点的信息，从这些节点中选出对自己最有利的一组节点。这里采用了前面介绍的Gossip协议。2）节点选择模块（Parent Selection）；在PD模块选择出一组对自己有利的节点后，PS模块从中随机选出一部分节点作为自己的父节点进行数据传输，并逐步的改善传输带宽。图2给出了PD和PS模块之间的交互。图2 PD和PS模块之间的交互在PRO中，接收节点通过检测每个父节点的可用带宽来间接发现可能存在的瓶颈链路。图3说明了这个过程。节点加入新的父节点，同时监测和总的可用带宽，如果的可用带宽发生了下降，可以推断两父节点之间存在某个瓶颈链路，图中的。假设此时，节点选择节点作为自己的父节

12、点，这就和节点展开了竞争，图中的成为瓶颈链路。如果节点获得了更高的可用带宽份额，节点检测到可用带宽的下降，随机等待一段时间，将节点丢弃。节点将重新选择新的父节点。图3 间接检测可用带宽4.1 节点发现节点发现模(PD)实际上是对组播组中的节点进行搜索，从中选出对自己最有利的节点。为了方便下面的说明，定义一些符号如图3所示， 图4 使用的符号这里采用了Gossip协议来交互信息，其工作机制如下：初始选择阶段：当一个新节点加入到组播组时，它首先和服务器建立连接，相当于集合节点，服务器从组播组中随机选择一定数目的节点，新节点与这些节点建立连接。同时为每个节点生成一条记录，记录包括以下参数：1）节点的

13、IP地址；2）拥有的层数；3）输出带宽和输入带宽；4）时间戳，记录的产生时间。所有的记录存放在节点的本地镜像。目标选择：当从集合节点获取了初始节点之后，节点从中随机选择一个目标节点作为Gossip对象，也就是说节点向节点发送Gossip消息。内容选择：在目标选择确定之后，节点调用效用函数对本地镜像中所有节点计算它们对节点的有用性，并根据计算结果，对所有节点进行分等级排序，我们根据输出带宽和到节点延时进行联合排序。节点从本地镜像中为节点选取个节点，节点被选中的概率是和它的有用性是成比例的。也就是说节点向节点发送一条含有条记录的Gossip消息。节点收到这个消息后，回送一条消息，该消息中包含了对节

14、点最有用的条记录。镜像更新阶段：节点收到Gossip消息后，首先将加入到本地镜像，随后进行本地镜像更新，删除符合以下条件的记录： n 该记录代表的节点性能较差。n 由上层PS模块丢弃的性能较差的节点。n 时间戳高于门限的记录。我们已经说明了Gossip工作机制，显然，消息交互的频率和消息的大小决定了节点镜像的时效性。4.2 节点选择节点选择机制实质上是在本地镜像搜索一组父节点的过程。通过节点选择达到以下设计目标：1）最大化传输带宽；2）最小化传输延时；3）最大化传输路径的多样性。每个节点拥有有效的父节点数（）在设定范围【】内，节点总是希望以最少的父节点来达到最大化的传输带宽。如果节点起初拥有的

15、父节点（）不能够最大化传输带宽，节点将会增加父节点数。在PS模块我们考虑以下三个问题：4.2.1 何时选择新的父节点PRO采用了数据驱动的方式来选择新的父节点，这可以有效的降低选择新节点的次数，提高了重叠网络的稳定性。在下列情况下，将选择新的父节点：1）初始阶段，当一个新节点加入组播组时，它将周期性地加入新的父节点，直到拥有父节点为；2）替换性能较差的父节点，如果某个父节点的带宽显著下降并持续一段时间没有恢复，接收节点将丢弃该节点，并选择一个新的父节点来代替；3）提高性能，如果某个父节点的加入能够显著的改善性能，如增加带宽和降低延时，加入该节点。4.2.2 成为父节点的条件父节点总是在本地镜像

16、中选出来的，选择某个节点是随机的，选中的概率跟节点的有用性，也可以说是节点的等级是成正比的。这种选择策略均衡地利用了每个节点地带宽，没有使得高带宽节点负载过重。4.2.3 怎样丢弃父节点初始阶段后，节点在每个时刻拥有的父节点数为，为了保证性能的单调提高，新父节点总是在丢弃某个节点之前加入。符合以下条件的节点将被丢弃：1） 在所有父节点中，提供的带宽最小；2） 为了最大化传输路径的多样性，找出拥有最多节点的一条瓶颈链路，将其中提供带宽最小的节点丢弃；接收节点为每个父节点设置一个计时器，在丢弃某个父节点时，为了避免下次选择到该节点，将节点上的计时器进行指数级的递减。至此，我们已经介绍了一个简单的接

17、收者驱动方式构建重叠网络，在PRO构建的重叠网络基础之上，另一种机制PALS将负责如何从多个父节点获取实时的分层编码视频流。PRO和PALS是相辅相成的，PRO为实时视频流的分发选择了父节点，最大化传输带宽，PALS则保证了每个视频数据包的及时到达。五 应用层组播方案比较下面我们对节点动态性的容忍度，系统开销和公平性（带宽效率角度）三个方面对一些典型的应用层流媒体方案进行比较。传统的基于单树方案，每个节点只有一个父节点。根节点，也就是源节点管理树中所有节点信息，这种集中式管理方案系统开销小。若上层节点失效，下层所有的节点都将无法获取数据，容忍度差。由于每个节点只能从一个父节点处获取数据，公平性

18、差。目前针对基于树方案，提出了许多改进算法，包括构建多个数据分发树等方案，都期望提高对节点动态性的容忍度。数据驱动方案其设计理念是每个节点独立的选择接入组播组的方式，最大化自己的利益。这样每个节点拥有多个父节点，可以有效地提高了容忍度，同时在公平性方面更好。但相比集中式管理，系统开销大。六 我的一些想法从前面介绍的PRO中，可以看出许多参数如根据带宽和延时对节点进行排序，每个节点拥有的父节点数等，都没有明确，需要进一步的细化工作。在PRO节点的本地镜像中，给每个节点保存一条记录，是否可以考虑增加一项节点的生存时间，一般认为，生存时间越长的节点越稳定。数据驱动方式没有考虑到底层网络特性，也就是没

19、有考虑节点的本地性，PRO中仅仅依靠延时来进行判断。我们需要尽量减少跨ISP的情况。在将分层编码应用到数据驱动方式时，需要很好地考虑多个父节点之间的协调。七 参考文献【1】 章淼,吴建平, "应用层组播研究综述", 清华大学计算机系网络研究所，2003 【2】 Yeo C K,Lee B S,Er M H.A, "A survey of application level multicast techniques", Computer Communications,2004【3】 Y. Chi and K. Nahrsted, "Layered

20、 Peer-to-Peer Streaming", In Proc. of NOSSDAV 2003【4】 V. Agarwal and R. Rejaie, "Adaptive Multi-Source Streaming in Heterogeneous Peer-to-Peer Networks", In Proceedings of the 12th Annual Multimedia Computing and Networking (MMCN '05), January 2005【5】 Tran D, Hua K, Do T, "ZI

21、GZAG: An Efficient Peer-to-Peer Scheme for Media Streaming", Proc. of the IEEE INFOCOM 2003【6】 R.Rejaie and S. Stafford, "A Framework for Architecting Peer-to-Peer Receiver-driven Overlays", Nossdav 04, Ireland, June 2004【7】 Tadeusz Piotrowski, Suman Banerjee, et al., "Peer-to-peer Streami