在网络分流器中利用TCAM用户空间实现组合规则的算法

DOI：10.16660/j.cnki.1674-098X.2018.07.158

在网络分流器中利用TCAM用户空间实现组合

规则的算法①

高海源

(天津光电通信技术有限公司 天津 300000)

摘 要：网络分流器依据大量的匹配规则集对网络流量进行过滤分流，常用TCAM芯片来存储规则集并对输入流量进行查找匹配，依据命中结果对报文做后续处理。本文针对多条子规则之间形成“与”、“或”等关系的组合规则需求，利用TCAM提供的用户空间来存储关联信息，实现组合规则的匹配过滤算法，以满足匹配性能要求以及规则间关联的灵活需求。关键词：深度报文检测(DPI) TCAM 组合规则 匹配算法中图分类号：TM4 文献标识码：A 文章编号:1674-098X(2018)03(a)-0158-03

用于深度报文检测(DPI)的万兆以太网(10GE)分流器，既要满足每通道10Gbps的线速率，又要支持大规模的匹配规则集，通常使用高性能FPGA加上TCAM芯片才能满足需求。对流量的处理流程通常包括以下步骤：(1)FPGA接入10GE光纤信号，从报文中提取出感兴趣的字段传给TCAM。(2)TCAM中存储着规则集，对提取字段进行匹配判断是否命中某条规则，结果告知FPGA。(3)FPGA根据命中结果，选择命中规则对应的操作，例如从某个端口输出等。

常见的规则有包头匹配和特征串两大类，包头匹配最常见的是对IP五元组匹配，如表1所示。

表中*表示对该字段不关心，实际应用中规则数量可达到10万条以上，并且字段不局限于IP五元组，还可能包含源MAC地址、目的MAC地址、GRE协议封装的IP地址等字段。

另一类对报文载荷进行特征串匹配的规则，如表2所示。其中规则6要对特征串进行全报文匹配，如果匹配算法速度不够快，对分流器的线速率性能有很大挑战。

数;(3)丢弃该报文;(4)从某个端口输出并告警;(5)复制几份从多个端口输出等。命中操作码属于规则内容但不从报文中获得，所以需要在处理流程中能获取操作码，并且操作类型可扩展。

针对以上需求，使用TCAM结构中的固定数据条目较难实现，而且复杂的处理流程也影响FPGA的低延时实现。为此，本文选用TCAM型号为Broadcom公司的NLA12000系列，该款芯片提供和固定条目关联的用户空间，适用于灵活扩展的需要。

2 TCAM空间结构

NLA12000系列TCAM芯片的存储结构如图1。TCAM的存储结构主要由数据空间和用户空间组成。数据空间划分为32个superblock，每个superblock包含4个block，每个block包含512个0b位宽条目。用户空间划分为32个UDA block，每个UDA block的位宽固定用b，所以每个UDA block包含32K个b关联信息。因此对于数据空间共K个可匹配的条目，可映射每个条目到1条b的关联信息，用户空间足够使用。映射的效果是，每次输入字段到TCAM进行查找匹配，如果命中某个条目(即1条子规则)，除了返回该条目的地址外，还附带返回该条目映射的关联信息。将这些返回信息都传递给FPGA，FPGA就能依据关联信息对报文做相应处理。

用户输入的每条组合规则，在算法中先分解为若干条包头匹配或特征串子规则，并指出“与”还是“或”的组合关系；然后将子规则写入TCAM数据空间中，每个条目保存一条子规则。将每个条目映射到用户空间的一条b关联信息，该b信息的格式如表3所示。

关联信息的各字段定义如下：

Action type:命中该条目执行的动作，定义枚举数值：从某个端口输出=1；不输出只递增计数器=2；丢弃该报文

1 规则灵活性需求

在实际应用中，用户需要更加灵活的规则匹配过滤功能，规则之间需要有一定的关联性，可以总结为以下几种。

(1)组合“与”关系：输入的一条组合规则，可以包含一个IP五元组子规则加多个特征串子规则，子规则之间通过“与”关系形成组合规则，即输入报文匹配所有子规则时，才认为命中该组合规则。

(2)组合“或”关系:输入包头规则需要对某个字段进行范围匹配，例如协议类型满足范围关系6≤protocol≤17，由于TCAM每个条目是基于最长前缀匹配(LPM)的，所以范围关系需要拆解成多个TCAM条目的前缀形式，多个条目之间通过“或”关系形成组合规则。

(3)多种命中操作：需要扩展报文命中规则时执行的多种动作，可能包括:(1)从某个端口输出;(2)不输出只递增计

①作者简介:高海源(1984,12—)，男,汉族，天津人，博士，高级工程师，系统工程师，研究方向:网络通信协议及算法。158

科技创新导报 Science and Technology Innovation Herald

信息科学

规则ID123

源IP地址62.38..11192.168.*.**

目的IP地址95.36.78.*192.168.* .**

2018 NO.07Science and Technology Innovation Herald科技创新导报表1 包头匹配中常见的IP五元组规则示例

源端口号目的端口号协议类型命中操作2121Tcp(6)端口1输出* 1122Udp(17)端口2输出22331122Tcp(6)统计计数表2 特征串匹配规则示例

规则ID特征串起始位置特征串命中操作4第41字节www.baidu.com端口4输出5第61字节newDPI_algorithm端口5输出6载荷内任意位置http://统计计数

表3 用户空间b关联信息定义

63-5655-4847-4039-3635-32Action typeOutput portReservedNext entry relationNext entry type

31-0

Next entry offset

数据空间共32个Superblock用户空间共32个UDA blockentry relation!=1时才有效，定义枚举数值：包头匹配规则=1；特征串匹配规则=2。

Next entry offset：下一个条目所要匹配的字段在报文中的偏移位置，用于下次查找匹配流程的提取环节，只有当Next entry relation!=1时才有效。

算法分解完用户输入的组合规则后，求出b关联信息的各字段内容，写入到每个条目映射的b关联信息中，为后续算法流程提供信息。

每个block包含512个0b的条目0b匹配值+0b掩码空间映射32个UDA block每个UDA block包含32K个bb关联信息0b匹配值+0b掩码32个Superblock每个Supperblock包含4个block512个0b条目0b匹配值+0b掩码512个0b条目512个0b条目0b匹配值+0b掩码图1 TCAM芯片数据空间和用户空间的存储结构

输入网络流量提取报文头部包含IP五元组的0b数据发送0b3 FPGA及TCAM算法流程

结合TCAM的查找匹配功能，以及算法填入的关联信息，设计FPGA和TCAM协作处理网络流量的算法流程，如图2。

FPGA每收到1个报文，提取报文头部包含IP五元组的0b信息，将该0b装到一个request消息中发给TCAM

命中得到b关联信息判断Next entry relation“与”关系TCAM对子规则查找匹配发送0b未命中进行查找匹配，固定时钟周期后FPGA收到TCAM的一个response消息，其中包括该次查找是否命中，如果命中的话

发送0b丢弃该报文会一并返回b关联信息。FPGA判断如果未命中，丢弃该报文。如果命中，判断关联信息中的Next entry relation，如果是无组合关系或者“或”组合关系，按照Action type字段执行操作，如果要输出报文按照Output port字段从某端口输出。如果命中，且Next entry relation是“与”组合关系，再判断Next entry type字段，如果是包头匹配规则按照Next entry offset再次从包头提取0b数据，如果是特征串规则按照Next entry offset从载荷中提取0b

判断Next entry type无组合关系“或”关系按Action type执行动作，按Output port输出包头匹配规则特征串规则按照Next entry offset提取包头0b数据按照Next entry offset提取载荷0b数据数据。然后将新提取的0b数据再次送入TCAM，循环下一次匹配流程。

需要指出的是，“或”组合关系近似于TCAM自身的查找匹配逻辑，即TCAM将输入0b数据与数据空间内的所有条目依次判断匹配，如果发现匹配就返回匹配条目的地址。因此算法在分解“或”关系的组合规则时，可以方便地拆解成多条子规则，直接写入TCAM的多个条目。上述一次的匹配流程，在TCAM中查找匹配未命中，等价于多条子规则都未命中，即该“或”关系组合规则未命中，所以后续步骤为丢弃该报文。

实现中要确保FPGA与TCAM芯片之间的带宽比FPGA

图2 FPGA和TCAM算法流程

=3。未来可根据需求扩展。

Output port:命中条目后的输出端口编号，只有当Action type=1时有效。

Reserved: 保留字段，动作类型扩展使用。

Next entry relation:和下一个条目的关系，定义枚举数值：无组合关系=1；和下一个条目是“与”关系=2；和下一个条目是“或”关系=3。

Next entry type:下一个条目的类型，只有当Next

科技创新导报 Science and Technology Innovation Herald

159

科技创新导报2018 NO.07Science and Technology Innovation Herald信息科学

配、或者多个特征串匹配等场景，在确保分流器性能的同时为规则集提供了更大的灵活性。

接入万兆以太网的带宽有一定的富余。因为多次查找匹配的流程，带来访问TCAM的带宽增大。同时也要组合规则总数，以及可包含的子规则数，避免匹配流程循环过多次数。在实际应用中，组合规则总数和子规则数上限通常不会太大，将TCAM带宽定为输入网络带宽的2倍，通常能够支持输入网络流量的线速处理。算法对多条组合规则的合理分解，包括处理好子规则之间的包含-被包含、交叠等关系，也能够化简FPGA和TCAM对报文的处理流程，降低访问TCAM带宽的压力。

参考文献

[1] 刘宗仁.网上内容过滤技术的现状及面临的问题[J].现代

情报,2005(3):74-80.

[2] 何一凡,徐国银,沈海斌.基于CAM/TCAM分组

的Multi-Gigabit速率模式匹配引擎[J].电子器件,2007,30(1):158-161.

[3] 周立力.基于TCAM技术的高速路由查找方案[J].计算机

应用,2003,23(9):17-19.

[4] 李伟男,鄂越鹏,阁敬国,等.多模式匹配算法及硬件实现

[J].软件学报,2006,17(12):2403-2415.

[5] 陈兵,张峰,丁秋林.基于ARM处理器的嵌入式防火墙设

计与实现[J].计算机工程,2009,35(6):197-199.

4 结语

本文设计了一种在网络分流器中支持组合规则的算法。该算法充分利用了TCAM芯片的数据空间与用户空间的匹配映射能力，在用户空间的存储相应的关联信息，以支撑FPGA对输入报文按照组合规则进行匹配过滤。该算法适用于对网络流量进行多层包头的匹配、多个字段的灵活范围匹(上接157页)

MULTICAST MTU:1500 Metric:1

eth4:0 Link encap:Ethernet HWaddr 40:F2:E9:18:37:40

inet addr:192.168.70.252 Bcast:192.168.70.255 Mask:255.255.255.0

UP BROADCAST RUNNING MULTICAST MTU:1500 Metric:1

④测试网络通讯正常。

xcatmn2#ping 192.168.70.100

bytes from 192.168.70.100: icmp_seq=1 ttl= time=0.278 ms2.3 VNC服务配置

（1）在被控端集群管理节点端安装VNC服务端软件，并启动VNC server。

xcatmn2$vncserver ögeometry 1600X1200（2）在监控端办公室微机上，安装VNC的客户端软件VNC viewer。

（3）启动监控端办公室微机上VNC viewer软件，并配置与VNC server端通讯的用户名和密码，进入被控集群管理节点。

2.4 监控集群服务器运行状态

进入被控端2号管理节点的界面后，启动火狐网络浏览器，输入集群刀箱节点的IP地址：https：//192.168.70.20，回车之后，登录到IBM集群管理模块界面。输入管理用户的名称和密码，则进入内部的管理界面，即可以观察到各刀箱上刀片服务器的运行状态。2.5 VNC出现问题解决措施

如果在办公室的监控端无法使用VNC软件，则可以在被控端2号管理节点上停止VNC server进程，然后重新启动VNC server。在办公室重新启动VNC viewer，重新连

接VNC监控端和被控端，即可监控集群节点状况。

xcatmn2$vncserver ökill *202:1

xcatmn2$vncserver ögeometry 1600X1200

3 结语

VNC代表虚拟网络计算，它是一款使用RFB协定的屏幕画面分享及远程操作软件。在实际工作中，通过运用VNC虚拟网络计算技术，可以随时随地远程监控集群服务器运行状态，并及时排除发现的问题，确保了集群服务器系统硬件平台的运行稳定，保障了科研生产任务的顺利开展。

参考文献

[1] 李蔚泽.Red Hat Linux 7.2系统管理[M].北京：清华

大学出版社，2002.

[2] 朱居正.Red Hat Enterprise Linux系统管理[M].北

京：清华大学出版社，2009.

[3] 高俊峰.循序渐进Linux 基础知识 服务器搭建 系统管

理 性能调优 虚拟化与集群应用[M].2版.北京：人民邮电出版社，2016.

160

科技创新导报 Science and Technology Innovation Herald