组播之PIM篇v1.0.doc

组播之PIM篇内部公开华为三康技术有限公司Huawei-3Com Technologies Co., Ltd.文档编号 Document ID密级 Confidentiality level内部公开文档状态 Document Status共20页 Total 20 pages组播之PIM篇拟制Prepared by 王君菠Date日期2006-02评审人Reviewed by Date日期批准Approved byDate日期华为三康技术有限公司Huawei-3Com Technologies Co., Ltd.版权所有 侵权必究All rights reserved修订记录 Revision Record 日期Date修订版本Revision Version修改章节Sec No. 修改描述Change Description作者Author2006-02-101.00initial 初稿完成王君菠目 录1PIM-DM篇51.1简介51.2RPF 逆向路径查询51.3PIM的组播转发方式71.4PIM-DM 的剪枝（prune）81.5PIM-DM的嫁接（Graft）91.6剪枝否决（pruning override）101.7断言（Assert）111.8PIM-DM的状态维护111.9DR的选取122PIMSM篇132.1引述132.2PIM-SM表项建立和转发过程132.3PIM-SM 注册与注册停止152.4PIM-SM 剪枝162.5PIM-SM的状态维护162.6组播分发树模型和RPT到SPT的切换163参考资料20前 言近几年，随着网络应用的发展，多媒体会议普及、IPTV炒作的越来越热，组播变的越来越热，应用的越来越多。组播要完成从组播源到客户端传递信息，可分成两个部分理解：客户端主机和路由器之间的组播数据传输及实现；路由器与路由器之间的组播数据传输及实现。其中客户端和主机之间是IGMP来完成的；路由器与路由器之间，是组播路由协议，常见的有DVMRP，CBT，MOSPF，MBGP，MSDP，PIM等。PIM （Protocol Independent Multicast）分为两种模式：PIM-SM（SparseMode稀疏模式） 和 PIM-DM（DenseMode密集模式），本文就这两部分分别展开讨论。1 PIM-DM篇1.1 简介适用场景：组播接收客户端分布比较密集。要想理解组播的转发，必须理解单播的转发过程。当路由器收到一个单播报文后，路由器会根据报文的目的地址查找自己的转发表（路由表或FIB表或cache中的表项，这属于路由转发的范畴，这里就不讨论了），找到一个匹配项后，直接按照出接口和下一条确定报文的二层封装，然后改写报文二层头，从相应的接口发送出去。单播的转发过程路由器不用关心报文从哪里来，它关心的仅仅是报文的目的地址（策略路由除外）。每个单播报文都一个目标地址，从源到目的沿途每台路由器都按照自己的转发表转发该报文，如果所有设备都转发正确，那么报文离目的地越来越近，最后被送到目的地。而路由器在转发组播报文的时候它第一个要关心的是：“该组播报文从哪里来”，如果（来路不正者斩，这是RPF的功能，下文有述），然后关心的才是自己的转发表里是否有转发表项。而组播报文的目的地址并不是单独一台主机，组播地址是一个逻辑的概念，它只是一个标记，就好比是电视台的频道。一般一个组播地址对应着零个、一个到N个接受者，而且路由器的转发路由表中并不存放组播主机，如果再按照单播转发的那种思想去转发组播显然是不行的。那么当路由器接收到一个组播报文应该怎么做呢？路由器有它的三板斧：首先RPF、然后查组播转发表项，最后按照表项转发该组播报文。什么是RPF呢，路由器又是如何建立组播转发表项的呢，这个过程和你所熟悉的ospf、rip等路由协议建立路由表的过程一样吗？带着这些问题，听我下文的分解。1.2 RPF 逆向路径查询路由器在转发单播报文的时候关心的是报文的目的地址，而在转发组播报文的时候，如上文所述，它首先关心的是组播报文的源地址和接受到该组播报文的入接口。当路由器收到一个组播报文时，要判断接收到组播报文的“入接口”是不是本路由器到达该组播报文的“源地址”的最佳路径的“出接口”；这个最佳路径是通过查找自己的路由表得出的。如果是那么路由器就考虑对改组播报文进行转发，如果不是的话直接丢弃，这就是RPF（Reverse Path Forwarding逆向路径查询）理论比较晦涩，举例子说明下图1 组播转发RPF如上图的RTE，该路由器从两个口上收到server给他的组播报文，这时RTE会查询它的单播路由表（假设组播服务器的IP地址为101.3.240.3）图2 RPF续101.3.240.3在RTE的路由表里出接口应该是S1口，而组播的入接口是S0口，RPF查询失败，丢弃该组播数据包，同时向S0口发送一个剪枝报文（后续内容中对该报文有详细介绍，它的作用就是告诉上层路由器，不用给我发送该组播报文了）再举一个查询成功的例子见下图图3 RPF续假设组播服务器IP地址为101.3.240.3，此时该路由器在自己的S1口收到该组播报文，查找路由表，101.3.240.3 出接口是S1，RPF查询成功，转发该组播数据包现在我们知道RPF是怎么一个处理过程了，那么此时聪明的你可能要问：为什么要RPF？或者RPF为什么要这么做呢？其实答案很简单，还是从RTE的角度考虑，如果RTE在转发组播数据包的时候不考虑RPF逆向查询，那么从S0口和S1口收到的组播数据都转发的话，在接收者那里每个组播报文至少会收到两份一模一样的，为了避免这种情况，所有我们用RPF查询：只转发一份从最优路径来的组播数据包，这就是RPF的目的。那么路由器是如何建立组播转发表项，并转发组播数据包的呢，这就靠组播路由协议了，不同的协议有不同的转发方式。目前pim用的最多，本文只讨论pim的行为。1.3 PIM的组播转发方式该节讨论PIM-DM的组播转发方式。在概述中讨论过，PIM-DM适用于组播接收客户端分布比较密集的场景，这跟PIM-DM的假设有关，pim路由器在转发组播报文时它假设：路由器的每个接口下都有组播接收客户端。PIM-DM组播路由器接收到组播报文后，就会非常主动的建立转发表项，所谓组播的转发表项就是由S，G,Upstream interface lists和Downstream interface list所组成的，S 表示source，即组播报文的发起者，一般是服务器，G 表示组地址，Upstream interface list表示组播报文的入接口，Downstream interface lists，表示组播报文的出接口，就是说组播报文要被路由器从这些端口发送出去。PIM-DM建立表项时，upstream interface list即RPF检查成功的组播报文的入接口，downstream interface lists就是所有的其它接口，因为pim-dm假设所有的接口下面都有组播的接收者（dm，即dense mode，密集模式）。（S，G）即直接取组播报文的源地址和它的目的地址即组地址。当建立表项后根据转发表项直接把组播报文复制N份（N为downstream interface lists的接口数），从各个downstream interface lists 转发出去。1.4 PIM-DM 的剪枝（prune）这时你可能要问：pim-dm的这种转发方式和广播有什么区别？答案是，在PIM-DM中，还有一种剪枝机制。当一台pim路由器接口up后，它也会像大家熟悉的ospf一样，通过发送hello报文来发现自己的邻居，hello报文里面包含hello-interval 和hold time。如果一台路由器的某个接口开启pim，但该接口的neighber列表为空，说明它是一个边缘路由器（leaf router）。当边缘路由器接收到一个组播报文后它会查自己的igmp表项，查看是否有该组的用户，如果有，则转发，如果没有，那么此时本路由器接收这个组的组播报文就没有意义了，所以他要向自己的上游（upstream interface list）路由器发送剪枝消息。它的上游pim路由器在收到来自下游的剪枝消息之后会把接收剪枝消息的接口标记为pruning状态，同时启动一个定时器，在定时器超时前不会再向被置为pruning状态的downstream interface发送组播报文，当定时器超时后，路由器会再次向该接口发送组播报文，如果下游路由器仍没有接受者，它仍然会向上发送剪枝消息，然后本路由器再次把该接口置为pruning状态，这种行为被称为“剪枝-扩散-剪枝-扩散”。假设一个路由器的DownStream interface list的所有接口都被置为pruning状态，则说明它的下游都没有接受者了，此时这台路由器接收该组的组播地址也会变得没有意义，所以他也向它的上游发送剪枝消息。举一个pim-dm转发的例子图4 Pim-dm转发流程PC1、PC3、PC4是该组播组的成员，PC2不是该组播组成员，那么当组播报文被转发到RTG的时候，RTG查找自己的IGMP表项发现该组没有成员，则向RTF发送剪枝报文，RTF只有一个DownStream口，从该口收到剪枝消息意味着RTF也没有该组播组成员，所以RTF也向上发送剪枝消息，RTE收到该剪枝消息后，把该接口置为pruning状态，但此时RTE的DownStream list中的接口并不是全部被置为pruning状态，所以它不再向上发送剪枝消息。此时RTE启动一个剪枝消息的计时器，当计时器超时，再次从被剪枝的接口向下发送该组播组报文，当组播报文发送到RTG时，和上次处理过程相同，RTG查找IGMP 表项，发现没有该组表项，然后发送剪枝消息，RTF继续发送剪枝消息，RTE启动计时器，这个过程被称为 剪枝-扩散-剪枝-扩散（题外话：从这一点可以看出来PIM-DM路由器很热情，不停的想送你礼物，你不需要的话我过段时间再去问问你需要不需要，而PIM-SM就很羞涩，在SM章节会向大家展示）1.5 PIM-DM的嫁接（Graft）当下游路由器刚刚发送剪枝消息给自己的上游路由器后不久，他收到一个igmp report报文，该report报文要求加入刚刚被剪枝的那个组，此时该路由器是否要等待上游的路由器剪枝定时器超时后再开始接受组播数据呢，答案是否定的，此时它可以向自己的上游邻居发送嫁接消息，当上游的路由器收到嫁接消息后马上收到嫁接消息的接口的状态从pruning状态置为forwarding状态，此时分两种情况：一、如果本路由器正在向其它下游接口发送该组的组播数据，那么该路由器马上把接收到嫁接消息的接口状态机从pruning状态转换为forwarding 状态，并且开始从该接口向下游转发该组的组播数据，同时向下游发送嫁接应答（Graft-Ack）消息。二、如果此路由器该（S，G）组中所有的downstream list 中的所有接口都是pruning状态（此时说明路由器已经把自己从组播树中剪枝掉了，也就是说它也向自己的上游发送过剪枝消息），那么该路由器首先把接收到嫁接消息的downstream interface状态机从pruning状态转换位forwarding状态，同时向自己的上游发送嫁接消息，以此类推。1.6 剪枝否决（pruning override）图5 剪枝否决如图，路由器RTA在以太网共享网段上有两个pim邻居，转发组播数据的时候RTB和RTC都是下游路由器，如果RTC下面没有接受者，那么他会发送剪枝消息给自己的上游设备，（注意剪枝消息发送的目的地址是224.0.0.13，所有的pim路由器都可以接收到，所以RTB也可以收到一份）。RTA通过hello消息知道自己的以太口下面有两个邻居，当RTA收到剪枝消息后，它不知道是否该把该以太口从组播转发树中剪掉，此时他会启动一个计时器（一般是3秒），计时器超时前他不会剪枝该接口。上面说过，RTB也会收到RTC的剪枝消息，RTB发现对方要剪枝的（S，G）组播组恰恰是自己下游有接收端要接收的组,此时RTB也并不是黔驴技穷，他会向自己的上游发送加入消息（一般在pim-dm中很少用的到加入报文），当RTA收到该加入报文后，就继续向该端口发送组播报文而忽略RTC的剪枝消息，这就是剪枝否决。1.7 断言（Assert）图6 断言如图，在共享式以太网上，RTA和RTB都有到达同一个组播源的路由，而且RPF检查成功，因此该以太网上的接受者将收到两份一模一样的报文，这是没有必要的。当RTA和RTB发送组播报文时，他们都会从自己的DownStream接口上收到对方的组播报文，当路由器从自己的downstream接口收到同一个（S，G）的组播报文时，它会从该接口发送断言消息，该消息包括：组播源、组地址，单播到源的路由的路由协议优先级。RTA和RTB将对各自的断言消息和进行比较，以选择谁是该共享网段的该（S，G）组播报文发送者，过程如下：1. 发现到组播源的路由的路由协议优先级高者（数越小优先级越大），将成为forwarder2. 如果RTA和RTB到源的路由协议都一样，那么到源的metric值小的路由器将成为forwarder3. 如果metric值相等，两个路由器谁的IP地址大谁将是forwardePIM-DM使用五中协议报文来完成邻居的维护、组播分发树的建立维护删除、组播转发项维护和组播路由器邻居的维护等1.8 PIM-DM的状态维护PIM-DM的（S，G）表项靠组播数据包来维护，也就是说路由器每收到一个组播数据包，就把关于该组的（S，G）表项的老化实现重置。如果（S，G）表项超时，则删除该表项。（S，G）表项的DownStream interface list中有部分接口的状态为pruning，它们是在剪枝扩散的重复着。1.9 DR的选取其实，DR的选取和PIM关系不大，只是对于边缘路由器而言，有的路由器运行的IGMPv1，而IGMPv1没有选取查询器的功能，所以靠PIM选择的DR来做为自己的查询器，单单说DR对PIM而言，意义并不是很大，只是DR负责在以太网上传输组播报文而已。它的选择机制很简单，首先比较优先级，然后比较IP地址，高者获胜。总体而言，PIM-DM从状态机到转发过程都比较简单容易理解，下面给大家介绍一下PIM的另一种转发模式PIM-SM（稀疏模式）2 PIMSM篇2.1 引述如上文所述，PIM-DM转发方式源于一种假设：路由器除了接受组播的接口外每个接口都有接收者，所以它的转发方式是泛洪式的转发，如果没有剪枝，那么就很类似广播了，所以它在接收者密集的场景效率比较高。但如果接收者比较少，那么PIM-DM的那种“扩散剪枝”的转发方式势必会效率很低，这时候就需要另一种转发机制。PIMSM的转发模式是源于另一种假设，这种假设和PIMDM的假设恰恰相反：假设网络中没有任何接受者，所以当路由器接收到组播报文后并不转发，而是等着下游的路由器主动加入，从哪个口接收到加入报文，就把该接口添加到downstream interface list中，并向该接口转发组播报文。和PIM-DM相比，SM的这种加入方式是显式的加入，即有明确的加入报文声明要加入哪个组；而PIM-DM的加入方式是隐含的加入，在密集模式的加入过程中并没有pim的加入报文（而且密集模式中很少用到pim的加入报文，只要在剪枝否决的时候用到），当收到上游组播报文后，只要设备不向上游发送剪枝消息，就是隐含的接受本组的组播报文了。这两种加入方式都有自己适用的场景。2.2 PIM-SM表项建立和转发过程当一个边缘路由器（leaf router）收到一个igmp的report报文时，它会建立一个关于该组的表项。但是此时它并不知道改组的源在哪里。所以它的表项不能建立成（S，G）方式，而只能建立（*，G）表项，该表项只表明组，而不关心组播源是谁。接下来，该leaf router就该发送pim加入消息了，此时你肯定要问：它不知道源在哪里，那么它的pim加入报文发给谁呢？难道是泛洪式的全网转发吗？答案是：它此时不需要知道组播源的IP地址。在PIM-SM的转发模型中，不仅是边缘路由器不知道源在哪里，而且靠近组播组播源的路由器（称之为DR，DR的概念上文有述，和ospf的DR稍有区别）也不知道谁是它的接受者，此时若没有中间人站出来协调一下，恐怕大家只能撤着嗓子狂喊了（泛洪式转发）这种方式好像又回到了PIMDM的转发方式去了。所以在PIMSM的转发模型中，又添加了一个中间人的角色（Rendezvous Point）RP，RP可以负责几个或者所有组播组的转发，所以网络中可以有一个到多个RP，那么此时如果DR和Leaf router想转发组播数据的话，只需找到RP即可。但是，它们如何找到RP呢？泛洪吗？方法有两种：1. 在DR和Leaf router以及组播将要经过的所有路由器上手工制定RP的IP地址2. 启动BootStrap 协议第一种方式简单，如果网络不大的话这也不失为一种好方法，但所有静态的配置都有它不利的一面，扩展性，可管理性不高等等等等，想想静态路由的优缺点，那么静态配置的RP的优缺点你也就知道了。第二种方式，BootStrap Protocol，是一种开放的协议，它可以负责通过BootStrap Message通过给网络中所有的路由器关于RP和每个RP所能转发的组播组的消息。BootStrap router工作的原理和过程：首先要在网络中选择合适的路由器把它配置成候选BSR（C-BSR，Candidate BootStrap Router），每个C-BSR都有优先级，当它得知自己是C-BSR后，首先启动一个定时器（默认为130秒），监听网络中的 BootStrap Message。BootStrap Message 初始时通告发送路由器的优先级、BSR的IP地址，当C-BSR收到一个BootStrap Message后，它会把自己的优先级和报文里的优先级做比较，如果对方的优先级高，它就把自己的定时器重置，继续监听BootStrap Message；如果是自己的高，那么它就发送BootStrap Message声明自己是BSR，如果优先级相等，则比较IP地址，谁的IP地址大谁就是BSR。BSR消息发送的目的地址是224.0.0.13，所有的PIM路由器都能接收到这个报文，该报文TTL一般被置为1，但每个PIM路由器收到此报文后都是把它以泛洪的方式从自己所有的使能PIM的接口上发送出去，这就能保证网络中的每台PIM设备都能收到BootStrap Message。RP就像C-BSR一样需要在设备上手工配置，首先配置C-RP（Candidate Rendezvous Point），包括RP地址、优先级和它所能服务的组。正如上文所述，一个RP可以给所有的组播组提供服务，也可以只给部分组提供服务。当C-RP收到BootStrap Message后，它可以从该message中得知网络中谁是BSR，然后C-RP通过Candidate-RP-Advertisement Message把自己所能服务的组单播给BSR，每个C-RP都这么做的话那么BSR就收集到了网络中所有C-RP的信息并把这些信息整理成一个集RP-Set。此后BSR通过BootStrap Message把RP-Set的信息通告给全网所有的路由器。回到开始部分的讨论，边缘路由器（leaf router）收到IGMP report报文后，它不需要知道该组的组播源是谁，它只需知道关于改组的C-RP是谁就可以了，所以它建立的表项是（*，G)。当Leaf Router收到IGMP Report报文后，它检查从BSR学来的RP-Set，此时：1. 如果RP-Set对应改组地址的C-RP只有一个,那么DR就选该C-RP做RP2. 如果对应改组地址的有多个C-RP，那么优先级最高的是RP（优先级数越小优先级越高）3. 如果大家优先级相等，那么DR将开始Hash运算，把组地址、hash掩码、和C-RP的地址做为输入参数，输出是一些数字，数字高的C-RP将是改组的RP4. 如果hash的结果大家也相等，那么IP地址最大的C-RP将成为改组的RP这些选择RP的规则其实就是为了保证在一个网络中对于一个组播组大家选择的RP是同一个C-RP。算出RP来之后，Leaf Router就向RP的方向发送PIM Join，目的地址是224.0.0.13，ttl为1，从Leaf Router到RP沿途每台路由器当收到PIM Join报文后，（假设这是它收到的第一个关于该组的join报文）都重复Leaf Router的动作：计算RP，建立（*，G）表项，向RP方向的相邻PIM路由器发送 PIM Join Message，直到RP收到关于改组的join报文。至此，RP中间人的角色完成了一半，Leaf Router已经找到中间人了，那么靠近组播源的DR路由器如何把组播报文发送给RP呢？2.3 PIM-SM 注册与注册停止当靠近组播源的DR收到第一个组播报文后，它就开始寻找关于该组的RP（方法同Leaf Router），然后通过注册消息把组播报文封装成单播报文发送给改组对应的RP，RP收到该单播报文后，首先要建立（S，G）表项，然后会检查自身的PIM的（*，G）表项，如果有关于改组的（*，G）表项（也就是说该组有接受者，因为如果RP有表项说明它收到过Join报文）那么RP就把源该单播报文解封装成组播报文，然后根据自己的（*，G）表项向DownStream interface list中的接口转发组播报文；如果RP没有对应该组的表项，那么它会向源DR路由器单播发送注册停止消息，此后源DR启动一个定时器，定时器超时前，DR不会再向RP发送注册报文，定时器超时，则DR向RP发送单播注册消息。这里可能你会问，RP收到注册报文后为什么要建立（S，G）表项呢，如果下游没有该组的组播接收者，那么建立（S，G）表项岂不是没有意义？请考虑这么一种情况：假设RP收到注册报文时，没有该组的（*，G）表项，那么它发送一个注册停止消息给源DR，此时DR启动一个注册超时定时器，在该定时器未超时前，RP收到一个关于该组的加入报文，而此时RP有没有保存关于该组的组播源的任何消息，那么它此时只能等DR的定时器超时再此给他发送注册消息的时候才能给下游发送该组的组播数据；而如果RP第一次收到注册报文就马上建立（S，G）表项，那么再有加入报文时，它可以直接根据（S，G）的源地址向组播源的方向发送PIM Join报文请求该组播组的报文而不用等DR的定时器超时，这就是RP一收到注册报文就建立（S，G）的原因。至此，对于PIM-SM组播转发的过程给大家一个大致的介绍，接下来介绍稀疏模式的其他特性2.4 PIM-SM 剪枝当边缘路由器（Leaf Router）收到igmp leave报文后，它会发送两次igmp 特定查询，以确定是否该组已经没有接收者。当它确定自己没有任何接受者后，会向自己的UPStream发送剪枝报文，然后把关于改组的（*，G)表项和igmp表项删除。当它的PIM邻居路由器收到剪枝消息后，确认自己还有没有其他邻居需要该组的组播数据，如果有，那么它只需把接收到剪枝报文的接口从自己的（*，G）表项的DownStream interface list中删除即可；如果它也没有其他接收者了（即自己的（*，G）表项的DownStream interface list中只有一个接口），那么它把（*，G）表项删除，同时它也向自己的上游发送剪枝消息。沿途所有的设备都如此操作直到RP。（回忆一下PIM-DM的操作，当它收到剪枝报文后它是如何做的，）思考：1. PIM-SM用嫁接消息吗？2. PIM-SM收到剪枝消息，会有剪枝扩散的现象出现吗？2.5 PIM-SM的状态维护PIM-SM的（*，G）表项的超时时间是靠下游的pim加入消息来维护的，当收到一个pim的加入消息，那么就把该组的（*，G）表项的老化时间重置。2.6 组播分发树模型和RPT到SPT的切换请大家回忆PIM-DM的转发方式，组播数据是从组播源出发，从最近的路径（RPF保证这一点）逐跳转发到组播的接受者，以组播源为根，组播数据包走过的路径形成一个树状的拓扑，因为这种树可以保证组播数据报文所走过的路径是最短的，所以大家习惯上称之为最短树（SPT）图7 最短树模型PIM-SM的转发并不是以组播源为根的，它是首先在网络中确定一个中间人RP，然后以RP为根向各个组播成员发送组播数据，但它并不能保证组播数据所走路径是最优（最短）路径，但是PIM-SM的转发方式注定它只能这么做。图8 共享树模型如图8所示，所有接收者的组播数据都是从RP那里转发过来的，对于PC3和PC4而言，他们的组播数据所走路径并不是最优路径（假设网络中所有线路的cost一样）。所以RPT的缺点就是如果组播流量比较大，那么RP压力比较大，而且组播所走路径不是最优路径势必增加数据传输的延迟时间。而如果直接用PIM-DM协议的话如果接受者比较少它的那种泛洪式的转发和剪枝扩散机制效率又比较低。这时，我们需要一个折中的解决方法：即要PIM-SM的这种显式的加入，又要PIM-DM的SPT，所以就有了PIM-SM的RPT到SPT的切换。PIM-SM为什么要选择RPT呢，请大家回忆PIM-SM的表项建立流程和转发过程，开始Leaf Router并不知道组播源在哪里，而且在没有收到组播数据前它也无法知道组播源的IP地址，所以它只能通过BSR的message得到关于该组的中间人RP，通过RP再接收组播数据。此时的组播分发树的模型就是RPT（Rendezvous Point Tree）共享树（因为多个组播组可以用一个RP做为自己的树根，所以有的文档称之为共享树。）当Leaf Rou