《【大学课件】信息通信专业 应用层组播tree结构的探讨.ppt》由会员分享，可在线阅读，更多相关《【大学课件】信息通信专业 应用层组播tree结构的探讨.ppt（49页珍藏版）》请在三一办公上搜索。
1、应用层组播tree结构的探讨,应用层组播tree结构的探讨,一、综述,1、组播算法,组播算法的基本出发点是：在存在多个接收者的时，通过合并重复信息的传输来达到减少带宽浪费和降低服务器处理负担的目的。,应用层组播tree结构的探讨,一、综述,2、应用层组播的提出,近年来，随着Peer-to-Peer Network 和Overlay Network 等技术的提出，出现了“应用层组播”（ALM:Application Layer Multicast）这样一个研究方向。,应用层组播tree结构的探讨,一、综述,3、应用层组播的主要思想,保持Internet原有的“单播、尽力发送”模型，尽量不改变原来
2、网络的体系结构，而主要通过增加端系统的功能来实现组播的功能。由于对网络本身的改变很少，应用层组播具有很好的灵活性。但是，端系统的稳定性一般不如专用网络设备，应用层组播在带宽利用效率方面也无法和IP组播相比。另外，应用层组播中的系统框架和很多细节技术也还在研究当中。这些问题的存在为应用层组播的研究提供了广阔的空间。媒体编码技术、Peer-to-Peer 和Overlay Network等技术的发展对应用层组播的研究也有很大的促进作用,应用层组播tree结构的探讨,一、综述,4、应用层组播和IP组播的不同,和IP 组播增加网络机制的方法不同:应用层组播的基本思想是保Internet 原有的简单、不
3、可靠、单播的转发模型，由端系统来实现组播转发的功能。这也是著名的”end-to-end argument”所倡导的思想。,应用层组播tree结构的探讨,一、综述,5、应用层组播算法的设计中的假设,(1)网络中的带宽和转发资源是相对丰富的，而服务器的能力是一个主要瓶颈。使用应用层组播会比IP 组播消耗更多的带宽，但是和单播方案相比，它还是可以有效的降低服务器的负载和减少带宽的使用。,应用层组播tree结构的探讨,一、综述,5、应用层组播算法的设计中的假设,(2)大多数参与组播的端系统可以贡献出一部分资源用于组播的转发。这个假设并不是针对所有的应用层组播算法，但是不少的应用层组播算法都有这个假设。
4、,应用层组播tree结构的探讨,一、综述,5、应用层组播算法的设计中的假设,(3)上层应用对性能的要求并不很苛刻，可以容忍报文的丢失和较大的延迟。Internet 的可靠性本来就无法完全保证，参与组播的主机性能也无法保证。所以，应用层组播并不针对所有的应用，而主要针对那些对可靠性和性能要求较低的应用。,应用层组播tree结构的探讨,一、综述,6、应用层组播的主要优势,（1）应用层组播便于实现和推广。它只需要改变端系统，而不需要对路由器进行任何修改。（2）应用层组播便于针对特定应用进行优化，可以针对不同的应用使用不同的实现方案，而不必象IP 组播那样必须统一到一个模型中。,应用层组播tree结构
5、的探讨,一、综述,7、应用层组播的主要缺点,（1）一般会比IP 组播使用更多的网络资源。（2）由于参与转发的端系统可能不稳定，导致组播转发的可靠性受到影响。（3）由于参与转发的端系统的性能无法保证，可能导致延迟、转发速率等性能的下降。,应用层组播tree结构的探讨,一、综述,8、应用层组播的主要应用,基于这些特点，目前应用层组播的研究主要集中于视频会议系统、媒体流的分发系统（如视频广播）和订阅/分发系统（Publish/Subscribe System）等。应用层组播的主要应用是实时的多媒体传输。一方面这利用了多媒体信息的性质，即在传输链路质量下降的情况下，用户仍然可以利用收到的低速率的或者不
6、完整的信息，这适用于同一组播组中的多个用户可能接收能力不同的情况。而文件传输等可靠传输则没有这样的性质。另一方面也发挥了组播“时间上集中、空间上分布”的特点。,应用层组播tree结构的探讨,一、综述,Overlay是一个应用层组播解决方案的完整的部分，它是影响多点通信的基本机制。其节点可以逻辑地组织成两种拓扑结构，即控制拓扑和数据拓扑。控制拓扑携带控制信息，如heartbeat信息，更新信息，网络探测和探测数据等。数据拓扑由实际数据交付至多端的路径组成。控制拓扑的节点不必是多播组成员，因此控制拓扑是数据拓扑的超集，他是大多数采用tree结构的数据拓扑的标准，而且是易于建立和有效的。控制拓扑假定
7、一个mesh形式的分离的物理结构，在这个结构中，拓扑里的节点占用较高的连接，或者像数据拓扑一样分享同一结构。依据采用的途径，overlay拓扑可以分成三个部分：tree，Mesh-Tree，植入结构。,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（1）应用层组播体系(Application Layer Multicast Archetecutre,ALMA)早期的ALMA版本依据网络距离如RTT(round trip time)，选择离自己最近的节点作为自己的父节点。在新的版本中，ALMA依据丢失率和RTT的共同考虑来选择父节点。组成员定期向DS
8、提供它们的丢失率。通过端对端的测量方法收集成员至成员的RTT。Gossip-style算法用来在成员离开tree时的分割恢复。组成员通过定期地和一些gossip candidates交换丢失率和RTT以选择更好的父节点。,应用层组播tree结构的探讨,图1 ALMA结构。,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（2）香蕉tree协议（Banana Tree Protocal,BTP）BTP利用基于接收的、自组织的途径建立共享数据tree。它被设计用来分布式文件共享应用。第一个加入组的主机成为tree的根，后加入的新成员学习根并加入到tree
9、中。其算法是允许一个节点转到一个同属节点，如果该同属节点比这个节点的父节点更接近该节点。同属节点在每个节点内维护的信息由节点的父节点更新。,应用层组播tree结构的探讨,图2显示同属节点转换可以降低tree开销。,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（2）香蕉tree协议（Banana Tree Protocal,BTP）满足以下两个条件：其一，当一个节点在自己转换进程中能够拒绝其他所有的转换尝试；其二，节点必须把当前父节点的信息包含在转换请求中以便潜在的父节点能确认其为真正的同属节点。能防止如图3中的同时转换引起的循环和图4中的过期信息
10、引起的循环。,应用层组播tree结构的探讨,图3 同时转换引起的循环,应用层组播tree结构的探讨,图4 过期信息引起的循环,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（3）主机多播（Host Multicast,HM）HM的目的是用以提供应用中的高效的多播交付服务和能于ip多播在最大程度上的共容。它自动连接IP多播岛并通过单播隧道提供多播给不能多播的端主机。经由指定成员（Designated Member,DM）之间的UDP隧道，多播岛就连接起来了，每一个岛选择一个DM。,应用层组播tree结构的探讨,图5 HM结构,应用层组播tree结构的
11、探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（3）主机多播（Host Multicast,HM）数据分配tree是共享tree，任何成员都可以成为一个源。HM利用分布式tree建立协议来度量组成员的数量。,应用层组播tree结构的探讨,图6 在共享树上新成员H通过集合点（Rendezvous Point,RP）发现根A,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,（3）主机多播（Host Multicast,HM）图6显示的是在共享树上新成员H通过集合点（Rendezvous Point,RP）发现根A。H把A当作潜在的父
12、节点并请求A的子节点列表，沿着树径一路搜索下来，根据距离A最近的原则，H选择F作为自己的父节点。HM中的每一个成员都维护其到根节点A的路径信息。每一个成员都要定期通过阻止一些来自根路径上的随机成员的加入进程来寻找跟近的父节点。HM利用循环探测机制代替循环避免机制。为了从树分割中恢复，每一个成员都可以重新加入任何一个新成员在它的根路径或者缓存上，缓存在成员沿着树径“走”下来的初始进程中建立。,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,(4)重叠网多播网络结构（Overlay Multicast Network Infrastructuer,OMN
13、I）OMNI从一组多播服务节点（multicast service nodes,MSN）建立一个单一源节点树结构,如图7所示。重叠网tree的建立过程包括一个在数据交付开始前的离线初始化阶段和数据交付过程中的动态的自组织进程。OMNI的关键特性是关键基于服务组大小（所服务的客户机数量）的不同的MSN的动态优先级来迭代优化重叠网tree，动态自组织进程如图8所示。,应用层组播tree结构的探讨,图7 OMNI从一组多播服务节点（multicast service nodes,MSN）建立一个单一源节点树结构,应用层组播tree结构的探讨,图8 动态自组织进程,应用层组播tree结构的探讨,二、关
14、于tree的一些概念和分析,1、几种常见的tree结构,(4)重叠网多播网络结构（Overlay Multicast Network Infrastructuer,OMNI）在开始的结构MSN0到MSNx的时延是59ms，客户机增加，MSN的重要性也相应地增加，它首先把父节点改到MSN6上将时延降为54ms，然后改到MSN0上降为51ms。随后其客户减少，x也就从树上往下移动，同时有其他MSN的客户的增加引起其上移，为了协调时延，每个MSN之间定期交换，在交换能减少当前平均时延的情况下，交换仅限于两层之间的交换。,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的t
15、ree结构,（5）Tree Building Control Protocal(TBCP)TBCP的目的是提供高效和分布式的协议来为应用层多播建立控制数据交付tree。如图9所示，新成员M像C1，C2，C3一样要加入到P上，如果最新的结构是最优的，M加入到P，而C3则要重新开始加入过程最后加入到M上。,应用层组播tree结构的探讨,图9,应用层组播tree结构的探讨,二、关于tree的一些概念和分析,1、几种常见的tree结构,另外还有Application Level Multicast Infrastructure，Overcasts等树结构。,应用层组播tree结构的探讨,三、Tree结
16、构发展的一种新型算法,1、利用分层编码主要存在的问题,其一，是由于流技术的特性限制，子节点的接收率是不能超过父节点的接收率，如图1所示，主机B是主机A的子节点，即便B有更高的下载带宽也不能获得更高的数据速率，因为A的速率不高。在这种情况下，分层编码不能充分利用而且每台主机在选择父节点时必须谨慎。,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,1、利用分层编码主要存在的问题,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,1、利用分层编码主要存在的问题,其二，寻找一个适当的父主机是很复杂的，通常，新加入ALM tree的主机都是叶子主机，它通过交换带宽信息搜
17、寻邻居主机，并找到拥有自己需要的前向数据速率的主机。然而，这种进程是复杂而费时的。而且因为其加入tree中只能获得重叠网的本地信息的缘故，它将很难通过适当的方式得到端主机。,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,2、“degree”的参数,它原本是描述一台父主机能维护多少台主机。其数值取决于父主机的前向吞吐量。一台主机i的前向吞吐量是Fi，单一流数据率是R，degree值Di的表达式为 DiFi/R（1）,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,3、解决分层编码存在的问题,为了解决利用分层编码主要存在的问题，这里重定义“degree”的参数
18、。以使每台主机能够恰当地决定自己的父主机，利用这个方法的一个好处就是这个值是事先知道的，因此每个新成员加入ALM tree时不必再搜索父主机，显而易见地，通过这种参数方法，当父主机离开tree时，不是所有的后代主机决定他们的父主机。图2，显示的是所有主机的degree是2，主机B（或A）将不能再连到G上因为父节点P的离开，它必须搜寻另一台有未使用degree的主机。最简单的方法是向新加入成员那样，重新加入tree中，但是这会消耗很多恢复时间和overhead。,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4
19、、“degree”的参数的重定义,在互联网上，一个边缘路由器和每台主机之间的访问连接特别是上行连接的带宽通常比干线连接窄。因此，一般考虑发送端主机连接是P2P网络的瓶颈，基于这一点，degree限制参数描述的是如（1）式所述的父主机拥有多少主机。这样就很容易参考这个参数来决定一个新成员是否加入父主机，在ALM的分层编码的应用中，流速率R不是固定不变的，需要重新定义。,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、“degree”的参数的重定义,首先，用R1代替R，R1为基层速率Di=Fi/R1(2),应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、
20、“degree”的参数的重定义,其次，R1假定为1，实时数值比例提供的每一层“积累”速率赋予R1，新的degree描述父主机拥有的流的数量，例如，多播流速率为50,50,100kbps,主机I的发送吞吐量为300kbps,根据（2）式，主机的degree为6，积累速率的比率为1：2：4，这样，主机I有4个基层流和1个第二层流（14216）或1个第二层流和一个第三层流（21416），这个degree称为outdegree，在接收端描述的叫indegree。,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,4、“degree”的参数的重定义,最后确定indegree和outdeg
21、ree之间的关系，在ALM视频流系统中，每台主机为交换接收服务都要贡献一部分带宽，提供不了多少前向速率的接收就少，因此，主机的indegree限制在小于或等于outdegree：indegree=outdegree(3),应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.1:Send a join-request massage to the source New participant host N sends a join-request massag
22、e to thesource with its in and out degrees information.The sourceaddress and degree information are already known.,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.2:Search for candidates of the parent host All hosts maintain the degree information of itself and itschildren and grand-children.The h
23、ost receiving the join-request(at first,the source)refers to its degree information and N.s one,it becomes the parent candidate of host N when each of thefollowing two conditions is satisfied at least.Otherwise,itforwards the request message to its children and this processmight be repeated.,应用层组播tr
24、ee结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.2:Search for candidates of the parent host _ Ns in-degree its(remaining)out-degree_ Ns out-degree maximum of its children hosts.outdegreesThe second condition is based on the concept that hosts whichhave big out-degrees should be in higher-position of the t
25、ree.This is the incentive idea as described previously in Section 4.1.When N.s out-degree is bigger than those of the children hosts,N is in higher-position of the tree and can take more advantageof various points than other hosts.,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.3:Decide the paren
26、t The parent candidates send their response messages to host Nand host N measures RTTs respectively.Then,host P which hasthe minimum RTT is decided to be the parent host of N.,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Step.4:Exchange link connections locally Under the condition at Step 2,host N i
27、s connected to host Psimply and N becomes a leaf host.Under the condition,Pneeds to exchange connections in the local area which includeshosts from P to P.s grand-children based on the degree and Ncan join any host of them.At this time,their total out-degree ofthem are equal to or bigger than total
28、in-degrees because of(3).Thus,this process can be completed locally.,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Recovery phase,应用层组播tree结构的探讨,三、Tree结构发展的一种新型算法,5、Tree结构的建立,Recovery phase our proposal is that all new participant hosts memorize(cache)their parent candidates which are found at Step 2
29、,andrequest from one which has the second minimum RTT of them toreconnect directly when their ancestors depart the tree as Figure 5shows.This new parent host(host P2)also can send data to hostN at the rate which host N desires and host P2 is near host Npractically,too.In this way,descendants of the departing hostonly execute Step4 and can shorten the recovery time andoverhead.,
