信息通信专业资料读书报告--两种大规模单源组播方案(NICE和Zigzag)的比较(word版).doc

Application Layer Multicast读书报告 -两种大规模单源组播方案（NICE和Zigzag）的比较1介绍1组播的重要性1IP组播简介1应用层组播简介2应用层组播算法简介32NICE算法6NICE的原理6NICE的拓扑结构6NICE的控制73Zigzag算法8Zigzag算法思想8Zigzag的拓扑结构9Zigzag的控制94NICE与Zigzag的比较11拓扑结构上的比较11系统可靠性的比较12管理维护性能的比较125参考13成员工作说明131介绍组播的重要性组播是网络传输方案的一种，表示传递分组给一组主机，而主机在时间和空间上都有可能有很大的差异。主要有两种组播方式：一对多和多对多方式。 随着网络技术的发展以及网络设备的更新进步，基于网络进行实时或异步的交流成为现实，如网络会议，网络游戏，分布式计算，视频通讯，讨论组等。而这些应用都是基于组播方式之上的，所以，对组播方案的研究成为当前热门的研究领域。IP组播简介IP组播是指在网络层上实现组播方案，IP组播的地址格式不同于普通的IP地址，而是专门的组播地址，1110+28bits(Group id) （IPV4）。IP组播中，发送端只发送一个数据报，路由器接收后负责复制和转发。所以路由器专门为这个组播组维护特定的信息。所有连接有组成员的路由器之间构成一个组播树，以路由转发组播分组。 路由器之间的组播路由协议有DVMRP，PIM等。 对于组成员的加入和退出的控制，通过组播管理协议在主机和路由器之间进行。 IP组播的缺点是：1 路由器必须为每个组播组单独保存状态，这造成IP组播的扩展性很差2 要求所有参加组播的端系统之间的路由器都必须支持组播功能，这给IP组播的推广带来了困难3 试图用一种统一的组播模型来适应所有的应用，而现实中不同的应用对组播的要求差别很大，这给组播算法的设计造成很大的困难4 组播组的管理方法存在缺陷，在组播组的加入、退出和管理等方面开销大，组播组的加入和退出的延迟也很大。当存在大量规模很小的组播组，或者组播成员在空间上的分布很稀疏时，组播组管理上的开销将超过组播在带宽方面上的优势5 对于计费机制来说，很难适用于传统的基于流量计费的方式6 对于安全和拥塞控制方面也存在比较大的问题。应用层组播简介和IP 组播增加网络机制的方法不同，应用层组播的基本思想是仍然保持Internet 原有的简单、不可靠、单播的转发模型，由终端系统来实现组播转发的功能，也就是在应用层之上构建一个重叠的网络，在这个网络上实现组播功能。 应用层组播相对于IP组播的优点：1 便于实现和推广，因为应用层组播只需要改变终端系统，而不需要对网络中的路由器进行任何改变。2 减轻了路由器的负担，路由器一般都会进行很大流量的数据接收和转发，并且维护路由信息，如果对每一个组播组都建立相应的信息并维护它，则路由器会产生很大的负载。所以，应用层组播只需要终端系统进行维护组信息，减轻了路由器的负担。3 便于针对特定的应用进行优化，可以针对不同的应用使用不同的实现方案。 同时，应用层组播相对于IP组播也有如下缺点：1 一般会比IP 组播使用更多的网络资源。2 由于参与转发的终端系统可能不稳定，导致组播转发的可靠性受到影响。3 由于参与转发的终端系统的性能无法保证，可能导致延迟、转发速率等性能的下降。 基于这些特点，目前应用层组播的研究主要集中于视频会议系统、媒体流的分发系统（如视频广播）和订阅/分发系统（Publish/Subscribe System）等。应用层组播的主要应用是实时的多媒体传输。一方面这利用了多媒体信息的性质，即在传输链路质量下降的情况下，用户仍然可以利用收到的低速率的或者不完整的信息，这适用于同一组播组中的多个用户可能接收能力不同的情况。而文件传输等可靠传输则没有这样的性质。另一方面也发挥了组播“时间上集中、空间上分布”的特点。应用层组播算法简介应用层组播算法很多，我们可以按照不同的属性对它们进行分类。1 按照组播网络拓扑结构分类组播网络的拓扑结构主要分为两部分：控制拓扑结构和数据拓扑结构。在应用层组播算法中，位于控制网络中的节点可能并不是组播组中的成员，所以说，控制拓扑是数据拓扑的超集。拓扑结构分为三种：树形结构，网-树形结构和内含式结构。树形结构是指组成员采用自组织形式构建共享组播树，然后各个组成员通过主动探测，发现组播树中的其他节点，并和这些节点保持控制连接。树形结构的优点就在于它的结构比较简单，而且易于建立一棵传输比较高效的组播树（传输路径的长度在logN以内）。树形结构的缺点是必须在维护组播树的算法中判断有没有环路，而且一个节点失效会导致组播树的断裂，从而导致组播的失败，需要有附加的算法来解决。网-树形结构是指组成员分布式的自组织起一个网状的控制结构，在此结构之上，通过路由协议定义成员之间的唯一的路径。数据就是通过路由算法定义的组播树进行分发。网-树形结构的优点就是他不需要对每个源节点所对应的组播树进行维护，对于节点失效可以有效的处理，不需要刻意避免环路。他的缺点是比单纯的树结构要复杂。内含式结构是指使用大规模P2P网络的路由机制创建带有某些特殊属性的控制拓扑。在控制拓扑中就隐含定义了数据转发路径。他比起上两种结构的优点在于每个组成员转发信息不需要使用很完善的路由机制，从而提高了效率，而且每个组成员只需要知道很小一组成员的信息，从而使得网络的扩展性很好。缺点是对效率的考虑比较少，而且如何使得网络的结构适应实际的物理网络结构，是比较耗时和比较难做的事情。根据这三种结构将应用层组播算法划分如下图：2 按照服务的特点分类主要是指各种算法的优点体现在下面几个方面：Without Complete mechanism，end-to-end，reliable transfer，reliable delivery3 按照单/多源节点分类4 按照网络体系结构分类组播网络体系结构主要有两种：P2P和Infrastructure。基于P2P的网络所有方法和实现都是在终端用户上；基于Infrastructure的网络有一个代理服务器负责进行高效的数据分发并且为终端用户提供增值服务。5 按照网络的规模分类2NICE算法NICE的原理NICE算法是基于层次化节点群的思想，将大规模的组播网络分割成不同的层，其中最底层L0包括了所有节点，然后将节点划分为多个节点群（cluster），从每个节点群中选出领导者进入L1层，再将L1层的节点重复同样的事情，直到选出最高层。算法如下：所有节点纳入最底层L0对于当前最高层Li，按照一定算法将其节点划分为多个节点群根据一定算法求出各节点群的领导者，算法是找出距离其他所有节点路径和最小的节点做领导者将选出的领导者纳入L(i+1)层如果当前最高层的节点数目仍然可以划分为节点群，则跳转到，否则，退出。我们可以知道，每个节点需要维护的信息是它所属的所有节点群和它在自己所属的最高层节点群中领导者所属的节点群的信息。NICE的拓扑结构NICE的层次拓扑结构如下图：从图中可以看到，每个节点群的领导者是连接本群其他节点与上层其他节点的桥梁。如C0与A0就通过B0进行连接。而在layer0上，可以看到实际的网络连接情况。从上图，我们可以得到NICE的控制结构如下： 我们可以看出，这个控制的拓扑结构就是小图构成大图的过程。从每一个节点都可以引出一个以其为源点的组播树。引导的过程就是根据其控制结构，由领导节点导出子树的过程。例如，A0的组播树如下： NICE的控制RP节点在NICE的控制中有一个节点RP（Rendezvous Point），它始终是最高层集群的领导节点，RP与其他节点在控制上联系。节点的加入对于节电加入的维护，有如下过程：节点联系RP，获得RP所领导的集群中的成员对于获得集群中的成员，找出节点X，X与其在路径上最接近如果已经到达L0层，则返回；否则，获得X所领导的集群的成员，转向分析：节点加入算法的时间复杂度为O(klogkN)，而其网络延迟是O(logkN)*RTT，因为在加入的过程中，共需要考察k*logkN个节点，而需要与logkN个节点进行联系。新加入的节点可能导致重新选择集群的领导节点，如果这样，原领导者会将自己从其作为领导者的层起向上，逐层删除自身，新领导者会重新加入本层以上各层。每个受影响的层重新选择领导节点。如果新加入的节点导致了集群规模超过最大规模（通常为3k-1）时，需要进行机群的分割。信息的维护位于Li层上的每个成员会周期性的探测L(i+1)层上的节点，如果发现某个节点H距离自己比现在的领导者还要近，则离开现在的集群，加入到H所领导的集群中去。3Zigzag算法Zigzag算法思想Zigzag的分层集群制的思想与NICE是一致的，但是其在数据拓扑上与NICE不尽一致，它的分层集群的控制拓扑结构并不是其数据拓扑结构的超集。在控制上，与NICE相似，每个节点负责向其兄弟节点，孩子节点以及父亲节点传送控制信息，从而达到维护整个结构的目的；而在数据传输上，领导者与其领导的集群节点之间没有数据传输，而是其兄弟节点与其领导的集群节点之间有数据传输。也就是说，物理上的结构与逻辑上的结构完全分开来。Zigzag的拓扑结构Zigzag的层次拓扑结构如下：可以看出其层次结构与NICE的层次结构一致Zigzag的数据拓扑结构如下：本图表现了一个从S出发的数据流的情况，可以看到，与NICE不同的是，数据流从一个节点流向其同集群节点所领导的子集群中去。Zigzag的控制控制协议每个节点负责与其领导节点，同集群节点和其所领导的子集群节点的信息联系。与同集群节点通讯时，如果本节点有数据链路到与其同集群节点所领导子集群节点，本节点将会将此信息传递给同集群节点。如上图，节点5的同集群节点是S,6,7，而5由数据链路连接到S的子群和6的子群节点，所以5会将信息（S，Ss child），（6，6s child）传送给S和6，7。与其领导节点通讯时，本节点将发送Reachable和Addable信息。如果本节点有一条数据路径到L0层节点，则Reachable=true；否则为false。如果本节点所下属的子群中（包括子群节点的子群）有子群的规模还可以扩充（没有满），则Addable为true；否则为false。而所有这些信息都是从其子群节点传来的。节点的加入节点加入的算法如下：1. If X is a leaf2. Add P to the only cluster of X3. Make P a new child of the parent of4. Else5. If Addable(X)6. Select a child Y :Addable(Y ) and D(Y )+d(Y , P) is min7. Forward the join request to Y8. Else9. Select a child Y :Reachable(Y ) and D(Y )+d(Y , P) is min10.Forward the join request to YZigzag节点加入的算法在控制上无需考虑插入节点与原集群节点间的物理路径的远近，这是因为逻辑网络结构与物理网络结构分开的缘故。当节点的插入导致集群规模超标时，同样需要分割。分割算法并不需要一超标就进行，而是周期性的进行。这样，对于动态变化比较快的网络环境，分割的消耗就减小了。分割的过程如图：数据流的负载平衡如果一个节点正在负责向很多子节点传送数据，而造成其负载很重，此节点可以通过方法将一部分与子节点的传输任务分流到其他负载较轻的节点上去。其基于节点度的大小的算法如下：1. For(i = 1; i 0dX - dY - si is max3. If such Y exists4. Redirect non-members of Ci to Y5. Update dX and dY accordingly其基于吞吐量大小的算法如下：（此算法的前提是节电知道同集群节点的带宽B）4NICE与Zigzag的比较拓扑结构上的比较控制拓扑结构在控制拓扑结构上，两者的结构基本一致。在控制信息和算法上，Zigzag需要额外的信息，而且会和较多的节点进行连接，会占用较多的网络资源。数据拓扑结构在数据拓扑结构上，NICE是领导者与其所领导集群节点间的连接，与控制结构一致，这样会减少节点间的连接，但是会增大领导节点的负担，并且，在现有的数据拓扑结构上，很难实现负载的平衡；Zigzag的数据拓扑结构与控制结构互补，会增加节点间的连接，但是可以实现负载平衡，从而使得网络资源得到合理的应用。负载平衡的实现也是有代价的，因为会增加节点连接断开和重连所需要的负担。所以，在Zigzag上也不可一味的追求负载平衡。系统可靠性的比较因为NICE的控制结构和数据结构是一致的，也就是说，数据的转发和集群的管理是同一个节点完成的，所以系统的可靠性会较高，管理也会更加方便。而Zigzag在系统可靠性方面会较低。管理维护性能的比较在节点加入方面，双方的时间复杂度都是O(klogkN)，控制的时间复杂度也都是O(logkN)。在节点失效的恢复负载方面，Zigzag优于NICE。有试验证明，设置一个1000 client节点和一个源server的场景。进行1000次运行，每次都有一个节点失效或者是一个节点加入，也即，一个节点失效的概率为p，则一个节点加入的概率为1-p，且二者是互斥的。实验结果如图：可以看出，在几乎所有的失败概率下，节点失效后的恢复负载，Zigzag优于NICE。在节点失效的状况下节点间的伸展度方面，也即组播的路径长度和单播的路径长度之比方面，Zigzag也优于NICE。5参考1 C.K. Yeo, B.S. Lee, M.H. Er, A survey of application level multicast techniques, Computer Communic