（计算机科学与技术专业论文）组播路由协议pimdm的研究与实现.pdf

国防科学技术人学研究生院学位论文 摘要 作为当前计算机通讯领域的热点问题之一，组播路由协议是一个重要的研究方向。 由于视频会议、视频点播、大规模协同计算、白板等等应用，都依赖于从一个主机向多 个主机或者从多个主机向多个主机发送同一信息的能力，这些都需要更高的带宽，超出 了单路广播的能力。一种得到学术界和工业界关注的技术是口组播技术。 本文对组播路由协议的实现，高性能组播转发树的生成与优化，与i p 层和操作系统 的高性能交互优化，以及多个组播路由协议之间的优化互操作的关键技术进行了研究和 探讨。 在组播路由转发树的优化与生成上，提出了优化算法f l s p t ( f a s tl o w c o s t s h o r t e s tp a t ht r e e ) ，该算法采用d i j k s t r a 最短路径算法中路径递增的基本思想，并 结合d d m c 算法中目的节点共享路径方法，当源节点到某节点的最短路径不惟一时，总是 选择一条与其他目的节点的共享路径最长的最短路径，从而降低所构造s p t 的总消耗。 当某一节点被选中作为当前计算节点时，无须重新计算其父节点，因此可以大大减少计 算量。因为邻接节点的最短路径长度值和最近日的节点距离值是根据当前计算节点进行 修改的，所以在此时修改父节点标识与在后面根据向量值重新计算父节点是等效的。因 此，f l s p t 算法计算得出的晟短路径树性能与d d s p 算法一样，但计算效率比d d s p 算法 高。 本文针对多个组播路由协议同时运行的情况和实际要求，根据d a v e t h a l e 模型设计 了m b r ( m u l t i c a s tb o r d e rr o u t e r ) 模块，并且扩展为组播路由协议的驱动模块。从而 创新地实现了多个组播路由协议互操作，能够大大提高路由器中组播路由协议的性能。 修改了口层核心代码，使其能够高效完成组播数据流的转发。实验结果表明，本文 实现的组播路由协议具有较好的性能。 关键词：组播路由协议，p i m - d m ，组播转发最短路径树，组播互操作 同防科学技术大学研究牛院学位跄文 图目录 图l l 单播与组播的区别。 图2 1h e l l o 消息 图2 2 r p f 检查一一 图2 3p n i d m 分布树 图2 4p 蹦d m 剪枝前状态 1 3 ，1 4 图2 - 5p d 江d m 剪枝消息 图2 _ 6p l m 剪枝甭决一 图2 7 p d 嫁接 图2 8 p d d 声明机制 图2 9 状态刷新 图4 1 传统数据拷贝 图4 2 零拷贝方式 1 9 2 4 囤舫科学技术大学研究生院学位论文 表目录 表2 1 管理距离缺省值。 表2 2p d m 状态标志 ，2 l 2 3 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 组播跬协邀i 丛二趔的丛盔曼塞趣 学位论文作者签名： 互鱼日期：驴1 5 ，年，月日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 组搔监自垃逖旦! 丛二趔的盟宜皇塞丑 学位论文作者签名：查益 作者指导教师签名 弘逮l 日期：加f 年f f 月z 日 日期：莎矿玎年，月一目 国防科学技术大学研究生院学位论文 第1 章绪论 1 1 组播简介 随着网络技术的不断发展，f r p 、h t t p 、s m t p 等传统数据业务已经难以满足人们 对信息业务的需求，视频点播、远程教学、新闻发布、视频会议等业务在应用中变得日 益重要。这类业务的特点是，信息在一个组内以一对多或者多对多的形式进行传输。例 如新闻发布，信息由一个服务器发布，大量不固定的接收端接收。如果采用单播方式来传 输这些信息，那么发送源就必须维护每个客户信息。当客户数目很多时，对于发送源来 说还需要很高的传输速率。另外，相同的数据可能在同一个链路上传输多次，消耗大量 的网络带宽。因此需要一种专门的组传输机制，这就是组播。组播可以在网络的各个层 次上实现：物理层( 例如，卫星、以太网) 、网络层( i p 组播) 、应用层( 覆盖组播应 用层组播) 等”j 。 传统的点对点单播通信，在发送方和每一接收方需要单独的数据通道。在这种通讯 方式下，源主机向指定的目标口主机发送信息包。疋信息包中的目标地址就是口网 络中唯一的主机地址。从一台主机送出的每个数据包只能传送给一个客户机，通过路由 器或交换机将这些信息包从源主机发送到目标主机。在源主机和目标主机之间的路径 上的每一个路由器都维护由单播路由协议生成的单播路由信息库( r i b ) ，并根据信息包 中的目标地址在单播路由信息库中查找单播包转发路径，这样的信息传播方式称为单 播。当网络中的主机需要向多台目标机广播相同的数据包时，必须依次向这些目标机传 送该数据包，包中除目标机器地址不同外，其他内容是相同的，这种传送方式称为单路 广播。在单路广播方式中，如果有另外的多个用户希望顺路获得这个数据包的拷贝是不 可能的，发送信息的主机必须向每个用户发送一份单独的数据包拷贝。这种重复、冗余 的传输方式给源处理机( 常为网络中的服务器) 带来了沉重的工作负荷，影响到服务的 响应时间，为达到预定的服务质量，就需要更大的投资，购买更多的硬件设施，无疑将 提高运行成本。 在通信领域，另种数据传播的方式是i p 广播，在这里，源主机一次就能向个 网段中的所有伊主机发送口信息包。碑广播包的目标地址的主机部分被设置成全1 ，网 络部分设置成子网地址。在一些例子中，主机部分设置为全零，但是这种形式的口广播 地址通常不再使用。 i p 主机( 包括路由器) 都能识别以伊广播地址作为目标地址的信息包，一个子网中 的所有m 主机都接收地址为本子网的广播地址的信息包。除非特别配置，路由器一般不 会转发碑广播信息包，因此，m 广播通信通常被限制在本地的子网内。 第1 页 国防科学技术大学研究生院学位论文 如果路由器转送这些广播，那么，路由回环将很可能引起一场严重的广播风暴。而 且广播的主要缺点就是每个广播都要发送数据至所有机器，消耗了所有机器上的资源， 而传送的数据要被网络中大多数机器所丢弃1 2 j 。 解决上述这些妒单播和口广播问题的办法是构建一种具有组播能力的网络，允许路 由器一次将数据包复制到多个通道上。采用组播方式，单台服务器能够对几十万台桌面 机同时发送连续数据流而无延时。组播发送方只要发送一个信息包而不是很多个，所有 目的地同时收到同一信息包，更及时，更同步，可以把信息发送到物理位置不同但属于 同一组播组的所有主机，能减少网络上传输的信息包的总量，网络成本也将变得更低 廉，并达到从未有过的传送能力i jj 。 口组播通信介于口单播和广播通信之间，并且能使主机发送口信息包到d 网络 中任何一组特定的主机上。这些主机都具有一种特定的p 地址，称之为组播组地址。 支持组播的路由器会转发砰组播信息包至所有具有该组播地址的主机接口上 4 1 【”。 单播与组播的区别如图1 1 所示： 单播 图( j 一1 单播与组播的区别 上图中，d 1 、d 2 和d 3 代表数据包d 的三次传输，可以看出，单播传送发送数据的 多个拷贝，每个拷贝发送到一个接收者，主机轮流发送数据的拷贝，网络分别将它们转 发至每个接收者，主机一次只能发送至一个接收者。而组播传送则是发送数据的个拷 贝到多个接收者，主机发送数据的一个拷贝，可同时发送数据到多个接收者，网络在每 个路由器节点根据组播转发地址表向目的地有选择的复制数据包进行发送，在个给定 的网络传播路径上每一个包只发送一次 6 7 f 8 jf 9 j 。 第2 页 国防科学技术大学研究生院学位论文 密集模式协议的主要特点有：用推的模式来发送数据。数据在一开始被扩散到整个 网络。没有接收者的分支要被剪枝。被剪枝的分支刻意被嫁接回来以减少加入延迟。 密集模式协议主要在如下环境中使用：发送者和接收者距离较近( 同一个l a n 中) 。发送者较少，而接收者很多。组播流量密集持续。 稀疏模式协议：总是假定在子网中都没有组播信息的接收者。缺省不向网络中转发组 播信息，除非有一个显式的加入机制来专门申请，否则组播信息不会被传送到接收站 点。在p i m s m 等稀疏模式协议中利用共享树来发送组播信息。 稀疏模式协议的主要特点有：用拉的模式来发送数据。显式的加入行为一假定如果 不加入就没有接收者。加入消息从接收者传播到组播源或是汇聚点( r p ) 。可以加入源 树或是共享树。稀疏模式协议主要应用于如下环境：接收者和发送者被w a n 隔开。接收 者较少。间断的组播信息流。 链接状态协议：例如m o s p f 与密集模式协议比较类似，它们都使用s p t ，向网络中接 收源主机发送组播信息流。然而，链接状态协议不使用用于d v m r p 或p i m d m 的扩散和剪 枝机制。相反，它们扩散特殊的组播，即链接状态信息，这些信息可随时随地识别网络 组成员，也就是接收站点。所有的网络路由器使用本组成员信息来建立从每一个源地址 到所有接收站点的最短路径树。 1 。2 5 组播研究历史及进展 1 9 8 8 年，d w a l t z m a n ，c p o r t r i d g e ，s e d e e r i n g 发表题为距离向量组播路 由协议的文章( r f c l 0 7 5 ) ，提出了将组播的功能机制增加到数据网i p 层的组播实现 体系结构，这种体系结构称为i p 组播( i pm u l t i c a s t ) 。i e t fr f c l l l 2 对i p 组播的业务 提供的方式和形式进行了描述和定义，被看成是i p 组播的标准业务模型的定义。2 0 世纪 8 0 年代中期，斯坦福大学的博士生s e d e e r i n g 发表h o s tg r o u p ：am u l t i c a s t e x t e n s i o nt ot h ei n t e r n e tp r o t o c o l ( r f c 0 9 6 6 ) 和h o s te x t e n s i o n s f o ri p m u l t i c a s t i n g ( r f c 0 9 8 8 ) 两篇论文。他总结出：“o s p f 的链路状态机制完全能被扩展用 来支持组播，r i p 的基本机制能被用来作为一种新的距离向量的组播路由协议的基 础。”这些论断提出了i p 组播的可能性。它是组播路由协议的首次实践： 1 9 9 1 年1 2 月，s e d e e r i n g 发表了他的博士论文数据报互连网络中的组播路 由( r f c i l l 2 ) 。它奠定了组播网络体系结构和路由协议的基础。该文也成为i n t e r n e t 组管理协议( i g m p ) 的原型； 1 9 9 4 年3 月，形成了对o s p f 协议的扩展协议m o s p f ( r f c l 5 8 4 ) ： 1 9 9 6 年i 1 月，出现了对于基于u n l 3 0 3 ，1 的a t m 组播网络支持协议( r f c 2 0 2 2 ) ： 1 9 9 7 年9 月，有核树( c b t v 2 ) 组播路由体系结构形成( r f c 2 1 8 9 ) ； 1 9 9 7 年1 1 月，组管理协议i g m p v 2 得到i e t f 的批准，成为标准( r f c 2 3 3 6 ) ： 第6 页 国防科学技术大学研究生院学位论文 第2 章p i m d m 组播路由协议研究 协议无关组播( p m t o c o lh l d e p e n d e n tm u l t i c a s t ：p 蹦) 由d m r ( 域问组播路由) 工 作组设计，是一种性能优良、广泛使用、被主要路由器厂商所支持的组播路由协议，如 c i s c o 路由器就将p 作为其支持的主要组播协议。p n 订的设计出发点是在i i l t e m e t 范围 内同时支持s p t 和共享树，并在两者之间灵活转换，因而集中了它们的优点提高了组播 效率。p 垤定义了两种模式：密集模式( d e n s e m o d e ) 和稀疏模式( s p a r s e m o d e ) 。下面 主要就p 江一d m 协议作详细的论述【3 2 1 【3 6 l 【1 “。 2 1p im 协议概述 p d 证之所以被称作”协议独立组播”，是因为它必须使用组播路由信息库( r 璐) 中由任 何路由协议输入的所有路由信息，来完成组播的r p f 检查，进行转播转发。这些路由协 议可以是单播协议，如r p 、0 s p f 。也可以是路由器中的其他组播协议，如d v m r p 。 因此，p d 江组播协议虽然需要其他的路由协议来完成自己的路由发现，但是独立于具体的 路由协议。p 订的优点在于不必保持它自己的路由表，不需要像其他协议那样发送或接收 组播路由更新，例如m o p s f ( 组播开放式最短路径优先) 或d v m r p 。由于不必发送组 播路由更新，所以与其他组播协议相比，p 讧协议的开销降低了许多。 p m 协议所支持的两种模式中，密集模式p i m - d m 在协议行为上比较简单，易于理 解。p v f - d m 具有p d 订协议的基本特征，同时作为密集模式协议，具有密集模式的通用 特征。所以将p m i d m 的协议特征概括如下： 1 独立于协议( 可以使用任何单播路由表进行对) f 校验) ； 2 没有分离组播路由协议( d v m r p 中存在) ； 3 扩散剪枝机制( 9 0 秒的周期) ； 4 无类( 只要有单播路由支持变长地址掩码) 。 从协议实现的角度来看，p 讧一d m 与p 订一s m 的本质区别在于p d 以- d m 没有周期性的 j o n 消息，只有触发的g r a 舯r u n e 消息。同时p 蹦一d m 没有汇合点( r e n d e z v o u s p o i n t ：r p ) 。 组播协议中的密集模式和稀疏模式分别有自己的适用范围，p 讧一d m 作为密集模式协 议，也遵循这些规则。实际应用中，如果满足下面的些条件，密集模式组播将比稀疏 模式的组播协议带来更高的效率。 i ：高速网络； 儿：组播源和接收者比较靠近； i i i ：对组播组发送者少接收者多； 第1 0 页 国防科学技术大学研究生院学位论文 ：组播数据流比较大且比较稳定。 以下为本章涉及的一些技术术语： 路由邻居：组播协议根据接口进行组播数据的转发，接口上的邻居和组成员状态决 定了数据是否转发，所以p d 订协议必然要在路由器之问建立邻居关系。p v i 协议中是通 过向所有接口周期性地发送h e l l o 消息来宣告自己的存在，这样根据收到的h e l l o 消息， p v i 路由器可以在每个接口上维护一个p m i 邻居表，邻居状态的变化后可以进行相应的 处理。 组播数据包的转发：为了完成组播转发，沿途的路由器需要为组g 和源s 创建相应 的组播路由项( s ，g ) 。( s ，g ) 路由项包括组播源地址、组播组地址、入接口、出接口列 表、定时器和标志等。( s ，g ) 的入接口和出接口决定了数据包转发方法。p d 订一d m 使用 s p t 树进行数据包的转发，p d 垤一d m 中规定了s p t 树的建立、修改和撤销的过程。 s p t 树的剪枝过程：p d 以一d m 是密集模式( d e n s em o d e ) 组播路由协议，存在典型 的扩散剪枝过程，数据包在所有可能的接口上转发，由下游邻居来对特定( s ，g ) 进行 剪枝，剪枝操作由上游邻居和所有的下游邻居共同协作完成。 s p t 分支的嫁接：当路由器已经对某个( s ，g ) 向上游邻居进行了成功的剪枝操作， 只有当剪枝超时后路由器才可能重新从上游邻居处收到组播数据包，但当有新成员加入 时，这个延时过长。通过主动的给上游邻居发送g r a f t 消息，可以有效地减少延时。这 个机制实际上在d v m r p 中已经出现过。 a s s e r t 过程：在多路访问l n 中( 比如以太网) ，同一网段上可能连接多个并行的 p d 讧路由器。为了不在网络上重复的发送相同的组播数据，必须决定一个路由器来负责组 播数据的转发。通过a s s e n 消息p 订路由器可以进行这个选举的过程。一般情况下，由 该网段的d r ( d e s i g n a t e dr o u t e r ，指定路由器) 负责向该网段转发组播包。但在某些情 况下，也可以由另外的路由器转发组播包。 另外，在所有的p 瑚协议图示中，为了明确路由器的状态转换，尽可能表示出内部 状态。都采用c i s c o 路由器中的命令行显示格式。以后不再说明。除非有特别说明，对采 用p m i 协议的说法，表示不仅仅适用于p 肼一d m ，同时也适用于稀疏模式p v i s m 。 2 2p lm 路由令b 居 就像d v m r p ，p v i 也有自己的邻居发现机制，用于建立p i m 邻居关系。路由器通 过发送h e l l o 消息向所有的p m i 路由器宣告自己的存在，通过h e l l o 消息，路由器可以建 立路由器的邻居关系。 第1 1 页 国防科学技术大学研究生院学位论文 图o 争1h e l l ，0 消息 图2 - 1 中，两个p i m 路由器相互发送h e l l o 消息，建立了邻居关系。邻居关系的建 立，对p i m 协议是非常重要的，下面从几个方面介绍p i m 的h e l l o 消息。 p i m h e l l o 消息 在每个h e l l o 周期( 缺省为3 0 秒) 内，p i m 路由器在自己所有配置了p i m 协议的接 口上发送p i m h e l l o 消息到组播地址2 2 4 0 0 2 ( 所有p i m 路由器) ，以便向各个接口上可 能的p i m 路由器通知自己的存在。p i mh e l l o 信息包含一个保持时间，表示发送h e l l o 消 息的p i m 路由器在多长时间内是有效的。也就是说，接收方如果在这个时间过后没有收 到同样的p i mh e l l o 消息，将认为h e l l o 消息的发送方不存在了，终止与发送方的邻接关 系。这个保持时间一般设置为p i m h e l l o 发送间隔的3 倍。比如发送周期为3 0 秒，保持 时间将设置为90秒，接收方收到hello消息后，在90秒钟中内可以认为hello消息的发 送路由器仍然正常工作。不论是pimdm还是pimsm，都需要hello消息来完成邻居发 现过程。 pim指定路由器(dr)除了建立p i m 邻接之外，p i m h e l l o 消息也用来为多路访问网络( 比如以太网) 选择 指定路由器(dr)。pim路由器通过发送hello消息来进行dr的选举，选举的获胜者成 为本网络段的dr。对pimdm来说，dr没有任何意义。这个功能仅当网络中仍然使用i g m pv l 协议的时候有用，因为i g m p v 1 需要组播协议来指定d r ，这个d r 在 l a n 上成为i g m p v l 的查询者。 dr选举遵循一定的规则。一般根据路由器的网络地址来进行判断，m地址最大的路 由器将成为dr。不过当有多个路由器工作在一个局域网段时，网络管理员经常需要强制 dr的选取(即选取特定路由器作为dr)，如果通过重新设定路由器的m地址的方法来 指定，非常的不方便甚至是不可能的。最新的pim协议草案(draft)中建议在pimv2的h e l l o 信息上增加d r 优先权，用于p i m d r 选取过程。通过对路由器的配置可以指定 局域网上每个路由器的d r 优先权( 缺省的优先权= 1 ) ，最优先的路由器将成为本网段的 d r 。如果在所有路由器有同样的优先权，重新使用地址作为d r 选举的标准。 行论述。下图显示了一个在p m i d m 网络中沿着广播树向下扩散的例子。随着组播数据 的扩散，各个路由器建立了特定的状态。图( ) 2 3p i m d m 分布树 组播数据包根据r p f 规则在所有的接口上进行扩散；路由器c 上存在( + ，g ) ，并且转发项上的标志指明l n 上有直接连接的组成员； 路由器c 生成( s ，g ) 项； 路由器f 有p v i 协议邻居，但是没有建立( s ，g ) 状态。当组播数据包第一次到达 蒜译：商讨；蠢! = 前辩潲鞘稚；| = 釜；径； 漫嚣臻；柏塞塑露盟量剃燕! t i 薹薹；址l ? 蠢 ，成襄哥为完整的组搔协以妻萼蒌赫赫；落 灞墒鞴情矧胖谨j j 捌数刊粒雒莺| ! l 噼擦箍潍。 罄鲥助拜酬弛m 彗露蚺碍殛：薄蛞瞵艘国峪擘姐也譬耋蓥弦添墨馨叁纛肆骶琵崔j 岳 謦翼帮垮丁滤噬啭；理一例蛙唔猫嚣醯麴受繇戮薛蓦。矾戛孽鞠t 工程任务组) 下属 的组播工作组有：i d m r 5 、 p i m 6 、m s e c 7 、r m t 8 、m a g m a 9 和s s m i o 。i d mr 工作组致力于完成域问的组播路由：p i m 工作组主要研究域内组播路由；m s e c 工作组主要研究组播安全方面的内容，保证只有合 法成员才可以得到组通讯内容，合法的组成员可以进行源认证和内容认证、抵抗拒绝服 务攻击、组密钥管理和组策略管理：r m t 工作组负责可靠组播传输的标准化工作；m a g m a 工作组研究组播和任播( a n y c a s t ) 机制，其中涉及组播成员的认证、访问控制等等，这 一点与m s e c 工作组的工作类似；s s m 工作组负责定义特定信源组播机制。这些工作组的 分工不是十分明显。比如负责组播安全的m s e c 通常需要与具体实现安全的i p s o c 等工 作组交融，与诸如p i m ，r m t ，i d r m ，m a g m a 工作组进行联系。总体上，根据这些工作组 的分工可以将组播的研究领域大致分成：组播路由、安全组播、可靠组播和特定源组 国防科学技术大学研究生院学位论文 在介绍剪枝消息的发送前首先介绍p d 讧一d m 中的一个概念一叶网络。如果p i m d m 路由器的某个接口上所连接的网络上没有p 蹦一d m 路由邻居，此网络成为叶网络。连接 了叶网络的p m l d m 路由器成为叶路由器。( p d 一d m 中的p r u n e 状态在叶路由器上初 始化) 。 p 垤一d m 对某个源发送剪枝消息的条件如下： 信息到达p v i d m 路由器的非r p f 点对点接口。因为这种情况下，p v i d m 路由器 可以肯定的认为自己收到了不需要的组播数据。 p v i d m 路由器没有下游邻居，并且路由器的所有叶网络上没有组播组的成员。 p 订一d m 路由器所有接口上的下游邻居已经通过了剪枝表决。 下面通过一个详细的例子来说明p d d m 的剪枝过程。 ( ，2 i 2 。1 2 72 5 4 】0 0 二0 0 ：j 0 ，0 g ：0 0 0 0 r f0 00 。0 ，f 1 目口3 ：d i m i 埘i n t e r f a o el i l r p f 幽p00o0 o u t g o i r 埘i n e r f a 口e 1i # e ： o o r i a l j ，乳r w a r d ，d 嵇1 s e ，0 00 0 ：1 0 ，0 0 ：0 0 ；0 0 s e f i a l 3 髓r d o 掣蟮o ，0 00 0 ：1 0 o o 0 0 ：o o 【】2 8gi 6 043 ，j 2 十2 2 2 24 ，+ 2 s 4 ) 一0 ( ) ：u ，j ：jo ， 1 0 ：0 24 9 ，1 a q 自r t n o 龇i h gi n t 自r ：8 e r t a l dp rpfn b rj9 89 2i12j o u b g o i 埘i a t e r 1 i g t ： o e y i a l i 脚r “a z d ，d e n o e ，0 0 0 0 ：1 0 0 0 0 00 0 o 帆a l j 。f b r d d e ：。，0 0 ：0 0 ：1 0 7 0 0 ：d o 0 0 图o 争4p i id m 剪枝前状态 图中，路由器n r a 上的组播数据包在所有的接口上进行扩散。可以看到路由器中同 时存在( 4 ，g ) 和( s ，g ) 。( 4 ，g ) 状态在收到了i g m p 消息后生成或者当生成 ( s ，g ) 的时候自动生成。接口s l 和s 3 同时存在于出接口列表当中。 由于路由器n r _ b 是一个叶路由器，并且没有直接相连的接收者，所以必须对s o 接口 上的组播数据进行剪枝。 第1 5 页 国防科学技术大学研究生院学位论文 图0 26p i m 剪枝否决 在图中，各个路由器的行为如下： 路由器i 没有组播组成员，所以向上游邻居发送p r u n e 。由于是点对点链路，所以 不存在剪枝否决过程，剪枝马上发生。路由器e 在状态发生变化后也会触发p r u n e 消息 到c ( r p f 路由器) 。路由器c 知道自己的子网上存在组播组成员，所以忽略p r u n e 消 息。 路由器g 没有组播组成员，所以向上游邻居f 发送p r u n e 。路由器f 收到剪枝消息 后，由于是多路访问链路，所以不立即进行剪枝，等待其他下游邻居j o i n 消息。路由器 h 在收到了g 的剪枝消息后，发现自己仍然有组播组成员，向f 发送j o i n 消息来覆盖g 的p r u n e 消息，这样路由器f 取消将要发生的剪枝行为。 剪枝延迟累加 多路访问网络中剪枝存在一定的滞后，这个问题可能会带来严重的后果。为了说明 这个问题，首先说明剪枝过程中，上游邻居所完成的处理。当p i m d m 路由器在多路访 问网络中收到剪枝消息时会启动3 秒钟剪枝延迟计时器。如果在这个时间内没有收到 j o i n 信息，那么该剪枝生效。这样一个可能的剪枝真正发生存在3 秒的滞后。问题出现 在当组播信息流过多个多路访问网络时，延迟可能累加。结果就是不需要的组播数据在 很长的一段时间后才能从网络从被剪枝，浪费了带宽。所以在设计p i m d m 网络时必须 留心多访问剪枝延迟。 2 5p im - d m 嫁接 p i m d m 还有一种能力把前面剪枝的分布树上的分支嫁接回来以便用最小的延迟重新 启动组播信息流。下面通过“个例子来说明这个过程。 丽1 r i 一 国防科学技术大学研究生院学位论文 图篮一7p i m 嫁接 图中显示的网络例子和是前面的例子剪枝后的状态，现在接收者3 加入到与路由器1 已经断开的组播组。这是通过i g m p 协议来完成的。 如果路由器i 没有组的状态不作任何处理，因为这表示组播数据没有扩散到路由器i 或者有一段时间没有特定组播组的数据了，所以没有必要进行处理。但是现在路由器i 存 在组状态，只不过对应的接口不在出接口列表中，所以路由器i 将这个接口加入出接口列 表。 加入了接口后，路由器i 发现自己先前已经对组播组向e 进行了剪枝，只有在剪枝超 时后组播数据才可能重新发送到自己，为了马上收到组播数据，i 向路由器e 发送一个特 定的g r a f t 消息，e 从路由器i 接收g r a f t 消息后，马上发送嫁接确认来应答，同时 将这个接口的剪枝状态取消。现在组播数据就可以转发到接收者3 了，整个过程中没有任 何滞后。 2 。6p im - d m 声明 p i m 中的声明可以通过下面的例子来说明。图中，组播信息初始扩散后，可以通过路 由器c 和d 发送到以太网上，进入接收站点1 ，这样产生了重复的组播信息。 为了解决这个问题，必须断开一个组播信息流，只保留一个流向接收站点1 的组播信 息流。p i m 使用声明机制来完成这个功能，通过声明机制，可以选定个特定的路由器 来进行组播数据的转发。首先必须判断的是什么时候需要进行声明选择过程，这是由上 游的并行路由器来进行判断的。 规则：如果路由器在某个转发状态的输出接口列表中的接口上收到源的数据包，就 可以判断出收到了重复的组播数据，需要进行a s s e r t 过程来决定一个转发者。 第1 8 页 国防科学技术大学研究生院学位论文 p i m p i m 当在某个接口上启动声明机制时， 路由器发送包含有关尺度的 声明消息到 这个接口。这个接口上的所有p i m 路由器检查p i m 声明消息中的尺度来确定哪个路由器 有最好的尺度返回组播源。具有最佳尺度的该路由器继续负责组播数据的转发，而所有 其他的p i m 路由器把它们的接口剪枝。如果在尺度上相等，就使用路由器地址来判断， 具有最高坤地址的路由器将当选。 下图显示了p i m 声明机制工作流程。 图0 9 一8p i l , t 声明机制 步骤1 ：路由器c 和d 通过串行接口开始接收相同的源信息，并转发至同一个以太 网网络。结果，每个路由器通过它们的输出接口列表上的一个接口接收来自组播源的信 息包。所以路由器c 和d 发送p i m 声明消息来决定谁将成为转发者。 步骤2 ：路由器发送和接收的p i m 声明消息中包含管理距离( 用来作为高位部分的 比较值) 及对源的路由选择协议尺度( 用来作为低位部分的比较值) 。p i m 声明消息的值 经比较得出最小值( 即当管理距离和路由尺度都被考虑时，有最适合信源的尺度) ，具 有最小值的一方赢得声明。失败者都停止发送源信息到网络，并剪枝他们的通往组播源 的接口。 图中路由器c 和d 正通过输出接口( 以太网上) 发送p i m 声明消息，假设路由器c 和d 相同尺度，但c 有更高的妒地址，c 赢得声明后继续向以太网转发信息，而路由器 d 剪枝它的接口。 路由器e 在收到的a s s e r t 消息中进行比较，胜出者c 成为自己的上游邻居。假设 c 不同于自己对组播源的r p f 邻居d ( 根据自己的单播路由表) 。则对当前上游邻居c 进入j o i n 过程。同时启动a s s e r t 定时器。定时器超时后，重新将上游邻居设置为s 的r p f 邻居d 。 第1 9 页 国防科学技术大学研究生院学位论文 2 7 转发与状态 路由器中，组播转发状态表现形式为组播路由表或”m r o u t e ”表中的( 。，g ) 和( s ， g 、项，通过执行”s h o wi pm r o u t e ”命令可咀显示这些信息。 路由器是根据组播路由状态来转发，为了描述后面的状态规则，首先对路由器根据 状态进行转发的过程进行说明。 无论何时，只要收到组播包，就通过输入包源地址( s ) 和组地址( g ) 来搜索组播路由表 的最长匹配。这个最长匹配搜索首先要搜索表中一个( s ，g ) 匹配项，然后使用这个相匹配 的项。如果现有的( s ，g ) 项都不匹配，就寻找( 。，g ) 项的匹配，再加以使用。( 注意p i m d m 应该使用在组播路由表中与( s ，g ) 项对应的源树，但如果无现有的( s ，g ) 项与之匹配，则创 建一个( s ，g ) 项，创建中如果存在( 。，g ) 项，根据( 。，g ) 来进行生成) 。 在找到相匹配的项( 或创建了) 时，在输入包上进行r p f 检查。此项检查是通过将组播 路由表上的输入接口与该包的实际接口进行比较来完成的。如果该包不是经过正确的输 入接口到达的，将此包丢弃。值得注意的是，一般的协议实现中都保存了组播路由表项 的输入接口，并不是每次都查询单播路由。这样r p f 检查中只需进行简单匹配，看到达 的接口是否与输入接口匹配。否则如果不保存入接口信息，每当有组播包到达路由器都 必须扫描单播路由表来进行r p f 检查，这个过程对系统性能有重大影响。这种方式下， 为了适应网络拓扑结构的任何变化，每隔规定的时间( 秒) 重新的计算每个组播项的输 入接口，或者在路由信息发生变化的时候重新计算。 如果该包经正确的接口到达( 即r p f 检查成功) ，将此包转发到所有输出接口列表 上未剪枝的接口上。 下面解释了在p i m d m 中使用的一些基本状态维护规则。有一些条件下，这些规则 是p i m d m 和p i m s m 双方通用的规则( 即使有时有不同的用法) ，这些规则称为通用 规则，仅适用于密集模式的规则就称规则。 p i m d m ( 4 ，g ) 状态规则 虽然p i m d m 规范中没有要求，但无论何时只要创建( s ，g ) 状态，c i s c o 的组播路 由协议就自动创建父( + ，g ) 状态。主要理由是在c i s c o 的组播路由协议中所有( s ， g ) 数据结构是与其父( t ，g ) 数据结构链接在一起的。这样做不仅使附加的维护这些 ( * ，g ) 项的存储器耗费最小，而且还由于各种p i m 内部的最佳化效果获得补偿。由此 产生p i m 通用规则。 通用规则l 无论何时，只要创建一个( s ，g ) 项而其相应的父( $ ，g ) 项不存在，就首先自动 创建新的( * ，g ) 项。密集模式中( m ，g ) 不用于组播转发，他们的主要功能是维护那 些与组有关的信息使之成为一个整体。例如， ( * ，g ) 项表示组运行的模式( 在此为密 集模式) ，而密集模式也映射了连接其他邻居或直接连在组现有成员上的接口。由此产 生第1 条密集模式规则。 国防科学技术人学研究生院学位论文 密集模式规则1 密集模式( + ，g ) 项的输出接口列表映射了现有的p i m d m 邻居接口或直接连接的 组成员接口。 p i m d m ( s ，g ) 状态规则 在p i m d m 中，组播信息流到达后创建( s ，g ) 项( 再次强调，如果父( * ，g ) 项 不存在，首先创建它，而其所提供的输出接口列表如前面有关章节所述) 。 ( s ，g ) 项 输出入接口可以计算源s 的r p r 接口可以估算出来，r p f 接口用下列规则计算： 通用规则2 r p f 接口是作为对源地址( 或稀疏模式( + ，g ) 项，r p ) 的最小开销路径接口 ( 基于管理距离) 2 度) 来估算的。如果多个接口开销相同，选择最高坪地址的接口作为 ”切入点( t i e b r e a k ) 。” 缺省的行为方式是选择到源的最小开销路径，它在单播路由表中指明。然而，对 r p f 来说，使用别的信息源，诸如组播边界网关协议( m b g p ) 表、d v m r p 路由表以及 静态组播路由表等可能会有另外的接口。各个表有其自己的管理距离，这对r p f 计算有 影响。 注意：像单播路由一样，当，一个的路由是从一个以上的路由源学习到的时候就使用 管理距离计算组播r p f 。当路由器运行组播路由协议或定义了静态路由时，上述情况就 会发生。每个路由管理距离值( 简称距离) 在同一网络中有多个路由器时被用作_ 丌销的 高位部分的比较值。此时，选最小距离的路由。 下表给出了各种r p f 数据的源的管理距离缺省值。 表缺省距离 单播 ( 路由距离) i m b g p l 2 0 0 e m b g p 2 2 0 d v m r p0 静态组播路由 o 表0 甚一1 管理距离缺省值 1 ：从内部对等的m b g p 上得到的路由 2 ：从外部对等的m b g p 上得到的路由 如果管理距离相同，那么宁愿选静态路由而不选其他源。而且，如果在一个表内有 多个路由匹配路由。这不适用于跨表之间的情况。例如，在d v m r p 路由表中有一个 1 5 l ，1 0 0 0 1 6 路由( 假定d v m r p 缺省距离为0 ) ，而在单播路由表中有匹配的 1 5 1 1 0 1 0 2 4 路由器，仍然是d v m r p 路由被使用，即使单播路由有更长的匹配也是如 第2 1 页 国防科学技术大学研究生院学位论文 此。然而，如果d v m r p 路由表中有1 5 1 1 0 0 0 1 6 和1 5 1 1 0 1 0 2 4 两个路由项，那么使用 1 5 1 1 0 1 0 2 4 路由，因为它是来自同一表的路由。 当( s ，g ) 项刨建时，其输出接口表复制父( + ，g ) 项的输出接口列表( 因为此父 辈的密集模式的出口表含有所有p i m 邻居或直接连接的成员列表，结果是信息流一丌始 就按扩散及剪枝方式经过新建的( s ，g ) 项转发) 。由此产生通用规则3 。 通用规则3 在创建新的( s ，g ) 项时，其出接口列表复制父( + ，g ) 项的输出接口列表。很可 能( s ，g ) 项的输入接口也在其父( * ，g ) 接口的输出接口列表中。这样会导致路由循 环，这是无法接受的。所以，每当计算( s ，g ) 项的r p f 接口时，都要检查输入接口是 否在输出接口列表上。如果在，就把它从出口表上清除掉。下一个通用规则就是这个过 程的总结。 通用规则4 组播转发项的入口( r p f 接口) 决不能在其出口表上出现。 p i m d m 状态维护规则：当一个组播包到达后一个适当的p i m d m 状态被建立时， 路由器中的各种事件发生变化都可能导致状态项定期的更新。最常见的就是如果其他路 由信息发生了变化，对组播转发表中的所有项定期进行r p f 接口( 输入接口) 的重新计 算。重新计算的作用是在网络拓扑变化后使组播路由能收敛。 通用规则5 每个组播状态项的r p f 接口( 即输入接口) 每5 秒重新计算一次，而且依据规则4 对输出接口的列表做适当的调整( 以防在出口表上出现输入接口) 。 此外，在创建一个密集模式( s ，g ) 项时，在输出接口列表上各个接口的状态被标 记为”转发密集”，以便开始按密集模式把信息从输出接口扩散出去。对其中一个接口进 行剪技( 作为从下游邻居处接到对该( s ，g ) 剪枝消息的结果) 并不从出口表上删除此 接口，而是标记为”p r u n e d e n s e , 并启动3 分钟剪枝计时器。当3 分钟计时器计满，该接 口回到”f o r w a i d d e n s e ”状态，信息重新从这个接口扩散出去。 密集模式规则2 密集模式( s ，g ) 项的出口在剪枝时不能删除，而是被动标记为”p r u n e d e n s e ”，且 仍保留在出口表上。最终，所有( s ，g ) 项的出口表上接口其父( 母，g ) 项的出口保持 同步( 受通用规则4 的约束) 。这样就可以添加或删除任何p i m 邻居或直接连接的组成 员，他们反映了密集模式( + ，g ) 项出口表的变化，也反映了对应( s ，g ) 项的变化。 通用规则6 总结了这个过程。 通用规则6 对( e ，g ) 项的出口表的添加和删除都被复制( 在通用规则4 的限制下) 到所有与 该组有关的( s ，g ) 项。在另一个接口上检测到一个新的p i m d m 邻居时，通用规则6 第2 2 页 国防科学技术大学研究生院学位论文 会发挥作用。依据通用规则6 新接口被加到有关( s ，g ) 项的输出接口列表上，以便信 息能扩散到这个新邻居。 运用上述的通用和密信模式规则，可以预计cisco路由器在典型的密集模式下会有怎 么样的行为表现。 pimdm状态项：加深对pimdm状态信息的理解是非常重要的，这些状态信息用”s h o wi p lnrorte”命令显示。这些信息通常使一些新的组播用户糊涂，而在解决组播问题时 又是从路由器可以获得的最重要的信息。本部分关注的是一些密集模式命令的输出实 例，并用逐行逐行地加以探究。对每一项显示的标志加以定义并解释其含义将有助于读者理解这些项。 pimdm状态标志：每个组播路由的项第一末尾的标志字段都显示了一个或多个状 态标志。下表解释了密集模式项标志字段中出现的状态标志。理解了这些状态标志的设 置和清除及他们的意义就是向理解组播路由状态迈进了一大步。 d 密集模式 表示组播是一个密集模式组(注：d标志仅出现在(， 标志 c 连接标志 g)(+，g)和(s，g)两种项下都出现，表示该组播组有直l 本地标志 接(+，g)和(s，g)两种项下都出现，表示路由器自己就是组成员。因此，该路由器将在过程级处理向本组播组发 组是pim-sm发现(2240140)组，这个组被用来发布自 p剪枝标志表示输出接口列表为空或所有输出接口列表中的接口处于 剪枝状态，这个状态会触发剪枝消息到此( s ，g ) 的上游( r p f )t 最短路径邻居标志pt) 只在( s ，g ) 项上出现，表示信息经( s ，g ) 项( 即s p t ) 转发无论 置该标志( 因此，在密集模式t 标志始终设置在( s ，g ) 项上。 表0 争2 p i m d m 状态标志2 8 新p i m 邻居的邻结性 如