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

多播技术郑州大学信息工程学院李向丽第9章多播路由技术9.7多播开放最短路径优先MOSPF9.8基于核心的树CBT9.9PIM-DM9.10PIM-SM9.11域间多播技术9.12多播主干MBone9.13IPv6多播技术9.1在局域网LAN上的多播9.2多播转发和路由选择信息9.3多播转发树9.4多播路由算法9.5多播路由协议9.6距离向量多播路由协议DVMRP9.1在局域网LAN上的多播多播源和多播组成员关系多播源和所有成员同在一个以太网上。则不需要多播控制协议。多播源将多播IP分组封装在以太网帧中。以太网帧的目的MAC地址为一个基于IP多播地址的多播映射地址。以太网上的多播组成员监听这个多播物理地址，接收此多播分组。非多播组成员则丢弃收到的多播分组。多播源不在本地LAN中，路由器判断该LAN中是否有多播组成员。如果有，则将多播分组转发给LAN；如果没有，则不向此LAN转发该多播分组。交换式LAN上的多播实现交换机LAN通过一台路由器连接到互联网中。首先，路由器通过使用IGMP报文，获知LAN上是否有组成员存在。若有，则将多播分组转发到交换式LAN上。其次，交换机对目的MAC地址转发该分组。但是IGMP是第三层协议，交换机的MAC地址转发表中没有此多播MAC地址的转发表项（多播地址，输出接口），会导致交换机只能洪泛多播分组。对于大型交换式局域网，这将影响网络的运行效率。交换机LAN对多播分组转发的解决方法⑴手工配置交换机转发表。⑵使用通用多播注册协议（GeneralMulticastRegisterProtocol，GMRP）。⑶IGMP侦听（IGMPSnooping）。⑷通过CGMP协议（CiscoGroupManageProtocol）。9.2多播转发和路由选择信息多播转发和路由选择与单播情况不相同，并且相当复杂。通过下图的例子进行说明。“○”标记多播组Group1，成员有主机A、B和C“△”标记多播组Group2，成员有主机D、E和FNet2没有Group1的成员。○△△△○Net1Net3○FGA路由器RNet2BCDE1.对动态路由选择的需求在多播路由选择中，即使网络拓扑不发生变化（包括网络中设备的故障状态也没有发生变化），但由于某个应用程序加入或离开了一个多播组，多播路由都会发生变化。在单播路由选择中，只有当拓扑结构变化或设备出故障时，才会发生路由改变。2.多播转发时需要检查分组的目的地址和源地址主机E和F各给Group2发送分组。路由器R把E的分组发送到Net2，而把F的分组发送到Net1。R接收到主机A发往Group2的分组时，将转发两个副本，分别发送给Net1和Net2。多播转发要求路由器不仅检查目的地址，而且还检查源地址，以确定什么时候将多播分组进行复制，并转发多播分组的副本。○△△△○Net1Net3○FGA路由器RNet2BCDE3.任意的发送方IP允许任意主机（不一定是多播组的成员）向多播组转发分组。主机G不是任何多播组的成员，并且G所在的网络没有Group1多播组的成员。但是G可以给Group1发送分组。更重要的是，该分组穿过互联网时，很可能穿过其它没有多播组的网络。可见，多播分组可以由不是多播组成员的主机产生，并且可能通过没有任何组成员的网络。9.3多播转发树单播路由协议能找出到达某一目的网络的最短路径。单播路由表项：目的网络地址、下一跳路由器地址、本路由器的输出接口等字段。路由器收到单播分组，根据目的IP地址，在路由表中找到匹配的表项，把分组从指定的接口转发出去。多播路由协议实现逆向路由选择不是将多播分组转发给一个目的网络，而是从多播源开始，多播分组沿着多播树转发到本多播组的多个目的网络。多播分组从某一特定的源主机发出。所以，多播路由器可依据多播源的IP地址，通过多播路由协议选择从目的网络到源的最短路径。这是一个逆向路由选择过程。1．多播转发树使用图论术语描述从特定源节点到多播组的所有成员的一组路径，这些路径定义了图论中的树，有时也称为转发树（forwardingtree）。每个多播路由器对应树中的一个节点（node）。连接两个路由器的网络对应于树中的一条边（edge）。分组的源节点是树的根（root）或根节点。从源节点出发，沿着一条路径到达的最后一个路由器称为叶子路由器（leafrouter）。连接在叶子路由器上的网络称为叶子网络（leafnetwork）。负责将多播分组通过自身接口发往某个网络的路由器，称作该网络的父路由器。基于源的树(SourceBasedTree，SBT)和共享树（SharedTree，ST）多播转发树有两种基本类型：基于源的树SBT，从每个源到接收者之间有不同的树（多棵树）。共享树ST，被所有组成员所共享的一棵树。基于源的树也称作最短路径树（SPT），用二元组（S，G)表示。使用Dijkstra算法计算从源到所有组成员的最短路径。基于源的树的协议有：DVMRP、MOSPF、PIM-DM等。共享树共享树是一棵以某个路由器为根，到所有接收者的树。用二元组（*，G）表示。这棵共享树可以被多个多播源共享，维护较少的状态信息，但是转发路径未必最优。共享树中树根的位置很重要。如果给每条链路指定费用，那么最优的多播路由树就是具有最小费用的树。使用共享树的协议实例主要有：CBT(corebasedtree)、PIM-SM。2.基于源的树为了进行多播，我们需要这样一棵树源主机是树根，而多播组的成员是树叶，这棵树连接了一个多播组的所有节点。从树根到树叶的每一条路径都是可能的最短路径（按照某种度量tolerance）。这样的树叫最短路径树（ShortestPathTree，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，不存在一个中心多播路由器。若互联网中有N个多播组和M个不同的源端，则最多可以有N×M个SPT树，每棵SPT树对应不同的源和多播组的组合，即由源和多播组的组合决定树的结构。3.共享树共享树也叫汇聚点树（RendezousPointTree，RPT），汇聚点（RendezousPoint，RP）作为RPT树的公共根。与基于源的树SPT不同，发送多播分组的源主机不是直接向网络中发送多播分组，而是先把分组发往RPT树的根RP，然后再由RP向网络中的所有成员发送它接收到的多播分组。在从源发送分组到RP，从RP发送分组到各个接收者的过程中，都是以最短路径进行转发。RPT树路由器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路由器RBRP从RP到各个接收者，是相应多播组的唯一的一棵以RP为多播源的SPT树。RP汇聚了多播源。共享树方式，减少了路由器多播路由表中表项的数量，降低了对路由器资源的需求，使多播更具有扩展性。共享树中的每一个多播组共享同样的树。若有N个多播组，则最多有N棵树。每棵树对应一个多播组，即由多播组决定树。9.4多播路由算法9.4.1最短路径树算法9.4.2最小生成树算法9.4.3Steiner树算法9.4多播路由算法多播路由算法用来建立一棵性能良好的多播树，满足各种业务的服务质量QoS需求。多播路由算法可以分为无约束和基于约束的多播路由算法。约束包括端到端的延迟上限、最小带宽、丢失概率等。多播树不仅要保证对接收者的可达性，还必须保证路由满足QoS约束。多播路由算法有静态和动态之分。静态多播路由算法针对初始多播成员构造一棵多播树，不能根据当前实际传输量和拓扑变化来做路由选择，而是按初始设计好的路由传送。动态路由算法随着网络拥塞情况和拓扑的动态变化情况，路由器频繁执行路由选择算法。动态多播路由算法处理成员的加入和离开之后的更新问题。多播树通过每个路由器设置路由表而建立起来的，路由表给出了选择哪个网络接口转发多播分组，才能送达多播组成员。9.4.1最短路径树算法最短路径树是从多播源到每个接收者的路径都是两者之间最短路径的多播树。若所有链路的权值都为1，则算法所得到的多播树即为最小跳（hop）树。如果权值代表链路延迟，则得到的就是最小延迟树。Bellman-Ford算法和Dijkstra算法是两个解决最短路径问题的著名算法。9.4.2最小生成树算法最小生成树是连接网络中的所有节点，并且树的全部链路权值之和最小的多播树。Prim算法是解决最小生成树问题的集中式算法。在Prim算法中，树的构造从任意一个根节点开始，直到所有的组成员连接到树上。每一步，选择一个最小费用边加入已经部分完成的多播树，最终得到的多播树具有最小的全局代价。最小生成树算法用于解决树优化问题。9.4.3Steiner树算法为了有效利用网络资源，要求多播树的总费用最小。多播树的费用是指多播树中所有链路费用的总和。在网络中寻找费用最小的多播树问题在图论中被称为Steiner树问题，通过求解费用最小的Steiner树来求解费用最小的多播树。所谓Steiner树是指一棵以多播源为根，覆盖所有多播分组的目的节点的生成树。与最小生成树的区别：最小生成树必须包括网络中全部节点；Steiner树问题只需要求出连接网络中部分节点（多播组成员）的费用最小的多播树。9.5多播路由协议域内多播路由选择协议多播协议基于源端树共享树9.6DVMRP距离向量多播路由选择协议DistanceVectorMulticastRoutingProtocol9.7.1逆向路径转发RPF9.7.2逆向路径广播RPB与截尾逆向路径广播TRPB9.7.3逆向路径多播RPM9.7.4剪枝和嫁接9.7.5DVMRP的协议行为9.6距离向量多播路由协议DVMRPDVMRP是基于源的路由协议，首先部署在MBone上，是第一个支持多播功能的路由协议。DVMRP与RIP类似，只是增加了支持多播的功能，是单播的距离向量路由选择协议DVRP的扩展。DVMRP为每个多播源构建不同的多播转发树。最短路径以“跳数”为度量单位。当一个源向多播组的成员发送分组时，就会建立一棵多播转发树，使用“广播和剪枝”技术维护多播转发树。DVMRP的重要特性以距离向量为基础、周期性更新路由（缺省为60秒）、TTL上限是32跳（RIP是16）、具有逆向抑制转发功能等。DVMRP报文封装在IP分组中，协议号为2（与IGMP共用协议号）。多播转发树的构建通过逆向路径转发机制实现，确保多播转发树不会出现回环，而且从源到所有接收者都是最短路径。DVMRP概述为了支持多播，需要进行两个阶段的处理：需要设计一种广播机制，使分组能够转发到互联网的所有网络上；进一步将机制细化，删除那些没有主机属于多点播送组的网络。DVMRP实现了具有逆向路径转发、嫁接和剪枝的基于源的多播树。目前已基本上被PIM所取代9.6.1逆向路径转发RPFDVMRP的最初想法是使用RPF。RPF是修正的洪泛(接收到信息的节点以广播方式转发数据包)策略。在RPF中，路由器只转发位于从该路由器到源路由器的最短路径上的分组，其它分组都丟掉。路由器在接收到报文后，必须根据源和目的地址来确定上游(指向多播源)和下游方向，把报文向下游（远离多播源）方向转发。逆向路径转发RPFRPF使用距离向量路由协议DVRP的单播路由表，判断一个分组是否走过了最短路径。即用分组的源地址在路由表中查找离开接口，如果所查到的分组离开接口与到达接口相同，则该分组已经走过了最短路径，即该路由器到源端的路径是最短的，则转发该分组；否则，不是最短路径，丢弃该分组。最短路径离开到达离开离开分组被转发不是最短路径到达丢弃分组被丢弃逆向路径转发RPF当路由器在链路L上收到来自源节点S的分组时，路由器将检查L是否属于针对S的最短路径。如果是，则该分组被转发到所有除了L的链路上；否则该分组被丢弃。RPF拒绝转发分组示例E0路由器RD路由器RCE1路由器RAS0S1路由器RB来自192.168.0.22的多播分组路由器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

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

RPB创建了从源到目的端的一条最短路径广播树，它保证分组到达每个网络，每个目的端只接收到一份且只有一份分组的副本。RPF和RPBR1是Net1和Net2的父路由器R2是Net3的父路由器2.截尾逆向路径广播TRPB截尾逆向路径广播（TruncatedReversePathBroadcasting，TRPB）算法对RPB进行了改进。TRPB多播路由器需要两项信息：单播路由表通过每个网络接口可达的多播组列表。路由器使用RPF和多播组列表处理多播分组当多播分组到达时，路由器首先使用RPF规则。RPF根据源地址查找单播路由表，来确定是转发分组还是丢弃分组。如果RPF确定丢弃分组，则路由器丢弃之；若RPF转发转发该分组时，路由器根据目的地址检查多播组列表，确定多播组成员通过某接口是可达的。如果某接口没有多播组可达，则路由器就会跳过该接口，并检查下一个接口。TRPB不向没有组成员的网络发送多播分组在一个TRPB多播路由器接收到多播分组时，使用源地址、目的地址、RPF和多播组列表决定是否丢弃分组，或者是否转发分组到某个接口上。截尾的含义：若某路径上不再有多播组成员时，路由器就会使转发截止。这样，TRPB算法就不再向没有多播组成员的网络上发送多播分组。9.6.3逆向路径多播RPM(reversepathmulticasting)RPF对分组不是进行多播，而是广播，这是低效率的。要做到高效率，多播分组必须只到达具有特定多播组成员的网络。而DVMRP使用广播方式把第一个分组发送到每一个网络，然后分组还要经历两个过程：修剪Pruning和移植Grafting。RPM实现了具有逆向路径转发RPF和剪枝算法的基于源的树。RPM创建了多播最短路径树，在RPB基础上增加了修剪和移植，以支持动态成员的变化。RPF,RPB,andRPM修剪pruning后移植grafting后被移植的路由被剪枝的路由9.6.4剪枝和嫁接1、洪泛和修剪（剪枝）每个网络的指定父路由器使用IGMP负责保持组成员的关系。当路由器发现所有下游路由器或所连接的所有网络都对某个多播组没有兴趣时（已经没有多播组的成员），那么，该路由器就向上游路由器发送修剪报文，使它修剪相应的接口，上游路由器就会停止通过这个接口给该路由器发送多播分组。如果这个路由器从所有下游路由器收到了修剪报文，则向它的上游路由器发送修剪报文。修剪报文用来删除到达多播组成员不经过的树枝。洪泛和剪枝路由器RB

多播组的源S路由器RG路由器RD路由器RE路由器RAPA路由器RC路由器RFPEPB接收者PC接收者PD叶子路由器洪泛剪枝剪枝后的转发树路由器RB

多播组的源S路由器RG路由器RD路由器RE路由器RAPA路由器RC路由器RFPEPB接收者PC接收者PD2、移植（嫁接）当已删除树枝上的一个新的主机再想加入多播组时，则会发送一种移植报文，用来使转发树中以前剪掉的树枝重新接入。由于新的成员可以在任何时候加入到多播组，而且新成员可能在某个被剪除的分枝加入，因此DVMRP就周期性地重新启动多播树的构造过程。移植报文强迫上游路由器继续发送多播报文。嫁接路由器RB多播组的源S路由器RG路由器RD路由器RE路由器RAPA路由器RC路由器RFPEPB新加入接收者接收者PC接收者PD加入组报文嫁接报文3、默认寿命所有DVMRP修剪报文都有一个字段定义修剪寿命。默认值是2小时。修剪仅在分组的修剪寿命内有效。之后，自动恢复接收多播报文。例如，若某个路由器向上游路由器发送修剪报文，并指出修剪寿命为1小时，表示该路由器在1小时以内不接收某个特定组的多播报文。在1小时后，若没有第二个修剪报文，就可以接收多播分组了。这需要每个路由器对每个活跃组都有一个修剪计时器。9.6.5DVMRP的协议行为DVMRP协议行为通过报文实现，DVMRP报文类型：探测报文，用于发现邻居；路由通告报文，用于路由信息交换；请求邻居列表报文，用于请求邻居列表；邻居请求响应报文，用于响应邻居列表请求；剪枝报文，用于剪掉广播树上的某些无用分支；嫁接报文，用于嫁接某些又开始起作用的分支；嫁接确认报文，用于确认嫁接报文。DVMRP的协议行为主要包括邻居发现、路由交换和多播路由表维护、源转发树构造、多播转发、剪枝和嫁接。1.邻居发现DVMRP路由器定期向所有路由器（224.0.0.4）发送探测报文，向该接口所连接网络上的其它路由器说明自己的存在。并且要定时检查接口上的邻居信息。探测报文每10秒周期性地从接口转发出去，接口的邻居列表的每个表项都有35秒定时器。探测报文是各个DVMRP路由器定位自己和定位对方的方法每个接口将探测到的邻居放在探测报文中，再从该接口转发出去。探测报文提供一种保活机制，使接口能够快速地检测到邻居的丢失。收到邻居发来的探测报文后，如果在接口的邻居列表中能够查到发送该报文的接口的IP地址，则将邻居列表中的对应表项定时器刷新。如果一个邻居丢失，那么该邻居肯定不会向外发送探测报文，导致定时器超时。通过这种方式能检测到邻居的丢失。2.路由交换在DVMRP中，路由器在邻居之间定期（60秒）发送路由通告报文。根据信息通告，各个路由器计算自己的路由表，等路由表收敛后，针对每个源，路由器的上下游关系就确定了，上游接口和下游接口列表也就形成了。上游接口是路由器从多播源接收多播分组的接口，上游接口也是RPF接口。下游接口是多播分组的转发接口。经过路由交换后，基于源网络的多播转发树就形成了。3．源树构造为了建立一个截尾广播树，DVMRP路由器通过一个特殊的逆向抑制路由通告，来通知上游路由器，说明它处于下游。逆向抑制路由通告告诉上游路由器，把“我”放在该源网络的截尾广播树上。即，把任何来自源的多播分组从该接口上转发出去，以便下游路由器可以接收到它。当某个多播源开始传输多播分组的时候，多播分组沿着截尾广播树向下传送到网络的所有节点。如果某些网络中不存在接收者，DVMRP路由器就会将不需要的分支剪枝掉。4．多播转发在多播模型中，源主机根据IP分组的多播地址，向该多播组的所有成员发送信息。DVMRP协议利用逆向路径转发（RPF）算法，决定是否转发多播分组。5、DVMRP的修剪与移植当修剪区域内出现了多播组成员时，下游不必等待上游修剪状态超时，而是主动向上游发送移植报文，以使修剪状态变为转发状态。DVMRP是由数据触发驱动建立多播路由表路由树的建立过程可以概括为“广播与修剪”转发特点可以概括为“被动接受，主动退出”。DVMRP嫁接机制使用嫁接确认报文为了增加可靠性，上游路由器接收到嫁接报文后，需要发送嫁接确认报文，确认嫁接己经完成。可以防止由于拥塞等原因而引起的嫁接报文丢失。如果嫁接报文丢失或者嫁接确认报文丢失，则需要重传嫁接报文。嫁接报文被一跳一跳地向上游传送，直到到达该多播源的多播转发树。同时，嫁接确认报文也一跳一跳向下传送。9.7MOSPF多播开放最短路径优先协议(MulticastOpenShortestPathFirstRouting)

MOSPF是OSPF的扩展，它使用多播链路状态路由选择创建源端基准树。1、OSPF的最短路径生成树在使用OSPF协议的网络中，每个路由器监测直接相连的链路状态，当状态改变时，向所有其它路由器发送一个更新信息。每个路由器都可以基于一个共同的链路状态数据库，了解整个网络的拓扑图。然后使用Dijkstra算法计算出以该路由器为根、到达所有其它路由器的最短路径树。2、对OSPF的扩展在MOSPF中，路由器通过IGMP周期性地收集多播组成员的信息。组成员信息和链路状态信息一起被周期性地传送到这个路由区域中的其它路由器。这样，每个路由器都知道各个多播组的所有成员的位置。根据从邻接路由器接收到的消息，路由器将修改自己的链路状态信息。路由器不预先计算特定源的多播树使用Dijkstra算法计算从源到所有组成员的最短路径生成树。计算很费时，所以路由器并不预先计算特定源的多播树。在接收到IP多播分组后，路由器才对该报文的源点计算到其组成员的生成树。这样可以节省时间。MOSPF把AS划分成路由区域与OSPF类似，MOSPF把整个AS划分成多个路由区域，这些不同的路由区域与一个主干路由区域相互连接。根据路由器功能的不同，MOSPF路由器可以分为域内路由器、域间路由器、主干路由器和AS边界路由器。MOSPF的扩展性不好当组成员发生变化时，MOSPF将向区域内的所有路由器发布链路状态通告LSA更新，导致所有多播树中路由器更新自己的路由状态。如果组成员变化频繁，MOSPF将会发送大量的LSA更新，并且触发大量的路由计算。所以MOSPF的扩展性并不好。MOSPF没有得到广泛应用。MOSPF不支持隧道机制，也不支持增量部署。9.8CBT核心基干树9.8.1树的形成9.8.2发送多播分组CBT是共享树，即多播中的所有源节点共享这棵树，使用一个核心作为树根。自治系统划分为多个区，每个区选择一个核心-汇集路由器。9.8.1树的形成当汇集路由器选好后，就将它的单播地址通知给每个路由器。每个路由器发送单播“加入报文”（类似于移植报文）表示它愿意加入该组。在“加入报文”发送到汇集路由器的路径中，所有中间路由器从报文中提取必要的信息（例如：发送站的单播地址、该报文到达的接口），然后将报文转发给下一个路由器。当汇集路由器收到一个多播组的每个成员发来的所有加入报文后，树就形成了。每个路由器都知道它的上游路由器（通往树根的路由器）和下游路由器（通往树叶的路由器）。具有汇集路由器的组共享树若某个路由器想退出该组，就给它的上游路由器发送“退出”报文。上游路由器就从树中删除到该路由器的链路，并把该报文转发给它的上游路由器。汇集路由器成员成员成员成员成员CBT构造过程R2R4R7R1S核心路由器MR5R3R6R8MMMjoinJoin-ack组成员组成员组成员欲加入多播组IGMP成员关系报告报文CBT多播树是双向的在CBT中，接口没有父子关系，接口只有两个状态：要么在树中，要么不在树中。非多播组成员的源节点向着核心路由器的方向发送分组，直到到达某个已经在树中的节点。从这个节点开始，分组被转发到在多播组中的所有接口，除了收到分组的那个接口。并不是所有分组都通过核心路由器转发，从而减轻核心路由器进行分组转发的负担。CBT不采用逆向路径检查机制CBT通过保证join报文和join-ack报文经过完全相同（方向相反）的路径进行传递，来保证不出现循环。如果join报文和join-ack报文的路径不一致，CBT就认为出现了路由循环，并重新启动加入过程。共享树成员成员成员成员成员图例单播多播核心路由器源端9.8.2发送多播分组形成了多播树后，任何一个源端都可以向该组的成员发送多播分组。使用单播地址就可以把分组发送给这个汇集路由器；然后汇集路由器再把这个分组分发到所有组的成员。多播分组从源端向组成员

发送分组的过程CBT中，分组从源端向组成员发送的过程如下：源端将多播分组封装在一个单播分组中。单播地址就是该核心（汇集路由器）地址，把分组发送给核心。核心拆封单播分组，然后转发给所有感兴趣的接口。接着，收到多播分组的每个路由器再把它转发到所有感兴趣的接口。CBT与DVMRP和MOSPF的不同在树的形成上，CBT是从树叶制作的，DVMRP和MOSPF是从树根制作的。DVMRP中，先构造广播树，然后再修剪；而在CBT中，开始并没有树，使用加入（移植）的方法逐渐地建立树。单播协议相关上，CBT使用单播路由表就可以获得通往汇集路由器的下一跳路由器信息，这样CBT就可以与任何一个单播路由协议协同工作。DVMRP和MOSPF都只能与特定的单播路由协议协同工作。PIM协议无关多播Protocol-independentmulticastPIM不依赖任何具体的底层单播路由算法

PIM采用了PIM-DM（densemode）和PIM-SM（sparsemode）协议PIM有两种不同的多播分布情形稠密模式:多播成员位置分布稠密带宽很充足稀疏模式:相对于互连网络来说，由小组成员组成的网络很小小组成员“广泛分散”带宽不是很充足稀疏-稠密划分的结果Dense假定路由器都是小组成员，除非路由器明确剪枝数据驱动多播树的构造

(例如,RPF)对带宽和非多播路由器的处理比较浪费Sparse:假定路由器都不是小组成员，除非路由器明确加入接收者驱动多播树的构造

(例如，基于中心点)对带宽和非多播路由器的处理比较保守9.9PIM-密集模式PIM-DM

PIM-DM适合于密集多播的环境。PIM-DM是基于源端的路由选择协议。PIM-DM工作原理类似于DVMRP，使用逆向路径转发算法RPF和修剪/移植策略来构造多播树。但是也有所不同：PIM-DM独立于任何单播路由协议，假定有某种单播协议已经构造好了路由表PIM-DM较简单PIM-DM中的RPF算法当路由器R收到从源S到多播组G的多播分组时，首先在单播路由表中检查：到达端口是否是向S发送单播分组时的输出端口，若是，路由器将把该分组从所有没有收到剪枝报文的端口发送出去如果所有端口都被剪枝了，则通过分组到达端口发送剪枝报文否则，分组将被丢弃，并向分组到达端口发送剪枝报文。9.10PIM-SM9.10.1汇聚点RP的选定9.10.2RP共享树的构建9.10.3共享树的剪枝9.10.4发送多播分组9.10.5从共享树切换到基于源的树9.10.6多播源到多播组成员的SPT树的建立9.10.7PIM-SM的特点9.10PIM-SMPIM-SM（RFC2362）适用于稀疏模式。PIM-SM协议结合了SPT和CBT的优点，是前景最为广阔的一种协议。PIM-SM使用单向共享树，根节点称为汇聚点RP，相当于CBT的核心路由器。PIM-SM域内的所有路由器必须知道RP地址。CBT(RFC2189)与PIM-SM相似，二者不同：CBT只使用共享树进行数据传输，并且无法从共享树切换到基于源的多播转发树PIM-SM可以这样做。PIM-SM支持基于源的树和共享树两种多播树。它首先生成共享树，通过共享树传送最初的多播分组，以及使多播组成员发现本组的活动源主机。由于共享树导致多播分组传送的低效性，在多播组成员接收多播分组的速率超过一定的门限后，多播组成员会将多播分组切换到基于源的树上。9.10.1汇聚点RP的选定PIM-SM的共享树为单向树。多播分组只能从RP沿共享树向下传递到多播组成员。PIM-SM的RP的选取方式：⑴静态指定RP路由器；⑵通过开放标准的自举协议指定和通告RP；⑶通过Cisco的私有协议即Auto-RP协议指定和通告RP。Auto-RP协议是Cisco的私有协议，故仅介绍⑴和⑵两种方式。1.静态指定RP路由器此方式是在PIM-SM域（域指一个PIM路由器的集合）中，人工指定一个RP，为该RP分配一个地址，此地址一般采用Loopback接口地址。然后对每个路由器进行配置，告知其本域中RP路由器的地址。静态指定RP方式最大的弱点是存在RP的单点故障现象。当RP出现故障时，此RP所负责的组将无法进行正常的多播分组传送。2.开放标准的自举协议指定和通告RP此方式中用到的几个符号。C-BSR表示候选自举路由器；BSR表示自举路由器；C-RP表示候选RP。为保证网络的强壮性，一般在网络上设置多个C-BSR和C-RP，且C-BSR和C-RP位于同一个路由器，并通过IP地址予以表示，此地址一般采用路由器的Loopback地址。自举协议指定和通告RP方式R2R4R1组成员R3R6R5C-BSRC-RPC-BSRC-RP组成员组成员

从C-BSR中选取BSR⑴首先，从C-BSR中选取BSR。最初，C-BSR将自己的优先权和IP地址放在自举（Bootstrap）报文中发送给PIM-SM域中所有路由器；然后，C-BSR依据接收到的其它C-BSRBootstrap报文中的优先权和IP地址，判定该C-BSR是否比本C-BSR优先；若是，本C-BSR停止在发送Bootstrap报文。最终，就只剩下一个C-BSR在网上发送Bootstrap报文，此C-BSR即成为域中的BSR。图中假设R2是选出的BSR。计算RP⑵C-RP从收到的Bootstrap报文中获知BSR的地址，将本C-RP的优先权、IP地址和所服务的多播组的地址发送给BSR，在BSR处形成RP信息集。BSR将RP集放在Bootstrap报文中，转发给网上每一台PIM-SM路由器。接收到该报文的路由器，使用统一算法计算出网上的RP，在本例中假设选中了R3。BSR起着“镜子”作用BSR将域中所有C-RP的报文“反射”到本域的所有PIM-SM路由器处。采用统一算法，保证了计算出的RP是同一个RP。自举协议配置了多个C-BSR和C-RP，一旦当前BSR或RP出现故障，其它某一个C-BSR或C-RP将会被选举为新的BSR或RP，消除了RP单点故障。可在PIM-SM域中设置多个RP默认情况下，RP为所有多播组共用，RP的处理能力将成为多播分组传送的瓶颈。为此，可在PIM-SM域中设置多个RP，通过访问列表ACL，将多播组的处理工作分配给这些RP。通过将不同的多播组映射到相对应的RP上，从而将所有多播分组处理工作分摊在不同的RP上。9.10.2RP共享树的构建多播路由表是在路由器中维持的多播树的节点状态，由发送的路由协议控制报文的内容来建立或更新。多播路由表随着多播树的构建过程而建立起来。1．多播路由表项基于源的多播树SPT和共享树有不同的路由表项。⑴SPT的多播路由表项基于源的多播树SPT的路由器都有一个多播路由表，表项包含的主要内容有：（S，G）地址对RPF邻居地址上游接口下游接口超时时间等。路由表项字段含义（S，G）地址对，是对（源，组）多播路由的标识，类似于单播路由表中的目的地址，是查找路由表的关键字；RPF邻居地址，为与该接口相连的上游邻居路由器的地址；上游接口，离多播源最近的接口，也叫RPF接口。用于RPF检查多播分组是否从正确的接口到达；路由表项字段含义（续）下游接口，离多播组成员最近的接口，即本路由器多播分组的输出接口，类似于单播路由中的出口。多播树可能在某个路由器节点处分叉，可能同时有多个下游接口。所以，该字段又称为下游接口列表；超时时间，多播表项需要进行周期性刷新，在规定的超时时间内未得到刷新，则此表项将被删除。⑵共享树的多播路由表项共享树上多播路由器的多播路由表表项：（*，G）地址对，标识多播组GRP地址，RP的IP地址RPF邻居地址上游接口下游接口超时时间等。2．RP共享树的构建过程在PIM-SM中，成员主机想要接收多播数据时，需要先向RP注册加入RP共享树。成员主机的加入通过指定路由器来完成。指定路由器（DesignedRouter，DR）是与主机直接相连的路由器，它生成多播路由表，处理和转发join/prune报文和Register报文，转发多播分组。想要加入某一多播组的每一个网络都应该有一个指定路由器。指定路由器DR推选方法只连接一台路由器的网络，此路由器就是DR。与多台路由器相连接的网络，路由器的每个接口都是一个候选指定路由器，且每一个接口都对应一个DR权值。DR权值越大，优先权就越高。权值最高的被选中为DR。如果权值相同，那么IP地址高的那个被选中。PIM-SM组成员加入过程R2R4R1组成员R3R6R5RP组成员组成员主机A⑵发送关于（*，G）的join报文⑴IGMP成员关系报告报文⑶新加入的分支cbba

各个路由器接口的IP地址R2R4R1组成员RPR6R5源：172.16.1.1多播组：230.80.1.1组成员组成员源abaaaaabbbbbccc172.16.2.5172.16.3.9172.16.6.17172.16.7.22172.16.7.21172.16.6.18172.16.3.10172.16.5.14172.16.5.13172.16.4.12172.16.4.11172.16.2.6L0：172.16.8.1R3共享树上各路由器相应的多播表项（*，G）地址对RP地址RPF邻居路由器地址上游接口下游接口R4（*，230.80.1.1）172.16.8.1172.16.5.14cbR5（*，230.80.1.1）172.16.8.1172.16.6.17ab、cR6（*，230.80.1.1）172.16.8.1172.16.7.21abR1（*，230.80.1.1）172.16.8.1172.16.3.9abR3（*，230.80.1.1）172.16.8.10.0.0.0Nullb、c9.10.3共享树的剪枝共享树建立起来后，可以进行加入join或剪枝prune操作。主机X向指定路由器DR发出IGMP离开组报文。如果X是多播组的最后一个成员，DR从（S，G）和（*，G）的下游接口列表中删除DR与X所在网络相连的接口。如果（*，G）的下游接口列表为空，表明此路由器的任何接口上都没有多播组G的接收者，路由器向RP发送关于（*，G）的剪枝报文。剪枝报文的传送剪枝报文的传送过程中，检查中间节点的（*，G）的下游接口列表，如果为空，则剪枝报文向上游发送。不为空，说明路由器在其它接口上仍有(*，G)的接收者，共享树在此分叉，则路由器只是删除该接口，剪枝报文不再向上游发送。共享树的剪枝过程R1aR2向RP（131.1.12.1）发送剪枝（*，G）报文bR2删除（*，G）表项，向RP发送剪枝报文向R2发送IGMP离开组报文abc9.10.4发送多播分组因为PIM-SM使用单向共享树，多播信息只能沿着共享树向下游传送。若多播组中出现了一个活动的多播源，将开始进行多播分组的传送。多播分组首先从源主机传送给RP。然后，由RP沿着共享树转发。1.多播源到RP的多播分组初始传送由于在多播分组初始传送时，源主机到RP没有多播树，所以从源主机到RP的多播分组无法通过多播树进行传送。这时，PIM-SM利用Register报文将源主机的多播分组传递给RP。PIM-SM利用Register报文和Register-stop报文实现注册机制。多播源的注册R1R3从源到R1的第一个多播分组未封装的多播分组接收节点R2RP源R1向RP发送Register报文（S，G）join报文（S，G）join报文图例多播分组

PIM-SM报文多播源的注册当多播源向某个多播组发送多播分组时，源主机的指定路由器DR（例如，R2）将多播分组封装在PIM-SM的注册Register报文中，注册报文再封装到IP分组中，IP分组的目的地址为RP的Loopback地址172.16.8.1，源地址为R2接口a的地址172.16.2.5。然后，将此IP分组以单播方式，通过R2的单播路由表转发给RP。这个过程称为注册。源到RP的多播分组传送效率较低为了提高效率，RP接收到源发来的第一个多播分组后，RP建立一个新的路由表项（S，G），并向S发送（S，G）源指定join报文。沿途经过的路由器在自己的多播路由表中建立一个（S，G）表项，最终建立多播源主机S和RP之间的一棵SPT树，专门用于转发S向组G发送的多播分组。以后，由源S到RP的多播分组将沿此SPT树发送，然后从RP通过共享树发送给各接收端。如果SPT与共享树有交叉，则多播分组在交叉点直接通过共享树传送，不需要再向RP转发。多播源注册停止RP可能收到两份同样的多播分组。在源到RP的SPT建立期间，源S可能继续使用注册Register报文，向RP传送多播分组。另一方面，源S的DR可能会把IP多播分组直接从SPT传送到RP。这时，RP将丢弃Register报文，并向S发送注册停止Register-Stop报文以便抑制Register报文。一旦DR收到Register-Stop报文，就不再使用Register报文携带多播分组，而是直接发送多播分组。RP发送Register-Stop报文的另一种情况：共享树中没有该多播组成员。这时，RP丢弃相关多播分组，并发送注册停止报文，通知DR停止发送Register报文和多播分组。多播源注册停止R1R3从源到R1的多播分组多播分组接收节点R2源R1向RP发送Register报文来自RP的Register-Stop报文多播分组多播分组图例多播分组

PIM-SM报文

2.多播源到RP的SPT树建立如前所述，RP收到由多播源发送来的第一个多播分组时，将从RP到源主机建立SPT树。SPT树的建立通过PIM-SM的加入join报文和剪枝prune报文实现。R2的多播表首先，RP（R3）查询单播路由表，选择到指定多播源172.16.1.1的最短路径。然后，沿此路径向RPF邻居R2以单播方式发送对（172.16.1.1，230.80.1.1）组的加入join报文。R2根据此报文的信息在多播表中生成相应的（S，G）表项，并将接收此报文的R2的接口a定义为输出接口（下游接口）。（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）0.0.0.0NullaRPF邻居地址为0，上游接口为空（Null），表明R2是与多播源172.16.1.1直连的路由器各个路由器接口的IP地址R2R4R1组成员RPR6R5源：172.16.1.1多播组：230.80.1.1组成员组成员源abaaaaabbbbbccc172.16.2.5172.16.3.9172.16.6.17172.16.7.22172.16.7.21172.16.6.18172.16.3.10172.16.5.14172.16.5.13172.16.4.12172.16.4.11172.16.2.6L0：172.16.8.1R3R3的多播表（*，G）地址对RP地址RPF邻居地址上游接口下游接口（*，230.80.1.1）172.16.8.10.0.0.0Nullb、c（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）172.16.2.5ab、c

作为RP，R3的多播路由表为两个表项，即RPT和SPT各一个表项按最长匹配规则查询多播路由表多播路由器根据多播分组的（S，G）地址对内容作为关键字，按照最长匹配规则查询多播路由表，然后根据匹配表项的指示进行转发。对于（172.16.1.1，230.80.1.1）多播分组，R3上的最长匹配表项为第二个表项，所以R3依据此表项将多播分组转发到b、c接口上。R1、R4、R5、R6路由器的路由表项没有变化。3.RP到多播组成员的传递RP收到Register报文后，将其解封装，取出原始多播分组，然后根据多播路由表将此多播分组沿共享树转发到各接收节点。RP（R3）收到源主机发来的多播分组后，查询多播路由表，决定将分组转发到b、c接口。R1路由器进行RPF检查，即检验分组是否从指定的上游接口a接收。若是，则将分组转发到指定的下游接口b。路由器R5、R6和R4进行同样的操作，最终所有多播组成员都接收到源主机发来的多播分组。PIM-SM提供RPT到SPT的切换机制共享树传递多播分组的路径，不一定是从源到多播组成员主机的最短路径。例如，源主机到R4的多播分组传递是沿着R2-R3-R4的共享树路径进行的，而最短路径却是R2-R4。9.10.5从共享树切换到基于源的树共享树一般只用于帮助多播组成员发现某一活动的多播源（S，G），以及用于多播分组传送的初始阶段。为了减少网络延迟和减少在RP上可能出现的拥塞，当接收节点的DR所接收多播分组的比特率超过某个特定阈值时，此DR就可以开始建立基于源的SPT树，建立一棵从这一特定多播源S到该多播组成员的SPT树。此后，该多播分组的传递将从RPT共享树切换到SPT树上。DR发起RPT向SPT的切换当接收节点的DR接收多播分组的比特率超过某个特定阈值时，DR首先建立多播路由表项（S,G），并向多播源S发送关于（S,G）的加入join报文。当join报文最终到达多播源的DR时，就建立了一棵从源S到DR路由器的最短路径树SPT。可能会有两个（S,G）多播分组向组成员传送，导致网络带宽的浪费：一条是先发送给RP，然后再沿共享树RPT传送；另一条则是直接沿着最短路径树SPT的传送。为了避免接收者同时重复接收分组，需要沿着通往RP的共享树向上发送剪枝报文。PIM-SM路由器的RPF检查PIM-SM路由器将多播分组转发到所有成员主机。在转发多播分组之前，路由器先执行一个RPF检查。如果是RPT，则RPF检查使用RP的IP地址；如果是SPT，则RPF检查使用多播源的地址。9.10.6多播源到多播组成员的SPT树的建立如上所述，共享树上的指定路由器DR，例如R4、R5、R6收到的某一指定（S，G）多播分组的发送速率超过某一门限值时，将建立到源的SPT树。R6的多播表（*，G）地址对RP地址RPF邻居地址上游接口下游接口（*，230.80.1.1）172.16.8.1172.16.7.21ab（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）172.16.7.21abR6接收（172.16.1.1，230.80.1.1）多播分组，获知多播源的IP地址。根据多播源IP地址查询R6的单播路由表，获知到多播源的最短路径、RPF邻居和上游接口。由此生成多播路由表的相应表项。

R5的多播表（*，G）地址对RP地址RPF邻居地址上游接口下游接口（*，230.80.1.1）172.16.8.1172.16.6.17ab、c（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）172.16.6.17ab、cR6向其RPF邻居R5发送加入join报文，R5接收到join报文后，将接收此报文的接口c定义为下游接口，同时向上游路由器R1（其RPF邻居）发送join报文。

R1的多播表（*，G）地址对RP地址RPF邻居地址上游接口下游接口（*，230.80.1.1）172.16.8.1172.16.3.9ab（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）172.16.3.9ab

R3的多播表（*，G）地址对RP地址RPF邻居地址上游接口下游接口（*，230.80.1.1）172.16.8.10.0.0.0Nullb、c（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）172.16.2.5acR4的多播表（*，G）地址对RP地址RPF邻居地址上游接口下游接口（*，230.80.1.1）172.16.8.1172.16.5.14cb（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）172.16.4.11abR2的多播表（S，G）地址对RPF邻居地址上游接口下游接口（172.16.1.1，230.80.1.1）0.0.0.0Nulla、b9.10.7PIM-SM的特点PIM-SM的主要特点有：⑴不需要自己单独的多播路由表，不必发送多播路由更新报文，开销小。⑵PIM-SM比CBT更灵活。PIM-SM可以使路由器从共享树切换到基于源的树，以便减少与共享树有关的网络延迟。⑶多播组成员加入采用显式模式，更适合于在广域网连接末端有潜在成员的多播网络，多播组中成员较少，发送者和接收者被隔离或比较稀疏，分组的传输带宽不一定很丰富的场合。9.11域间多播技术9.11.1域间多播问题9.11.2MSDP协议9.11.3MBGP协议9.11.4域间多播示例9.11域间多播技术PIM-DM和PIM-SM结合起来使用，是最早的域间多播路由方案之一。PIM-DM进行域内路由，PIM-SM用作域间路由。PIM-SM构造一棵共享树，连接每个域内用PIM-DM建立的基于源的树。因为发布RP和维护PIM-SM中的状态信息会消耗大量网络资源，不能应用到因特网中。另一个方案使用三个协议：MBGP用于自治域之间交换多播路由信息；多播源发现协议MSDP用于ISP交换多播源信息；PIM-SM用作域内多播路由协议。9.11.1域间多播问题假设有多播信息互通的自治域均为PIM-SM多播域。对于域间多播的实现，需要解决两个问题：多播源发现-多播源发现协议MSDP域间多播分组RPF检查的有效性-多播边界网关协议MBGP实现RP通过MSDP知道其它域中的活动多播源，通过查询MBGP路由表对多播分组进行RPF检查MSDP和MBGP联合使用，域间RP是MSDP对等体，也是MBGP对等体（EMBGP或IMBGP）。9.11.2MSDP协议多播源发现协议（MulticastSourceDiscoveryProtocol，MSDP）用来发现其它PIM-SM域内的多播源信息。MSDP对等体（MSDPpeer）的RP，将其域内的活动多播源信息通过SA报文通告给它的所有MSDP对等体。MSDP对等体又称作为MSDP发言人（MSDPspeaker）MSDP对等体可以建立在不同PIM-SM域的RP之间、同一个PIM-SM域的多个RP之间、RP与普通路由器之间。MSDP对等体使用TCP连接。1．MSDP协议原理MSDP发言人周期性地创建活动源（SourceActive，SA）报文，SA报文中包含RP本域内活跃多播源信息：多播源的IP地址多播组地址发送该SA的源RP地址。当某MSDP对等体（例如RPx）接收到SA报文后，像PIM-SM协议一样进行RPF检查。使用SA报文中的源RP地址，确保此报文是从源RP通过正确的自治系统路径（AS-PATH）到达RPx的。如果通过了RPF检查，则进行RPF转发如果RPx中有SA报文中的（*，G）状态信息，且（*，G）的下游接口（出接口）不为NULL，则说明RP的共享树中有这个多播组的接收者。RPx向多播源地址发送（S，G）加入join报文，把基于源的多播树的一个分支引入自己的域内。之后，这个多播源的多播分组就会通过该分支到达此RP，RP再沿着自己的共享树把多播分组转发给该多播分组的接收者。叶子路由器从共享树上接收到分组之后，同样可以选择切换到基于源的树上。2．MSDP协议的工作过程AS2指定路由器DRRP2RP3源SAS3组成员组成员AS1R31①发送多播分组②发送注册报文③域内多播分组转发④向对等体转发SA报文⑤向多播源发送join报文④RP1⑥RP3转发多播分组给组成员

9.11.3MBGP协议MBGP提供了一种进行多播RPF检查方法。BGP-4是一个有效、稳定的单播域间路由协议。MBGP是对BGP-4协议的增强和扩展。RFC2858中定义了MBGP（MulticastBGP）。MBGP是对BGP的增强和扩展MBGP不仅携带IPv4单播路由信息，也携带其它网络层协议（如多播、IPv6等）的路由信息，携带多播路由信息只是其中一个扩展功能。MBGP向相邻自治系统通告“从我这里可以到达发送者S”。当RP或者多播组成员向其它AS中的多播源S发送join报文时，该报文需要沿着逆向路径到达多播源S，有了MBGP提供的路由就可以实现RPF检查。9.11.4域间多播示例加入组AS200RP2RP3RP1AS100RP4AS300AS400(a)RP建立对等关系Join报文(*,230.80.1.1)发送SA报文SA报文RP2RP3RP1AS100RP4SA报文SA报文SA报文AS300AS400(*,230.80.1.1)AS200Register报文(172.16.1.1,230.80.1.1)源SAS400有一多播组成员申请加入（*，230.80.1.1）组，通过PIM-SM加入join报文，在AS400中建立以RP4为树根的共享树RP1向MSDP对等体发送SA报文RP3执行RPF检查，接收AS100的SA报文，将AS200的SA报文丢弃多播源到RP的SPT组员AS200RP2RP3RP1AS100RP4AS300AS400源RPTSPT