基于网络处理器实现PIM协议及组播数据快速转发.docVIP

基于网络处理器实现PIM协议及组播数据快速转发摘 要：本文提出了在网络处理器Intel IXA IXP2XXX中PIM-SM组播路由协议高效实现方法。将PIM-SM 协议规范中涉及数据转发的操作加以分解，并将它们分布于转发引擎和主控引擎，微引擎转发数据包仅需一次查表，与控制平面尽量隔离，实现了组播包的高速转发。关键词：PIM-SM；网络处理器；微引擎Achieving PIM and Line-rate Forward Ability based on NP(Network Processor) Abstract:This paper presents an efficient implementation of PIM-SM in Network Processor IXP2XXX. It decomposes forwarding functions in PIM-SM specification and distributes them in main controller and forwarding engine. The forwarding hardwareMicroengine only needs one lookup to forward packet and forwarding behavior is isolated with the control panel. The forwarding speed can get line rate.Key words:PIM-SM；Network Processor；Microengine1 引言网络设备的基本功能是实现网络通信业务流的控制和转发，处于网络边缘的设备需要将来自不同物理链路的各种业务流复用到统一的传输链路上，传统的方法是在网络边缘设备上采用通用的处理器来完成协议栈处理、路由选择以及包头的剥离等功能。随着网络规模和性能迅速增长以及新业务接连不断出现，要求网络设备具有线速和智能的处理能力。能否实现线速转发是网络设备组播性能的重要检验指标，也是长期困扰组播应用的一个关键问题。于是用专用芯片完成包的处理成为一种趋势，网络处理器（NP，Network Processor）就是在这样的背景下诞生的。网络处理器是新一代用来执行数据处理和转发的高速可编程处理器，与传统的处理器不同，它的设计采用了全新的理念，使其既有ASIC(Application Specific Integrated Circuit，专用集成电路)的高速处理能力，又有完全的可编程特性。网络处理器设计的关键技术主要有快速表查找、提供高容量的存贮器带宽、处理器的可编程性能和软件开发环境，以及如何有效地利用多处理器机制实现并行化处理，这些都为组播的线速转发提供了保证。本文提及的NP采用Intel IX架构的IXP2XXX系列网络处理器。PIM-SM实现了RFC1112提出的ASM组播服务模型,具有非常强大的分发功能,是目前应用比较广泛的域内组播路由协议。它采用的是由接收者发起的加入模型,通过建立组播转发树实现组播数据的转发。从其协议的实现行为来看, PIM-SM可以分为协议控制引擎和数据转发引擎两大部分。其中控制引擎用来处理相关的协议报文,包括PIM报文、MLD报文、网管命令等,从而对组播树状态信息进行维护和更新，保证协议的正确运行。数据引擎则通过由控制引擎生成的组播转发表项进行组播数据的转发。与一般的单播路由协议有所不同, PIM-SM的控制引擎和数据引擎难以清楚的分离,它的很多协议行为需要靠数据进行驱动,如Assert过程、SPT树切换及KAT定时器等。因此数据引擎还必须对能够驱动协议行为的数据报文进行特别的处理,并通过特殊的方式和控制引擎进行交互,这导致了组播数据转发的复杂和低效。做为IP网络的骨干节点，要求以线速进行包转发，这就势必要求用硬件实现数据转发功能，NP无疑有其不可替代的优势。2 方案的提出2.1 传统解决方案的缺点协议报文数据报文伪消息更新转发表PIM控制引擎网络通信模块内核模块（转发引擎）路由表 MRIB转发数据图 1传统PIM-SM组播实现结构框图传统路由器在实现PIM-SM协议时大都采用在实时操作系统内核中嵌入相应转发引擎的方式来实现数据的转发，这种转发引擎大多采用Cache维护包括源地址、组地址、出接口列表等信息的转发表项，数据报文则是通过Socket方式接收到后查询相应的转发表项,如果发现匹配的表项则在该表项中的每一个出接口都转发一次;反之则进一步判断是否是能够驱动协议行为的数据包;如果不是,则丢弃该数据包;如果是,则生成事先约定好的伪消息发送到控制引擎,随后控制引擎对该消息进行相应的处理并对组播路由信息表MRIB进行更新,并通过进程间通信的方式对内核中的转发表项进行修改。其实现结构框图如图1所示。可以看出,在传统的PIM-SM实现机制中,完全依靠软件方式实现数据转发。控制引擎和转发引擎采用进程间通信方式交互效率低下,转发性能受到处理器处理能力、调度算法、数据流量等诸多因素的影响,难以得到提高。2.2 新方案的提出随着组播应用的广泛开展,对支持高性能组播的路由器的需求日趋迫切。近年来,人们提出了许多方法来提高路由器的转发性能,如改造路由表组织结构、采用Cache转发、数据缓冲队列、零拷贝转发等。这些方法的主体思想仍旧是采用软件方式实现。在实际应用中发现,只能较低程度而难以大规模的提高转发速率。解决转发性能瓶颈的关键在于尽可能地减少数据包的处理时间,只有依靠NP的高性能网络数据处理能力才能实现高速的数据包处理。3 硬件转发方案IXP2XXX解决方案3.1 方案介绍在传统的网络设备，比如路由器中，通过内核处理来处理每个数据包，又加上大量的定时器处理操作。这大大增加了系统开销从而造成了处理效率的低下,难以实现数据转发的高速处理，而且利用软件查找转发表项也是转发性能低下的一个关键原因。利用NP实现就可以摈弃这些缺陷，由于NP微引擎的完全可编程特性，通过采用不同的编程模型以及相应的协议、算法，在低层硬件设备的支持下，完全可以实现许多复杂的网络处理功能，如PIM-SM中对一些控制数据包的复杂处理等，而且具有很好的功能灵活性。3.2系统结构和设计原理PIM-SM在NP中实现的系统结构如图2所示：主控部分运行控制消息的接收、处理、组播树状态的维护和控制消息的发送等功能。它对控制消息进行相应的处理并根据协议规范触发组播树状态信息集（TIB）的变化以及其它信息集的维护并产生相关动作，比如接收Join/Prune协议数据包，根据其内路由表管理子系统网管软件子系统组播路由表控制消息处理消息接收/发送其它控制消息PIM-SM数据驱动控制消息（DDM）组播转发表组播查表组播报文总裁处理报头报文缓存单元分类检查转发引擎主控图2 PIM-SM 组播协议实现体系结构容生成或更新组播状态表，从而触发组播转发表的更新，同时向上游节点发送相应的Join/Prune协议数据包，从而实现整个组播共享树的更新或维护等。转发引擎则根据主控部分下发的组播转发表转发组播数据包，并且在必要时向主控上报数据驱动控制消息，以触发协议体的相关动作和状态变化。本文将重点讨论PIM-SM组播包高速转发的实现的相关问题，PIM-SM 协议控制包及其它协议包的处理见文献 13等。系统实现的基本原则是：PIM-SM协议控制平面与数据平面（转发）尽量独立，交互的信息量和频度尽量小；利用NP的微引擎的高速处理能力实现组播包的转发，尽量减少查表次数，缩短查表所需的指令周期，提高查表效率；功能符合协议规范，组播树状态信息与转发表状态应尽可能保持同步。3.3 PIM-SM的转发过程分析与功能分解PIM-SM数据包的转发过程涉及的条件判断与当前TIB树的状态机及其函数相关，为达到快速转发的目的，需要将TIB与转发过程相关的状态和状态函数的结果下发到转发模块，以便转发模块直接确定出接口列表oiflist或触发相关的动作；另外，转发过程也可能触发必须反映到控制平面的相关动作，如重置KAT（S,G）、Update_SPTbit(S,G,iif)、 发送Assert消息等，因此，需要由转发引擎构造PIM-SM数据驱动控制消息（DDM）适时上报主控模块，以便主控模块完成相应的动作。PIM-SM数据包转发过程1的功能可以如下分解：其伪代码中“ ”部分（由F*作为标识）由转发引擎完成，“ ”部分（由Z*作为标识）由主控完成（进行计算下发至转发表或根据DDM 完成的相应动作），“ ”部分（由B*标识）功能需要进一步分解由转发引擎和主控引擎共同协作来完成。在iif（入接口）接收到从源S到目标G的数据包：if( DirectlyConnected(S) = TRUE )F1/判断S是否为跟DR直连的源。set_KeepaliveTimer(S,G)_to Keepalive_Period Z1 /重置KAT（S,G）Update_SPTbit(S,G,iif) B1 /第一个组播数据包从SPT树到达, (S,G) SPTbit 的更新g过程oiflist = NULLif(iif=RPF_interface(S)F2AND UpstreamJPState(S,G) = Joined Z2) /按照（S，G）状态转发oiflist = inherited_olist(S,G)Z3if( oiflist != NULL )F3 restart KeepaliveTimer(S,G)Z1 else if( iif = RPF_interface(RP(G)F4 ANDSPTbit(S,G) = FALSE)NOT F5 /按（*,G）或（*,*,RP）转发oiflist = inherited_olist(S,G,rpt)Z4CheckSwitchToSpt(S,G)B2else /RPF 检查失败if ( SPTbit(S,G) = TRUEF5AND iif is in inherited_olist(S,G)F6 ) send Assert(S,G) on iif Z5/在入接口发Assert(S,G)else if ( SPTbit(S,G) = FALSE NOT F5 ANDiif is in inherited_olist(S,G,rpt) F7send Assert(*,G) on iif Z6/在入接口发Assert(*,G)oiflist = oiflist (-) iif F8forward packet on all interfaces in oiflist F9(S,G) SPTbit 用于区分是根据(*,*,RP)/(*,G)状态还是根据(S,G)状态转发，也就是决定从组播共享树（RPT）转发还是从最短路径树（SPT）转发，而且从SPT切换到RPT需要一个过渡周期，在此周期内从S到G的组播数据包持续从组播共享树上转发，与此同时以源S为目标的最短路径树（SPT）正在建立，在SPT建立起来以前路由器必须仍然只按 (*,*,RP)/(*,G) 状态进行也就是只能在RPT上转发。当一个从S到G的数据包从SPT 树到达, (S,G) SPTbit 的更新过程如下：Update_SPTbit(S,G,iif) if ( iif = RPF_interface(S) F10#数据包沿源树到来AND JoinDesired(S,G) = TRUEAND ( DirectlyConnected(S) = TRUEOR RPF_interface(S)!=RPF_interface(RP(G)OR inherited_olist(S,G,rpt) = NULLOR RPF(S,G) = RPF(*,G) ) )Set SPTbit(S,G) to TRUE在PIM 稀疏模式下,最后一跳路由器向RP 加入共享树。一旦组播数据到达最后一跳路由器，它可选择从SPT 接收组播流量，发起从RPT 切换到SPT 的决策函数如下:CheckSwitchToSpt(S,G) if ( pim_include(*,G) (-)pim_exclude(S,G)(+)pim_include(S,G) != NULL )F11AND SwitchToSptDesired(S,G) )restart KeepaliveTimer(S,G);其中， F11 表示本地有接收者， 本地接收者集合经集合运算公式得到数学表达式为：pim_include(*,G)(-)pim_exclude(S,G)(+)pim_include(S,G)Z7 ，由主控完成计算，并将判断结果F11 下发至转发表，转发引擎根据其值决定是否上报主控重置KAT（S，G）。主控模块在下发转发表之前可能完成的运算或操作有Z2、Z3、Z4、Z7。转发引擎完成的操作有F1F11。为限制上报主控的PIM-SM 数据驱动控制消息（DDM）的频率，DDM分为两类：DDM1（通知主控完成Z5/Z6/B1）和DDM2（通知主控完成Z1）。主控将KAT（S,G）重置、SPT 与RPT 相互转换等所引起TIB 的变化采用触发方式下发至转发表。为保证线速处理，在具体实现上，按照如下规则处理：1) PIM-SM控制引擎在网络处理器的Xscale Core上实现,转发引擎利用微引擎的可编程能力及高速数据包处理能力来实现。由于Xscale Core的时钟频率也很高，在控制引擎与转发引擎之间的数据交换能力完全可以满足要求。2) 转发表项用CAM和SRAM配合来实现,可以实现对数据结构的高速缓存和快速操作，基本一次查表可得。使得查找时间缩短在纳秒级别。3) 利用微引擎的汇编指令快速判断报文类型并读取数据包源和目的地址信息,协议报文经微引擎识别后上交给主控控制引擎处理。数据报文通过快速查找转发表项后经转发模块直接输出。4) 如果数据报文查找转发表项失败，则将该数据包上交主控模块处理。5) 驱动协议行为的数据报文经过微引擎辨别后仍旧采用伪消息方式通知主控模块,主控模块按照一般的协议报文处理流程来处理该伪消息。6) 主控模块处理协议报文后更新路由表MRIB,然后采用定时触发方式下发到微引擎重新生成转发表项，更新组播转发表。4 转发引擎的设计要保证组播数据的线速转发，转发引擎的设计是关键，包含两部分：组播转发表的设计和组播转发过程的设计。转发表的设计要简洁合理，同时又必须包含必要的有用信息，最关键的是要便于快速查找和便于更新。转发过程则要求快速、准确，同时在所有需要转发的端口上转发组播数据，这就涉及到Packet Copier，而网络处理器也恰好提供了相应的Packet Replication Algorithm，可以快速实现数据包的复制。4.1组播转发表的设计根据功能的要求，组播转发表如表1。表1 组播转发表SS1S2*GG1G2G3RPF-interface(S)RPF-interface(S1)RPF-interface(S2)-RPF-interface(RP(G)-RPF-interface(RP(G2)RPF-interface(RP(G2)Olistinherited_olist(S1,G1)inherited_olist(S2,G2,rpt)inherited_olist(*,G3)RPT011Local_Recv-1/01/0Data_LiveXXX-Data_follow1/0-组播转发表是按照组播转发表项的逻辑数据结构构造的，包含3类表项：1)第一类为组播转发表中的（S,G,RPT=0）类型的表项，用于匹配直接从SPT转发的组播数据包，这类数据包的源地址是组播数据的源发送地址，通过最短路径树SPT转发，其出接口列表（olist）的值由主控模块计算Z3得到，并下发，更新或维护存于SRAM中的组播转发表；Data_Live域表示当有与该组播转发表项匹配的组播数据包到达时，通知主控模块重新设置DDM2(重置KAT（S,G）)消息的最迟响应时刻，其设定值根据PIM-SM协议的相关规定来设置，由转发软件在下发该组播转发表项时计算并写入或更新组播转发表；Data_follow域表示在组播转发表中存在该组播转发表项之后是否有与该表项相匹配的组播数据包通过，初始生成该组播转发表项时将该域置为0，如果有数据包通过则将其置为1。2)第二类为（S,G,RPT=1）类型的表项，这类表项用来匹配通过组播共享树（RPT）转发的特定源的数据包，其olist由主控模块计算Z4得到，下发到转发模块，更新或维护SRAM中的组播转发表；Local_Recv由主控模块计算Z7得到并下发。3)第三类为（*,G,SPT=1）类型的组播转发表项，这一类型的表项用于任意源组播数据的转发，当前两种表项都不能匹配的情况下，通过查找此种类型的组播转发表项来匹配通过RPT转发的组播数据流量，其olist的值由主控模块计算Immediate_olist（*，G）并下发，更新或维护SRAM中的组播转发表。根据PIM-SM协议规范，组播数据包只能通过两种途径转发，组播共享树（RPT）转发和最短路径树（SPT）转发。因此，在组播转发表中，第一类转发表项与第二类转发表项无法共存于组播转发表中，任一时刻只能有一种类型的转发表项有效。当主控模块判断存在（S,G）状态但最短路径树SPT尚未建立（SPTbit为FALSE，即NOT F5）起来时,转发的是（S,G,RPT=1）类型的组播数据包；当主控模块判断存在（S,G）状态并且最短路径树SPT已经建立（SPTbit为TRUE，即F5）起来时，转发的是（S,G,RPT=0）类型的组播数据包；转发第一第二类型的组播数据包时，如果组播转发表中存在相应的（S,G）第一第二类型转发表项时，需要将其覆盖。RPF-interface(S)和 RPF-interface(RP(G)在主控模块下发组播转发表之前根据组播路由信息表（MRIB）求得，得到的结果存进组播转发表。在（S,G,RPT=1）类型表项中同时保存这两项的目的在于：当从组播共享树接收组播数据包的同时，还需要监控是否有组播数据包从最短路径树到达（F10）,如果某时刻监测到RPF(S) OK?U_SPT=1START组播查表：查表条件: 组播包中S，G匹配转发表中的S,G 域输出:SUCC（ 是否成功1/0）RPF-interface（S）RPF-interface(RP(G)olist: 输出列表RPT : 共享1/源0 树Local-Recv : 本地有无接收者1/0Data-Live: 重置KAT 最终期限Data_follow: 是否已有数据通过S直连KAT 处理1iif=RPF_interface(S)且RPT=1YesNoYes息No息Is (S,G) match?Is(*,G) match?Noif olistNULL olistYes,succ=1,查找成功Is SPTbitset?YesRPF(S) OK?NoIS Drop?YesDrop YesException processNoYesKAT处理2olist=olist-iif; 在OLIST所有的接口转发数据包NoRPF(RP(G) OK?Yesif olistNULL olistYes,succ=1,查找成功If Local_Recv = 1KAT处理1YesS directly connect?NoException processDrop YesNoDrop PacketNoU-SPT = 1 or ASSERT-S=1生成DDM1:消息格式为（U-SPT,ASSERT-S,ASSERT-G,iif，组播数据包头信息）将DDM1上报主控模块ENDYesNo图3 组播转发模块处理过程数据包既从RPT到达又从SPT到达，则需要通知主控模块进行Updata_SPTbit（S,G,iif）的处理工作，即B1。4.2 组播转发过程转发模块完成的转发处理过程如图3所示。U-SPT、ASSERT-S、ASSERT-G是在转发过程中用来分别记录是否（1/0）需要通知主控模块执行B1、Z5和Z6操作的标志位。根据RFC PIM-SM协议规范，这3种事件发生概率较小，故DDM1消息不会过于频繁。由于当：(1) S 为直连源; (2)从S 到G 的数据包沿源树到达且有本地接收者；(3)从S 到G 的数据包沿源树到达时，均需重置KAT(S,G)，进行中断和重启定时器的操作。因此，如果每次出现上述情况时均通知主控模块，势必会造成通知的过于频繁，造成时钟中断的过于频繁，占用处理器资源过多以及消息缓冲区溢出从而影响数据包的快速转发，而网络处理器恰好提供了RBUF缓存，通过空闲进程将数据从RBUF中移入DRAM重组得到完整的Packet。RBUF 用于缓存多个需要通知主控模块执行Z1的相应（S,G）项，再利用网络处理器的通用寄存器记录缓冲区内容上报主控模块的最终期限时刻。由于在网络处理器中主要进行组播数据包的快速转发，（1）、（2）的情况较少，当网络处理器微引擎检查发生(1)、(2)情况时，则将（S,G）对直接放入缓冲区（KAT 处理1）。由于第(3)种情况发生的频率过于频繁，必须限制（S,G）项写入缓冲区的次数,减少中断的发生，完成的是KAT 处理2：如果匹配表项的Data_follow=0 , 将该表项Data_follow置1，将(S,G)对写入缓冲区并判断匹配表项的Data-Live（最后上报期限）是否小于时间寄存器中记录的时间，如果小于则将时间寄存器的值置为Data-Live的值，完成定时器的更新。如果定时器时刻到达或缓冲区将满，则将缓冲区中的（S,G）数据加上控制报头生成DDM2上报主控模块, 同时清空缓冲区并将时间寄存器设为最大值（最大值根据PIM-SM协议规范来确定）。5 结论本设计对PIM-SM 协议进行了细致的功能分割；转发模块可采用流水作业，利用网络处理器的高速处理能力和快速可编程能力，仅需一次查表，实现组播数据包的线速转发；解决了转发硬件、转发软件和主控之间速度不匹配以及上报KAT 重置消息的问题。 参考文献1Bill Fenner, Mark Handley, Hugh Holbrook. draft-ietf-pim-sm-v2-new-12.txt INTERNET-DRAFT 20 March 20062 S. Deering, W. Fenner and B. Haberman, “Multicast Listener Discovery (MLD) for IPv6”, RFC 2710, 19993B.Haber