大学课件信息通信专业两种大规模单源组播方案NICE和Zigzag的比较PPT

1、两种大规模单源组播方案（nice和zigzag）的比较 介绍 组播的重要性组播的重要性 ip组播简介组播简介 应用层组播简介应用层组播简介 应用层组播算法简介应用层组播算法简介组播的重要性组播的重要性 组播是网络传输方案的一种，表示传递分组给一组主机，而主机在时间和空间上都有可能有很大的差异。主要有两种组播方式：一对多和多对多方式。 网络会议，网络游戏，分布式计算，视频通讯，讨论组等 介绍 组播的重要性组播的重要性 ip组播简介组播简介 应用层组播简介应用层组播简介 应用层组播算法简介应用层组播算法简介ip组播简介组播简介 ip组播是指在网络层上实现组播方案 发送端只发送一个数据报，路由器接收

2、后负责复制和转发 路由器专门为这个组播组维护特定的信息 所有连接有组成员的路由器之间构成一个组播树，以路由转发组播分组 路由器之间的组播路由协议有dvmrp，pim等 对于组成员的加入和退出的控制，通过组播管理协议在主机和路由器之间进行。 ip组播简介组播简介ip组播的缺点 路由器必须为每个组播组单独保存状态，这造成ip组播的扩展性很差要求所有参加组播的端系统之间的路由器都必须支持组播功能，这给ip组播的推广带来了困难试图用一种统一的组播模型来适应所有的应用，而现实中不同的应用对组播的要求差别很大，这给组播算法的设计造成很大的困难ip组播简介组播简介ip组播的缺点 组播组的管理方法存在缺陷，在

3、组播组的加入、退出和管理等方面开销大，组播组的加入和退出的延迟也很大。当存在大量规模很小的组播组，或者组播成员在空间上的分布很稀疏时，组播组管理上的开销将超过组播在带宽方面上的优势对于计费机制来说，很难适用于传统的基于流量计费的方式对于安全和拥塞控制方面也存在比较大的问题。介绍 组播的重要性组播的重要性 ip组播简介组播简介 应用层组播简介应用层组播简介 应用层组播算法简介应用层组播算法简介应用层组播简介应用层组播简介 基本思想是仍然保持internet 原有的简单、不可靠、单播的转发模型，由终端系统来实现组播转发的功能 在应用层之上构建一个重叠的网络，在这个网络上实现组播功能 应用层组播简介

4、应用层组播简介应用层组播相对于ip组播的优点：便于实现和推广，因为应用层组播只需要改变终端系统，而不需要对网络中的路由器进行任何改变。减轻了路由器的负担，应用层组播只需要终端系统进行维护组信息，减轻了路由器的负担。便于针对特定的应用进行优化，可以针对不同的应用使用不同的实现方案。应用层组播简介应用层组播简介应用层组播相对于ip组播的缺点：一般会比ip 组播使用更多的网络资源。由于参与转发的终端系统可能不稳定，导致组播转发的可靠性受到影响 。由于参与转发的终端系统的性能无法保证，可能导致延迟、转发速率等性能的下降 。介绍 组播的重要性组播的重要性 ip组播简介组播简介 应用层组播简介应用层组播简

5、介 应用层组播算法简介应用层组播算法简介应用层组播算法简介应用层组播算法简介按照组播网络拓扑结构分类应用层组播算法简介应用层组播算法简介按照服务的特点分类应用层组播算法简介应用层组播算法简介按照服务的特点分类应用层组播算法简介应用层组播算法简介按照单/多源节点分类应用层组播算法简介应用层组播算法简介按照网络体系结构分类应用层组播算法简介应用层组播算法简介按照网络的规模分类nice算法 nice的原理的原理 nice的拓扑结构的拓扑结构 nice的控制的控制nice的原理的原理 层次化节点群 算法：所有节点纳入最底层l0对于当前最高层li，按照一定算法将其节点划分为多个节点群根据一定算法求出各节

6、点群的领导者，算法是找出距离其他所有节点路径和最小的节点做领导者将选出的领导者纳入l(i+1)层如果当前最高层的节点数目仍然可以划分为节点群，则跳转到，否则，退出。nice算法 nice的原理的原理 nice的拓扑结构的拓扑结构 nice的控制的控制nice的拓扑结构的拓扑结构 层次拓扑结构 nice的拓扑结构的拓扑结构 控制结构 nice的拓扑结构的拓扑结构 数据结构 nice算法 nice的原理的原理 nice的拓扑结构的拓扑结构 nice的控制的控制nice的控制的控制 rp节点节点 节点的加入节点的加入 节点联系rp，获得rp所领导的集群中的成员 对于获得集群中的成员，找出节点x，x与

7、其在路径上最接近 如果已经到达l0层，则返回；否则，获得x所领导的集群的成员，转向nice的控制的控制 重新选择集群的领导节点重新选择集群的领导节点 机群的分割 zigzag算法 zigzag算法思想算法思想 zigzag的拓扑结构的拓扑结构 zigzag的控制的控制zigzag算法思想算法思想 在数据拓扑上与nice不尽一致 分层集群的控制拓扑结构并不是其数据拓扑结构的超集 每个节点负责向其兄弟节点，孩子节点以及父亲节点传送控制信息，从而达到维护整个结构的目的 zigzag算法思想算法思想 在数据传输上，领导者与其领导的集群节点之间没有数据传输，而是其兄弟节点与其领导的集群节点之间有数据传输

8、 物理上的结构与逻辑上的结构完全分开来 zigzag算法 zigzag算法思想算法思想 zigzag的拓扑结构的拓扑结构 zigzag的控制的控制zigzag的拓扑结构的拓扑结构zigzag的拓扑结构的拓扑结构 数据拓扑结构数据拓扑结构 zigzag算法 zigzag算法思想算法思想 zigzag的拓扑结构的拓扑结构 zigzag的控制的控制zigzag的控制的控制 控制协议控制协议 每个节点负责与其领导节点，同集群节点和其所领导的子集群节点的信息联系 与同集群节点通讯时，如果本节点有数据链路到与其同集群节点所领导子集群节点，本节点将会将此信息传递给同集群节点。 与其领导节点通讯时，本节点将发

9、送reachable和addable信息 。zigzag的控制的控制 节点的加入节点的加入 1. if x is a leaf 2. add p to the only cluster of x 3. make p a new child of the parent of 4. else 5. if addable(x) 6. select a child y : addable(y ) and d(y )+d(y , p) is min 7. forward the join request to y 8. else 9. select a child y : reachable(y ) a

10、nd d(y )+d(y , p) is min 10.forward the join request to y。zigzag的控制的控制 节点的加入节点的加入 zigzag节点加入的算法在控制上无需考虑插入节点与原集群节点间的物理路径的远近，这是因为逻辑网络结构与物理网络结构分开的缘故 分割算法 zigzag的控制的控制 数据流的负载平衡数据流的负载平衡 基于节点度的大小的算法 1. for(i = 1; i 0 dx - dy - si is max 3. if such y exists 4. redirect non-members of ci to y 5. update dx and dy accordinglyzigzag的控制的控制 数据流的负载平衡数据流的负载平衡 基于吞吐量大小的算法nice与zigzag的比较 拓扑结构上的比较 控制拓扑结构控制拓扑结构 在控制拓扑结构上，两者的结构基本一致。 在控制信息和算法上，zigzag需要额外的信息，而且会和较多的节点进行连接，会占用较多的网络资源。 数据拓扑结构数据拓扑结构 nice是领导者与其所领导集群节点间的连接 。 zigzag的数据拓扑结构与控制结构互补 nice与zigzag的比较 系统可靠性的比较系统可靠性的比较 因为nice的控制结构和数据