【大学】信息通信专业 应用层组播tree结构的探讨

应用层组播tree结构的探讨编辑ppt应用层组播tree结构的探讨一、综述1、组播算法组播算法的基本出发点是：在存在多个接收者的时，通过合并重复信息的传输来达到减少带宽浪费和降低服务器处理负担的目的。编辑ppt应用层组播tree结构的探讨一、综述2、应用层组播的提出近年来，随着Peer-to-PeerNetwork和OverlayNetwork等技术的提出，出现了“应用层组播”（ALM:ApplicationLayerMulticast）这样一个研究方向。编辑ppt应用层组播tree结构的探讨一、综述3、应用层组播的主要思想保持Internet原有的“单播、尽力发送”模型，尽量不改变原来网络的体系结构，而主要通过增加端系统的功能来实现组播的功能。由于对网络本身的改变很少，应用层组播具有很好的灵活性。但是，端系统的稳定性一般不如专用网络设备，应用层组播在带宽利用效率方面也无法和IP组播相比。另外，应用层组播中的系统框架和很多细节技术也还在研究当中。这些问题的存在为应用层组播的研究提供了广阔的空间。媒体编码技术、Peer-to-Peer和OverlayNetwork等技术的发展对应用层组播的研究也有很大的促进作用编辑ppt应用层组播tree结构的探讨一、综述4、应用层组播和IP组播的不同和IP组播增加网络机制的方法不同:应用层组播的基本思想是保Internet原有的简单、不可靠、单播的转发模型，由端系统来实现组播转发的功能。这也是著名的”end-to-endargument”所倡导的思想。编辑ppt应用层组播tree结构的探讨一、综述5、应用层组播算法的设计中的假设(1)网络中的带宽和转发资源是相对丰富的，而服务器的能力是一个主要瓶颈。使用应用层组播会比IP组播消耗更多的带宽，但是和单播方案相比，它还是可以有效的降低服务器的负载和减少带宽的使用。编辑ppt应用层组播tree结构的探讨一、综述5、应用层组播算法的设计中的假设(2)大多数参与组播的端系统可以贡献出一部分资源用于组播的转发。这个假设并不是针对所有的应用层组播算法，但是不少的应用层组播算法都有这个假设。编辑ppt应用层组播tree结构的探讨一、综述5、应用层组播算法的设计中的假设(3)上层应用对性能的要求并不很苛刻，可以容忍报文的丢失和较大的延迟。Internet的可靠性本来就无法完全保证，参与组播的主机性能也无法保证。所以，应用层组播并不针对所有的应用，而主要针对那些对可靠性和性能要求较低的应用。编辑ppt应用层组播tree结构的探讨一、综述6、应用层组播的主要优势（1）应用层组播便于实现和推广。它只需要改变端系统，而不需要对路由器进行任何修改。（2）应用层组播便于针对特定应用进行优化，可以针对不同的应用使用不同的实现方案，而不必象IP组播那样必须统一到一个模型中。编辑ppt应用层组播tree结构的探讨一、综述7、应用层组播的主要缺点（1）一般会比IP组播使用更多的网络资源。（2）由于参与转发的端系统可能不稳定，导致组播转发的可靠性受到影响。（3）由于参与转发的端系统的性能无法保证，可能导致延迟、转发速率等性能的下降。编辑ppt应用层组播tree结构的探讨一、综述8、应用层组播的主要应用基于这些特点，目前应用层组播的研究主要集中于视频会议系统、媒体流的分发系统（如视频广播）和订阅/分发系统（Publish/SubscribeSystem）等。应用层组播的主要应用是实时的多媒体传输。一方面这利用了多媒体信息的性质，即在传输链路质量下降的情况下，用户仍然可以利用收到的低速率的或者不完整的信息，这适用于同一组播组中的多个用户可能接收能力不同的情况。而文件传输等可靠传输则没有这样的性质。另一方面也发挥了组播“时间上集中、空间上分布”的特点。编辑ppt应用层组播tree结构的探讨一、综述

Overlay是一个应用层组播解决方案的完整的部分，它是影响多点通信的基本机制。其节点可以逻辑地组织成两种拓扑结构，即控制拓扑和数据拓扑。控制拓扑携带控制信息，如heartbeat信息，更新信息，网络探测和探测数据等。数据拓扑由实际数据交付至多端的路径组成。控制拓扑的节点不必是多播组成员，因此控制拓扑是数据拓扑的超集，他是大多数采用tree结构的数据拓扑的标准，而且是易于建立和有效的。控制拓扑假定一个mesh形式的分离的物理结构，在这个结构中，拓扑里的节点占用较高的连接，或者像数据拓扑一样分享同一结构。依据采用的途径，overlay拓扑可以分成三个部分：tree，Mesh-Tree，植入结构。编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（1）应用层组播体系

(ApplicationLayerMulticastArchetecutre,ALMA)早期的ALMA版本依据网络距离如RTT(roundtriptime)，选择离自己最近的节点作为自己的父节点。在新的版本中，ALMA依据丢失率和RTT的共同考虑来选择父节点。组成员定期向DS提供它们的丢失率。通过端对端的测量方法收集成员至成员的RTT。Gossip-style算法用来在成员离开tree时的分割恢复。组成员通过定期地和一些gossipcandidates交换丢失率和RTT以选择更好的父节点。编辑ppt应用层组播tree结构的探讨图1ALMA结构。

编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（2）香蕉tree协议（BananaTreeProtocal,BTP）

BTP利用基于接收的、自组织的途径建立共享数据tree。它被设计用来分布式文件共享应用。第一个加入组的主机成为tree的根，后加入的新成员学习根并加入到tree中。其算法是允许一个节点转到一个同属节点，如果该同属节点比这个节点的父节点更接近该节点。同属节点在每个节点内维护的信息由节点的父节点更新。编辑ppt应用层组播tree结构的探讨图2显示同属节点转换可以降低tree开销

。

编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（2）香蕉tree协议（BananaTreeProtocal,BTP）满足以下两个条件：

其一，当一个节点在自己转换进程中能够拒绝其他所有的转换尝试；

其二，节点必须把当前父节点的信息包含在转换请求中以便潜在的父节点能确认其为真正的同属节点。

能防止如图3中的同时转换引起的循环和图4中的过期信息引起的循环。编辑ppt应用层组播tree结构的探讨图3同时转换引起的循环编辑ppt应用层组播tree结构的探讨图4过期信息引起的循环编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（3）主机多播（HostMulticast,HM）HM的目的是用以提供应用中的高效的多播交付服务和能于ip多播在最大程度上的共容。它自动连接IP多播岛并通过单播隧道提供多播给不能多播的端主机。经由指定成员（DesignatedMember,DM）之间的UDP隧道，多播岛就连接起来了，每一个岛选择一个DM。

编辑ppt应用层组播tree结构的探讨图5HM结构

编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（3）主机多播（HostMulticast,HM）数据分配tree是共享tree，任何成员都可以成为一个源。 HM利用分布式tree建立协议来度量组成员的数量。编辑ppt应用层组播tree结构的探讨图6在共享树上新成员H通过集合点（RendezvousPoint,RP）发现根A编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（3）主机多播（HostMulticast,HM）图6显示的是在共享树上新成员H通过集合点（RendezvousPoint,RP）发现根A。H把A当作潜在的父节点并请求A的子节点列表，沿着树径一路搜索下来，根据距离A最近的原则，H选择F作为自己的父节点。HM中的每一个成员都维护其到根节点A的路径信息。每一个成员都要定期通过阻止一些来自根路径上的随机成员的加入进程来寻找跟近的父节点。HM利用循环探测机制代替循环避免机制。为了从树分割中恢复，每一个成员都可以重新加入任何一个新成员在它的根路径或者缓存上，缓存在成员沿着树径“走”下来的初始进程中建立。编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构(4)重叠网多播网络结构（OverlayMulticastNetworkInfrastructuer,OMNI）

OMNI从一组多播服务节点（multicastservicenodes,MSN）建立一个单一源节点树结构,如图7所示。重叠网tree的建立过程包括一个在数据交付开始前的离线初始化阶段和数据交付过程中的动态的自组织进程。OMNI的关键特性是关键基于服务组大小（所服务的客户机数量）的不同的MSN的动态优先级来迭代优化重叠网tree，动态自组织进程如图8所示。编辑ppt应用层组播tree结构的探讨图7OMNI从一组多播服务节点（multicastservicenodes,MSN）建立一个单一源节点树结构,编辑ppt应用层组播tree结构的探讨图8动态自组织进程编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构(4)重叠网多播网络结构（OverlayMulticastNetworkInfrastructuer,OMNI）在开始的结构MSN0到MSNx的时延是59ms，客户机增加，MSN的重要性也相应地增加，它首先把父节点改到MSN6上将时延降为54ms，然后改到MSN0上降为51ms。随后其客户减少，x也就从树上往下移动，同时有其他MSN的客户的增加引起其上移，为了协调时延，每个MSN之间定期交换，在交换能减少当前平均时延的情况下，交换仅限于两层之间的交换。编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构（5）TreeBuildingControlProtocal(TBCP)TBCP的目的是提供高效和分布式的协议来为应用层多播建立控制数据交付tree。如图9所示，新成员M像C1，C2，C3一样要加入到P上，如果最新的结构是最优的，M加入到P，而C3则要重新开始加入过程最后加入到M上。编辑ppt应用层组播tree结构的探讨图9编辑ppt应用层组播tree结构的探讨二、关于tree的一些概念和分析1、几种常见的tree结构另外还有ApplicationLevelMulticastInfrastructure，Overcast’s等树结构。编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法1、利用分层编码主要存在的问题其一，是由于流技术的特性限制，子节点的接收率是不能超过父节点的接收率，如图1所示，主机B是主机A的子节点，即便B有更高的下载带宽也不能获得更高的数据速率，因为A的速率不高。在这种情况下，分层编码不能充分利用而且每台主机在选择父节点时必须谨慎。编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法1、利用分层编码主要存在的问题编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法1、利用分层编码主要存在的问题其二，寻找一个适当的父主机是很复杂的，通常，新加入ALMtree的主机都是叶子主机，它通过交换带宽信息搜寻邻居主机，并找到拥有自己需要的前向数据速率的主机。然而，这种进程是复杂而费时的。而且因为其加入tree中只能获得重叠网的本地信息的缘故，它将很难通过适当的方式得到端主机。编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法2、“degree”的参数它原本是描述一台父主机能维护多少台主机。其数值取决于父主机的前向吞吐量。一台主机i的前向吞吐量是Fi，单一流数据率是R，degree值Di的表达式为

Di＝Fi/R（1）编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法3、解决分层编码存在的问题为了解决利用分层编码主要存在的问题，这里重定义“degree”的参数。以使每台主机能够恰当地决定自己的父主机，利用这个方法的一个好处就是这个值是事先知道的，因此每个新成员加入ALMtree时不必再搜索父主机，显而易见地，通过这种参数方法，当父主机离开tree时，不是所有的后代主机决定他们的父主机。图2，显示的是所有主机的degree是2，主机B（或A）将不能再连到G上因为父节点P的离开，它必须搜寻另一台有未使用degree的主机。最简单的方法是向新加入成员那样，重新加入tree中，但是这会消耗很多恢复时间和overhead。

编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法4、“degree”的参数的重定义在互联网上，一个边缘路由器和每台主机之间的访问连接特别是上行连接的带宽通常比干线连接窄。因此，一般考虑发送端主机连接是P2P网络的瓶颈，基于这一点，degree限制参数描述的是如（1）式所述的父主机拥有多少主机。这样就很容易参考这个参数来决定一个新成员是否加入父主机，在ALM的分层编码的应用中，流速率R不是固定不变的，需要重新定义。编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法4、“degree”的参数的重定义

首先，用R1代替R，R1为基层速率Di=Fi/R1(2)

编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法4、“degree”的参数的重定义其次，R1假定为1，实时数值比例提供的每一层“积累”速率赋予R1，新的degree描述父主机拥有的流的数量，例如，多播流速率为{50,50,100}kbps,主机I的发送吞吐量为300kbps,根据（2）式，主机的degree为6，积累速率的比率为1：2：4，这样，主机I有4个基层流和1个第二层流（1×4＋2×1＝6）或1个第二层流和一个第三层流（2×1＋4×1＝6），这个degree称为outdegree，在接收端描述的叫indegree。

编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法4、“degree”的参数的重定义

最后确定indegree和outdegree之间的关系，在ALM视频流系统中，每台主机为交换接收服务都要贡献一部分带宽，提供不了多少前向速率的接收就少，因此，主机的indegree限制在小于或等于outdegree：indegree<=outdegree(3)编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法5、Tree结构的建立编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法5、Tree结构的建立Step.1:Sendajoin-requestmassagetothesource

NewparticipanthostNsendsajoin-requestmassagetothesourcewithitsinandoutdegreesinformation.Thesourceaddressanddegreeinformationarealreadyknown.编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法5、Tree结构的建立Step.2:Searchforcandidatesoftheparenthost

Allhostsmaintainthedegreeinformationofitselfanditschildrenandgrand-children.Thehostreceivingthejoin-request(atfirst,thesource)referstoitsdegreeinformationandN.sone,itbecomestheparentcandidateofhostNwheneachofthefollowingtwoconditionsissatisfiedatleast.Otherwise,itforwardstherequestmessagetoitschildrenandthisprocessmightberepeated.编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法5、Tree结构的建立Step.2:Searchforcandidatesoftheparenthost

_N’sin-degree≦its(remaining)out-degree_N’sout-degree≧maximumofitschildrenhosts.outdegreesThesecondconditionisbasedontheconceptthathostswhichhavebigout-degreesshouldbeinhigher-positionofthetree.ThisistheincentiveideaasdescribedpreviouslyinSection4.1.WhenN.sout-degreeisbiggerthanthoseofthechildrenhosts,Nisinhigher-positionofthetreeandcantakemoreadvantageofvariouspointsthanotherhosts.编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法5、Tree结构的建立Step.3:Decidetheparent

TheparentcandidatessendtheirresponsemessagestohostNandhostNmeasuresRTTsrespectively.Then,hostPwhichhastheminimumRTTisdecidedtobetheparenthostofN.编辑ppt应用层组播tree结构的探讨三、Tree结构发展的一种新型算法5、Tree结构的建立Step.4:Exchangelinkconnectionslocally

Underthecondition①atStep2,hostNisconnectedtohostPsimplyandNbecomesa