高级计算机网络PPT课件

《高级计算机网络PPT课件》由会员分享，可在线阅读，更多相关《高级计算机网络PPT课件（68页珍藏版）》请在金锄头文库上搜索。

1、 高级计算机网络高级计算机网络2024/9/221内容提要内容提要6.1 6.1 概述概述6.2IP多播协议多播协议6.3多播路由多播路由6.4扩散技术扩散技术6.5跨越树的多播路由算法跨越树的多播路由算法6.6约束约束Steiner树树6.7反向路径广播反向路径广播6.8截断的反向路径广播截断的反向路径广播6.9反向路径多播反向路径多播2024/9/222内容提要内容提要6.10核心树核心树KMB6.12动态多播路由选择算法动态多播路由选择算法VTDM6.13限界最短多播算法限界最短多播算法BSMA6.14适用于光纤网络的多播的适用于光纤网络的多播的MZQ算法算法6.15多播的应用多播的应用

2、 2024/9/2236.1 6.1 概述概述 将分组同时发往所有目的地称做广播（将分组同时发往所有目的地称做广播（broadcastingbroadcasting）。）。 单单源源，多多目目的的的的通通信信方方式式称称之之为为多多点点通通信信（multipointcommunication），通通常常只只在在分分叉叉的的时时候候复复制制信信息息，又又称称为为多多播（播（multicast）。）。 在在单单播播的的环环境境下下，每每个个结结点点一一次次只只能能给给另另一一个个结结点点发发出出信信息息。在在多多播播的的环环境境下下，每每个个结结点点一一次次可可以以有有效效的的把把一一个个打打包包

3、的的信信息息同同时时发发往往多多个个目目标标。必必须须有有支支持持IPIP多多播播的的结结点点处处理理系系统统和和TCP/IPTCP/IP栈，网络中的结点才能顺利的进行多播。栈，网络中的结点才能顺利的进行多播。 2024/9/2246.1 6.1 概述概述 多多信信道道IPIP包包和和单单信信道道IPIP包包的的主主要要在在于于头头部部目目标标地地址址域域的的“组组 地地 址址 ”， 多多 播播 使使 用用 D D类类 地地 址址 ， 也也 就就 是是 在在 244.0.0.0-244.0.0.0-239.255.255.255239.255.255.255之间的地址。之间的地址。多播的特性：

4、 1. 1. 可靠性：对不同类型的应用是否有不同的可靠性模型？可靠性：对不同类型的应用是否有不同的可靠性模型？ 2. 2. 允允许许动动态态加加入入和和离离开开：每每个个对对话话过过程程必必须须是是接接受受者者可可控控制的。制的。 3. 3. 地址：地址： 在每层上如何对各组编址在每层上如何对各组编址 在在IPIP层层以以上上的的各各层层是是否否需需要要标标识识组组，如如果果需需要要，怎怎样样标识？标识？ 4. 4. 方向性：方向性： 一对多一对多 或者或者 多对多多对多 转送者是否是接受者的一个子集？转送者是否是接受者的一个子集？ 2024/9/2256.1 6.1 概述概述2024/9/2

5、266.1 6.1 概述概述2024/9/2276.2 6.2 IP IP 多播协议多播协议80年年代代开开始始研研究究，1988年年Stanford大大学学实实施施了了第第一一次次多多目目通通话话，1992年年Internet程程特特别别小小组组（IETF）定定义义和和发发布布了了一一个个多多播播的的网网络络标标准准，用用于于建建立立多多播播主主干干网网（MBONE），即即在在Internet上上运运行行的的单单路路广广播播和和多多播播综综合合网网络络。MBONE于于1993年年刹刹那那间间名名声声远远扬扬。1995年年，Cisco公公司司和和Lucent公公司司开开始始销销售售支支持持多多

6、播播的的路路由由器器和和交交换换机机，一一年年后后依依赖赖多多播播的的应应用用产产品品开开始始上上市。市。IP多多播播的的最最早早实实施施方方案案依依赖赖于于传传统统的的竭竭尽尽全全力力方方法法和和UserDatagranProtoco1，但它们不能保证多播数据流的可靠传输。但它们不能保证多播数据流的可靠传输。2024/9/2286.2 6.2 IP IP 多播协议多播协议HP的的Internet群管群管JF协议（协议（LGMP）ProtocolIndependentMu1ticast、 Mu1ticastBorderGatewayProtocolHierarchical DVMRP（ Dis

7、tance Vector MulticastRoutingProtocol）2024/9/229多播路由多播路由共享树（共享树（sharedtree）源源根根结结点点的的最最短短路路径径树树（SRSPTSRSPT： source source rooted rooted shortest path treeshortest path tree）。）。2024/9/2210共享树（共享树（sharedtree）共共享享树树方方法法中中使使用用一一个个中中央央多多播播路路由由器器，有有时时候候又又称称为为核核心心路路由由器器。需需要要进进行行多多播播的的源源结结点点将将他他们们所所要要传传递递的的

8、信信息息包包都都传传给给这这个个核核心心路路由由器器，然然后后由由这这个个核核心心路路由由器器通通过过一一棵棵共共享享树树将将信信息息包包一一个个一一个个的的传传给给组组中中的的每每一一个个接接收收结结点点。每每个个组组中中只只要要建建立立一一棵棵共共享享树树就就可可以以了了，而而不不是是象象在在SRSPTSRSPT中中需需要要为为组组中中的的每每个个源源结结点点建建立立一一棵棵树树。与与SRSPTSRSPT算算法法相相比比，共共享享树树对对路路由由器器和和网网络络带带宽宽（bandwidthbandwidth）的的需需求求更更小小。在在CBTCBT和和PIMPIM协议中使用共享树的思想来传递

9、信息包。协议中使用共享树的思想来传递信息包。2024/9/2211 源根结点的最短路径树源根结点的最短路径树这这种种源源根根结结点点的的最最短短路路径径树树只只能能建建立立在在具具有有多多播播功功能能的的路路由由器器上上。它它为为每每个个组组中中的的每每个个源源结结点点建建立立一一棵棵树树，这这棵棵树树以以该该传传送送结结点点为为根根，使使其其与与所所有有的的接接收收结结点点相相连连。一一般般而而言言，该该组组中中有有多多少少个个源源结结点点，就就需需建建立多少棵这样的树。立多少棵这样的树。 一一棵棵这这种种基基于于源源结结点点的的树树将将一一个个特特定定的的源源结结点点与与所所有有的的接接收

10、收结结点点相相连连，并并被被称称为为“源源根根结结点点的的最最短短路路径径树树”。这这些些路路径径并并不不需需要要通通过过一一个个特特定定的的中中央央多多播播路路由由器器。等等到到由由协协议议将将一一棵棵这这样样的的树树建建成成后后，这这棵棵树树的的源源结结点点就就可可以以沿沿着着这这棵棵树树上上的的路路径径将将所所要要传传递递的的信信息传到它的每一个接收结点。息传到它的每一个接收结点。2024/9/2212SRSPT树的优点树的优点（1）使用经典的单信道路由表很容易计算）使用经典的单信道路由表很容易计算SRSPT树；树；（2）可可以以有有效效的的实实现现分分布布式式处处理理不不需需要要整整个

11、个网网络络的的拓扑结构；拓扑结构； （3）返回的路径中不会存在回路。）返回的路径中不会存在回路。2024/9/2213SRSPTSRSPT树的缺点树的缺点 （1）没有最小化整个分布式处理的代价；）没有最小化整个分布式处理的代价； （2）可伸缩性不好；）可伸缩性不好；（3）在在每每个个路路由由器器上上都都要要保保存存每每个个组组中中每每个个源源结结点的点的SRSPT树的信息；树的信息； （4）如如果果下下层层的的单单信信道道路路由由是是非非对对称称的的则则可可能能会会导致失败。导致失败。2024/9/2214性能指标性能指标(1)低低延延迟迟。将将源源结结点点到到目目的的结结点点的的端端到到端端

12、的的延延迟迟与与点点到到点点的单信道最短路径的延迟相比较；的单信道最短路径的延迟相比较；（2）低低代代价价。全全部部的的带带宽宽消消耗耗以以及及保保存存树树状状态态信信息息所所需需的的代价；代价；（3）轻的网络拥塞）轻的网络拥塞2024/9/2215多点路由算法的需求多点路由算法的需求（1）支支持持可可靠靠的的传传输输。连连接接失失败败不不应应该该增增加加延延迟迟或或者者减减少少可用的资源可用的资源（2）对于得到最佳路由所需要的一些考虑。）对于得到最佳路由所需要的一些考虑。1：所需付出的代价（对带宽的消耗）：所需付出的代价（对带宽的消耗）2：端到端的延迟（所需跨越的结点数）：端到端的延迟（所需

13、跨越的结点数）（3）最小化对网络的负担。）最小化对网络的负担。1：避免回路：避免回路2：避免在一些连接或子网上出现网络拥塞：避免在一些连接或子网上出现网络拥塞（4）最小化在路由器中所需存储的状态数量。）最小化在路由器中所需存储的状态数量。2024/9/2216密集模式密集模式 密密集集模模式式假假设设多多播播组组的的成成员员密密集集分分布布在在网网络络中中，每每个个子子网网至至少少含含一一个个成成员员。密密集集模模式式还还需需要要充充足足的的带带宽宽。DVMRP,MOSPF和和PIM-DM都都是是密密集集模模式式路路由由选选 择择 协协 议议 。 密密 集集 模模 式式 路路 由由 选选 择择

14、 协协 议议 依依 靠靠 扩扩 散散（flooding）技术把信息传播到整个网络的路由器上。技术把信息传播到整个网络的路由器上。2024/9/2217稀疏模式稀疏模式 假假设设多多播播组组的的成成员员稀稀疏疏分分布布在在网网络络中中，而而且且网网络络可可以以提提供供的的带带宽宽不不是是很很宽宽裕裕。在在稀稀疏疏模模式式下下，用用户户可可能能分分散散在在Intent的的各各个个部部分分，也也可可能能是是被被ISDN专专线线连连接接起起来来的的。这这种种模模式式下下用用户户不不一一定定很很少少，只只是是它它们们分分散的范围很广。散的范围很广。2024/9/22186.4 6.4 扩散技术扩散技术1

15、路由器接收到要发往多播组的一个报文。路由器接收到要发往多播组的一个报文。2路由器用协议机制决定这是不是第一次收到该报文。路由器用协议机制决定这是不是第一次收到该报文。3如如果果它它是是第第一一次次收收到到该该报报文文，路路由由器器将将该该报报文文发发往往Internet上上除除了了它它的的来来源源的的所所有有接接口口。这这保保证证了了多多播播报报文文将将到到达达所所有有的的路由器。路由器。 如果路由器以前曾收到该报文，就把它丢弃。如果路由器以前曾收到该报文，就把它丢弃。2024/9/2219扩散技术局限性扩散技术局限性1扩散技术不适用于大规模网络，如扩散技术不适用于大规模网络，如Interne

16、t。2同样不适用于广域网，因为它产生大量复制包。同样不适用于广域网，因为它产生大量复制包。3扩扩散散技技术术使使用用Internet网网上上的的所所有有可可用用路路径径，网网络络上上所所有有路路径的流量容易引起拥塞。径的流量容易引起拥塞。4因因为为每每个个路路由由器器必必须须为为最最近近接接收收的的包包维维护护一一张张表表，所所以以并并不是很有效的使用路由器的内存。不是很有效的使用路由器的内存。2024/9/2220建立生成树的步骤建立生成树的步骤1选选择择一一转转送送设设备备作作为为根根：刚刚开开始始所所有有的的转转送送设设备备先先假假设设自自身身为为根根，告诉其他设备它作为根连接。告诉其他

17、设备它作为根连接。总总的的来来说说，优优先先级级低低的的设设备备设设为为根根。如如果果优优先先级级相相同同，MAC地地址址低低的的设设备备设为根。设为根。2估估计计路路径径成成本本：如如果果一一转转送送设设备备接接到到另另一一设设备备的的包包，认认为为存存在在更更好好的路径，就不再告诉别的设备自身是根，而是告诉别的设备更优的根。的路径，就不再告诉别的设备自身是根，而是告诉别的设备更优的根。3选选择择根根端端口口，并并且且在在每每个个局局域域网网制制定定一一个个转转送送设设备备：最最终终，每每个个设设备都认同了最佳转送设备，该设备就成为根。备都认同了最佳转送设备，该设备就成为根。设设备备的的根根

18、端端口口提提供供了了指指向向根根转转送送设设备备的的最最低低成成本本路路径径。路路径径成成本本相相同同时时，端端口口接接头头优优先先级级低低的的成成为为根根端端口口。如如果果接接口口优优先先级级再再相相同同，具具低低优优先先级级的的设备上的断口为根端口。设备上的断口为根端口。4.每每个个子子网网指指定定一一个个端端口口（路路由由器器）：生生成成树树算算法法设设指指定定连连接接转转送送设设备备和局域网的端口位置顶端口。尤其当子网上的设备靠近根时。和局域网的端口位置顶端口。尤其当子网上的设备靠近根时。2024/9/2221建立生成树的步骤建立生成树的步骤2024/9/2222建立生成树的步骤建立生

19、成树的步骤2024/9/22236.7 6.7 反向路径广播反向路径广播 无无论论是是子子网网上上哪哪一一个个源源，反反向向路路径径广广播播（reverse pathbroadcasting,RPB）算算法法针针对对每每一一个个组组建建立立一一棵棵生生成成树树，提提供供了了源源和和组组的的成成员员之之间间的的有有效效路路径径。这这样样的的生生成成树树根根植植于于直直接接和和源源连连接接的的子子网网上上，意意味味着着每每个个活活跃跃的的源源-组组队队都都有有一一棵棵生生成成树树。路由器利用逆向路径广播算法建立根植于源的树路由器利用逆向路径广播算法建立根植于源的树2024/9/2224反向路径广播

20、转送算法反向路径广播转送算法2024/9/2225反向路径广播转送算法反向路径广播转送算法 链链接接状状态态路路由由选选择择协协议议使使用用拓拓扑扑数数据据库库来来确确认认相相邻邻的的路路由由器器是是否否在在子子链链接接上上，也也就就是是考考虑虑该该路路由由器器是是否否在在相相邻邻路路由由器器回回溯到源的最短路径上。溯到源的最短路径上。 距距离离向向量量路路由由选选择择协协议议使使用用邻邻居居发发布布的的源源-组组对对的的前前一一站站距距，或或者者翻翻转转该该路路由由来来决决定定下下一一相相邻邻路路由由认认为为该该路路由由在在到到源源的的最短路径上。最短路径上。2024/9/2226反向路径广

21、播的例子反向路径广播的例子2024/9/2227反向路径广播的例子反向路径广播的例子 从从路路由由器器A A收收到到报报文文，确确认认连连接接1 1是是源源- -组组对对的的父父母链。母链。 把把报报文文发发往往任任何何含含有有小小组组成成员员的的叶叶子子子子网网，如如发发往连接往连接4 4、连接、连接5 5。 从从路路由由选选择择信信息息交交换换中中得得知知路路由由器器C C认认为为连连接接2 2是是源源- -组对的父母链，于是不再将报文发往连接组对的父母链，于是不再将报文发往连接3 3。 路路由由器器C C将将丢丢弃弃从从连连接接3 3来来的的报报文文，因因为为是是从从源源- -组对的非父

22、母链上来的。组对的非父母链上来的。2024/9/22286.8 6.8 截断的反向路径广播截断的反向路径广播 截截断断的的反反向向路路径径广广播播（truncated truncated reverse reverse path path broadcasting, broadcasting, TRPBTRPB）改改进进了了上上一一个个算算法法中中不不考考虑虑多多播播组组的的成成员员限限制制的的问问题题。它它使使用用了了IGMPIGMP来来决决定定某某个个子子网网上上是是否否存存在在该该广广播播组组的的成成员员，并并以以此此为为依依据据截截断断原原来来构构造造的的跨跨越越树树上上的的一一些些枝

23、枝叶叶。一一旦旦弄弄清清楚楚这这一一点点，TRPBTRPB不不再再往往不不含含组组成成员员的的叶叶子子网网上上发发送送报报文文。路路由由器器从从扩扩展展传传送送树树上上剪剪除除不不含含组组成成员员的的叶叶子子网网，这这一排除不在最短路径上的接口的过程称为一排除不在最短路径上的接口的过程称为“截断截断”。2024/9/2229截断的反向路径广播算法的截断的反向路径广播算法的例子例子2024/9/2230TRPBTRPB源源通通过过父父路路由由器器连连接接入入路路由由器器，多多播播组组的的成成员员第第一一组组用用G1G1表表示示、第二组第二组G2G2、第三组第三组G3G3与路由器下属的转送装置相连

24、。与路由器下属的转送装置相连。当路由器接收了源当路由器接收了源- -G1G1对的一多播报文，它将：对的一多播报文，它将： 因因为为接接口口2 2至至少少含含有有第第一一组组的的一一个个成成员员，路路由由器器把把报报文文发往接口发往接口2 2。 当当且且仅仅当当该该路路由由器器的的一一个个下下属属路路由由器器认认为为接接口口3 3是是它它的源的源- -G1G1对的父母链的一部分，该路由器才把报文发往接口对的父母链的一部分，该路由器才把报文发往接口3 3。 接口接口4 4没有目标组的成员，报文不发往接口没有目标组的成员，报文不发往接口4 4。TRPB虽虽然然避避免免了了叶叶子子网网中中的的不不必必

25、要要的的流流量量，但但是是在在建建立立分配树的枝干的时候没有考虑是否含组成员的问题。分配树的枝干的时候没有考虑是否含组成员的问题。2024/9/22316.9 6.9 反向路径多播反向路径多播反反 向向 路路 径径 多多 播播 （ reverse reverse path path multicasting,RPMmulticasting,RPM）是是对对于于RPBRPB和和TRPBTRPB的的改改进进。具具体体而而言言，如如果果一一个个接接收收接接口口可可以以用用于于向向多多播播报报文文的的源源发发送送单单信信道道广广播播报报文文，路路由由器器向向除除了了接收接口以外的所有接口发送多播报文。

26、接收接口以外的所有接口发送多播报文。换换句句话话说说，RPMRPM建建立立的的传传送送树树只只覆覆盖盖了了广广播播组组成成员员和和到到含含广广播播组组成成员员子子网网最最短短路路径径沿沿途途径径过过的的路路由由器器和和子子网网。RPMRPM截截断断了了根根植植于于源源的的生生成成树树，路路由由选选择择协协议议只只向向通通往往目目标标组组成成员员的的枝枝干干发发送送报文。报文。2024/9/2232RPMRPM2024/9/2233工作原理工作原理上上级级路路由由器器收收到到截截断断信信息息后后储储存存起起来来。如如果果从从所所有有的的子子链链收收到到截截断断信信息息，该该路路由由器器也也往往它

27、它的的上上级级路路由由器器发发送送截截断断信信息息。这这个个过过程程产产生生的的多多播播树树只只含含有有通通向向活活跃组成员的枝干。跃组成员的枝干。协协议议不不时时的的更更新新多多播播树树，更更新新后后每每个个路路由由器器清清除除内内存存中中的的所所有有剪剪除除信信息息，并并且且将将受受到到的的下下一一个个多多播播报报文文送送往往所所有有的的子子链链。这这样样又又重重新新开开始始了了定定义义多多播播树树的的新新一轮过程。一轮过程。2024/9/2234工作原理工作原理组组成成员员的的动动态态特特征征意意味味着着树树需需要要定定期期的的更更新新。也也就就是是说说，多多播播报报文文必必须须定定期期

28、的的发发往往InternetInternet网网络络中中的的每每个个路路由由器器。这这就就使使得得在在大大规规模模传传送送服服务务如如在在InternetInternet上上的的传传送送问问题题不不容容忽忽视视，而而且且，每每个个路路由由器器必必须须保保留留关关于于源源和和组组的的所所有有状状态态信信息息。尽尽管管这这对对于于小小网网络络来来说说不不构构成成威威胁胁，但但是是当当源源的的数数目目和和多多播播组组成成员员大大幅幅增增加加时就是一个严重的问题。时就是一个严重的问题。2024/9/22356.10 6.10 核心树核心树核核心心树树（core-based core-based tre

29、e, tree, CBTCBT）算算法法将将建建立立一一棵棵被被小小组组中中所所有有的的发发送送者者和和接接收收者者共共享享的的传传送送树树( (图图6.10)6.10)，而而不不是是为为每每一一个个源源- -组组对对建建立立一一棵棵树树。使使用用CBTCBT算算法法时时，无无论论报报文文是是从从那那个个源源发发出出的的，路路由由器器将将多信道信息沿着相同的传送树来传递。多信道信息沿着相同的传送树来传递。共共享享树树途途径径最最显显著著的的优优势势是是能能够够很很好好的的适适应应大大规规模模网网络络。然然而而，CBTCBT可可能能导导致致在在核核心心路路由由器器附附近近的的流流量量集集中中和和

30、瓶瓶颈颈问问题题。这这是是因因为为从从任任意意源源结结点点发发出出的的信信息息在在接近核心时，都沿着相同的连接。接近核心时，都沿着相同的连接。2024/9/2236CBTCBT2024/9/2237设计目的设计目的 (1) (1) CBTCBT是是用用于于大大规规模模网网络络，处处理理过过程程中中只只需需要要少少量量的的内内存存和和带带宽宽资资源源。因因为为CBTCBT不不针针对对于于源源，尤尤其其适适合于多发送者的应用程序。合于多发送者的应用程序。 (2) (2) CBTCBT时时健健壮壮的的多多播播路路由由选选择择算算法法。为为了了获获得得健健壮的多播传送树，核心将放置在最佳位置。壮的多播

31、传送树，核心将放置在最佳位置。 (3)(3)和和其其他他多多播播路路由由选选择择协协议议比比较较而而言言，CBTCBT协协议议比较简单。简单性能导致性能的提高。比较简单。简单性能导致性能的提高。 (4)(4)CBTCBT路路由由选选择择算算法法适适度度利利于于协协议议的的。任任何何地地方方都都可可以以安安装装，并并且且支支持持域域间间多多信信道道路路由由选选择择。CBTCBT与与CBMRPCBMRP有有着着良良好好的的协协同同工工作作的的机机制制，CBMRPCBMRP是是一一种种能能够够普遍连接不同种类的多播域的协议。普遍连接不同种类的多播域的协议。2024/9/2238当一主机成为多播组的成

32、员当一主机成为多播组的成员将执行以下步骤将执行以下步骤 (1)(1)主机向所有连接广播一主机向所有连接广播一IGMPIGMP主机成员报告。主机成员报告。 (2)(2)附附近近的的一一个个具具CBTCBT算算法法的的路路由由器器唤唤醒醒加加入入树树的过程：的过程： 产生产生JOIN_REQUESTJOIN_REQUEST信息信息 将将信信息息发发往往沿沿着着导导向向组组的的核核心心路路由由器器的的路路径的下一个站点。径的下一个站点。 (3)(3)核核心心路路由由或或发发送送路路由由和和核核心心路路由由之之间间的的另另一一路由器确认该信息。路由器确认该信息。2024/9/2239当一主机成为多播组

33、的成员当一主机成为多播组的成员将执行以下步骤将执行以下步骤 (4)(4)请请求求加加入入的的信信息息在在它它穿穿过过的的路路由由器器暂暂时时建建立立加加入入状状态态，包包括括组组、进进入入的的接接口口和和连连出出的的接接口口。所所有有中中间路由器处理加入请求：间路由器处理加入请求： 确认加入请求是从那个接口接收的。确认加入请求是从那个接口接收的。 告知信加入的主机告知信加入的主机CBTCBT传送树。传送树。 (5)(5)临临时时状状态态如如果果没没有有接接到到从从上上游游传传来来的的确确认认信信息息，将将最最终终超超时时。因因为为有有临临时时加加入入状状态态，加加入入确确认认可可以沿着加入请求

34、来的路径返回。以沿着加入请求来的路径返回。 (6)(6)一一旦旦加加入入确确认认到到达达产产生生加加入入请请求求的的路路由由器器，发向这个组的信息将同时发往这个新的接收者。发向这个组的信息将同时发往这个新的接收者。 2024/9/2240CBTCBT (4)(4)请请求求加加入入的的信信息息在在它它穿穿过过的的路路由由器器暂暂时时建建立立加加入入状状态态，包包括括组组、进进入入的的接接口口和和连连出出的的接接口口。所所有有中中间路由器处理加入请求：间路由器处理加入请求： 确认加入请求是从那个接口接收的。确认加入请求是从那个接口接收的。 告知信加入的主机告知信加入的主机CBTCBT传送树。传送树

35、。 (5)(5)临临时时状状态态如如果果没没有有接接到到从从上上游游传传来来的的确确认认信信息息，将将最最终终超超时时。因因为为有有临临时时加加入入状状态态，加加入入确确认认可可以沿着加入请求来的路径返回。以沿着加入请求来的路径返回。 (6)(6)一一旦旦加加入入确确认认到到达达产产生生加加入入请请求求的的路路由由器器，发向这个组的信息将同时发往这个新的接收者。发向这个组的信息将同时发往这个新的接收者。 2024/9/2241KMBKMB理想化的多播路由选择算法应该是：理想化的多播路由选择算法应该是： 构建树时具有所想要的成本和延迟特征。构建树时具有所想要的成本和延迟特征。 算算法法可可以以适

36、适用用于于广广播播组组的的成成员员增增加加的的情情况况（如如CBTCBT），而而不不是是每每次次成成员员增增加加都都需需要要更更新新（如如SMTSMT）。）。 维护原始路由的特性。维护原始路由的特性。 不干扰正在进行的数据传送。不干扰正在进行的数据传送。 是由接收者驱动的。是由接收者驱动的。 2024/9/2242问题的形式化定义问题的形式化定义给定图给定图G=(V,E,c)V=顶点集顶点集E=边集边集c=成本函数成本函数c:EZ0+(边边非负整数非负整数)Z-顶点集顶点集:终结集合终结集合(有时用有时用M表示表示)S-点集点集:非终结集合非终结集合TO:初始树初始树=s.Q:树上顶点的优先级

37、队列树上顶点的优先级队列Vt:树上顶点树上顶点At:树上边树上边 2024/9/2243Dijkstra最短路径算法Begin. v V,将将v加到集合加到集合U,Distance(v)=cost(s,v)Distance(s)=0;从从U中删除中删除s.whileU不为空不为空do具有最小距离的任何具有最小距离的任何G的成员的成员v.U=U-v.For每个每个v的近邻的近邻w,doifmember(w,U)distance(w)=min(distance(w),cost(w,v)+distance(v);Stop.2024/9/2244 Matsuyama最短成本路径启发式算法BeginT1

38、:包含任选的包含任选的iZ的的G的子树的子树.k=1;Zk=i.找到离找到离Tk最近的最近的i Z-Zk在在Tk的基础上加入从的基础上加入从Tk到到I的最短路径建树的最短路径建树Tk+1k=k+1.Ifkp,转转T1.Ifk=p,输出结论输出结论TpStop.2024/9/2245 KMB 算法输入：图输入：图G和顶点集和顶点集Z输出：输出：Steiner树树Th步骤：步骤：1由由G和和Z建立完全有向带权图建立完全有向带权图G1=（V1，E1，c1）。）。2找到找到G1的最小生成树。的最小生成树。3用用G中相应的最短路径替换中相应的最短路径替换T1中的一边，建立中的一边，建立G的子图的子图Gs

39、。4找到找到Gs的最小生成树的最小生成树Ts。5.如如必必要要的的话话删删去去Ts中中的的边边，构构建建Steiner树树Th，使使得得Th中中所所有有的叶子为的叶子为Steiner点。点。2024/9/2246KMBKMB算法算法 KMBKMB算算法法最最坏坏时时间间复复杂杂度度 O O（|S|V|S|V|2 2）。成本不大于成本不大于2 2（1-1/1-1/l l）最优成本，其中最优成本，其中l = l = SteinerSteiner树的叶结点数。树的叶结点数。2024/9/2247KMB算法的工作过程2024/9/2248KMB算法的工作过程2024/9/2249成本建模成本建模W(e

40、, i):边边e上波长为上波长为 i的成本。的成本。如果边如果边e上上 i值不确定值不确定w值为无穷。值为无穷。cv( p, q):v结点上波长从结点上波长从 p变为变为 q的代价。的代价。如果如果v结点上波长不能从结点上波长不能从 p变为变为 qcv值为无穷。值为无穷。Ifp=q,cv( p, q)=0。C(T)= v Tw(p(v),v), (v)+ v T-sCp(v)( (p(v), (v)，其中其中p(v)是树中是树中v点的父母。点的父母。2024/9/2250虚主干 虚虚主主干干是是基基本本图图中中的的一一棵棵树树，用用作作建建立立多多播播树树的的模模板板，也也就就是是说说，扩扩展

41、展为为虚虚主主干干的的结结点点具具有有最最大大可可能能性性变变为为多多播播树树中中的的一一部部分分。如如果果一一个个结结点点有有越越多多的的路路径径穿穿过过它它，就就有有越越大大的的可可能能成成为为多多播播树树的的一一部部分分。定定义义点点v vi i 的的权权重重 W(vW(vi i) ) = = 穿穿越越 v vi i的的最最短短路路径径的的数数目目，以以权权重重作作为为是是否否吸吸收收一一个个结点为虚主干的重要标准结点为虚主干的重要标准2024/9/2251建立虚主干的步骤 （1 1）找到图）找到图 G G中所有结点对的最短路径。中所有结点对的最短路径。（2 2）给图）给图 G G中的所

42、有结点赋权值。中的所有结点赋权值。（3 3）找到主干结点集合）找到主干结点集合F F。（4 4）为主干结点集合建立完全图。为主干结点集合建立完全图。（5 5）在完全图上找到最小生成树。）在完全图上找到最小生成树。（6 6）把把最最小小生生成成树树上上的的边边转转化化为为图图G G上上相相应应的的最最短短路径。路径。（7 7）执执行行最最小小生生成成树树算算法法，去去除除不不必必要要的的结结点点和和连连接，获得虚主干。接，获得虚主干。2024/9/2252VTDM 路由选择算法 1.1.建立虚主干。建立虚主干。 2.2.往多播组中加入一结点：往多播组中加入一结点：建立该结点到已建立的虚主干之间的

43、最短路由。建立该结点到已建立的虚主干之间的最短路由。 虚主干到源的路由已经建立起来了。虚主干到源的路由已经建立起来了。把结点加入多播组。把结点加入多播组。 3. 3. 从多播组中去除一结点：从多播组中去除一结点：先从多播组中移出该结点。先从多播组中移出该结点。如果是叶子结点，从多播树中去掉该叶子。如果是叶子结点，从多播树中去掉该叶子。如果该结点没有下属结点，剪除多余的枝干。如果该结点没有下属结点，剪除多余的枝干。2024/9/2253增加结点 (加入结点 B)第一步第一步: : 如果结点如果结点B B在虚主干上，指定它为结点在虚主干上，指定它为结点A A，转到第二步。转到第二步。 否否则则找找

44、到到B B到到虚虚主主干干的的最最短短路路由由，把把最最短短路路由由中中不不属属于于多多播播树树的那部分加入多播树中。的那部分加入多播树中。 设虚主干上沿最短路径离设虚主干上沿最短路径离B B最近的点为最近的点为A A。 第二步第二步: : 如果如果A A已经在多播树上，转到第三步。已经在多播树上，转到第三步。 否否则则，把把从从A A到到源源结结点点的的路路由由不不在在多多播播树树上上的的那那部部分分加加入入多多播播树中。树中。 第三步第三步: : 把结点把结点B B加入多播树中。加入多播树中。2024/9/2254模拟结果 定定义义平平均均失失效效率率=使使用用算算法法A的的树树成成本本/

45、使使用用算算法法B的的树树成本。成本。 将将VTDM与与动动态态贪贪心心法法(DG)，最最短短路路径径法法(SP)比比较较。对对于于结结点点数数增增加加的的平平均均失失效效率率，VTDM大大大大优优于于SP，优优于于DG。对对于于多多播播组组的的规规模模增增大大的的平平均均失失效效率率，VTDM在在大大规规模模组组中中大大大大优优于于SP，优优于于DG。对对于于多多播播树树中中结结点点的的最最大大度度(也也就就是是数数据据复复制制的的份份数数)，VTDM大大大大小小于于SP，小于小于DG。2024/9/22556.13 限界最短多播算法BSMA BSMA算算法法使使多多播播树树的的成成本本最最

46、小小化化，并并且且保保证证所所有有的的延延迟迟小小于于预预先先设设定定的的界界限限。BSMA的的可可行行领领域域是是所所有有延延迟迟受受限的限的Steiner树。树。先先简简要要的的描描述述一一下下BSMA的的步步骤骤：首首先先用用Dijkstra最最短短路路径径算算法法构构建建最最小小延延迟迟Steiner树树T0，在在可可行行的的区区域域内内不不断断的重复更新的重复更新T0以获的更低的代价。以获的更低的代价。2024/9/2256BSMA成本函数的定义 使用驱动成本使用驱动成本沿路径的连接成本的总和最小化。沿路径的连接成本的总和最小化。拥塞驱动成本拥塞驱动成本沿路径的最大连接成本最小化。沿

47、路径的最大连接成本最小化。连接成本函数连接成本函数将连接的成本和连接的使用联系起来。将连接的成本和连接的使用联系起来。连接延迟函数连接延迟函数连接上排队、传输、散播的延迟。连接上排队、传输、散播的延迟。目标延迟限界函数目标延迟限界函数(DDF)从源到每个目的站点沿途的延迟的上界。从源到每个目的站点沿途的延迟的上界。2024/9/2257优化Steiner树的方法 用用Dijkstra最最短短路路径径算算法法构构建建最最小小延延迟迟Steiner树树T0的的方方法法在在前前面面已已经经介介绍绍过过了了。怎怎样样在在可可行行的的区区域域内内不不断断的的优优化化T0，使使最最后后获获得得的的树树的的

48、成成本本最最小小呢呢。这这里里要要用用到到路路径径交交换换法，优化法，优化Tj获得获得Tj+1步骤如下：步骤如下： 从从Tj中选择路径中选择路径pTj=Tj1+Tj2 p 从从图图G中中选选取取不不在在Tj中中的的新新路路径径ps替替代代从从Tj中中删删除的路径。除的路径。Tj+1=Tj1+Tj2 ps.Tj+1满足延迟受限。满足延迟受限。2024/9/2258超边 首首先先从从Tj获获得得Tj/，树树Tj/含含源源结结点点，所所有有的的目目标标结结点点和和所所有有度度大大于于2的的中中继继结结点点。Tj/的的边边称称为为超超边边，在在超超边边的的两两个个端端结结点点之之间间的的所所有有结结点

49、点，都都是是度度为为2的的转转送送结结点点。每每条超边都是条超边都是Tj中交换的候选路径中交换的候选路径2024/9/2259BSMA具体算法 初始化所有超边为无标记。初始化所有超边为无标记。第一步第一步:在所有无标记边中，在所有无标记边中，BSMA选中最高成本的超边选中最高成本的超边Ph。将将Ph和另一条成本低一些的超边交换，得到的树延迟受限。和另一条成本低一些的超边交换，得到的树延迟受限。以下两种情况必有一种发生：以下两种情况必有一种发生： 1.延迟限界的最短路径与延迟限界的最短路径与Ph相同。相同。标记超边，转第一步。标记超边，转第一步。 2.延迟限界的最短路径不同于延迟限界的最短路径不

50、同于Ph. 替换替换 删除所有的超边的记号。删除所有的超边的记号。 转到第一步。转到第一步。 当所有超边都被标记后算法停止。当所有超边都被标记后算法停止。2024/9/2260BSMA动态递增动态递增 BSMA动动态态递递增增的的计计算算子子树树Tj1和和Tj2之之间间的的k条条最最短短路路径径。当当构构成成延延迟迟限限界界树树的的最最短短路路径径找找到到后后决决定定K，以以下下两两个条件满足的时候，最短路径递增构建停止：个条件满足的时候，最短路径递增构建停止：1.新发现的最短路径和刚删除的等长。新发现的最短路径和刚删除的等长。2.新发现的最短路径使新树不超过延迟限界。新发现的最短路径使新树不

51、超过延迟限界。扩扩展展的的Dijkstra算算法法用用于于构构建建两两子子树树间间的的最最短短路路径径，而而不不是是两两点点之之间间的的最最短短路路径径。在在Tj1中中，一一个个伪伪源源结结点点s与与所所有有结结点点相相连连。在在Tj2中中，一一个个伪伪目目标标d所所有有结结点点相相连连。最最短短路路径算法始于径算法始于s终止于终止于d。2024/9/2261贪心路径交换 增益增益=进行了一轮路径交换以后所减少的成本。进行了一轮路径交换以后所减少的成本。c = Tj 的的成成本本，c_prime = Tj+1的的成成本本，增增益益 = c -c_prime。BSMATj中中所所有有可可能能的的

52、路路径径交交换换对对的的增增益益，而而后后选选择择一个具有最大增益的交换对。一个具有最大增益的交换对。BSMA继续贪心交换法，继续贪心交换法，直到最大增益为直到最大增益为0时结束。时结束。这种贪心途径的时间复杂度更高，为这种贪心途径的时间复杂度更高，为O（kn3log（n）。）。2024/9/2262 6.14 适用于光纤网络的多播的MZQ算法 1：限限制制的的波波长长转转化化：每每个个结结点点有有能能力力将将一一个个输输入入波波长转化为一组输出波长长转化为一组输出波长2：稀稀疏疏的的波波长长转转化化：一一个个输输入入波波长长可可以以被被转转化化为为任任意的输出波长，但只有少数的几个结点拥有这

53、样的能力。意的输出波长，但只有少数的几个结点拥有这样的能力。3：稀稀疏疏的的分分裂裂：只只有有一一部部分分结结点点能能够够将将所所有有的的信信息息复本传输出去，其余结点没有这样的分裂能力。复本传输出去，其余结点没有这样的分裂能力。4：MZQ算算法法假假设设在在每每条条链链路路上上总总是是有有足足够够的的波波长长。在在具具有有分分裂裂能能力力的的结结点点上上构构造造多多播播树树。在在这这样样的的树树中中，一一个没有分裂能力的结点最多只能有一个子结点。个没有分裂能力的结点最多只能有一个子结点。2024/9/2263 MZQ路由算法 1算法运行过程中保持着三个结点集合：算法运行过程中保持着三个结点集

54、合：(1)V：树树上上可可以以用用来来向向外外生生长长的的结结点点（具具有有分分裂裂能能力力的结点）的结点）(2)V1：树树上上无无法法用用来来向向外外生生长长的的结结点点（不不具具有有分分裂裂能力的结点）能力的结点）(3)UV：目目前前为为止止，没没有有被被包包括括进进任任何何树树中中的的终终端端结结点。点。2从从UV集合中挑选离树最近的结点。集合中挑选离树最近的结点。3在一个多播树中包括进尽可能多的目的结点。在一个多播树中包括进尽可能多的目的结点。4如如果果先先前前的的那那棵棵树树还还不不能能使使所所有有的的结结点点包包括括进进去去，那那算法就循环调用以生成另一棵多播树。算法就循环调用以生

55、成另一棵多播树。2024/9/2264 MZQMZQ算法的波长分配算法的波长分配 1.性能度量性能度量(1)波长的数目波长的数目(2)带宽的总量（信道总数）带宽的总量（信道总数）2.在每条链路上维持两个计数器在每条链路上维持两个计数器(1)I：使用的最高波长索引使用的最高波长索引(2)N：使用的波长数目使用的波长数目3.在每条链路上的波长数目没有限制在每条链路上的波长数目没有限制2024/9/2265 MZQMZQ算法的波长分配算法的波长分配 4.在波长的分配中使用首先适配算法在波长的分配中使用首先适配算法在所有光纤网络中的多播采用在所有光纤网络中的多播采用MZQ算法算法,可以得到如下结果：可

56、以得到如下结果：(1)由于使用多播的方法，带宽（由于使用多播的方法，带宽（bandwidth）可节省可节省50%(2)多播可将所需使用的波长（多播可将所需使用的波长（wavelength）数目减少数目减少60%(3)即即使使整整个个网网络络中中不不存存在在具具有有分分裂裂能能力力的的结结点点，使使用用多多播播算算法法也也能使消耗的带宽（能使消耗的带宽（bandwidth）的数目减少的数目减少43%到到45%(4)只只要要有有不不超超过过75%的的结结点点具具有有分分裂裂能能力力，整整个个系系统统就就能能取取得得和和所有结点都具有分裂能力的系统同样的性能。所有结点都具有分裂能力的系统同样的性能。2024/9/2266 6.15 多播的应用 信息发布信息发布 视频会议视频会议 远程学习远程学习 发现资源发现资源 公司内部的资源共享公司内部的资源共享 2024/9/2267 谢谢! THANK YOU2024/9/2268