高级计算机网络.ppt

《高级计算机网络.ppt》由会员分享，可在线阅读，更多相关《高级计算机网络.ppt（68页珍藏版）》请在三一文库上搜索。

1、2019/4/2,史忠植 高级计算机网络,1,高级计算机网络,2019/4/2,史忠植 高级计算机网络,2,内容提要,6.1 概述 6.2 IP 多播协议 6.3 多播路由 6.4 扩散技术 6.5 跨越树的多播路由算法 6.6 约束Steiner 树 6.7 反向路径广播 6.8 截断的反向路径广播 6.9 反向路径多播,2019/4/2,史忠植 高级计算机网络,3,内容提要,6.10核心树 6.11路由多播选择算法KMB 6.12 动态多播路由选择算法VTDM 6.13 限界最短多播算法BSMA 6.14 适用于光纤网络的多播的MZQ算法 6.15 多播的应用,2019/4/2,史忠植 高

2、级计算机网络,4,6.1 概述,将分组同时发往所有目的地称做广播（broadcasting）。 单源，多目的的通信方式称之为多点通信（multipoint communication），通常只在分叉的时候复制信息，又称为多播（multicast）。 在单播的环境下，每个结点一次只能给另一个结点发出信息。在多播的环境下，每个结点一次可以有效的把一个打包的信息同时发往多个目标。必须有支持IP多播的结点处理系统和TCP/IP栈，网络中的结点才能顺利的进行多播。,2019/4/2,史忠植 高级计算机网络,5,6.1 概述,多信道IP包和单信道IP包的主要在于头部目标地址域的“组地址”，多播使用D类地址

3、，也就是在244.0.0.0-239.255.255.255之间的地址。多播的特性： 1. 可靠性：对不同类型的应用是否有不同的可靠性模型？ 2. 允许动态加入和离开：每个对话过程必须是接受者可控制的。 3. 地址： 在每层上如何对各组编址 在IP层以上的各层是否需要标识组，如果需要，怎样标识？ 4. 方向性： 一对多 或者 多对多 转送者是否是接受者的一个子集？,2019/4/2,史忠植 高级计算机网络,6,6.1 概述,2019/4/2,史忠植 高级计算机网络,7,6.1 概述,2019/4/2,史忠植 高级计算机网络,8,6.2 IP 多播协议,80年代开始研究，1988年Stanfor

4、d大学实施了第一次多目通话，1992年Internet 程特别小组（IETF）定义和发布了一个多播的网络标准，用于建立多播主干网（MBONE），即在Internet上运行的单路广播和多播综合网络。MBONE于1993年刹那间名声远扬。1995年，Cisco公司和Lucent公司开始销售支持多播的路由器和交换机，一年后依赖多播的应用产品开始上市。 IP多播的最早实施方案依赖于传统的竭尽全力方法和User Datagran Protoco1，但它们不能保证多播数据流的可靠传输。,2019/4/2,史忠植 高级计算机网络,9,6.2 IP 多播协议,HP的Internet群管JF协议（LGMP） P

5、rotocol Independent Mu1ticast、 Mu1ticast Border Gateway Protocol Hierarchical DVMRP（Distance Vector Multicast Routing Protocol）,2019/4/2,史忠植 高级计算机网络,10,6.3多播路由,共享树（shared tree） 源根结点的最短路径树（SRSPT： source rooted shortest path tree）。,2019/4/2,史忠植 高级计算机网络,11,共享树（shared tree）,共享树方法中使用一个中央多播路由器，有时候又称为核心路由器

6、。需要进行多播的源结点将他们所要传递的信息包都传给这个核心路由器，然后由这个核心路由器通过一棵共享树将信息包一个一个的传给组中的每一个接收结点。每个组中只要建立一棵共享树就可以了，而不是象在SRSPT中需要为组中的每个源结点建立一棵树。与SRSPT算法相比，共享树对路由器和网络带宽（bandwidth）的需求更小。在CBT和PIM协议中使用共享树的思想来传递信息包。,2019/4/2,史忠植 高级计算机网络,12,源根结点的最短路径树,这种源根结点的最短路径树只能建立在具有多播功能的路由器上。它为每个组中的每个源结点建立一棵树，这棵树以该传送结点为根，使其与所有的接收结点相连。一般而言，该组中

7、有多少个源结点，就需建立多少棵这样的树。 一棵这种基于源结点的树将一个特定的源结点与所有的接收结点相连，并被称为“源根结点的最短路径树”。这些路径并不需要通过一个特定的中央多播路由器。等到由协议将一棵这样的树建成后，这棵树的源结点就可以沿着这棵树上的路径将所要传递的信息传到它的每一个接收结点。,2019/4/2,史忠植 高级计算机网络,13,SRSPT树的优点,（1）使用经典的单信道路由表很容易计算SRSPT树； （2）可以有效的实现分布式处理不需要整个网络的拓扑结构； （3）返回的路径中不会存在回路。,2019/4/2,史忠植 高级计算机网络,14,SRSPT树的缺点,（1）没有最小化整个分

8、布式处理的代价； （2）可伸缩性不好； （3）在每个路由器上都要保存每个组中每个源结点的SRSPT树的信息； （4）如果下层的单信道路由是非对称的则可能会导致失败。,2019/4/2,史忠植 高级计算机网络,15,性能指标,(1) 低延迟。将源结点到目的结点的端到端的延迟与点到点的单信道最短路径的延迟相比较； （2）低代价。全部的带宽消耗以及保存树状态信息所需的代价； （3）轻的网络拥塞,2019/4/2,史忠植 高级计算机网络,16,多点路由算法的需求,（1）支持可靠的传输。连接失败不应该增加延迟或者减少可用的资源 （2）对于得到最佳路由所需要的一些考虑。 1：所需付出的代价（对带宽的消耗）

9、 2：端到端的延迟（所需跨越的结点数） （3）最小化对网络的负担。 1：避免回路 2：避免在一些连接或子网上出现网络拥塞 （4）最小化在路由器中所需存储的状态数量。,2019/4/2,史忠植 高级计算机网络,17,密集模式,密集模式假设多播组的成员密集分布在网络中，每个子网至少含一个成员。密集模式还需要充足的带宽。DVMRP, MOSPF和PIM-DM都是密集模式路由选择协议。密集模式路由选择协议依靠扩散（flooding）技术把信息传播到整个网络的路由器上。,2019/4/2,史忠植 高级计算机网络,18,稀疏模式,假设多播组的成员稀疏分布在网络中，而且网络可以提供的带宽不是很宽裕。在稀疏模

10、式下，用户可能分散在Intent的各个部分，也可能是被ISDN专线连接起来的。这种模式下用户不一定很少，只是它们分散的范围很广。,2019/4/2,史忠植 高级计算机网络,19,6.4 扩散技术,1 路由器接收到要发往多播组的一个报文。 2 路由器用协议机制决定这是不是第一次收到该报文。 3 如果它是第一次收到该报文，路由器将该报文发往Internet上除了它的来源的所有接口。这保证了多播报文将到达所有的路由器。 如果路由器以前曾收到该报文，就把它丢弃。,2019/4/2,史忠植 高级计算机网络,20,扩散技术局限性,1扩散技术不适用于大规模网络，如Internet。 2同样不适用于广域网，因

11、为它产生大量复制包。 3扩散技术使用Internet网上的所有可用路径，网络上所有路径的流量容易引起拥塞。 4因为每个路由器必须为最近接收的包维护一张表，所以并不是很有效的使用路由器的内存。,2019/4/2,史忠植 高级计算机网络,21,建立生成树的步骤,1选择一转送设备作为根：刚开始所有的转送设备先假设自身为根，告诉其他设备它作为根连接。 总的来说，优先级低的设备设为根。如果优先级相同，MAC地址低的设备设为根。 2估计路径成本：如果一转送设备接到另一设备的包，认为存在更好的路径，就不再告诉别的设备自身是根，而是告诉别的设备更优的根。 3选择根端口，并且在每个局域网制定一个转送设备：最终，

12、每个设备都认同了最佳转送设备，该设备就成为根。 设备的根端口提供了指向根转送设备的最低成本路径。路径成本相同时，端口接头优先级低的成为根端口。如果接口优先级再相同，具低优先级的设备上的断口为根端口。 4. 每个子网指定一个端口（路由器）：生成树算法设指定连接转送设备和局域网的端口位置顶端口。尤其当子网上的设备靠近根时。,2019/4/2,史忠植 高级计算机网络,22,建立生成树的步骤,2019/4/2,史忠植 高级计算机网络,23,建立生成树的步骤,2019/4/2,史忠植 高级计算机网络,24,6.7 反向路径广播,无论是子网上哪一个源，反向路径广播（reverse path broadca

13、sting, RPB）算法针对每一个组建立一棵生成树，提供了源和组的成员之间的有效路径。这样的生成树根植于直接和源连接的子网上，意味着每个活跃的源-组队都有一棵生成树。路由器利用逆向路径广播算法建立根植于源的树,2019/4/2,史忠植 高级计算机网络,25,反向路径广播转送算法,2019/4/2,史忠植 高级计算机网络,26,反向路径广播转送算法,链接状态路由选择协议使用拓扑数据库来确认相邻的路由器是否在子链接上，也就是考虑该路由器是否在相邻路由器回溯到源的最短路径上。 距离向量路由选择协议使用邻居发布的源-组对的前一站距，或者翻转该路由来决定下一相邻路由认为该路由在到源的最短路径上。,20

14、19/4/2,史忠植 高级计算机网络,27,反向路径广播的例子,2019/4/2,史忠植 高级计算机网络,28,反向路径广播的例子, 从路由器A收到报文，确认连接1是源-组对的父母链。 把报文发往任何含有小组成员的叶子子网，如发往连接4、连接5。 从路由选择信息交换中得知路由器C认为连接2是源-组对的父母链，于是不再将报文发往连接3。 路由器C将丢弃从连接3来的报文，因为是从源-组对的非父母链上来的。,2019/4/2,史忠植 高级计算机网络,29,6.8 截断的反向路径广播,截断的反向路径广播（truncated reverse path broadcasting, TRPB）改进了上一个算

15、法中不考虑多播组的成员限制的问题。它使用了IGMP来决定某个子网上是否存在该广播组的成员，并以此为依据截断原来构造的跨越树上的一些枝叶。一旦弄清楚这一点，TRPB不再往不含组成员的叶子网上发送报文。路由器从扩展传送树上剪除不含组成员的叶子网，这一排除不在最短路径上的接口的过程称为“截断”。,2019/4/2,史忠植 高级计算机网络,30,截断的反向路径广播算法的例子,2019/4/2,史忠植 高级计算机网络,31,TRPB,源通过父路由器连接入路由器，多播组的成员第一组用G1表示、第二组G2、第三组G3与路由器下属的转送装置相连。 当路由器接收了源-G1对的一多播报文，它将： 因为接口2至少含

16、有第一组的一个成员，路由器把报文发往接口2。 当且仅当该路由器的一个下属路由器认为接口3是它的源-G1对的父母链的一部分，该路由器才把报文发往接口3。 接口4没有目标组的成员，报文不发往接口4。 TRPB虽然避免了叶子网中的不必要的流量，但是在建立分配树的枝干的时候没有考虑是否含组成员的问题。,2019/4/2,史忠植 高级计算机网络,32,6.9 反向路径多播,反向路径多播（reverse path multicasting,RPM）是对于RPB和TRPB的改进。具体而言，如果一个接收接口可以用于向多播报文的源发送单信道广播报文，路由器向除了接收接口以外的所有接口发送多播报文。 换句话说，R

17、PM建立的传送树只覆盖了广播组成员和到含广播组成员子网最短路径沿途径过的路由器和子网。RPM截断了根植于源的生成树，路由选择协议只向通往目标组成员的枝干发送报文。,2019/4/2,史忠植 高级计算机网络,33,RPM,2019/4/2,史忠植 高级计算机网络,34,工作原理,上级路由器收到截断信息后储存起来。如果从所有的子链收到截断信息，该路由器也往它的上级路由器发送截断信息。这个过程产生的多播树只含有通向活跃组成员的枝干。 协议不时的更新多播树，更新后每个路由器清除内存中的所有剪除信息，并且将受到的下一个多播报文送往所有的子链。这样又重新开始了定义多播树的新一轮过程。,2019/4/2,史

18、忠植 高级计算机网络,35,工作原理,组成员的动态特征意味着树需要定期的更新。也就是说，多播报文必须定期的发往Internet网络中的每个路由器。这就使得在大规模传送服务如在Internet上的传送问题不容忽视，而且，每个路由器必须保留关于源和组的所有状态信息。尽管这对于小网络来说不构成威胁，但是当源的数目和多播组成员大幅增加时就是一个严重的问题。,2019/4/2,史忠植 高级计算机网络,36,6.10 核心树,核心树（core-based tree, CBT）算法将建立一棵被小组中所有的发送者和接收者共享的传送树(图6.10)，而不是为每一个源-组对建立一棵树。使用CBT算法时，无论报文是

19、从那个源发出的，路由器将多信道信息沿着相同的传送树来传递。 共享树途径最显著的优势是能够很好的适应大规模网络。然而，CBT可能导致在核心路由器附近的流量集中和瓶颈问题。这是因为从任意源结点发出的信息在接近核心时，都沿着相同的连接。,2019/4/2,史忠植 高级计算机网络,37,CBT,2019/4/2,史忠植 高级计算机网络,38,设计目的,(1) CBT是用于大规模网络，处理过程中只需要少量的内存和带宽资源。因为CBT不针对于源，尤其适合于多发送者的应用程序。 (2) CBT时健壮的多播路由选择算法。为了获得健壮的多播传送树，核心将放置在最佳位置。 (3)和其他多播路由选择协议比较而言，C

20、BT协议比较简单。简单性能导致性能的提高。 (4)CBT路由选择算法适度利于协议的。任何地方都可以安装，并且支持域间多信道路由选择。CBT与CBMRP有着良好的协同工作的机制，CBMRP是一种能够普遍连接不同种类的多播域的协议。,2019/4/2,史忠植 高级计算机网络,39,当一主机成为多播组的成员将执行以下步骤,(1)主机向所有连接广播一IGMP主机成员报告。 (2)附近的一个具CBT算法的路由器唤醒加入树的过程： 产生JOIN_REQUEST信息 将信息发往沿着导向组的核心路由器的路径的下一个站点。 (3)核心路由或发送路由和核心路由之间的另一路由器确认该信息。,2019/4/2,史忠植

21、 高级计算机网络,40,当一主机成为多播组的成员将执行以下步骤,(4)请求加入的信息在它穿过的路由器暂时建立加入状态，包括组、进入的接口和连出的接口。所有中间路由器处理加入请求： 确认加入请求是从那个接口接收的。 告知信加入的主机CBT传送树。 (5)临时状态如果没有接到从上游传来的确认信息，将最终超时。因为有临时加入状态，加入确认可以沿着加入请求来的路径返回。 (6)一旦加入确认到达产生加入请求的路由器，发向这个组的信息将同时发往这个新的接收者。,2019/4/2,史忠植 高级计算机网络,41,CBT,(4)请求加入的信息在它穿过的路由器暂时建立加入状态，包括组、进入的接口和连出的接口。所有

22、中间路由器处理加入请求： 确认加入请求是从那个接口接收的。 告知信加入的主机CBT传送树。 (5)临时状态如果没有接到从上游传来的确认信息，将最终超时。因为有临时加入状态，加入确认可以沿着加入请求来的路径返回。 (6)一旦加入确认到达产生加入请求的路由器，发向这个组的信息将同时发往这个新的接收者。,2019/4/2,史忠植 高级计算机网络,42,6.11路由多播选择算法KMB,理想化的多播路由选择算法应该是： 构建树时具有所想要的成本和延迟特征。 算法可以适用于广播组的成员增加的情况（如CBT），而不是每次成员增加都需要更新（如SMT）。 维护原始路由的特性。 不干扰正在进行的数据传送。 是由

23、接收者驱动的。,2019/4/2,史忠植 高级计算机网络,43,问题的形式化定义,给定图 G = (V, E, c) V= 顶点集 E= 边集 c= 成本函数 c: E Z0+ ( 边 非负整数) Z-顶点集: 终结集合(有时用M表示) S-点集: 非终结集合 TO: 初始树 = s. Q : 树上顶点的优先级队列 Vt: 树上顶点 At: 树上边,2019/4/2,史忠植 高级计算机网络,44,Dijkstra最短路径算法,Begin. vV, 将v加到集合U, Distance(v) = cost(s, v) Distance(s) = 0; 从U中删除s. while U 不为空 do

24、具有最小距离的任何G的成员v. U=U-v. For 每个v的近邻 w , do if member(w, U) distance(w) = min(distance(w), cost(w, v) + distance(v) ); Stop.,2019/4/2,史忠植 高级计算机网络,45,Matsuyama最短成本路径启发式算法,Begin T1 : 包含任选的iZ的G的子树 . k = 1; Zk=i. 找到离 Tk 最近的i Z - Zk 在Tk 的基础上加入从Tk 到 I的最短路径建树Tk+1 k = k+1. If k p, 转T1. If k = p, 输出结论 Tp Stop.,

25、2019/4/2,史忠植 高级计算机网络,46,KMB 算法,输入：图G和顶点集Z 输出：Steiner树Th 步骤： 1由G和Z建立完全有向带权图G1=（V1，E1，c1）。 2找到G1的最小生成树。 3用G中相应的最短路径替换T1中的一边，建立G的子图Gs。 4找到Gs的最小生成树Ts。 5. 如必要的话删去Ts中的边，构建Steiner树Th，使得Th中所有的叶子为Steiner点。,2019/4/2,史忠植 高级计算机网络,47,KMB算法,KMB算法最坏时间复杂度 O（|S|V|2）。成本不大于2（1-1/l）最优成本，其中 l = Steiner树的叶结点数。,2019/4/2,史

26、忠植 高级计算机网络,48,KMB算法的工作过程,2019/4/2,史忠植 高级计算机网络,49,KMB算法的工作过程,2019/4/2,史忠植 高级计算机网络,50,成本建模,W (e, i ): 边e上波长为i的成本。 如果边e上i值不确定w值为无穷。 cv(p , q ): v结点上波长从p变为q的代价。 如果v结点上波长不能从p变为q cv值为无穷。 If p = q, cv(p , q ) =0。 C(T) = v T w(p(v), v), (v) +v T-s C p(v) ( (p(v), (v)， 其中p(v) 是树中v点的父母。,2019/4/2,史忠植 高级计算机网络,5

27、1,虚主干,虚主干是基本图中的一棵树，用作建立多播树的模板，也就是说，扩展为虚主干的结点具有最大可能性变为多播树中的一部分。如果一个结点有越多的路径穿过它，就有越大的可能成为多播树的一部分。定义点vi 的权重 W(vi) = 穿越 vi的最短路径的数目，以权重作为是否吸收一个结点为虚主干的重要标准,2019/4/2,史忠植 高级计算机网络,52,建立虚主干的步骤,（1）找到图 G中所有结点对的最短路径。 （2）给图 G中的所有结点赋权值。 （3）找到主干结点集合F。 （4）为主干结点集合建立完全图。 （5）在完全图上找到最小生成树。 （6）把最小生成树上的边转化为图G上相应的最短路径。 （7）

28、执行最小生成树算法，去除不必要的结点和连接，获得虚主干。,2019/4/2,史忠植 高级计算机网络,53,VTDM 路由选择算法,1. 建立虚主干。 2. 往多播组中加入一结点： 建立该结点到已建立的虚主干之间的最短路由。 虚主干到源的路由已经建立起来了。 把结点加入多播组。 3. 从多播组中去除一结点： 先从多播组中移出该结点。 如果是叶子结点，从多播树中去掉该叶子。 如果该结点没有下属结点，剪除多余的枝干。,2019/4/2,史忠植 高级计算机网络,54,增加结点 (加入结点 B),第一步: 如果结点B在虚主干上，指定它为结点A，转到第二步。 否则找到B到虚主干的最短路由，把最短路由中不属

29、于多播树的那部分加入多播树中。 设虚主干上沿最短路径离B最近的点为A。 第二步: 如果A已经在多播树上，转到第三步。 否则，把从A到源结点的路由不在多播树上的那部分加入多播树中。 第三步: 把结点B加入多播树中。,2019/4/2,史忠植 高级计算机网络,55,模拟结果,定义平均失效率 = 使用算法A的树成本/使用算法B的树成本。 将VTDM与动态贪心法 (DG)， 最短路径法 (SP)比较。对于结点数增加的平均失效率，VTDM大大优于SP， 优于DG。对于多播组的规模增大的平均失效率，VTDM在大规模组中大大优于SP， 优于DG。对于多播树中结点的最大度 (也就是数据复制的份数)，VTDM大

30、大小于 SP，小于DG。,2019/4/2,史忠植 高级计算机网络,56,6.13 限界最短多播算法BSMA,BSMA算法使多播树的成本最小化，并且保证所有的延迟小于预先设定的界限。BSMA的可行领域是所有延迟受限的Steiner树。 先简要的描述一下BSMA的步骤：首先用Dijkstra最短路径算法构建最小延迟 Steiner 树 T0，在可行的区域内不断的重复更新T0以获的更低的代价。,2019/4/2,史忠植 高级计算机网络,57,BSMA成本函数的定义,使用驱动成本 沿路径的连接成本的总和最小化。 拥塞驱动成本 沿路径的最大连接成本最小化。 连接成本函数 将连接的成本和连接的使用联系起

31、来。 连接延迟函数 连接上排队、传输、散播的延迟。 目标延迟限界函数 (DDF) 从源到每个目的站点沿途的延迟的上界。,2019/4/2,史忠植 高级计算机网络,58,优化Steiner树的方法,用Dijkstra最短路径算法构建最小延迟Steiner树T0的方法在前面已经介绍过了。怎样在可行的区域内不断的优化T0，使最后获得的树的成本最小呢。这里要用到路径交换法，优化Tj 获得Tj+1步骤如下： 从Tj中选择路径 p Tj = Tj1 + Tj2 p 从图 G 中选取不在 Tj中的新路径 ps 替代从 Tj中删除的路径。 Tj+1 = Tj1 + Tj2 ps. Tj+1 满足延迟受限。,2

32、019/4/2,史忠植 高级计算机网络,59,超边,首先从 Tj 获得 Tj/，树Tj/ 含源结点，所有的目标结点和所有度大于2的中继结点。Tj/ 的边称为超边，在超边的两个端结点之间的所有结点，都是度为2的转送结点。每条超边都是 Tj 中交换的候选路径,2019/4/2,史忠植 高级计算机网络,60,BSMA具体算法,初始化所有超边为无标记。 第一步:在所有无标记边中， BSMA 选中最高成本的超边 Ph 。 将Ph 和另一条成本低一些的超边交换，得到的树延迟受限。 以下两种情况必有一种发生： 1.延迟限界的最短路径与 Ph相同。 标记超边，转第一步。 2.延迟限界的最短路径不同于Ph. 替

33、换 删除所有的超边的记号。 转到第一步。 当所有超边都被标记后算法停止。,2019/4/2,史忠植 高级计算机网络,61,BSMA 动态递增,BSMA 动态递增的计算子树 Tj1 和 Tj2之间的k条最短路径。当构成延迟限界树的最短路径找到后决定K，以下两个条件满足的时候，最短路径递增构建停止： 1. 新发现的最短路径和刚删除的等长。 2. 新发现的最短路径使新树不超过延迟限界。 扩展的Dijkstra算法用于构建两子树间的最短路径，而不是两点之间的最短路径。在Tj1中，一个伪源结点s与所有结点相连。在Tj2中，一个伪目标d所有结点相连。最短路径算法始于s终止于d。,2019/4/2,史忠植

34、高级计算机网络,62,贪心路径交换,增益 = 进行了一轮路径交换以后所减少的成本。 c = Tj 的成本，c_prime = Tj+1的成本，增益 = c - c_prime。 BSMA Tj 中所有可能的路径交换对的增益，而后选择一个具有最大增益的交换对。 BSMA 继续贪心交换法， 直到最大增益为0时结束。 这种贪心途径的时间复杂度更高，为O（kn3log（n）。,2019/4/2,史忠植 高级计算机网络,63,6.14 适用于光纤网络的多播的MZQ算法,1：限制的波长转化：每个结点有能力将一个输入波长转化为一组输出波长 2：稀疏的波长转化：一个输入波长可以被转化为任意的输出波长，但只有少

35、数的几个结点拥有这样的能力。 3：稀疏的分裂：只有一部分结点能够将所有的信息复本传输出去，其余结点没有这样的分裂能力。 4：MZQ算法假设在每条链路上总是有足够的波长。在具有分裂能力的结点上构造多播树。在这样的树中，一个没有分裂能力的结点最多只能有一个子结点。,2019/4/2,史忠植 高级计算机网络,64,MZQ路由算法,1 算法运行过程中保持着三个结点集合： (1)V：树上可以用来向外生长的结点（具有分裂能力的结点） (2)V1：树上无法用来向外生长的结点（不具有分裂能力的结点） (3)UV：目前为止，没有被包括进任何树中的终端结点。 2 从UV集合中挑选离树最近的结点。 3 在一个多播树

36、中包括进尽可能多的目的结点。 4 如果先前的那棵树还不能使所有的结点包括进去，那算法就循环调用以生成另一棵多播树。,2019/4/2,史忠植 高级计算机网络,65,MZQ算法的波长分配,1. 性能度量 (1)波长的数目 (2)带宽的总量（信道总数） 2. 在每条链路上维持两个计数器 (1)I：使用的最高波长索引 (2)N：使用的波长数目 3. 在每条链路上的波长数目没有限制,2019/4/2,史忠植 高级计算机网络,66,MZQ算法的波长分配,4. 在波长的分配中使用首先适配算法 在所有光纤网络中的多播采用MZQ算法,可以得到如下结果： (1)由于使用多播的方法，带宽（bandwidth）可节省50% (2)多播可将所需使用的波长（wavelength）数目减少60% (3)即使整个网络中不存在具有分裂能力的结点，使用多播算法也能使消耗的带宽（bandwidth）的数目减少43%到45% (4)只要有不超过75%的结点具有分裂能力，整个系统就能取得和所有结点都具有分裂能力的系统同样的性能。,2019/4/2,史忠植 高级计算机网络,67,6.15 多播的应用,信息发布 视频会议 远程学习 发现资源 公司内部的资源共享,2019/4/2,史忠植 高级计算机网络,68,谢谢! THANK YOU,