计算机网络第9章 多播路由技术

1、郑州大学信息工程学院郑州大学信息工程学院李向丽李向丽第第9章章 多播路由技术多播路由技术9.7 多播开放最短路径优先多播开放最短路径优先MOSPF9.8 基于核心的树基于核心的树CBT9.9 PIM-DM9.10 PIM-SM9.11 域间多播技术域间多播技术9.12 多播主干多播主干MBone9.13 IPv6多播技术多播技术9.1 在局域网在局域网LAN上的多播上的多播9.2 多播转发和路由选择信息多播转发和路由选择信息9.3 多播转发树多播转发树9.4 多播路由算法多播路由算法9.5 多播路由协议多播路由协议9.6 距离向量多播路由协议距离向量多播路由协议DVMRP9.1在局域网在局域网

2、LANLAN上的多播上的多播 多播源和多播组成员关系多播源和多播组成员关系 多播源和所有成员多播源和所有成员同在一个以太网同在一个以太网上。则不需要上。则不需要多播控制协议。多播控制协议。 多播源将多播多播源将多播IP分组封装在以太网帧中。以太分组封装在以太网帧中。以太网帧的目的网帧的目的MAC地址为一个基于地址为一个基于IP多播地址的多播地址的多播映射地址。多播映射地址。 以太网上的多播组成员监听这个多播物理地址，以太网上的多播组成员监听这个多播物理地址，接收此多播分组。非多播组成员则丢弃收到的接收此多播分组。非多播组成员则丢弃收到的多播分组。多播分组。 多播源不在本地多播源不在本地LAN中

3、中，路由器判断该，路由器判断该LAN中是中是否有多播组成员。如果有，则将多播分组转发给否有多播组成员。如果有，则将多播分组转发给LAN；如果没有，则不向此；如果没有，则不向此LAN转发该多播分组。转发该多播分组。交换式交换式LAN上的多播实现上的多播实现 交换机交换机LAN通过一台路由器连接到互联网中。通过一台路由器连接到互联网中。 首先，路由器通过使用首先，路由器通过使用IGMP报文，获知报文，获知LAN上是否有组成员存在。若有，则将多播分组上是否有组成员存在。若有，则将多播分组转发到交换式转发到交换式LAN上。上。 其次，交换机对目的其次，交换机对目的MAC地址转发该分组。地址转发该分组。

4、但是但是IGMP是第三层协议，交换机的是第三层协议，交换机的MAC地址地址转发表中没有此多播转发表中没有此多播MAC地址的转发表项地址的转发表项（多播地址，输出接口），会导致交换机只（多播地址，输出接口），会导致交换机只能洪泛多播分组。对于大型交换式局域网，能洪泛多播分组。对于大型交换式局域网，这将影响网络的运行效率。这将影响网络的运行效率。交换机交换机LAN对多播分组转发的对多播分组转发的解决方法解决方法 手工配置交换机转发表。手工配置交换机转发表。 使用通用多播注册协议（使用通用多播注册协议（General Multicast Register Protocol，GMRP）。）。 IGMP

5、侦听（侦听（IGMP Snooping）。）。 通过通过CGMP协议（协议（Cisco Group Manage Protocol）。）。9.2 多播转发和路由选择信息多播转发和路由选择信息 多播转发和路由选择与单播情况不相同，并且多播转发和路由选择与单播情况不相同，并且相当复杂。通过下图的例子进行说明。相当复杂。通过下图的例子进行说明。“”标记多播组标记多播组Group1Group1，成员有主机，成员有主机A A、B B和和C C“”标记多播组标记多播组Group2Group2，成员有主机，成员有主机D D、E E和和F FNet2Net2没有没有Group1Group1的成员。的成员。 N

6、et1Net3FGA路由器路由器RNet2BCDE1. 对动态路由选择的需求对动态路由选择的需求 在多播路由选择中，即使网络拓扑不发生变化在多播路由选择中，即使网络拓扑不发生变化（包括网络中设备的故障状态也没有发生变（包括网络中设备的故障状态也没有发生变化），但由于某个应用程序加入或离开了一个化），但由于某个应用程序加入或离开了一个多播组，多播路由都会发生变化。多播组，多播路由都会发生变化。 在单播路由选择中，只有当拓扑结构变化或设在单播路由选择中，只有当拓扑结构变化或设备出故障时，才会发生路由改变。备出故障时，才会发生路由改变。 2. 多播转发时需要检查分组多播转发时需要检查分组的目的地址和

7、源地址的目的地址和源地址 主机主机E和和F各给各给Group2发送分组。路由器发送分组。路由器R把把E的的分组发送到分组发送到Net2，而把，而把F的分组发送到的分组发送到Net1。 R接收到主机接收到主机A发往发往Group2的分组时，将转发两的分组时，将转发两个副本，分别发送给个副本，分别发送给Net1和和Net2。 多播转发要求路由器不仅检查目的地址，而且多播转发要求路由器不仅检查目的地址，而且还检查源地址，以确定什么时候将多播分组进还检查源地址，以确定什么时候将多播分组进行复制，并转发多播分组的副本。行复制，并转发多播分组的副本。Net1Net3FGA路由器路由器RNet2BCDE3.

8、 任意的发送方任意的发送方 IP允许任意主机（不一定是多播组的成员）允许任意主机（不一定是多播组的成员）向多播组转发分组。主机向多播组转发分组。主机G不是任何多播组的不是任何多播组的成员，并且成员，并且G所在的网络没有所在的网络没有Group1多播组的多播组的成员。但是成员。但是G可以给可以给Group1发送分组。更重要发送分组。更重要的是，该分组穿过互联网时，很可能穿过其它的是，该分组穿过互联网时，很可能穿过其它没有多播组的网络。没有多播组的网络。 可见，多播分组可以由不是多播组成员的主机可见，多播分组可以由不是多播组成员的主机产生，并且可能通过没有任何组成员的网络。产生，并且可能通过没有任

9、何组成员的网络。9.3 多播转发树多播转发树 单播路由协议单播路由协议能找出到达某一目的网络的最短能找出到达某一目的网络的最短路径。路径。 单播路由表项：目的网络地址、下一跳路单播路由表项：目的网络地址、下一跳路由器地址、本路由器的输出接口等字段。由器地址、本路由器的输出接口等字段。 路由器收到单播分组，根据目的路由器收到单播分组，根据目的IP地址，地址，在路由表中找到匹配的表项，把分组从指在路由表中找到匹配的表项，把分组从指定的接口转发出去。定的接口转发出去。多播路由协议多播路由协议实现逆向路由选择实现逆向路由选择 不是将多播分组转发给一个目的网络，而是从不是将多播分组转发给一个目的网络，而

10、是从多播源开始，多播分组沿着多播树转发到本多多播源开始，多播分组沿着多播树转发到本多播组的多个目的网络。播组的多个目的网络。 多播分组从某一特定的源主机发出。所以，多多播分组从某一特定的源主机发出。所以，多播路由器可依据多播源的播路由器可依据多播源的IP地址，通过多播地址，通过多播路由协议选择路由协议选择从目的网络到源的最短路径从目的网络到源的最短路径。 这是一个逆向路由选择过程。这是一个逆向路由选择过程。1多播转发树多播转发树 使用图论术语描述从特定源节点到多播组的所有成员使用图论术语描述从特定源节点到多播组的所有成员的一组路径，这些路径定义了图论中的树，有时也称的一组路径，这些路径定义了图

11、论中的树，有时也称为转发树（为转发树（forwarding tree）。）。 每个多播路由器对应树中的一个每个多播路由器对应树中的一个节点节点（node）。）。 连接两个路由器的网络对应于树中的一条连接两个路由器的网络对应于树中的一条边边（edge）。）。 分组的源节点是树的根（分组的源节点是树的根（root）或）或根节点根节点。 从源节点出发，沿着一条路径到达的最后一个路由从源节点出发，沿着一条路径到达的最后一个路由器称为器称为叶子路由器叶子路由器（leaf router）。）。 连接在叶子路由器上的网络称为连接在叶子路由器上的网络称为叶子网络叶子网络（leaf network）。）。 负责

12、将多播分组通过自身接口发往某个网络的路由负责将多播分组通过自身接口发往某个网络的路由器，称作该网络的器，称作该网络的父路由器父路由器。基于源的树基于源的树(Source Based Tree，SBT) 和共享树（和共享树（Shared Tree，ST） 多播转发树有两种基本类型：多播转发树有两种基本类型： 基于源的树基于源的树SBT，从每个源到接收者之间有，从每个源到接收者之间有不同的树（多棵树）。不同的树（多棵树）。 共享树共享树ST，被所有组成员所共享的一棵树。，被所有组成员所共享的一棵树。 基于源的树基于源的树也称作最短路径树（也称作最短路径树（SPT），用二元），用二元组（组（S，G)

13、表示。使用表示。使用Dijkstra算法计算从源到算法计算从源到所有组成员的最短路径。所有组成员的最短路径。 基于源的树的协议有：基于源的树的协议有：DVMRP、MOSPF、PIM-DM等。等。共享树共享树 共享树是一棵以某个路由器为根，到所有接收共享树是一棵以某个路由器为根，到所有接收者的树。用二元组（者的树。用二元组（*，G）表示。）表示。 这棵共享树可以被多个多播源共享，维护较少这棵共享树可以被多个多播源共享，维护较少的状态信息，但是转发路径未必最优。的状态信息，但是转发路径未必最优。 共享树中树根的位置很重要。如果给每条链路共享树中树根的位置很重要。如果给每条链路指定费用，那么最优的多

14、播路由树就是具有最指定费用，那么最优的多播路由树就是具有最小费用的树。小费用的树。 使用共享树的协议实例主要有：使用共享树的协议实例主要有：CBT (core based tree)、PIM-SM。2. 基于源的树基于源的树 为了进行多播，我们需要这样一棵树为了进行多播，我们需要这样一棵树 源主机是树根，而多播组的成员是树叶，这源主机是树根，而多播组的成员是树叶，这棵树连接了一个多播组的所有节点。棵树连接了一个多播组的所有节点。 从树根到树叶的每一条路径都是可能的最短从树根到树叶的每一条路径都是可能的最短路径（按照某种度量路径（按照某种度量tolerance）。这样的）。这样的树叫最短路径树（

15、树叫最短路径树（Shortest Path Tree，SPT）。）。 SPT描述了描述了IP多播分组在网络中经由的最短多播分组在网络中经由的最短路径。路径。 最短路径树最短路径树SPT路由器路由器RA 接收者接收者A 多播组的源多播组的源S2192.168.0.88组组G：239.0.0.11接收者接收者C 接收者接收者D 多播组的源多播组的源S1192.168.0.66组组G：239.0.0.11接收者接收者B 路由器路由器RC 路由器路由器RE 路由器路由器RD 路由器路由器RB 基于源的树基于源的树 在基于源的树中，一个多播组可能有若干个在基于源的树中，一个多播组可能有若干个SPT，不存

16、在一个中心多播路由器。，不存在一个中心多播路由器。 若互联网中有若互联网中有N个多播组和个多播组和M个不同的源端，个不同的源端，则最多可以有则最多可以有NM个个SPT树，每棵树，每棵SPT树对树对应不同的源和多播组的组合，即由源和多播组应不同的源和多播组的组合，即由源和多播组的组合决定树的结构。的组合决定树的结构。 3. 共享树共享树 共享树也叫汇聚点树（共享树也叫汇聚点树（Rendezous Point Tree，RPT），汇聚点（），汇聚点（Rendezous Point，RP）作）作为为RPT树的公共根。树的公共根。 与基于源的树与基于源的树SPT不同，发送多播分组的源主不同，发送多播分

17、组的源主机不是直接向网络中发送多播分组，而是先把机不是直接向网络中发送多播分组，而是先把分组发往分组发往RPT树的根树的根RP，然后再由，然后再由RP向网络中向网络中的所有成员发送它接收到的多播分组。的所有成员发送它接收到的多播分组。 在从源发送分组到在从源发送分组到RP，从，从RP发送分组到各个接发送分组到各个接收者的过程中，都是以最短路径进行转发。收者的过程中，都是以最短路径进行转发。RPT树树 路由器路由器RA 接收者接收者A 多播组的源多播组的源S2192.168.0.88组组G：239.0.0.11接收者接收者C 接收者接收者D 多播组的源多播组的源S1192.168.0.66组组G

18、：239.0.0.11接收者接收者B 路由器路由器RC 路由器路由器RE 路由器路由器RD 路由器路由器RB RP 从从RP到各个接收者，是相应多播组的唯一的到各个接收者，是相应多播组的唯一的一棵以一棵以RP为多播源的为多播源的SPT树。树。RP汇聚了多播汇聚了多播源。源。 共享树方式，减少了路由器多播路由表中表项共享树方式，减少了路由器多播路由表中表项的数量，降低了对路由器资源的需求，使多播的数量，降低了对路由器资源的需求，使多播更具有扩展性。更具有扩展性。 共享树中的每一个多播组共享同样的树。若有共享树中的每一个多播组共享同样的树。若有N个多播组，则最多有个多播组，则最多有N棵树。每棵树对

19、应一棵树。每棵树对应一个多播组，即由多播组决定树。个多播组，即由多播组决定树。9.4 多播路由算法多播路由算法 9.4.1 最短路径树算法最短路径树算法 9.4.2 最小生成树算法最小生成树算法 9.4.3 Steiner树算法树算法9.4 多播路由算法多播路由算法 多播路由算法用来建立一棵性能良好的多播树，多播路由算法用来建立一棵性能良好的多播树，满足各种业务的服务质量满足各种业务的服务质量QoS需求。需求。 多播路由算法可以分为无约束和基于约束的多多播路由算法可以分为无约束和基于约束的多播路由算法。播路由算法。 约束包括端到端的延迟上限、最小带宽、丢约束包括端到端的延迟上限、最小带宽、丢失

20、概率等。失概率等。 多播树不仅要保证对接收者的可达性，还必多播树不仅要保证对接收者的可达性，还必须保证路由满足须保证路由满足QoS约束。约束。 多播路由算法有静态和动态之分。多播路由算法有静态和动态之分。 静态多播路由算法针对初始多播成员构造一棵静态多播路由算法针对初始多播成员构造一棵多播树，不能根据当前实际传输量和拓扑变化多播树，不能根据当前实际传输量和拓扑变化来做路由选择，而是按初始设计好的路由传送。来做路由选择，而是按初始设计好的路由传送。 动态路由算法随着网络拥塞情况和拓扑的动态动态路由算法随着网络拥塞情况和拓扑的动态变化情况，路由器频繁执行路由选择算法。动变化情况，路由器频繁执行路由

21、选择算法。动态多播路由算法处理成员的加入和离开之后的态多播路由算法处理成员的加入和离开之后的更新问题。更新问题。 多播树通过每个路由器设置路由表而建立起来的，多播树通过每个路由器设置路由表而建立起来的，路由表给出了选择哪个网络接口转发多播分组，路由表给出了选择哪个网络接口转发多播分组，才能送达多播组成员。才能送达多播组成员。9.4.1 最短路径树算法最短路径树算法 最短路径树是从多播源到每个接收者的路径都最短路径树是从多播源到每个接收者的路径都是两者之间最短路径的多播树。是两者之间最短路径的多播树。 若所有链路的权值都为若所有链路的权值都为1，则算法所得到的多，则算法所得到的多播树即为播树即为

22、最小跳（最小跳（hop）树）树。 如果权值代表链路延迟，则得到的就是如果权值代表链路延迟，则得到的就是最小延最小延迟树迟树。 Bellman-Ford算法和算法和Dijkstra算法是两个解算法是两个解决最短路径问题的著名算法。决最短路径问题的著名算法。9.4.2 最小生成树算法最小生成树算法 最小生成树是连接网络中的所有节点，并且树最小生成树是连接网络中的所有节点，并且树的的全部链路权值之和最小全部链路权值之和最小的多播树。的多播树。 Prim算法是解决最小生成树问题的集中式算算法是解决最小生成树问题的集中式算法。法。 在在Prim算法中，树的构造从任意一个根节点算法中，树的构造从任意一个根

23、节点开始，直到所有的组成员连接到树上。每一步，开始，直到所有的组成员连接到树上。每一步，选择一个最小费用边加入已经部分完成的多播选择一个最小费用边加入已经部分完成的多播树，最终得到的多播树具有最小的全局代价。树，最终得到的多播树具有最小的全局代价。 最小生成树算法用于解决树优化问题。最小生成树算法用于解决树优化问题。 9.4.3 Steiner树算法树算法 为了有效利用网络资源，要求多播树的总费用最小。为了有效利用网络资源，要求多播树的总费用最小。 多播树的费用是指多播树中所有链路费用的总和。多播树的费用是指多播树中所有链路费用的总和。 在网络中寻找费用最小的多播树问题在图论中被称在网络中寻找

24、费用最小的多播树问题在图论中被称为为Steiner 树问题，通过求解费用最小的树问题，通过求解费用最小的Steiner树来求解费用最小的多播树。树来求解费用最小的多播树。 所谓所谓Steiner树是指一棵以多播源为根，覆盖所有树是指一棵以多播源为根，覆盖所有多播分组的目的节点的生成树。多播分组的目的节点的生成树。 与最小生成树的区别：最小生成树必须包括网络中与最小生成树的区别：最小生成树必须包括网络中全部节点；全部节点；Steiner树问题只需要求出连接网络中树问题只需要求出连接网络中部分节点（多播组成员）的费用最小的多播树。部分节点（多播组成员）的费用最小的多播树。 9.5 多播路多播路由协

25、议由协议域内域内多播多播路由选择协议路由选择协议多播多播协议协议基于源端树基于源端树共享树共享树9.6 DVMRP距距离离向量多播向量多播路由选择协议路由选择协议Distance Vector Multicast Routing ProtocolDistance Vector Multicast Routing Protocol9.7.1 9.7.1 逆向路径转发逆向路径转发RPFRPF9.7.2 9.7.2 逆向路径广播逆向路径广播RPBRPB与截尾逆向路径广播与截尾逆向路径广播TRPBTRPB9.7.3 9.7.3 逆向路径多播逆向路径多播RPMRPM9.7.4 9.7.4 剪枝和嫁接剪枝

26、和嫁接9.7.5 DVMRP9.7.5 DVMRP的协议行为的协议行为9.6 距离向量多播路由协议距离向量多播路由协议DVMRP DVMRP是基于源的路由协议，首先部署在是基于源的路由协议，首先部署在MBone上，是第一个支持多播功能的路由协议。上，是第一个支持多播功能的路由协议。 DVMRP与与RIP类似，只是增加了支持多播的功能，类似，只是增加了支持多播的功能，是单播的距离向量路由选择协议是单播的距离向量路由选择协议DVRP的扩展。的扩展。 DVMRP为每个多播源构建不同的多播转发树。最为每个多播源构建不同的多播转发树。最短路径以短路径以“跳数跳数”为度量单位。为度量单位。 当一个源向多播

27、组的成员发送分组时，就会建立当一个源向多播组的成员发送分组时，就会建立一棵多播转发树，使用一棵多播转发树，使用“广播和剪枝广播和剪枝”技术维护技术维护多播转发树。多播转发树。DVMRP的重要特性的重要特性 以距离向量为基础、周期性更新路由（缺省为以距离向量为基础、周期性更新路由（缺省为60秒）、秒）、TTL上限是上限是32跳（跳（RIP是是16）、具有逆向）、具有逆向抑制转发功能等。抑制转发功能等。 DVMRP报文封装在报文封装在IP分组中，协议号为分组中，协议号为2（与（与IGMP共用协议号）。共用协议号）。 多播转发树的构建通过多播转发树的构建通过逆向路径转发逆向路径转发机制实现，机制实现

28、，确保多播转发树不会出现回环，而且从源到所有确保多播转发树不会出现回环，而且从源到所有接收者都是最短路径。接收者都是最短路径。DVMRP概述概述 为了支持多播，需要进行两个阶段的处理：为了支持多播，需要进行两个阶段的处理： 需要设计一种需要设计一种广播广播机制，使分组能够转发到互机制，使分组能够转发到互联网的所有网络上；联网的所有网络上； 进一步将机制细化，进一步将机制细化，删除删除那些没有主机属于多那些没有主机属于多点播送组的网络。点播送组的网络。 DVMRP实现了具有逆向路径转发、嫁接和剪枝实现了具有逆向路径转发、嫁接和剪枝的基于源的多播树。的基于源的多播树。 目前已基本上被目前已基本上被

29、PIM所取代所取代 9.6.1 逆向路径转发逆向路径转发RPF DVMRP的最初想法是使用的最初想法是使用RPF。RPF是修正的是修正的洪泛洪泛(接收到信息的节点以广播方式转发数据接收到信息的节点以广播方式转发数据包包)策略策略。 在在RPF中，路由器中，路由器只转发只转发位于从该路由器到源位于从该路由器到源路由器的路由器的最短路径上的分组最短路径上的分组，其它分组都丟掉。，其它分组都丟掉。 路由器在接收到报文后，必须根据源和目的地路由器在接收到报文后，必须根据源和目的地址来确定上游址来确定上游(指向多播源指向多播源)和下游方向，把报和下游方向，把报文文向下游（远离多播源）方向转发向下游（远离

30、多播源）方向转发。逆向路径转发逆向路径转发RPF RPF使用距离向量路由协议使用距离向量路由协议DVRP的单播路由表，的单播路由表，判断一个分组是否走过了最短路径判断一个分组是否走过了最短路径。即用分组的。即用分组的源地址在路由表中查找离开接口，源地址在路由表中查找离开接口， 如果所查到的分组离开接口与到达接口相同，如果所查到的分组离开接口与到达接口相同，则该分组已经走过了最短路径，即该路由器到则该分组已经走过了最短路径，即该路由器到源端的路径是最短的，则转发该分组；源端的路径是最短的，则转发该分组； 否则，不是最短路径，丢弃该分组。否则，不是最短路径，丢弃该分组。最短路径最短路径离开离开到达

31、到达离开离开离开离开分组被转发分组被转发不是最短路径不是最短路径到达到达丢弃丢弃分组被丢弃分组被丢弃逆向路径转发逆向路径转发RPF当路由器在链路当路由器在链路L L上收到来自源节点上收到来自源节点S S的分的分组时，路由器将检查组时，路由器将检查L L是否属于针对是否属于针对S S的最的最短路径。如果是，则该分组被转发到所有短路径。如果是，则该分组被转发到所有除了除了L L的链路上；否则该分组被丢弃。的链路上；否则该分组被丢弃。RPF拒绝转发分组示例拒绝转发分组示例 E0路由器路由器RD路由器路由器RCE1路由器路由器RAS0S1路由器路由器RB来自来自192.168.0.22的多播分组的多播

32、分组路由器路由器RB的单播路由表的单播路由表目的网络目的网络接口接口192.168.0.0/16E1172.16.32.0/24S0202.194.210.0/24E0拒绝转发拒绝转发 RPF同意转发分组示例同意转发分组示例 E0路由器路由器RD路由器路由器RCE1路由器路由器RAS0S1路由器路由器RB来自来自172.16.32.33的多播分组的多播分组路由器路由器RB的单播路由表的单播路由表目的网络目的网络接口接口192.168.0.0/16E1172.16.32.0/24S0202.194.210.0/24E0同意转发同意转发 RPF存在的问题存在的问题Net3收到收到2个个copy R

33、PF中，一个网络可能会收到两个或多个副中，一个网络可能会收到两个或多个副本。其原因是一个网络是图，不是树。本。其原因是一个网络是图，不是树。 例如：例如：Net3有两个父节点。有两个父节点。9.6.2 逆向路径广播逆向路径广播 (RPB)和和截尾逆向路径广播截尾逆向路径广播 (TRPB)1.逆向路径广播逆向路径广播RPB RPB。 父节点的确定父节点的确定：选择到源端路径最短的路由器：选择到源端路径最短的路由器作为指定的父路由器。若有多个这样的路由器，作为指定的父路由器。若有多个这样的路由器，就选择就选择IP地址最小的一个。地址最小的一个。 分组到达每个网络，分组到达每个网络，RPF 和和 R

34、PBR1是是Net1和和Net2的父路由器的父路由器R2是是Net3的父路由器的父路由器2. 截尾逆向路径广播截尾逆向路径广播TRPB 截尾逆向路径广播（截尾逆向路径广播（Truncated Reverse Path Broadcasting，TRPB）算法对）算法对RPB进行了改进。进行了改进。 TRPB多播路由器需要两项信息：多播路由器需要两项信息： 单播路由表单播路由表 通过每个网络接口可达的多播组列表。通过每个网络接口可达的多播组列表。路由器使用路由器使用RPF和多播组列表处理多播分组和多播组列表处理多播分组 当多播分组到达时，路由器首先使用当多播分组到达时，路由器首先使用RPF规则。

35、规则。RPF根据源地址查找单播路由表，来确定是转根据源地址查找单播路由表，来确定是转发分组还是丢弃分组。发分组还是丢弃分组。 如果如果RPF确定确定丢弃分组丢弃分组，则路由器丢弃之；，则路由器丢弃之； 若若RPF转发转发转发该分组转发该分组时，路由器根据目的时，路由器根据目的地址检查地址检查多播组列表多播组列表，确定多播组成员通，确定多播组成员通过某接口是可达的。过某接口是可达的。 如果某接口没有多播组可达，则路由器如果某接口没有多播组可达，则路由器就会跳过该接口，并检查下一个接口。就会跳过该接口，并检查下一个接口。TRPB不向没有组成员的网络发送多播分组不向没有组成员的网络发送多播分组 在一

36、个在一个TRPB多播路由器接收到多播分组时，使多播路由器接收到多播分组时，使用用源地址、目的地址、源地址、目的地址、RPF和多播组列表和多播组列表决定是决定是否丢弃分组，或者是否转发分组到某个接口上。否丢弃分组，或者是否转发分组到某个接口上。 截尾的含义：若某路径上不再有多播组成员时，截尾的含义：若某路径上不再有多播组成员时，路由器就会使转发截止。这样，路由器就会使转发截止。这样，TRPB算法就不算法就不再向没有多播组成员的网络上发送多播分组。再向没有多播组成员的网络上发送多播分组。9.6.3 逆向路径多播逆向路径多播RPM(reverse path multicasting) RPF对分组不

37、是进行多播，而是广播，这是低效对分组不是进行多播，而是广播，这是低效率的。要做到高效率，多播分组必须只到达具有率的。要做到高效率，多播分组必须只到达具有特定多播组成员的网络。特定多播组成员的网络。 而而DVMRP使用广播方式把第一个分组发送到每使用广播方式把第一个分组发送到每一个网络，然后分组还要经历两个过程：修剪一个网络，然后分组还要经历两个过程：修剪Pruning和移植和移植Grafting。 RPM实现了具有逆向路径转发实现了具有逆向路径转发RPF和剪枝算法的和剪枝算法的基于源的树。基于源的树。RPM创建了多播最短路径树，在创建了多播最短路径树，在RPB基础上增加了修剪和移植，以支持动态

38、成员基础上增加了修剪和移植，以支持动态成员的变化。的变化。RPF, RPB, and RPM修剪修剪pruning后后移植移植grafting后后被移植的路由被移植的路由被剪枝的路由被剪枝的路由9.6.4剪枝和嫁接剪枝和嫁接1、洪泛和修剪（剪枝）、洪泛和修剪（剪枝） 每个网络的指定每个网络的指定父路由器使用父路由器使用IGMP负责保持组负责保持组成员的关系成员的关系。 当路由器发现所有下游路由器或所连接的所有网当路由器发现所有下游路由器或所连接的所有网络都对某个多播组没有兴趣时（已经没有多播组络都对某个多播组没有兴趣时（已经没有多播组的成员），那么，该路由器就的成员），那么，该路由器就向上游路

39、由器发送向上游路由器发送修剪报文修剪报文，使它修剪相应的接口，上游路由器就，使它修剪相应的接口，上游路由器就会停止通过这个接口给该路由器发送多播分组。会停止通过这个接口给该路由器发送多播分组。 如果这个路由器从所有下游路由器收到了修剪报如果这个路由器从所有下游路由器收到了修剪报文，则向它的上游路由器发送修剪报文。文，则向它的上游路由器发送修剪报文。 修剪报文用来修剪报文用来删除到达多播组成员不经过的树删除到达多播组成员不经过的树枝枝。洪泛和剪枝洪泛和剪枝 路由器路由器RB 多播组的源多播组的源S 路由器路由器RG路由器路由器RD路由器路由器RE 路由器路由器RA PA路由器路由器RC路由器路由

40、器RFPEPB接收者接收者PC接收者接收者PD叶子路由器叶子路由器洪泛洪泛剪枝剪枝剪枝后的转发树剪枝后的转发树路由器路由器RB 多播组的源多播组的源S 路由器路由器RG路由器路由器RD路由器路由器RE 路由器路由器RA PA路由器路由器RC路由器路由器RFPEPB接收者接收者PC接收者接收者PD2、移植（嫁接）、移植（嫁接） 当已删除树枝上的一个新的主机再想加入多播当已删除树枝上的一个新的主机再想加入多播组时，则会发送一种移植报文，用来使转发树组时，则会发送一种移植报文，用来使转发树中以前剪掉的树枝重新接入。中以前剪掉的树枝重新接入。 由于新的成员可以在任何时候加入到多播组，由于新的成员可以在

41、任何时候加入到多播组，而且新成员可能在某个被剪除的分枝加入，因而且新成员可能在某个被剪除的分枝加入，因此此DVMRP就周期性地重新启动多播树的构造就周期性地重新启动多播树的构造过程过程。 移植报文强迫上游路由器继续发送多播报文。移植报文强迫上游路由器继续发送多播报文。嫁接嫁接 路由器路由器RB 多播组的源多播组的源S 路由器路由器RG路由器路由器RD路由器路由器RE 路由器路由器RA PA路由器路由器RC路由器路由器RFPEPB新加入接收者新加入接收者接收者接收者PC接收者接收者PD加入组报文加入组报文嫁接报文嫁接报文3、默认寿命、默认寿命 所有所有DVMRP修剪报文都有一个字段定义修剪寿修剪

42、报文都有一个字段定义修剪寿命。默认值是命。默认值是2小时。小时。 修剪仅在分组的修剪寿命内有效。之后，自动修剪仅在分组的修剪寿命内有效。之后，自动恢复接收多播报文。恢复接收多播报文。 例如，若某个路由器向上游路由器发送修剪例如，若某个路由器向上游路由器发送修剪报文，并指出修剪寿命为报文，并指出修剪寿命为1小时，表示该路小时，表示该路由器在由器在1小时以内不接收某个特定组的多播小时以内不接收某个特定组的多播报文。在报文。在1小时后，若没有第二个修剪报文，小时后，若没有第二个修剪报文，就可以接收多播分组了。就可以接收多播分组了。 这需要每个路由器对每个活跃组都有一个修剪这需要每个路由器对每个活跃组

43、都有一个修剪计时器。计时器。9.6.5 DVMRP的协议行为的协议行为 DVMRP协议行为通过报文实现，协议行为通过报文实现，DVMRP报文类型：报文类型： 探测报文，用于发现邻居；探测报文，用于发现邻居； 路由通告报文，用于路由信息交换；路由通告报文，用于路由信息交换； 请求邻居列表报文，用于请求邻居列表；请求邻居列表报文，用于请求邻居列表； 邻居请求响应报文，用于响应邻居列表请求；邻居请求响应报文，用于响应邻居列表请求； 剪枝报文，用于剪掉广播树上的某些无用分支；剪枝报文，用于剪掉广播树上的某些无用分支； 嫁接报文，用于嫁接某些又开始起作用的分支；嫁接报文，用于嫁接某些又开始起作用的分支；

44、 嫁接确认报文，用于确认嫁接报文。嫁接确认报文，用于确认嫁接报文。 DVMRP的协议行为主要包括邻居发现、路由交换的协议行为主要包括邻居发现、路由交换和多播路由表维护、源转发树构造、多播转发、剪和多播路由表维护、源转发树构造、多播转发、剪枝和嫁接。枝和嫁接。1. 邻居发现邻居发现 DVMRP路由器定期向所有路由器（路由器定期向所有路由器（224.0.0.4）发送探测报文，发送探测报文，向该接口所连接网络上的其它向该接口所连接网络上的其它路由器说明自己的存在。路由器说明自己的存在。 并且要定时检查接口上的邻居信息。并且要定时检查接口上的邻居信息。 探测报文每探测报文每10秒周期性地从接口转发出去

45、，接秒周期性地从接口转发出去，接口的口的邻居列表邻居列表的每个表项都有的每个表项都有35秒定时器。秒定时器。探测报文是各个探测报文是各个DVMRP路由器路由器定位自己和定位对方的方法定位自己和定位对方的方法 每个接口将探测到的邻居放在探测报文中，再从每个接口将探测到的邻居放在探测报文中，再从该接口转发出去。该接口转发出去。 探测报文提供一种保活机制，使接口能够快速地探测报文提供一种保活机制，使接口能够快速地检测到邻居的丢失。检测到邻居的丢失。 收到邻居发来的探测报文后，如果在接口的邻居收到邻居发来的探测报文后，如果在接口的邻居列表中能够查到发送该报文的接口的列表中能够查到发送该报文的接口的IP

46、地址，则地址，则将邻居列表中的对应表项定时器刷新。将邻居列表中的对应表项定时器刷新。 如果一个邻居丢失，那么该邻居肯定不会向外发如果一个邻居丢失，那么该邻居肯定不会向外发送探测报文，导致定时器超时。通过这种方式能送探测报文，导致定时器超时。通过这种方式能检测到邻居的丢失。检测到邻居的丢失。2. 路由交换路由交换 在在DVMRP中，路由器在邻居之间定期（中，路由器在邻居之间定期（60秒）发秒）发送送路由通告报文。路由通告报文。 根据信息通告，各个路由器计算自己的路由表，根据信息通告，各个路由器计算自己的路由表，等路由表收敛后，针对每个源，路由器的上下游等路由表收敛后，针对每个源，路由器的上下游关

47、系就确定了，上游接口和下游接口列表也就形关系就确定了，上游接口和下游接口列表也就形成了。成了。 上游接口上游接口是路由器从多播源接收多播分组的接是路由器从多播源接收多播分组的接口，上游接口也是口，上游接口也是RPF接口。接口。 下游接口下游接口是多播分组的转发接口。是多播分组的转发接口。 经过路由交换后，基于源网络的多播转发树就形经过路由交换后，基于源网络的多播转发树就形成了。成了。3源树构造源树构造 为了建立一个截尾广播树，为了建立一个截尾广播树， DVMRP路由器通过路由器通过一个特殊的一个特殊的逆向抑制路由通告逆向抑制路由通告，来通知上游路由，来通知上游路由器，说明它处于下游。器，说明它

48、处于下游。 逆向抑制路由通告告诉上游路由器，把逆向抑制路由通告告诉上游路由器，把“我我”放放在该源网络的截尾广播树上。即，把任何来自源在该源网络的截尾广播树上。即，把任何来自源的多播分组从该接口上转发出去，以便下游路由的多播分组从该接口上转发出去，以便下游路由器可以接收到它。器可以接收到它。 当某个多播源开始传输多播分组的时候，多播分当某个多播源开始传输多播分组的时候，多播分组沿着截尾广播树向下传送到网络的所有节点。组沿着截尾广播树向下传送到网络的所有节点。 如果某些网络中不存在接收者，如果某些网络中不存在接收者，DVMRP路由器就路由器就会将不需要的分支剪枝掉。会将不需要的分支剪枝掉。4多播

49、转发多播转发 在多播模型中，源主机根据在多播模型中，源主机根据IP分组的多播地分组的多播地址，向该多播组的所有成员发送信息。址，向该多播组的所有成员发送信息。 DVMRP协议利用逆向路径转发（协议利用逆向路径转发（RPF）算法，）算法，决定是否转发多播分组。决定是否转发多播分组。5、DVMRP的修剪与移植的修剪与移植 当修剪区域内出现了多播组成员时，下游不必等当修剪区域内出现了多播组成员时，下游不必等待上游修剪状态超时，而是待上游修剪状态超时，而是主动向上游发送移植主动向上游发送移植报文报文，以使修剪状态变为转发状态。，以使修剪状态变为转发状态。 DVMRP是由数据触发驱动建立多播路由表是由数

50、据触发驱动建立多播路由表 路由树的建立过程可以概括为路由树的建立过程可以概括为“广播与修剪广播与修剪” 转发特点可以概括为转发特点可以概括为“被动接受，主动退出被动接受，主动退出”。DVMRP嫁接机制使用嫁接确认报文嫁接机制使用嫁接确认报文 为了增加可靠性，上游路由器接收到嫁接报文为了增加可靠性，上游路由器接收到嫁接报文后，需要发送嫁接确认报文，确认嫁接己经完后，需要发送嫁接确认报文，确认嫁接己经完成。成。 可以防止由于拥塞等原因而引起的嫁接报文可以防止由于拥塞等原因而引起的嫁接报文丢失。丢失。 如果嫁接报文丢失或者嫁接确认报文丢失，如果嫁接报文丢失或者嫁接确认报文丢失，则需要重传嫁接报文。则

51、需要重传嫁接报文。 嫁接报文被一跳一跳地向上游传送，直到到达嫁接报文被一跳一跳地向上游传送，直到到达该多播源的多播转发树。同时，嫁接确认报文该多播源的多播转发树。同时，嫁接确认报文也一跳一跳向下传送。也一跳一跳向下传送。9.7 MOSPF多播多播开开放最短路放最短路径优先协议径优先协议(Multicast Open Shortest Path First Routing)(Multicast Open Shortest Path First Routing)1、OSPF的最短路径生成树的最短路径生成树 在使用在使用OSPF协议的网络中，每个路由器监测协议的网络中，每个路由器监测直接相连的链路状

52、态，当状态改变时，向所有直接相连的链路状态，当状态改变时，向所有其它路由器发送一个更新信息。其它路由器发送一个更新信息。 每个路由器都可以基于一个共同的链路状态数每个路由器都可以基于一个共同的链路状态数据库，了解整个网络的拓扑图。据库，了解整个网络的拓扑图。 然后使用然后使用Dijkstra算法计算出以该路由器为根、算法计算出以该路由器为根、到达所有其它路由器的最短路径树。到达所有其它路由器的最短路径树。2、对、对OSPF的扩展的扩展 在在MOSPF中，路由器通过中，路由器通过IGMP周期性地收周期性地收集多播组成员的信息。集多播组成员的信息。 组成员信息和链路状态信息组成员信息和链路状态信息

53、一起被周期性地一起被周期性地传送到这个路由区域中的其它路由器。传送到这个路由区域中的其它路由器。 这样，每个路由器都知道各个多播组的所有这样，每个路由器都知道各个多播组的所有成员的位置。成员的位置。 根据从邻接路由器接收到的消息，路由器将根据从邻接路由器接收到的消息，路由器将修改自己的链路状态信息。修改自己的链路状态信息。路由器不预先计算特定源的多播树路由器不预先计算特定源的多播树 使用使用Dijkstra算法计算从源到所有组成员的最算法计算从源到所有组成员的最短路径生成树。短路径生成树。 计算很费时，所以路由器并不预先计算特定源计算很费时，所以路由器并不预先计算特定源的多播树。的多播树。 在

54、接收到在接收到IP多播分组后，路由器才对该报文多播分组后，路由器才对该报文的源点计算到其组成员的生成树。这样可以节的源点计算到其组成员的生成树。这样可以节省时间。省时间。MOSPF把把AS划分成路由区域划分成路由区域 与与OSPF类似，类似，MOSPF把整个把整个AS划分成多个划分成多个路由区域，这些不同的路由区域与一个主干路路由区域，这些不同的路由区域与一个主干路由区域相互连接。由区域相互连接。 根据路由器功能的不同，根据路由器功能的不同，MOSPF路由器可以路由器可以分为域内路由器、域间路由器、主干路由器和分为域内路由器、域间路由器、主干路由器和AS边界路由器。边界路由器。MOSPF的扩展

55、性不好的扩展性不好 当组成员发生变化时，当组成员发生变化时，MOSPF将向区域内的将向区域内的所有路由器发布链路状态通告所有路由器发布链路状态通告LSA更新，导致更新，导致所有多播树中路由器更新自己的路由状态。所有多播树中路由器更新自己的路由状态。 如果组成员变化频繁，如果组成员变化频繁，MOSPF将会发送大量将会发送大量的的LSA更新，并且触发大量的路由计算。所以更新，并且触发大量的路由计算。所以MOSPF的扩展性并不好。的扩展性并不好。 MOSPF没有得到广泛应用。没有得到广泛应用。MOSPF不支持隧不支持隧道机制，也不支持增量部署。道机制，也不支持增量部署。9.8 CBT核心基核心基干树

56、干树9.8.1 9.8.1 树的形成树的形成9.8.2 9.8.2 发送多播分组发送多播分组 CBT是共享树，即多播中的所有源节点共享这是共享树，即多播中的所有源节点共享这棵树，使用一个核心作为树根。棵树，使用一个核心作为树根。 自治系统划分为多个区，每个区选择一个核心自治系统划分为多个区，每个区选择一个核心-汇集路由器。汇集路由器。9.8.1 树的形成树的形成 当汇集路由器选好后，就将它的单播地址通知给当汇集路由器选好后，就将它的单播地址通知给每个路由器。每个路由器发送单播每个路由器。每个路由器发送单播“加入报文加入报文”（类似于移植报文）表示它愿意加入该组。（类似于移植报文）表示它愿意加入

57、该组。 在在“加入报文加入报文”发送到汇集路由器的路径中，所发送到汇集路由器的路径中，所有中间路由器有中间路由器从报文中提取必要的信息从报文中提取必要的信息（例如：（例如：发送站的单播地址、该报文到达的接口），然后发送站的单播地址、该报文到达的接口），然后将报文转发给下一个路由器。将报文转发给下一个路由器。 当汇集路由器收到一个多播组的每个成员发来的当汇集路由器收到一个多播组的每个成员发来的所有加入报文后，树就形成了。所有加入报文后，树就形成了。 每个路由器都知道它的上游路由器（通往树根的每个路由器都知道它的上游路由器（通往树根的路由器）和下游路由器（通往树叶的路由器）。路由器）和下游路由器（

58、通往树叶的路由器）。具有汇集路由器的组具有汇集路由器的组共享共享树树 若某个路由器想退出该组，就给它的上游路由器发若某个路由器想退出该组，就给它的上游路由器发送送“退出退出”报文报文。上游路由器就从树中删除到该路。上游路由器就从树中删除到该路由器的链路，并把该报文转发给它的上游路由器。由器的链路，并把该报文转发给它的上游路由器。汇集路由器汇集路由器成员成员成员成员成员成员成员成员成员成员 CBT构造过程构造过程 R2R4R7R1S核心路由器核心路由器MR5R3R6R8MMMjoinJoin-ack组成员组成员组成员组成员组成员组成员欲加入多播组欲加入多播组IGMP成员关成员关系报告报文系报告报

59、文CBT多播树是双向的多播树是双向的 在在CBT中，接口没有父子关系，接口只有两个中，接口没有父子关系，接口只有两个状态：要么在树中，要么不在树中。状态：要么在树中，要么不在树中。 非多播组成员的源节点向着核心路由器的方向非多播组成员的源节点向着核心路由器的方向发送分组，直到到达某个已经在树中的节点。发送分组，直到到达某个已经在树中的节点。 从这个节点开始，分组被转发到在多播组中的从这个节点开始，分组被转发到在多播组中的所有接口，除了收到分组的那个接口。所有接口，除了收到分组的那个接口。 并不是所有分组都通过核心路由器转发，从而并不是所有分组都通过核心路由器转发，从而减轻核心路由器进行分组转发

60、的负担。减轻核心路由器进行分组转发的负担。CBT不采用逆向路径检查机制不采用逆向路径检查机制 CBT通过保证通过保证join报文和报文和join-ack报文经过完报文经过完全相同（方向相反）的路径进行传递，来保证全相同（方向相反）的路径进行传递，来保证不出现循环。不出现循环。 如果如果join报文和报文和join-ack报文的路径不一致，报文的路径不一致，CBT就认为出现了路由循环，并重新启动加入就认为出现了路由循环，并重新启动加入过程。过程。共享树共享树成员成员成员成员成员成员成员成员成员成员图例图例单播单播多播多播核心路由器核心路由器源端源端9.8.2 发送多播分组发送多播分组 形成了多播