CN100403728C - 路由表表项保活方法及路由器组播协议分布实现系统 - Google Patents

Abstract

本发明涉及一种路由器中路由表表项保活方法和一种路由器组播协议分布实现系统。其中路由表表项保活方法包括：在定期下发的转发表中设置保活计时器KAT的门限值；转发处理单元接收数据报文；判断数据报文对应的路由表项是否失效；若失效则更新转发表项和路由表项，否则更新转发表项。组播协议分布实现系统包括路由表管理子系统、网管软件子系统、路由表控制单元、转发表生成单元和数据报文仲裁处理单元。本发明使路由器路由能力不再过分依赖个别器件的性能，适用于10Gbps到40Gbps的高性能路由器接口，实现高速的线速转发。

Description

路由表表项保活方法及路由器组播协议分布实现系统

技术领域

本发明涉及计算机通信领域的路由方法，尤其是计算机通信领域中路由器的路由表更新方法以及具有分布式体系结构的路由器组播协议分布实现系统。

背景技术

基于互联网协议(IP)的路由器技术随着互联网的发展而不断发展，已经从单处理器的路由器发展到具有分布式体系结构的路由器。目前，路由器完成的主要功能包括协议数据包的处理和转发数据包的处理；其中协议数据包主要包括单播或组播路由协议报文、控制报文等；转发数据包指用户的单播或组播数据报文。高性能路由器具有分布式系统结构，该系统如图1所示由线路接口单元1、转发处理单元2、高速交换网络3、内部通信模块4和主控单元5组成，其中：

线路接口单元1主要实现路由器接口上物理层和链路层线路连接的功能，一个路由器中包含多个线路接口单元，在高性能路由器中主要包括2.5G POS接口、1000M以太网接口、155M ATM接口和10G POS/LAN/WAN接口等。

转发处理单元2是高性能路由器的关键部件，一个路由器中可以有多个转发处理单元，它们用于对进入路由器的数据报文按照正确的接口线路进行转发，它的处理速度决定了路由器可支持的线路接口的最高速率。该单元实现第三层处理，包括：IP包的线速转发、过滤与安全监测、包的优先级分类、组播报文的识别与加贴标签、内部报文格式的形成等。

高速交换网络3实现数据报文的交换，为不同级别的业务提供不同的服务等级。交换网络的容量决定了路由器的吞吐量。

内部通信模块4保证路由器各个模块协调工作、保证主控单元对各个模块单元进行有效控制、帮助网络管理员对设备进行配置的关键单元。我们采用了以太网连接路由器基础平台的各个模块，因而内部通信机制的主要研究目标是在多处理器通过传统以太网络通信的环境下完成实时和可靠的通信。

主控单元5进行路由计算、网络管理，它与路由器中每个线路接口单元、转发处理单元和内部通信模块相连，控制路由器各个模块的工作状态，是高性能路由器的核心。

互联网协议定义了3种IP数据包的传输：单播(unicast)、广播(broadcast)和组播(multicast).其中组播指的是在局域网或广域网上将IP数据包从一个发送者传送到一组接收者，并且依靠网络将数据包只传送给需要接收它的网络。

目前的组播路由协议主要分为两大类，即域内组播路由协议和域间组播路由协议。域内协议主要有协议无关组播-密集模式(PIM-DM，ProtocolIndependent Muiticast-Dense Mode)、协议无关组播-稀疏模式(PIM-SM，Protocol Independent Muiticast-Sparse Mode)和协议无关组播-源特定组播(PIM-SSM Protocol Independent Muiticast-Source Specific Multicast)，其中PIM-DM采用洪泛加剪枝的工作模式，不适合较大规模的网络；PIM-SM采用接收者发起构建共享树的工作模式，是目前使用最多的组播路由协议；PIM-SSM是最新提出的组播路由协议，在协议简化、地址分配等方面有较好的改进，但是由于需要主机和网络设备支持Internet组管理协议第三版/组播监听者发现协议第二版(IGMPv3/MLDv2)，因此目前使用受限。

目前的高性能路由器设计中，需要实现组播数据报文的线速转发，并且支持主要的域内和域间组播路由协议，且高性能路由器必须实现组播协议中的PIM-SM协议。现有的实现方案主要有以下两种方式：

采用纯软件的实现方式，在这种方式下，组播的数据平面和控制平面都由软件来实现，软件的运算集中在路由器的主控单元，没有增加特殊的硬件设计，由于协议实现过程只由软件运算进行实现，相比借助硬件实现组播协议的效率低，因此目前这种纯软件的实现方式主要用于中、低端的路由器设备，无法支持高端路由器的实现。

采用网络处理机(NP)的方式，在这种方式下，组播的数据平面和控制平面都由网络处理机来完成，即组播协议的实现主要集中在网络处理机中，由于数据平面的处理过程会影响到主控单元的协议状态机的改变，也就是说数据包的转发行为与保持组播路由表以及协议体其他控制动作相互作用，它是一个复杂的处理过程，而网络处理机(NP)需要完成数据平面数据转发等处理工作，又要在控制平面中对组播路由表进行维护工作，即实现组播的数据平面和控制平面都是由网络处理机完成，因此路由器的整体性能完全依赖于网络处理机的器件性能，由于受到网络处理机开发技术水平和开发成本的限制，一般的路由器无法实现在10Gbps乃至40Gbps的速率下支持组播线速转发。

在现有路由器中有一个保活计时器(KAT，Keep Alive Timer)，其主要作用是维护组播路由表中相应表项的有效期，当一个表项存活时间超过KAT期限之后，该表项将会被清除出路由表。每次当有组播数据报文到达时，该数据报文相应表项的计时器KAT的值就要被重置，KAT值的重置是现有路由器中PIM-SM协议实现的难点之一，因为数据是在转发处理单元进行处理的，而相对应的组播路由表项是在主控单元中进行维护的，也就是说，每当数据平面有新的数据报文到达，就会影响到控制平面中组播路由表的改变。在一个10Gbps的线路接口上，组播数据的到达量非常大，如果每个到达的数据报文都上报主控单元，那么就会在路由器的内部产生非常大的数据流量，从技术实现上来说这种路由表表项有效期的维护方法是不可行的。随着网络中数据量的不断增大，需要路由器能够支持更高速的接口，目前高端路由器中采用的如前所述的路由表项的保活方法会使控制平面和数据平面间会产生大量的交互消息，使得PIM-SM协议控制平面和数据平面的高效消息交互存在较大的困难，也加大了NP的处理压力，限制了路由器转发效率的提高。

发明内容

本发明所要解决的技术问题是提供了一种组播协议中用于更新路由表的方法，即路由表表项保活的方法，这种方法通过降低控制平面和数据平面间的消息量提高了路由器的转发效率，使路由器实现了高速率下的线速转发。同时本发明还提供了一种适用上述表项保活方法的分布式路由器中组播协议分布式实现系统，这种方法降低了路由器性能对特定器件性能的依赖，提高了路由器的转发效率，使路由器可以实现更高速率下的线速转发。

为解决上述问题，本发明提供了一种路由器组播协议实现中对路由表表项的保活处理方法。这种方法在根据主控单元向转发处理单元定期下发的路由表生成的转发表中设置保活计时器KAT的门限值；在转发处理单元接收数据报文；通过比较所述数据报文的计时器的值及所述数据报文对应转发表项中的KAT的门限值，判断数据报文对应的路由表项是否失效；若失效则更新转发表项和路由表项，否则更新转发表项。其方法的具体实现为：预置一个计时器，用于监视每个转发表项的生存期，当生存期到达预置的生存期的期限，则需要从主控单元重新下发转发表，在下发转发表时，需要设置保活计时器的门限值；转发处理单元接收数据报文，并获取数据报文到达时的计时器的值和数据报文对应路由表项的保活计时器的门限值，将这两个值进行大小的比较，以判断数据报文对应的路由表项是否仍在有效期内，如果数据报文到达时的计时器的值不大于数据报文对应路由表项的保活计时器的门限值，则该表项有效，否则说明该表项失效。如果路由表项已经超出有效期，则删除转发表中超出有效期的表项，并且把修改内容上报给主控单元，并且可以将超出有效期的数据报文进行抛弃，如果比较结果证明数据报文对应的路由表项仍然在有效期内，则修改新的保活计时器门限值为数据报文到达转发处理单元时的计时器的值与预置的保活周期的值的和，并可以将仍在有效期的路由表项对应的数据报文正常转发。

由于本发明提供了新的表项保活的方法，因此需要对原有的转发表进行相应的修改，则发明提供的转发表中应该包括：数据报文的源地址、数据报文的组地址、用于表示该表项属于共享树或源树的标志位、用于控制数据平面与控制平面的交互的保活计时器门限值、用于表示源树是否成功建立的标志位、RPF接口列表和出接口列表。

本发明还提供了一种适用上述路由表表项保活方法的路由器中组播协议分布实现系统，该系统在路由器中的主控单元及转发处理单元间用于组播协议主要功能的实现。在主控单元中包括路由表管理子系统、网管软件子系统，同时路由器主控单元中还包括路由表控制单元，用于根据控制消息生成组播路由表并下发给转发处理单元；在转发处理单元中还包括转发表生成单元，用于根据主控单元下发的路由表内容生成转发表；数据报文仲裁处理单元，用于对不同数据报文进行处理，并将根据仲裁处理产生控制消息上报到主控单元。

在主控单元中的路由表控制单元还可以包括：消息收/发单元，接收转发处理单元的数据驱动控制消息，接收其他路由器的控制消息，或将本路由器的控制消息发送给其他路由器；控制消息处理单元，与消息收/发单元连接，用于根据收到的控制消息生成路由表；路由表管理单元，与路由表控制子系统单元和控制消息处理单元连接，用于将路由表下发到每一个转发处理单元。

如上所述的系统，在转发处理单元中还可以包括：数据报文报头缓存单元，用于将进入转发处理单元的数据报文进行缓存；直连检查单元，用于判断组播数据报文是否从正确地线路接口进入路由器；组播查表处理单元，与转发表生成单元连接，另一端与组播数据报文仲裁处理单元连接，用于根据转发表的内容，决定该数据报文出路由器的线路接口。

相应地，由于本发明提供了一种路由表表项保活的方法，该方法便于硬件实现，减轻了板级软件的处理负荷；同时该方案减少了从转发处理单元上报到主控单元的数据量。在正常情况下，每一个数据报文都会触发上报主控单元的信息。经过分析，表项超过有效期的情况只占到上报消息的小部分，大量的上报消息都是重复的，本发明的方法只把失效的情况上报给主控单元，对于大量的不失效的表项的消息不进行重复上报。根据测量，本发明所采用的消息机制控制报文过滤的方法使主控单元与转发数据单元间的数据交互的数据量减少了90％，使路由器可以支持高速数据接口。

本发明还提供了一种上述表项保活方法所适用的路由器中组播协议分布实现系统，这种系统将协议中的数据转发功能加以分解，并将协议状态控制功能和组播数据包转发功能分布到路由器的主控单元和转发处理单元中，适于软件与硬件结合的方式实现路由控制，降低了对单个器件性能的依赖，适用于高速路由器接口，达到线速转发的要求。

附图说明

图1是分布式路由器体系结构图；

图2是组播协议分布式实现系统图；

图3是转发表下发处理流程图；

图4是转发单元表项保活KAT处理流程图。

具体实施方式

本发明提供了一种路由表表项的保活处理方法。这种方法包括主控单元向转发处理单元下发路由表过程中的表项保活处理的第一个过程和转发处理单元转发过程中表项保活处理的第二个过程。

在第一个过程中在定期下发的转发表中设置保活计时器的门限值。具体为可以预置一个计时器，用于监视每个转发表的生存期，在每次生成转发表的时候将计时器清零并开始计时，将每一个用于维护路由表表项有效期的保活计时器的门限值设置为预置的保活周期值，组播协议中建议的保活周期值为210秒，因此，此处可以将保活计时器的门限值设置为210秒，计时器在第一个过程中对转发表的生存期进行监视，若判断转发表的生存期一直在预置的生存期的期限内，则维持当前转发表有效，若判断转发表的生存期到达预置的生存期的期限，则需要将这个过期的表删除，并且从主控单元重新将路由表下发到转发处理单元并且根据下发的路由表的内容生成新的转发表，这个将路由表下发到转发处理单元并生成转发表的过程概括称为转发表的下发，新的转发表下发后将计时器清零，重新开始第一个过程的循环。在第一个过程中，预置的用计时器进行监视的转发表的生存期的值并不是唯一的，它可以根据具体情况进行设定，本发明中并不作限制。

在第二个过程中，数据报文到达转发处理单元，转发处理单元获取数据报文到达时的计时器的值和数据报文所对应的路由表项的保活计时器的门限值，其中保活计时器的门限值可以通过查找转发表得到。将数据报文到达时的计时器的值与该数据报文所对应的路由表项的保活计时器的门限值进行大小的比较，可以判断数据报文对应的路由表项是否仍在有效期内。若数据报文到达时的计时器的值已经大于该数据报文所对应的路由表项的保活计时器的门限值，说明表项已经超出有效期，该表项所指示的路由线路已经不能指导该表项所对应的数据报文进行路由，此时应该删除转发表中超出有效期的表项，并且把修改内容上报给主控单元，该表项对应的数据报文也不再进行转发；反之若数据报文到达时的计时器的值不大于该数据报文所对应的路由表项的保活计时器的门限值，则比较结果证明该表项仍然在有效期内，表项所指示的路由线路对于该表项所对应的数据报文仍然有效，此时应该修改此表项的新的保活计时器门限值为数据报文到达转发处理单元时的计时器的值与预置的保活周期的值的和，并可以将仍在有效期的表项对应的数据报文正常转发。第二个过程中，转发处理单元通过对数据报文对应的表项有效期的验证，只将表项失效的情况上报给主控单元，减少了转发处理单元与主控单元之间需要交互的数据量。

由于本发明提供了这种新的表项保活的方法，方法应用保活计时器对表项的有效期进行判断，因而原有的转发表结构应该进行相应的修改，则转发表中应该包括如表1所示的内容，其中：S代表数据报文的源地址；G代表数据报文的组地址；RPF接口表示对于确定的S和G，数据报文应当从那个接口进入路由器；出接口列表表示对于确定的S和G，数据报文应当从哪些接口出去；一个用于表示该表项属于共享树或源树的标志位RPT；用于控制数据平面与控制平面的交互的保活计时器KAT门限值；一个用于表示源树是否成功建立的标志位SPT.接口列表和出接口列表。

S	G	RPF接口	出接口列表	RPT	KAT门限	SPT
							S1	G1	RPF_interface(S1)	inherited_olist(S1，G1)	0	N1	1/0
S2	G2	RPF_interface(RP(G2))	inherited_olist(S2，G2，rpt)	1	N2	1/0
							*	G3	RPF_interface(RP(G3))	Immediate_olist(*，G)	1	N3	-

表1

表中表示了PIM-SM协议中三种类型的路由表项：(S，G)，(S，G，RPT)(^*，G)。

图2所示为组播协议在分布式路由器中分布实现系统图，上半部分1为分布式体系结构路由器的主控单元，下半部分2为分布式体系结构路由器的转发单元，在分布式的路由器的体系结构中，一般主控单元有两个，互为热备份，而转发处理单元的数目可以根据需要进行扩展。

本发明提供了一种上述路由表表项保活方法适用的一种路由器中组播协议分布实现系统，即将组播协议各项功能的实现主要分布于路由器的主控单元1和转发处理单元2。主控单元包括路由表管理子系统3、网管软件子系统4，同时路由器主控单元中还包括路由表控制单元5，用于根据控制消息生成组播路由表并下发给转发处理单元；在转发处理单元中还包括转发表生成单元6，用于根据主控单元下发的路由表内容生成转发表；数据报文仲裁处理单元7，用于对不同数据报文进行处理，并将根据仲裁处理产生控制消息上报到主控单元。

主控单元中的路由表控制单元还可以包括：消息收/发单元8，接收转发处理单元的数据驱动控制消息，接收其他路由器的控制消息，或将本路由器的控制消息发送给其他路由器；控制消息处理单元9，与消息收/发单元连接，用于根据收到的控制消息生成路由表；路由表管理单元10，与路由表控制子系统单元和控制消息处理单元连接，用于将路由表下发到每一个转发处理单元。

如上所述的系统，在转发处理单元中还可以包括：数据报文报头缓存单元11，用于将进入转发处理单元的数据报文进行缓存；直连检查单元12，用于判断组播数据报文是否从正确地线路接口进入路由器；组播查表处理单元13，与转发表生成单元连接，另一端与组播数据报文仲裁处理单元连接，用于根据转发表的内容，决定该数据报文出路由器的线路接口。

本发明提供的组播协议分布实现系统将协议功能分布式实现的原理如下述：

在主控单元中，主控单元的消息收/发单元接收来自转发处理单元的数据驱动控制消息(DDM)，以及来自其他路由器的路由控制消息，也会将本路由器的控制消息发送给其他的路由器，消息收发单元将收到的控制信息传给控制消息处理单元，控制消息处理单元根据接收到的控制消息生成组播路由表，并将生成的路由表发送到路由表管理单元，路由表管理单元的主要作用就是将路由表内容下发到路由器的每一个转发处理单元，在主控单元中用户可以通过网管软件子系统对协议进行控制。

在转发处理单元内，转发表生成单元根据路由表的内容生成转发表，这个过程即上文概括称呼的转发表的下发。这时当有数据报文从B接口进入转发处理单元时，转发处理单元内的数据报文报头缓存单元将到达的数据报文进行缓存。直连检查单元对到达的数据报文进行检查，判断到达的数据报文是否是从正确的接口进入的数据报文，如果判断认为数据报文不是从正确的线路接口进入的，直连检查单元则给数据报文仲裁处理单元发送消息，数据报文仲裁处理单元将会抛弃该数据报文。组播查表处理单元将根据数据报文的属性(这些属性可以包括数据的源地址，组地址，以及进入路由器时所经过的接口信息等)在组播转发表中进行查表，根据转发表中与该数据报文对应的表项，决定该数据报文应从哪些线路接口出路由器。最后，数据报文仲裁处理单元将对对数据报文进行仲裁处理并将路由器表项进行更新，对数据报文的仲裁包括将合法的数据报文根据转发表进行转发，合法数据报文会通过接口C进入路由器内部的交换网络，再经过交换网络到输出接口，数据报文的仲裁还会将非法的数据报文进行抛弃；此时数据报文仲裁单元还可以对转发表项的有效期进行判断，当按照本发明所提供的表项保活方法判断该表项已经失效的时候，则应该将该表项所对应的数据报文抛弃，并将该表项从转发表中删除，同时将转发表的修改内容上报给主控单元；若判断转发表项仍然有效时，则将数据报文转发，并设置新的表项的保活计时器的门限值。转发处理单元的任务就是保证组播数据从合适的线路接口进入路由器，并且决定应从那些线路接口出去。

当然，上述系统和方法中会有多种基于形式的不同变换，如：在转发表项保活处理过程中对数据报文所对应的表项有效性进行的判断也可以在组播查表处理单元中实现，而此时数据报文仲裁处理单元则不对表项的有效性进行判断，而仅根据组播查表处理单元和直连检查单元的消息对数据报文进行处理，同时将生成的控制消息上报给主控单元。与此类似，数据仲裁处理单元中将新生成的控制信息上报给主控单元的功能也可以在之前的组播查表处理单元和直连检查处理单元中实现。

以上对本发明进行了详细论述。但应认识到，所述仅以示意的方式给出了详细描述和具体实例，对于本领域的一般技术人员，本发明的思想和应用范围都显然有各种修改或改进之处，尤其在各模块的定义及所述新方法在系统中的具体实现存在多种方式，因此本说明部分不应理解为对此项发明的限定。

Claims (12)

1.一种路由器中路由表表项保活方法，应用保活计时器KAT在所述路由器的主控单元与转发处理单元间维护路由表项的有效期，其特征在于：

1)在根据所述主控单元向所述转发处理单元定期下发的路由表生成的转发表中设置保活计时器KAT的门限值；

2)转发处理单元接收数据报文，并通过比较所述数据报文的计时器的值及所述数据报文对应转发表项中的KAT的门限值，判断所述数据报文对应的路由表项是否有效；若有效，则更新转发表项，否则更新转发表项和路由表项。

2.如权利要求1所述路由器中路由表表项保活方法，其特征在于步骤1)具体包括：

11)主控单元下发路由表到转发处理单元，转发处理单元根据所述路由表生成转发表；

12)设置保活计时器KAT的门限值；

13)当转发表项的生存期到达预置的时限，返回步骤11)。

3.根据权利要求2所述路由器中路由表表项保活方法，其特征在于：步骤11)与步骤12)之间还要对预置的计时器进行清零。

4.如权利要求1所述路由器中路由表表项保活方法，其特征在于，步骤2)中判断数据报文对应的路由表项是否有效具体为：

21)转发处理单元获取报文到达转发处理单元时的计时器的值；

22)转发处理单元获取数据报文所对应的转发表表项的保活计时器门限值；

23)比较步骤21)中获得的计时器的值与步骤22)中获得的保活计时器门限值的大小，若计时器的值不大于保活计时器门限值则数据报文对应的表项仍在有效期，否则该表项失效。

5.如权利要求1或4所述路由器中路由表表项保活方法，其特征在于，步骤2)中对失效的路由表项所对应的更新转发表项和路由表项处理过程具体为：

24)删除转发表中失效的表项；

25)将转发表的修改内容从转发处理单元上报给主控单元；

26)主控单元根据上报消息对路由表进行修改；

27)丢弃失效的路由表项对应的数据报文。

6.如权利要求1或4所述路由器中路由表表项保活方法，其特征在于，步骤2)中对仍在有效期的路由表项所对应的更新转发表项的处理过程具体为：

28)修改新的保活计时器的门限值为数据报文到达转发处理单元时的计时器的值与KAT的门限值的和；

29)将仍在有效期的路由表项对应的数据报文正常转发。

7.如权利要求1或4所述路由器中路由表表项保活方法，其特征在于，所述的转发表的结构中包括：数据报文的源地址、数据报文的组地址、用于表示该表项属于共享树或源树的标志位、用于控制数据平面与控制平面的交互的保活计时器门限值、用于表示源树是否成功建立的标志位、RPF接口列表和出接口列表。

8.一种如权利要求1所述路由器中路由表表项保活方法所适用的路由器组播协议分布实现系统，该系统在路由器中的主控单元及转发处理单元间用于组播协议主要功能的实现，主控单元包括路由表管理子系统、网管软件子系统，其特征在于：

路由器主控单元中还包括路由表控制单元，用于根据控制消息生成组播路由表并下发给转发处理单元；

转发处理单元中还包括转发表生成单元和数据报文仲裁处理单元，其中：

转发表生成单元，用于根据主控单元下发的路由表内容生成转发表，在所述转发表中设置保活计时器KAT的门限值；

数据报文仲裁处理单元，用于对不同数据报文进行处理，通过比较所述数据报文的计时器的值和所述数据报文对应转发表项中的KAT的门限值，仲裁所述数据报文对应的路由表项是否有效，若有效则产生更新转发表项的控制消息，否则产生更新转发表项和路由表项的控制消息，并将所述控制消息上报到主控单元。

9.如权利要求8所述路由器组播协议分布实现系统，其特征在于主控单元中的路由表控制单元还包括：

消息收/发单元，接收转发处理单元的数据驱动控制消息，接收其他路由器的控制消息，或将本路由器的控制消息发送给其他路由器；

控制消息处理单元，与消息收/发单元连接，用于根据收到的控制消息生成路由表；

路由表管理单元，与路由表控制子系统单元和控制消息处理单元连接，用于将路由表下发到路由器的每一个转发处理单元。

10.如权利要求8或9所述路由器组播协议分布实现系统，其特征在于，转发处理单元中还包括：数据报文报头缓存单元，用于将进入转发处理单元的数据报文进行缓存。

11.如权利要求8或9所述路由器组播协议分布实现系统，其特征在于，转发处理单元中还包括：直连检查单元，用于判断组播数据报文是否从正确的线路接口进入路由器。

12.如权利要求8或9所述路由器组播协议分布实现系统，其特征在于，转发处理单元中还包括：组播查表处理单元，与转发表生成单元连接，另一端与组播数据报文仲裁处理单元连接，根据转发表的内容，决定该数据报文出路由器的线路接口。

Images