网络处理器中树搜索引擎协处理器的模拟实现论文.doc

网络处理器中树搜索引擎协处理器的模拟实现

摘 要：
随着网络技术的发展，用户对网络带宽需求和网络节点机功能要求迅速增加，网络处理器作为一种兼具软硬件优点的网络处理设备显示出其优越性。本文主要介绍了网络处理器的大致结构，从软件仿真的角度对其中的一个重要部件树搜索引擎（TSE）组成结构和实现方式进行了比较详细的介绍，本文所作的工作将对网络处理器的算法验证和硬件实现有所帮助。

关键词：
网络处理器，系统结构，树搜索引擎，软件仿真

Abstract：
As network develops rapidly, users have more and more requirements on the bandwidth of the network and the functions of the network nodes. Network processor，having the advantages of both software and hardware solution, shows its power. This thesis mainly studys the architecture of Network Processor and introduce the software simulation of Tree Search Engine (TSE).It is one of the key components of Network Processor. This thesis may be useful in algorithm verification and hardware design of Network Processor.

Keywords：
Network Processor, Architecture, Tree Search Engine, Software-simulation
前 言
随着网络的规模的迅速膨胀，用户对网络的带宽和服务要求的迅速增加，对网络处理的要求也越来越高。
但是，当前的一些实现技术都不能很好满足对应的要求，基于软件的处理方法虽然具有很高的灵活性，但是不断增加的处理速度要求使这种方法很难满足性能要求；基于硬件的专用集成电路（ASIC，Application Specific Integrated Circuit）实现虽然具有很高的性能，但是它不可编程，灵活性很差，当有新的业务要求到达时又不能及时的适应变化。设计人员梦寐以求的是这样一种器件，它即具有很高的性能，又具有更高级的编程能力，这就是网络处理器(Network Processor，NP)。
网络处理器的出现是网络规模的膨胀性增长、用户对带宽需求的急速增加、各种新业务的层出不穷，使得基于软件的业务处理机和基于硬件的专用集成电路都无法胜任新的工作的必然结果。
网络处理器能提供ASIC 的性能和优化，还具有通用处理器的可编程性和灵活性，同时，网络处理器是专门为处理数据包设计的，其性能范围涵盖了客户端的集成化访问设备和驻留网关，及接入外设中的多服务路由器、交换机和运营商的多千兆位路由器。以网络处理器提供的框架结构为开端，工程师能立刻安排新业务和新功能的设计任务，包括远程管理、语音和数据融合、虚拟专用网的安全性、财务结算、以及QoS（服务质量），即产品个性化的更高层次。这一切可使工程师们在与对手竞争时处于领先地位。
本文所介绍的NP设计就是在这个背景下产生的，目的是对网络处理器进行研究和设计，为国内的网络处理器设计做出贡献，而本文所介绍的TSE设计就是该项目的一部分，在后面的文章中会进一步介绍。

目 录
1 问题的提出 1
2 设计方案 4
2.1 网络处理器介绍 4
2.2 微处理引擎和树搜索引擎协处理器介绍 7
2.3 控制存储器介绍 7
2.3.1 控制存贮器(CS)的地址结构 8
2.3.2 对象整形 9
2.4 TSE基础数据定义 10
2.4.1 查找输入参数 11
2.4.2 查找定义表(LUDefTable) 12
2.4.3 空闲链表(Free List) 14
2.4.4 比较定义表（Compare Definition Table） 15
2.4.5 直接表(Direct Table) 17
2.4.6 模式查找控制块（Pattern Search Control Block） 19
2.5 FM树结构 19
2.6 LPM树的结构 20
2.7 SMT树的结构 22
3 实现技术 23
3.1 SystemC简介 23
3.2 TSE寄存器及指令说明 24
3.3 FM树的搜索及维护算法实现 25
3.3.1 FM树的查找算法实现 25
3.3.2 FM树的插入算法实现 26
3.3.3 FM树的删除算法实现 26
3.4 LPM树的搜索及维护算法实现 27
3.4.1 LPM树的查找算法实现 27
3.4.2 LPM树的插入算法实现 28
3.4.3 LPM树的删除算法实现 30
3.5 SMT树的搜索及维护算法实现 31
3.5.1 SMT树的查找算法实现 31
3.5.2 SMT树的插入算法实现 32
3.5.3 SMT树的删除算法实现 33
3.6 其它一些问题 34
3.6.1 控制存储器的模拟实现 34
3.6.2 翻译器的实现 34
3.6.3 测试数据 35
4 结束语 35
谢 辞 36
参考文献 37
附 录 38

1 问题的提出
随着网络技术的飞速发展，使用基于软件的通用处理机或者基于硬件的专用集成电路处理网络数据已经不能很好的满足日益增长的网络带宽和服务要求。
人们迫切的要求使用一种新的兼具灵活性和高性能的器件来完成网络数据的处理。这种器件应该具有很高的处理性能和很好的可编程性，以满足用户对带宽的要求和快速的适应新的服务变化，这就是网络处理器(Network Processor，NP)。
网络处理器（Network Processor）是为网络应用而设计的ASIP（Application Specific Instruction Processor ，专用指令集处理器）芯片，它根据网络处理的特点设计了专门的指令集，有的网络处理器设计还有不同种类的协处理器，实现一些通用但复杂的网络处理操作，所以，这种器件不仅具有很高的网络数据的处理性能，也具有很好的可编程性。
人们提出的各种解决网络处理问题的方案，它包括专用集成电路（ASIC）方案、专用指令集网络处理器（NP）方案、使用协处理器结构（Co-Pro）方案、现场可编程门阵列（FPGA）方案以及通用处理器（GPP）方案等，下图（图 11）显示了当前人们提出的各种解决网络处理问题的方案的灵活性和性能的比较。

48

图 11 各种实现方案的灵活性与性能比较

从图中可以明显的看出，NP在绝大多数网络系统应用中都是一种最好的解决办法，它充分体现了硬件与软件的平衡，并满足了网络发展的所有要求，那就是：
A、 性能—— 通过在硬件中执行关键的可计算核，NP能在线速度下满足许多应用的性能要求，其性能与专用集成电路差别不大；
B、 灵活性—— NP 的软件系统是其重要的系统组成部分，这样通过校正软件，可以很灵活地适应协议标准和应用的变化；
C、 更快的TTM (Time-to-Market) —— 设计软件比设计具有同功能的硬件系统来说，在设计时间与设计售价上都要少很多；
D、 功耗 —— NP可能不被嵌入到能耗敏感的设备中，比如手提设备，因此他们的功耗更多的是考虑售价的原因，比如说封装。

网络处理器（NP）是为网络应用而设计的一种专用指令集处理器芯片。它根据网络处理的特点设计了专门的指令集，有的网络处理器设计还有不同种类的协处理器，实现一些通用但复杂的网络处理操作。这种器件具有很高的网络数据的处理性能和良好的可编程性，既可以满足不断增长的网络处理要求，又可以通过对NP的编程实现新的服务，快速的适应新的服务要求。
根据网络处理器设计者的设计思想与目的的不同，目前有如下几类NP：
A、适用于网络边缘的处理器，设计这类NP 的公司主要有：Alchemy, Infineon, Broadcom 等；
B、主要用于流量管理的NP：设计这类NP 的公司主要有：Acorn Networks, Lucent,Conexant 等；
C、专用于分组处理的NP：设计这类NP 的公司主要有：IBM, Intel, MMC, Xstream等；
D、适用于安全管理的NP：Philips, Chrysalis-ITC 等；
E、专用于分组分类的NP：Solidum, PMC-Sierra 等。

根据网络处理器的体系结构类型的不同，可以将它们分为以下几种：
A、 单处理器核：基于通用RISC 结构，这种结构集成有各种网络接口，有时还设计有专用协处理器如流量管理器、分类器等。
B、可编程的状态机：配置上硬件加速器的RISC 结构，这种结构主要用于分组分类。
C、并行处理：网络专用处理器，这种结构是专门重新设计的具有大规模并行流水线处理功能单元的NP。其采用的结构有多处理器方案、VLIW、multithread...等。

NP 的出现已极大地改变了网络设备的体系结构，它已是新一代网络路由器与交换机的核心器件之一，由此决定了NP 不但有极大的商机，而且将对国家信息基础设施的安全性产生重要的影响。中国作为一个巨大的信息产业市场，不能轻易让出这个商机，同时作为国家安全的需要，也迫使我们设计并使用自己的NP。
当前国内对这方面的研究比较少，本文所介绍的NP设计以及其中的一个重要的部件——树搜索引擎（TSE）就是来自一个NP的研究项目，希望本文的工作能为以后网络处理器的研究和设计提供一些帮助。在本文的后面，将对网络处理器的体系结构和TSE的软件仿真作进一步的叙述。
本次所设计的这款网络处理器是一款专用于分组处理的网络处理器，它采用的是配置了硬件加速器（即协处理器）的RISC芯片的结构。它包括入口处理单元、出口处理单元和核心处理单元等几个部分。其中，入口处理单元和出口处理单元主要完成物理接口及相应的一些简单功能，核心处理单元主要通过其中的MIPS指令集的RISC核和相应的硬件加速单元通过软件完成一些更加复杂的操作，核心处理单元正是该网络处理器的可编程性的主要体现者。
本文所讲述的树搜索引擎（Tree Search Engine, TSE）就是分属于核心处理单元（Kennel Processing Engine，KPG）的一个协处理器，即硬件加速器。TSE协处理器是KPG中的一种非常重要的组成部件，本文所作的主要就是该部件的仿真工作，在后面的文字中将进行进一步的说明。
2 设计方案
2.1 网络处理器介绍
在本文所涉及的这款NP中，KPG共包含8个双处理单元（Double Processor Unit, DPU），每个DPU中包含两个PE(Processing Engine，PE)和10个协处理器。这10个协处理器分为计数、校验、策略、数据存储、串拷贝、信号量、入队、命令仲裁和树搜索引擎(Tree Search Engine，TSE )等多种，这10个协处理器中有两个是TSE协处理器，TSE与PE一一对应，其余的8个协处理器可以被两个PE共享。另外，在DPU的外部还有计数管理器、完成单元以及信号量管理器等多个管理单元用于协调各个DPU内部的PE和协处理器，完成所需要的操作。
在每个PE上可以运行两个线程，故在每个DPU上可运行4个线程，任何时候每个DPU中最多只有两个线程在同时运行。每个DPU中的四个线程与其中的四个相互独立的容量为1K Bytes的共享存储池（Shared Memory Pool ，SMP）一一对应。在每个TSE看来，它只为一个PE服务，可以控制两个SMP ，对应与两个不同的线程。同时，TSE还连接了一个控制存储仲裁器（Control Store Arbiter，CSA），各个TSE通过它对控制存储器（Control Store）进行管理，使用控制存储器实现各种查找结构的存储并完成各项搜索工作。这几个部分的关系如下页图（图 21）所示：

图 21 TSE与其它部分接口

2.2 微处理引擎和树搜索引擎协处理器介绍
在这款网络处理器中，微处理引擎（Processing Engine ，PE) 是它的核心部件之一。微处理引擎是一个采用裁减了的MIPS指令集的RISC处理器，运行在该部件上的微码在加上相应的协处理指令可以用于实现各种功能。在PE上运行的线程可以分为三种类型：GDH、GTH、GPH。在KPG中运行的32个线程中，有两个是GPH线程，专用于与外部的控制层面的通用处理器通信；有一个是GTH线程，专用于完成对CS中的搜索树结构的维护和管理；其余的都是专用于处理数据分组的GDH线程，处理大量的数据分组。
微处理引擎可向各种协处理单元发送协处理命令，由它们完成一些常用但复杂的网络处理操作，协处理器返回操作的结果供PE使用。
在网络数据处理中，查找是一个非常重要的操作，在很多应用中都要用到。树搜索引擎协处理器（Tree Search Engine，TSE）就是为了加速网络处理器中的查找而专门设计的一个处理单元。该部件管理处理中所需要的各种表格和数据，根据PE发来的命令对这些表格进行维护和查找，返回相应的结果，供PE使用以加速处理过程。TSE是网络处理器中一个非常关键的部件，它的设计的优劣，直接关系到网络处理器的性能。
在这款网络处理器中，TSE主要实现全匹配（FM）、最长前缀匹配（LPM）、软件管理树（SMT）等三种查找树管理与搜索机制，同时还提供控制存贮器的(CS)访问接口以及对该存储模块的管理等功能。
2.3 控制存储器介绍
控制存储器是本文所涉及的网络处理器中专用于存放查找结构的一个存储单元，它可以是片内的或者片外的(片内H0、H1，片外Z0、D0-D3)。这些查找结构由运行在PE上的微代码来进行管理。由于存贮管理直接关系到树的结构及表查找算法，所以在这里首先加以介绍。
2.3.1 控制存贮器(CS)的地址结构
在本文所涉及的网络处理器中，控制存储器的地址空间是26位，包括了存贮器号（memID）、块号（BankID）及偏移量（Offset）三部分，具体结构见下表（表 21），TSE按照这种方式对CS进行访问。
控制存贮器的26位地址
4位
2位
20位
存贮器号
块号
偏移量
表 21 CS 地址结构

在本设计中，CS的不同的地址范围，分别使用不同的存储器类型，用于完成不同的操作，下表(表 22)给出了TSE可以直接访问的部分地址空间及相应的存储器类型和用法。
表 22 CS地址映射
存贮器号
块号
名称
类型
偏移量
用法
0001
00
Z0
外部 36 位ZBT SRAM
19~20
快速的 PSCB
0010
00
H0
内部128位SRAM
11
快速的叶子结点
01
H1
内部36位SRAM
11
快速的内部 SRAM
1000-1010
00-11
D0 A-D
DDR DRAM
18~20
叶结点
1011
00-11
D3 A-D
同上
同上
DT、 PSCB 表项
1100-1111
00-11
D6 A-D
同上
同上
外部存储器
2.3.2 对象整形
我们引入一个称为对象整形的概念，即为每个存储在CS中的数据对象定义一个形状(Object Shapes)，或者说 高度和宽度（Height and Width），用以说明在CS中该对象的存放形式。这样，在PE上运行的微代码看来，每个对象是一个整体，在读取时只需给出该对象的形状即可，存储器会给出相应的数据。
形状主要说明了叶节点、PSCB等在控制存贮中的陈列方式。叶节点中包含了作为关键字的数据，这些数据是和具体应用相关的，它的大小及使用情况在查找定义表（Lookup Definition Table，LUDefTable ，详见后面的说明）中进行定义。形状包括高度和宽度两个参数，对于可以放在一个存储单元中的较小的，也就是不需要考虑跨越多块存贮的数据对象，认为它的高度和宽度都为1，表示为(1, 1)，如32位和48位的数据在字长为64位的存储体中的形状就为（1，1）。但对于较大的数据块就需要使用其它的形状定义。
当控制存储器的存储块的字长小于数据对象长度时，就需要使用宽度或高度大于1的形状，下面是对形状的一些说明：
A：存贮高度指用来存放数据的连续地址空间数目。如对于高度为4的控制存贮A包括了A、A+1、A+2、A+3四块地址空间；
B：存贮宽度指用来存放数据的RAM块的数目。在连续的RAM块中存贮数据，对于(3, 1)的存贮形式，数据跨越了三块连续的RAM。ZBT SRAM和内部的SRAM的宽度只能为1，DDR DRAM 中的数据宽度可以大于1。
C：偏移量的增加可能导致地址跨越RAM块地址，这在CS中是不能支持的，所以查找表算法应该避免这一操作。
D：对于不同的高度和宽度，硬件可以自动读取相应的存贮单元，从微指令的角度来说，数据对象的访问是具有原子性的。在访问高度或宽度大于1的RAM数据时，其它的请求将会被屏蔽。
2.4 TSE基础数据定义
TSE使用查找树来存贮和检索信息。在这款网络处理器中，表格是以Patricia树或者它的扩展形式进行存贮的。所需的查找结果信息位于该树的叶子节点上，整个查找树及其控制结构存放在控制存贮器（CS）中。树的检索、插入、删除等操作都是根据关键字的值来进行的，例如MAC源地址或者IP源地址和目标地址。叶子结点中存放了作为索引的关键字值以及其它一些用户信息。
为了定位一个叶节点，查找算法首先对输入的关键字进行哈希操作，然后根据得到的哈希值计算相应的直接表入口，接着查找算法遍历挂在该直接表表项上的查找树，找到相应的叶子结点。
直接表的使用，大大提高了检索的效率，但同时也意味着存储查找结构的存储空间的增加，这是在存储空间和查找效率之间的一种折中。
TSE提供三种查找树结构：全匹配 (FM)、最长前缀匹配 (LPM)和软件管理树(SMT)。
FM和LPM树为Patricia树，当一个叶子结点被找到时，该结点就是唯一候选项。在查找的最后，还要进行一个称为Compare-at-End的操作，将输入的关键字与存放在叶子中的关键字进行比较以确定查找到的叶子是否与输入的关键字匹配，如果比较成功则返回成功标志OK，否则返回失败标志KO。
SMT树的结构类似于FM树，只是SMT树的一个叶子处存放的可能是一个叶子结点或者叶子结点的链表。当一个叶子被找到时，所有链在该叶子处的链表上的叶子结点中的关键字会逐一与输入的关键字比较，直到比较成功或者链表上的叶子全部被访问，若比较成功则返回成功标志OK，否则返回失败标志KO。
2.4.1 查找输入参数
下表 （表 23） 给出了进行各种查找时的输入参数。
表 23 查找输入参数
参数
长度（位）
描述
Key
192
关键字必须存贮在共享内存池中。所有的192位也都必须准确地存贮，对于不足192位的数据，其它位必须设置为0。
Key Length
8
包含了关键字长度减1的值。
LUDefIndex
8
指向LUDefTable的入口索引。
TSEDPA
4
线程共享内存池地址。存贮了包括关键字、关键字长度、颜色和叶节点位置。TSEDPA为线程的共享内存池高4位。
LCBANr
1
查找结果由TSEDPA定义，存贮在TSRx（TSR，查询结果寄存器，x=0,1,2,3）中，叶节点地址由LCBANr中定义的被存贮在LCBA0和LCBA1（LCBA，TSE内部寄存器）中。

对于FM和LPM树来说，输入关键字按照在LUDefTable中Hash_type域中定义的哈希算法被转换成哈希值。哈希函数的输出是与输入对应的192位数据，该值被存放于哈希值寄存器中，该寄存器的最低N位被用于计算直接表的索引值。 这里的N值在相应的LUDef Table Entry中定义。
2.4.2 查找定义表(LUDefTable)
查找定义表(LUDefTable)是管理CS和实现各种查找操作的一个关键数据结构，存在于片内。LUDef Table 包含128个表项，可定义了128个不同的树。该表的每一个表项定义了一棵查找树所在的位置(DDR DRAM、ZBT SRAM或片内SRAM)，该树是否Cache使能、关键字和叶节点大小、DT表的位置和大小以及所采用的查找算法等内容。
每一个LUDefTable 的表项都包含了两个指向查找控制块和叶子空闲链表(PSCB_Leaf_FQ)的索引。第一个索引定义了从何处获得查找树的内部结点，亦即该树的PSCB的位置，第二个索引定义了从何处获得该树的叶子结点，亦即该查找树的叶子结点的位置。当进行插入操作时，可以从PSCB_Leaf_FQ中获取存贮空间给树添加结点；当一个结点被删除时，相应的空间被添加入PSCB_Leaf_FQ中。
下表（表 24）给出了每个LUDefTable表项的各个域说明：
表 24 LUDefTable 各域的说明
域
位数
说明
Cascade_entry/cache_entry
1
指明该条目定义的树是否cache 使能，是否是一个重叠树，即如果一棵树是重叠的话，当一个查找在这棵树上失败的话，一个跟在这个条目的后的条目定义的树上的查找会自动开始。也就是说，连续的几个条目存放一棵树，在最后一个重叠使能的条目的该域应为一。
Srch_type
2
定义查找的类型：0：FM，1 ：LPM，2：SMT ，3：保留
Hash_type
4
定义了该树所采用的哈希类型
Color_en
1
该树是否 Color 使能
P1P1_Max_Size
5
定义了P1P2_Pattern 的最大长度（也就是关键字的最大长度,亦即树中叶子节点中的关键字的长度），以半字（16位）为单位，最大192位，
NLA_Rope_en
1
表明了叶子中是否包含了NLA_Rope(一个链接树中所有叶子的链表的指针)
PSCB_FQ_Index
6
一个指向内部的64个空闲链表中的指针，表明了取放PSCB的位置，用于插入和删除操作
DT_Base_Addr
26
Direct Table Base Addr: 用于在MRD和MWR指令中计算最后的地址和查找过程中获得DT表项的入口地址
DT_Size
4
该树的DT表的大小（该值加4 即为DT表地址的位数），
Leaf_FQ_Index
6
叶子空闲链表索引，指明了叶子的存取位置，用于插入删除
Leaf_Width
2
定义叶子的形状
Leaf_Height
3
Dynamic_Leaf_Shape_en
1
指明了树中的叶子是否动态大小使能
Leaf_read_disable
1
当该位为1时,查找只返回叶子的地址而不将结果写入TSRx
LuDef_State
1
用于用户程序测试该条目的当前状态，对查找无影响
LUDef_Invalid
1
当该位为1时，将阻塞任何在该树上进行的查找，当树正被建立或删除时将该位置1
以下至用于GTH指令
RopCLA
26
该树的叶子链表中的当前叶子地址
RopePLA
26
该树的叶子链表中的前一个叶子地址
LeafCnt
26
树中叶子的个数
LeafTh
5
2^LeafTh 为树中叶子个数阀值，当叶子个数大于或等于该值时，就会产生一个0号中断

LUDefTable存放在内部的SRAM中的H1 块的最低640字中（每个表项占用5个字，共128*5=640字）。
2.4.3 空闲链表(Free List)
TSE提供了64个空闲链表控制块，每个控制块的格式如下表（表 25）所示。
每个控制块可以用来定义一个空闲链表, 所以GTH线程可通过TSE中控制总数为64的空闲链表。每个空闲链表通常链接了空闲的PSCB或叶子结点，GTH线程可以通过微指令进行控制它以实现对各种树的维护操作并管理控制存储器。
空闲链表的每一个结点中都存放了一个指向后向结点的指针，各个结点通过这种方式连接在一起。存储在不同的存储块中或者形状不同的数据对象应该存放在不同的空闲链表中。
为了防止存储器的访问瓶颈，当对象存放在SDRAM中时，空闲链表可以通过“sprayed”的方式进行创建和访问。比如说在一次搜索一棵大的LPM树是需要访问5个PSCB，总共需要5次存储器操作，当采用 ”sprayed ” 方式时，这五个PSCB可能就存放在不同的存储体中，这样，虽然访问次数还是5次，但是访问时间将减少很多，从而避免存储器的访问瓶颈。
TSE 提供的64 个空闲链表控制块存放在H1 存储块的紧接着LUDef Table的192个字中（每个3字，总共64*3=192字）。
表 25 空闲链表表项格式
域名
长度
描述
Head
26
该空闲链表的表头在CS 中的地址
Tail
26
该空闲链表的表尾在CS 中的地址
QCnt
26
空闲链表中的对象个数
Threshold
5
2^Threshold 为空闲链表中对象个数阀值，当叶子个数小于或等于该值时，就会产生一个0号中断

2.4.4 比较定义表（Compare Definition Table）
在SMT树中，每个叶子节点中有两个用于比较的模式 ：Pattern0和 Pattern1 ，参与比较的关键字可以被分成不同的域，不同的域采用不同的比较方式。SMT树提供两种比较方式：掩码比较和最大最小值比较。
1、 掩码比较的方式：输入的关键字的某个域通过一个在Pattern1中对应域的定义的掩码与Patter0中的对应域比较，掩码中的某一位是‘1’表示关键字中的相应位应该与Pattern0中的相应位相同，‘0’表示该位会被忽略，不参与比较。只有所有要比较的位均与Pattern0中的值相同时，比较成功，否则失败。
2、 最大最小值比较：在该方式下， 输入关键字的相应域被视为一个整数，TSE会检查该值是否在由Pattern0和Pattern1定义的最小值（Min）和最大值（Max）之间，如果是的话，比较成功，否则失败。
一个可能的输入值及SMT树中叶子节点的结构的形式如下图（图 22）所示 ：

图 22 输入关键字及相应的SMT 树的 Pattern 格式示例
比较定义表中定义了上图所示的各个域及比较方式，表（表 26）显示了比较定义表表项的格式。
表 26 CmopTable 表项格式
域
位置（位）
长度（位）
说明
Range1 Offset(R1_Off)
7:0
8
定义了第一个要比较的域的起始位置，仅最低四位有效，该值乘以16即为该域的起始位置，起始位置只能是16的倍数
Range1 Length(R1_Len)
15:8
8
定义了第一个要比较的域的长度，仅最低四位有效，该值乘以4即为该域的起始位置，长度只能为4的倍数
Range2 Offset(R2_Off)
23:16
8
定义了第二个要比较的域的起始位置，仅最低四位有效，该值乘以16即为该域的起始位置，起始位置只能是16的倍数
Range2 Length(R2_Len)
31:24
8
定义了第二个要比较的域的长度，仅最低四位有效，该值乘以4即为该域的起始位置，长度只能为4的倍数
Range2 Valid(R2_Valid)
32
1
表明第二个域是否有效，0表示的二个域的定义无效，1表示有效
Continue(Cont)
33
1
指明了比较是否从下一个紧跟着的域开始，如果一个关键字中需要比较的域多于两个时，该位应置为1，否则置0

当关键字的某个域在CmopTable中指明时，该域就采用最大最小值比较方式，否则使用掩码比较方式。
若无需最大最小值比较的话，SMT树可转化为FM树，以降低树的复杂度，提高查找效率和减少存储空间。
比较定义表的每个表项占用H1中的一个单元，TSE共提供2^8 =256 个比较定义表项，占用了H1 中紧跟着FreeList 的256个字 ，故H1 Bank 的前640+192+256=1088个字不可用作其他用途。
2.4.5 直接表(Direct Table)
一次查找操作是从读入DT表中的一个DTEntry开始的，读取的地址是根据LUDef Table中定义的查找树的属性计算哈希值的最低N位再加上LUDef Table 中定义的DT_Base_addr 得到的。
一个DTEntry就是相应的查找树的一棵子树的根，它的结构由树的类型决定，各个树DTEntry结构详见后面对树的说明。
FM树的存储形式是Patricia树，LPM和SMT采用的是Patricia树的扩展形式。DT表的使用，在很大程度上减少查询时间(访问PSCB的时间)，直接表的大小的选取是在存贮空间和查找性能上的一个折衷。
当一个DTEntry上只有一个叶子结点时，它只包含一个指向该叶子结点的指针，如果该DTEntry上有多个叶子结点，它就包含了一个查找树子树的根，当DTEntry为空时，它不存在叶节点的信息。
下图（图 23）表示了使用直接表示的效率：

图 23 直接表的结构

2.4.6 模式查找控制块（Pattern Search Control Block）
模式查找控制块(PSCB)是TSE中的一个重要的数据结构，它用于构成一棵树的中间结点。
当读入的DTEntry为非空且不是包含一个叶子结点时，就需要遍历一个或多个PSCB块，直到找到一个合适的叶子结点。PSCB代表了树的叶子结点或者两个分支的起始位置，在PSCB中存储了一个称为NBT的域，表明了下一步要测试的一位的位置，0和1分别代表了两个分支。当访问到一个PSCB时，关键字NBT域以前的位都是相同的。这样，只有在叶结点中的关键字不同的地方才能插入PSCB。Patricia树的使用，使查找算法的性能主要取决于PSCB的层次亦即树中叶子的个数，而与关键字的长度无关。
2.5 FM树结构
完全匹配(Full Match，FM)树提供了对关键字为固定长度的表格查找机制，它要求查找所得到的叶子节点中的关键字总是与输入的关键字完全匹配，可用在需要完全匹配的场合，例如关键字固定为6个字节的2层单播以太网MAC表。因为这种数据结构可以较有效的使用哈希函数，对FM树的查找是非常有效的，而且一般使用多种不同的哈希函数来保证了较低的冲突率。
一个FM树的直接表表项（DTEntry）长度为36位，(表 27)中给出了它的具体格式。
FM树的PSCB和DTEntry结构是相同的，不同的是它包含两个连续的PSCBLines，每个PSCBLine和每个DTEntry完全相同。它包括一个指针，即下一个PSCB地址（Next PSCB Address， NPA)或者叶子控制块地址（Leaf Control Block Address ， LCBA)；它的另外一个域NBT（Next Bit to Test）指明下一步要测试关键字的哪一位，以确定下一步的动作，即遍历两个PSCBLines究竟使用的是哪一个。
表 27 FM 树的和PSCBLine 的格式
定义
成立条件
可否在DTEntry中出现
可否在PSCBLine中出现
格式(2位)
NPA/LCBA(26位)
NBT
(8位)
空DTEntry或PSCBLine
该项既不指向叶子结点也不指向PSCB
是
否
00
0
0
下一PSCB
该项包含一个指向PSCB的指针
是
是
00
NPA
NBT
叶节点动态形状无效
该项包含一个指向叶子结点的指针
是
是
01
LCBA
0
叶节点动态形状有效
该项包含一个指向叶子结点的指针，NBT中包含叶子形状
是
是
01
LCBA
4:0叶子形状

2.6 LPM树的结构
最长前缀匹配树（Longest Prefix Match ， LPM)提供了对变长关键字或变长前缀的查找机制，例如3层IP 路由的前缀表。
每个LPM DTEntry长度为64位，下表（表 28）显示了一个LPM DTEntry的结构。
LPM 树的PSCB和DTEntry结构是相同的，不同的是它包含两个连续的PSCBLines，每个PSCBLine和每个DTEntry完全相同。它包括两个指针，即下一个PSCB地址（Next PSCB Address， NPA)和叶子控制块地址（Leaf Control Block Address ， LCBA)；它的另外一个域NBT（Next Bit to Test）指明下一步要测试关键字的哪一位，以确定下一步的动作，即遍历两个PSCBLines究竟使用的是哪一个。
另外，多余的2位保留作为以后扩展功能之用。某个LPM树的PSCBLine可以使空的，这一点在FM树中是不允许的。
表 28 LPM DTEntry 和 PSCBLine 格式
定义
成立条件
DTEntry中是否有效
PSCBLine中是否有效
格式(2位)
NPA (26位)
NBT (8位)
LCBA
(26位)
保留
(2位)
空DTEntry或PSCBLine
空项目
是
是
00
0
0
0
0
LCBA无效
包含指向PSCB的指针
是
是
01
NPA
NBT
0
0
LCBA有效；NPA/NBT无效
包含指向叶子结点的指针
是
是
10
0
0
LCBA
0
LCBA有效；NPA/NBT有效
包含指向PSCB的指针和叶子的指针
是
是
11
NPA
NBT
LCBA
0

2.7 SMT树的结构
软件管理树（Software Managed Tree， SMT)提供了更为复杂和灵活的查找机制，它允许用户定义查找中比较的范围和方式，以实现更高级的搜索。例如一个包含了IP源地址（IPSA）、IP目标地址（IPDA）、源端口（SrcPort）、目标端口（DesPort）和协议号（Prot）的IP五重过滤表。
SMT树的DTEntry和PSCB 的结构和FM树的相同，具体结构间表（表 27）的说明。
SMT树与FM树不同的地方在于它的一个叶子的位置处可能挂的是一个叶子的链表。只有紧跟在该叶子位置的第一个叶子结点的存贮形式为LUDefTable Entry中所定义的存贮形式，叶子链表中的其它叶子的存贮形式链表中前一个以叶子的NLASMT域指明。NLASMT域的长度为32位，下表（表 29）给出了该域的格式。
还有，与FM树和LPM树不同的是，SMT树允许定义叶子结点的中某个域的范围，比如，源端口可以在100-110之间。当在某个PSCB后找到一个叶节点后，查找算法便执行一个Compare-at-End操作，如果返回OK，则查找停止；如果返回KO并且NLASMT域中为非零，则读入下一个叶节点，继续执行Compare-at-End操作，一直到返回OK或者NLASMT域为零时，并返回一个KO信号为止。
表 29 NLASM