[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN1195279C - 对软件管理树进行模式范围比较的方法、装置和系统 - Google Patents

对软件管理树进行模式范围比较的方法、装置和系统 Download PDF

Info

Publication number
CN1195279C
CN1195279C CNB011162147A CN01116214A CN1195279C CN 1195279 C CN1195279 C CN 1195279C CN B011162147 A CNB011162147 A CN B011162147A CN 01116214 A CN01116214 A CN 01116214A CN 1195279 C CN1195279 C CN 1195279C
Authority
CN
China
Prior art keywords
leaf
search
tree
carry out
model domain
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CNB011162147A
Other languages
English (en)
Other versions
CN1316708A (zh
Inventor
让·路易斯·卡尔维格纳
马尔科·C·赫兹
克拉克·德布斯·杰弗里斯
皮尤什·邱尼拉尔·帕特尔
马克·安托尼·里纳尔迪
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of CN1316708A publication Critical patent/CN1316708A/zh
Application granted granted Critical
Publication of CN1195279C publication Critical patent/CN1195279C/zh
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/742—Route cache; Operation thereof
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9027—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • Y10S707/99936—Pattern matching access
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99937—Sorting

Landscapes

  • Engineering & Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Computational Linguistics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Computer And Data Communications (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

一种对软件管理树进行模式范围比较的方法、装置和系统。该搜索机制不需要前一指针上的存储而是只使用一个前向指针以及下一个或下一组要检查的位，从而减少用于各节点的存储空间。该搜索机制在不必多次搜索并允许链接不同的过滤规则下为应用处理多个过滤规则。在每个叶子中存储长度相同的二个模式以定义范围比较。最后比较是按范围或者按屏蔽的比较中的一种。

Description

对软件管理树进行模式范围比较的方法、装置和系统
本申请和下述共同未决、共同转让的专利申请相关并含有共用的公开：“网络处理器处理复合体和方法”，序列号09/384,691，1999年8月27日提交；“用于网络处理器的全匹配(FM)搜索算法实现”，序列号09/543,531；以及“用于网络处理器的最长前缀匹配(LPM)算法实现”，序列号09/544,992。每件共同未决专利申请完整地收录为本说明书的参考资料。
技术领域
本发明一般地涉及模式匹配算法，并且更具体地涉及可在网络处理部件中实现的软件管理树搜索算法。
背景技术
为在媒体速度下支持越来越复杂的任务，需要硬件集成处理，这导致建立网络处理器。通过一组嵌入的可编程协议处理器以及互补的系统协处理器，网络处理器在具有功能灵活性下提供线路速度帧处理和传送能力。期待网络处理器会以微处理器用于当今的个人计算机的方式变为网络的基本网络构件。网络处理器提供多数据流的实时处理，提供增强的安全性并且提供IP包处理和传送能力。另外，它们通过先进的技术，例如并行分布式处理和流水线处理设计，提供速度改进。这些能力可以使有效的搜索引擎成为可能，可提高数据处理吞吐量并对复杂任务提供快速执行。网络处理器的可编程特性对网络产品开发人员在无须新顾客的专用集成电路(ASIC)设计下提供一种更容易的迁移路径来实现新协议和新技术。
网络处理器为因特网或企业网提供者开发互连解决办法提供一种可高定制化、可扩缩的技术。网络处理器为从低端、独立部件到多机柜设备的大范围的解决办法提供基础。通过采用高性能、非阻塞包路由选择交换技术以及专用接口，例如IBM的Data Aligned Serial Link(DASL)接口(该接口可适用于其它工业交换技术)，达到这种定标特性。
作为一种可编程通信集成电路，网络处理器提供非常有效的包分类、对每帧的多表查找、包修改、队列/政策管理以及其它包处理能力。网络管理器把交换引擎、搜索引擎、帧处理器和以太网MAC集成一个部件上以支持要求基于任何协议层上的帧内容的高容量、媒体加权交换帧的顾客的需求。
硬件加速器进行帧传送、帧过滤和帧改变。网络处理器的执行数百条带有复杂的范围及动作规定的规则的能力为过滤能力建立了新的基准，使得基于网络处理器的系统独特地适用于高能力的服务器处理应用。
用网络处理器构筑的典型系统采用分布式软件模型，其中各个可编程网络处理器并发地执行任务。有些功能是在控制点(CP)处理器处进行的，CP可在网络处理器的内部或外部。CP提供对层2和层3的路由选择协议、层4和层5的网络应用以及系统管理的支持。通过网络处理器硬件和常驻皮代码的组合实现线路速度传送和过滤功能。
在由一些互连节点组成的通信网络中，可从一节点向任何另一节点或向网络发送数据。称为路由器的专用节点负责把数据传送到它们的目的地。任何通过通信网络发送的数据包含有关目的地地址的信息，通常作为标题的一部分。每个路由器把该信息或者至少它的一部分和内部存储的地址表比较。若找到所存储的地址和目的地地址之间的匹配，该路由器建立一条通往该目的地节点的路径。取决于网络尺寸和结构，或者把数据直接传送到它们的目的地或者发送到另一个中间路由器。国际标准化组织已颁布一个路由选择标准，在其中路由器存储用于部分地址的路由选择信息。接着路由器把包发送到它的数据库中所具有的最佳匹配部分地址。该ISO标准允许利用给定数量的数字或给定的标题长度建立节点的分层结构。主路由器通过地址的起始部分定址，子路由器通过中间部分，而最终目的地通过地址的最后几位数字。从而，路由器读分配给数据要发送到层次的几位数字就够了。
接收包的路由选择基于伴随的地址串。该地址串充当数据库中的搜索关键字，其中该数据库含有该地址串以及其它有关细节例如在包的递送中哪个路由器是下一个路由器。该数据库被称为路由选择表，而当前路由器和下个路由器之间的链路称为包的前进中的下个跳跃。路由选择表搜索过程取决于地址的结构以及表的组织。例如，长度小于8位并具有非层次结构的搜索关键字应会最高效地在按一系列地址项组织的路由选择表中找到。该搜索关键字应充当表中的索引以定位正确的项。对于较长的搜索关键字，例如32位长，相应的路由选择表可能具有多于10,000的项，把这种数据库组织成简单的表以借助索引直接搜索会浪费大量的存储器空间，因为该表的大部分会是空的。
常规路由器把搜索过程分解为几步。第一步是判定路由器是否直接和目的地主计算机连接。在该情况下，消息离目的地为一次跳跃，并应在该方向上进行路由选择。若目的地计算机不和路由器直接连接，下一步是确定目的地网络的拓朴方向。若从拓朴布局确定方向，则以这种方式为消息选择路由。反之，最后的步骤是沿默认链路为消息确定路由。
典型地，第一步是利用线性搜索通过含有与路由器直接连接的主计算机的32位地址的表进行的。为了反映其局部拓朴，该地址表中的每项和一个直接导向被寻址的计算机的对应输出接口相连接。当路由器接收一目的地地址时，所有的32位和表中的每个目的地地址比较。若找到匹配，通过专用路由器接口把消息直接发送到对应的目的地。
确定目的地网络的方向的第二步通常不是通过对表的线性搜索进行的，因为网络地址会使这种表难以管理和使用。在现有技术中，当地址串遵从网络地址、子网地址和主标识的三层分层时，路由器利用数种周知的技术，例如散列、Patricia树搜索和多级搜索，中的一种进行确定。在散列下，散列函数减小网络的地址部分从而产生小的可管理的索引。散列索引用于检索散列表和搜索匹配的散列项。和散列表的每个散列项对应的是指向对应网络的拓朴方向的输出接口的地址。若在散列网络部分和散列项之间找到匹配，把消息引向对应的接口和目的地网络。
散列法把大量不能管理的字段简化成小的可管理的索引。然而，在这种处理中存在着二个或更多的字段产生相同散列索引的可能。这种情况称为冲突，因为必须把这些字段存储在散列表中的相同位置上。在冲突期间需要进一步搜索以区分这些项。因此，冲突减少利用散列搜索获得的效率，并且在最坏的情况下所有许可的地址简化成单个索引使散列法变成实践上不可使用的搜索过程。
Patricia树搜索避免散列法遇到的冲突。该搜索方法要求在一二进制树中存储所有地址串以及伴随信息，例如有关的路由信息。从地址串内的最高有效位位置开始，该搜索过程逐位地比较地址和树的各节点。匹配的位值引导搜索访问左子节点或者右子节点并且对地址中的下一位重复该过程。搜索时间正比于所存储的最长地址串的长度。在Patricia树搜索中，平均搜索时间和最坏情况搜索时间之间的差异不是非常大。另外，路由选择表是相当有效地组织的。和散列法的路由选择表相比，它需要的存储器较小。Patricia树搜索处理最坏情况搜索优于散列法，但在大多数情况中为定位匹配它需要明显更长的时间。从而，许多常用路由器使用散列和Patricia树搜索的组合。这种组合称为多级搜索。
多级搜索结合散列法和Patricia树搜索。一高速缓存存储一个包含着最近使用的并假定是最常用的路由网络地址的子集的散列表，而Patricia树存储完整的网络地址集。当接收消息时，把目的地地址散列到该表中。若在预定的时间周期内它未被定位，把该地址传送到Patricia树搜索引擎，后者若确保该地址已存储就会找到。
在现有技术中，存在一些周知的树搜索算法，包括固定匹配树、最长前缀匹配树和软件管理树。固定匹配树用于要求准确匹配的定长模式，例如层2以太网MAC表。最长前缀匹配树用于只需要部分匹配的可变长度模式，例如IP子网传送。软件管理树用于用范围或位屏蔽定义的模式，例如过滤规则。通常在树搜索引擎(TSE)的帮助下进行查找。
发明内容
本发明的一个目的是提供一种独特和有效的机制以在无需多级搜索下为应用处理多个过滤规则。
本发明的另一个目的是提供一种搜索机制，其不需要前一指针上的存储而是只使用一个前向指针以及下一个或下一组要检查的位，从而减少用于各节点的存储空间。
本发明说明一种用于软件管理树(SMT)的新颖数据结构，其提供一种建立遵循由控制点定义的搜索机制的树结构的机制。它的一个示例机制应是网际协议(IP)5元组过滤表，包括IP源地址(IPSA)、IP目的地地址(IPDA)、源端口(SP)、目的地端口(DP)和通信协议。和全匹配树或者最长前缀匹配树不同，SMT树能支持范围比较。例如，可利用叶子规定源端口必须在范围x和y中。这种方法允许高效存储和搜索时间下的有效且简单的实现。该方法还允许链接不同的过滤规则。
依据本发明的一个方面，提供一种通过计算机处理部件对软件管理树中的可变长度搜索关键字进行模式范围比较的方法，包括步骤：从一请求应用读作为搜索串的输入关键字；利用搜索关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引，其中每个非空表项含有一个指向搜索树中的下个分支或者一个叶子的指针，其中，N是大于1的整数；确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支；若该指针不指向对应搜索树的叶子，读下个分支内容；当到达对应搜索树的叶子时读叶子内容，并把该叶子的用于定义叶子的内容的范围的第一模式和第二模式与搜索关键字进行比较以判定由该叶子的第一和第二模式定义的范围是否包括该搜索关键字；以及若由该叶子的第一和第二模式定义的范围包括该搜索关键字，把找到的该叶子的内容回送给请求应用。
依据本发明的另一个方面，提供一种用于对软件管理树中的可变长度搜索关键字进行模式范围比较的设备，包括：用于从一请求应用读取作为搜索串的输入关键字的装置；用于利用搜索关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引的装置，其中每个非空表项含有一个对搜索树中的下个分支或对一个叶子的指针，其中，N是大于1的整数；用于确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支的装置；用于在该指针不指向对应搜索树的叶子时读取下个分支内容的装置；用于在到达对应搜索树的叶子时读叶子内容、并把该叶子的用于定义叶子的内容的范围的第一和第二模式和搜索关键字进行比较以判定由该叶子的第一和第二模式规定的范围是否包括该搜索关键字的装置，以及用于在这些叶子模式包括该搜索关键字时把找到的该叶子的内容回送给请求应用的装置。
依据本发明的再一个方面，提供一种在半导体基片上实现的用于对软件管理树中的可变长度搜索关键字进行模式范围比较的系统，包括：一个嵌入式处理器复合体，包括提供帧处理的多个协议处理器和一个内部控制点处理器；多个可对每个协议处理器访问并提供高速模式搜索、数据操作和帧分析的硬件加速器协处理器；多个存储多个表示至少一个搜索树的数据的可编程存储器部件，其中这些数据包括一个直接表、一个模式搜索控制块、一个比较表和一个包括一对要和搜索关键字比较的模式的叶子；以及一个控制存储器仲裁器，其控制每个协议处理器对该多个存储器部件的访问；以及一个和各协议处理器并行操作的以执行包括着存储器读、写和存储器范围检查的树搜索指令的树搜索引擎器，其中所述树搜索引掣器包括：用于从一请求应用读取作为搜索串的输入关键字的装置；用于利用搜索关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引的装置，其中每个非空表项含有一个对搜索树中的下个分支或对一个叶子的指针，其中，N是大于1的整数；用于确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支的装置；用于在该指针不指向对应搜索树的叶子时读取下个分支内容的装置；用于在到达对应搜索树的叶子时读叶子内容、并把该叶子的用于定义叶子的内容的范围的第一和第二模式和搜索关键字进行比较以判定由该叶子的第一和第二模式规定的范围是否包括该搜索关键字的装置，以及用于在这些叶子模式包括该搜索关键字时把找到的该叶子的内容回送给请求应用的装置。
附图说明
通过在连同附图下阅读下述对优选实施例的详细说明可更好地理解本发明，附图是：
图1示出依据本发明的一优选实施例的用于网络处理器的示例体系结构。
图2示出依据本发明的一优选实施例的用于嵌入式处理器复合体的示范实施例。
图3示出依据本发明的一优选实施例的示例协议处理器结构。
图4示出依据本发明的一优选实施例的示例入口处和出口处帧流。
图5示出依据本发明的一优选实施例的用于全匹配搜索算法的树数据结构。
图6示出依据本发明的一优选实施例使用直接表对示例数据结构的作用。
图7示出依据本发明的一优选实施例具有直接叶子对示例数据结构的作用。
图8示出依据本发明的一优选实施例的用于软件管理树(SMT)的输入关键字中的以及叶子模式中的各字段。
图9示出依据本发明的一优选实施例的比较定义表的项的示例格式。
图10示出依据本发明的一优选实施例的软件管理树搜索算法的处理逻辑。
图11示出依据本发明的一优选实施例的一示例查找定义表的内部结构。
图12示出PSCB寄存器的内部格式。
图13示出用于SMT树的固定叶子格式。
图14示出依据本发明的一优选实施例的树搜索引擎的示例体系结构。
具体实施方式
将在其中嵌有本发明的网络处理器的环境下说明本发明。网络处理器10是单芯片上的可编程交换和路由选择系统，在图1中描述它的体系结构。它提供用于10/100以太网、吉位以太网、SONET上的包(POS)的媒体接口并提供用于附着到交换接口上的数据对准串行链路(DASL)。内部硬件加速器提高性能和效率。嵌入式处理器复合体(EPC)12包括多个协议处理器以及一个内部控制点处理器，用于帧处理、配置和管理支持。
可使用多达N个的并行协议处理器。在16个协议处理机的实施例中，可得到16,384字的内部皮代码指令存储和32,768字的外部皮代码指令存储以提供每秒2,128百万条指令(MIPS)的集合处理能力。另外，每个协议处理器访问M个提供高速模式搜索、数据操作、内部芯片管理操作、帧分析和数据预取支持的硬件加速器协处理器。在一优选实施例中用于各协议处理器的控制存储是通过内部和外部存储器提供的：用于立即存取的32K的内部静态随机存取存储器(SRAM)28，用于快速存取的外部零总线往返(ZBT)SRAM30，以及用于大存储要求的外部双数据率(DDR)动态随机存取存储器(DRAM)32。
利用嵌入式硬件加速器以及在相连的控制点处理器34上运行的预处理算法，网络处理器10能在线路速度下通过带有复杂的范围、优先级、动作规定的一百条或更多的过滤规则处理帧。这使得基于网络处理器的系统很适用于网关、服务器处理应用以及对和处理混合业务相关的任务的过滤。
当网络管理员向相干的用户友好接口输入过滤规则时控制点软件提供自动的逻辑检查。利用基于稳定性理论的新颖流控制，在不造成传输控制协议(TCP)失败前提下比通常采用的随机早期放弃法能忍受更高的暂时过预约率。网络处理器10还通过自动地分配带宽，把网路管理员从必须根据瞬间或假定的业务统计预测设立阈值区的作用解脱出来提供有差别的服务。
单个网络服务器10为多达40个的快速以太网端口或者4个吉位以太网端口提供媒体速度交换。还可把它配置成支持OC-48C、OC-48、4个OC-12或16个OC-3端口。对于可扩缩性，可使用二个3.5Gbps的串行DASL连接来互连二个网络处理器以对端口密度翻番，或者和交换结构连接以创造对多达64个网络处理器的交换解决办法。这二个DASL连接，其中一个是主连接另一个是次连接，还可提供对一条冗余交换结构的连接以提高系统可使用性。
如图1中所示网络处理器10的一个示范实施例包括下述主要部分：
1.一个嵌入式处理器复合体(EPC)12，其包括多达16个可编程处理器加若干协处理器；
2.一个入队一离队调度逻辑14，用于从以太网物理层部件移动到交换结构(EDS-入口处)的帧；
3.一个入队一离队调度逻辑16，用于从交换结构移动到以太网物理层部件(EDS-出口处)的帧；
4.入口处交换接口(交换入口处)18和出口处交换接口(交换出口处)20 DASL连接，用于和另一个网络处理器或中间接线器互连；
5.从以太网或POS物理层物件26(PMM-入口处)接收帧的物理MAC多路复用器22以及对以太网或POS物理层部件26(PMM-出口处)发送帧的物理MAC多路复用器24。
图2示出嵌入式处理器复合体的示范实施例。它包括16个协议处理器，提供2128 MIPS的处理能力。每个协议处理器40包括一个3阶段流水线(取、译码和执行)、一组通用寄存器、一组专用寄存器、一个八指令高速缓存、一个专用算述逻辑单元(ALU)以及一组都在133MHz上运行的协处理器。其中二个协议处理器是专用的：一个用于处理导向帧(导向帧处理器)，另一个用于在控制存储器中建立查找数据(类属树处理器)。
图3示出协议处理器的一示范实施例。和每个可编程协议处理器40关联的各协处理器提供下述功能。
1.数据存储协处理器64和帧缓冲存储器42、44(入口和出口方向)接口以提供直接存储器存取(DMA)能力；
2.校验和协处理器62计算标题校验和；
3.入队协处理器66控制对含有关键字帧参数的256位的工作寄存器的访问。该协处理器和完成单元4.6接口以使帧进入交换队列和目标端口队列；
4.接口协处理器对所有协议处理器提供对内部寄存器、计数器和存储器的访问，以进行调试和统计数据收集；
5.串拷贝协处理器使EPC内的数据能有效移动；
6.计数器协处理器为各协议处理器40管理计数器更新；
7.政策协处理器确定流控制信息并且检查和预分配带宽的一致性。
分类器硬件助理48执行帧传送、帧过滤、帧改变和树搜索。网络处理器含有的其它特性包括新的过滤规则处理、散列运算和流控制。
协议处理器40可以执行一百条或更多的带有复杂的范围和动作规定的帧过滤规则。对于网络安全过滤是最基本的，并且分类器硬件助理48提供这些复杂规则组的线路速度执行。根据IP标题信息过滤规则可拒绝或允许帧或者分配服务质量。用来预处理规则的控制点软件自动地改正逻辑错误。在输入逻辑上正确的规则组后，从包标题信息形成关键字并利用网络处理器的软件管理树在线路速度下进行检查。
几何散列函数利用IP标题中的统计结构以胜过理想的随机散列。从而，低冲突率使能在无须附加的分辨搜索下对全匹配表高速查找。
在和各协议处理器的执行并行操作下，树搜索引擎70执行树搜索指令(包括存储器读、写或读一写)、存储器范围检查和非法存储器存取报告。图14示出树搜索引擎的一示范实施例。
在网络处理器10内存在二种系统控制选择。内部处理器34可充当系统的控制点(CP)处理器，或者替代地，可对四个以太网宏中的一个连接一个外部处理器用于初始化和配置。通过建立称为导向帧的专用以太网帧，CP处理器34和这些网络处理器内的其它处理器实体通信。可在DASL连接上把导向帧传送到其它部件，这允许和单个以太网端口连接的一个CP处理器和该子系统内含有的所有网络处理器部件通信并控制它们。每个网络处理器10的内部处理器34还可利用分立的32位PCI总线通信。
网络处理器10通常驻留在子系统板上并提供协议层(即，层2、层3、层4和更高层)帧处理。在CP子系统中的CP处理器34上运行的软件提供管理和路由发现功能。CP代码、各协议处理器上运行的皮代码以及在导向帧处理器上运行的皮代码使该系统能开始进行初始化、维护传送路径和管理系统。作为分布式系统，CP和每个网络处理器子系统包含多个并行操作和利用导向帧通信的处理器，以提高效率和性能。
通过PMM 22接收来自媒体的数据帧并传送到数据存储缓冲器42。在接收过程中PMM还进行CRC校验和帧确认。分配器50把64字节的帧信息发送到可使用的协议处理器40供帧查找。分类器硬件助理48提供识别帧格式的控制数据。协议处理器40利用该控制数据确定要应用的树搜索算法，包括固定匹配树、最长前缀匹配树或软件管理树。
在树搜索引擎(TSE)70的帮助下进行查找。TSE 70执行控制存储器72存取，以使协议处理器40能继续执行。控制存储器72存储皮代码所需的所有的表、计数器以及任何其它数据。为了高效，控制存储器仲裁器52通过在协议处理器40和各种芯片上、芯片外控制存储器选择54之间分配存储器周期管理控制存储器操作。
协议处理器40包括用于数据存储操作的一个主数据缓冲器、一个暂存数据缓冲器和控制寄存器组(集体地，72)。一旦找到匹配，可应用入口处帧改变，例如VLAN标题插入或覆盖。这些改变不通过EPC 12进行。替代地，若设定硬件标志，入口处交换接口硬件18执行改变。通过修改入口处数据存储42中保存的帧内容，可由皮代码和数据存储协处理器64完成其它帧改变。
在把帧发送到交换结构之前，收集控制数据并且用于建立交换标题和帧标题。控制数据包括交换信息例如帧的目的地，以及用于出口处网络处理器的以帮助它进行目的地端口的帧查找、多播或单播操作以及出口处帧改变的信息。
图4示出示例的入口处和出口处帧流。一旦完成，入队协处理器66建立必需的用于把帧排到队列控制块(QCB)中的格式并且把它们传送到完成单元46。完成单元46保证从16个协议处理器40的顶部到各交换结构队列76的帧次序。来自各交换结构队列76的帧分割成带有插入着交换标题和帧标题字节的64字节信元，如由交换结构76按此发送那样。
利用由重组控制块(RCB)80和EDS-出口44提供的信息把从交换结构接收的帧放到出口数据存储缓冲器78中并且入队到EPC 12。通过分配器把帧的一部分发送到任何空闲的协议处理器40以进行帧查找。把帧数据以及来自分类器硬件助理48的数据分配到协议处理器40。分类器硬件助理48利用入口处网络处理器建立的帧控制数据帮助确定供出口处处理的开始指令地址。
出口处树搜索支持和入口处搜索支持的算法相同的算法。用TSE70执行查找，以释放协议处理器40去继续执行。所有的控制存储器操作是由在各处理器复合体之间分配存储器存取的控制存储器仲裁器52管理的。
通过数据存储协处理器64访问出口处帧数据。成功查找的结果包含传送信息并且在某些情况下包含帧改变信息。出口处帧改变可包括VLAN标题删除、生存时间增加(IPX)或减少(IP)、IP标题校验和再计算、以太网帧CRC覆盖和MAC目的地地址或源地址覆盖或者插入。IP标题校验和是由校验和协处理器62准备的，嵌入式处理器复合体12不执行改变而是建立硬件标志，并由PMM出口处硬件24执行改变。一旦完成，利用入队协处理器46建立把帧入到EDS出口处各队列44中的所需格式并且把它们传送到完成单元46。完成单元46保证从16个协议处理器的顶部到馈送出口处以太网MAC的EDS出口处队列的帧次序。最后通过PMM出口处硬件24把完成的帧发送到以太网MAC或POS接口并且离开物理端口。
如图14中所描述的树搜索引擎(TSE)70利用树的概念存储和检索信息。检索即树搜索以及插入和删除是根据关键字完成的，关键字为位模式，例如为MAC源地址或者为IP源地址和IP目的地地址的串接。图5中描述本发明中使用的示例树数据结构。信息存储在称为叶子116、118、120、122的控制块中，叶子至少包含关键字102(所存储的位模式实际上的散列关键字106)。叶子还可包含其它信息，例如老化信息或用户信息，这可以是转发信息例如目标叶子片(blade)和目标端口号码。叶子的格式由皮代码定义；对象被放入到内部或外部控制存储中。
对树的搜索算法对包括着关键字102的各输入参数产生影响，对关键字完成散列104，访问直接表(DT)108，沿树进行模式搜索控制块(PSCB)110、112、114并且结束在叶子116、118、120、122处。每种类型的树具有它自己的搜索算法，从而根据不同的规则发生树查找。例如，对于固定匹配(FM)树，数据结构是Patricia树。当找到一个叶子时，该叶子是可和输入关键字102匹配的唯一可能候选。“最后比较”运算比较输入关键字102和该叶子中存储的模式。这验证该叶子是否真正和输入关键字102匹配。当找到该叶子并且出现匹配时搜索结果为成功(OK)，而在所有其它情况下搜索结果为失败(KO)。
搜索运算的输入包含下述参数：
关键字    必须在搜索或插入/删除之前利用专用皮代码指令建立176位的关键字。只存在一个关键字寄存器。然而，在开始树搜索后，可通过皮代码利用该关键字寄存器建立并发地利用执行该搜索的TSE 70的下个搜索的关键字。这是因为TSE 70散列关键字并且把结果存储到192位的“散列关键字”寄存器106中。
关键字长度    该8位寄存器含有减掉一位的关键字长度。在建立关键字期间通过硬件自动地更新它。
查找定义索引    这是对查找定义表的8位索引，它包含对在其中发生搜索的树的完整定义。图11示出查找定义表的内部结构。
TSRNr    搜索结果可存储在1位的树搜索结果区TSRO或TSR1之一中。这是通过TSRNr规定的。在TSE进行搜索的同时，皮代码可访问另一个TSR以分析前一次搜索的结果。
色彩    对于允许色彩的树(在查找定义表中规定)，在散列运算期间把16位色彩寄存器124的内容插入到关键字中。
对于FM树，如图4中所示，输入的关键字将会散列成散列关键字106。存在几种可使用的固定算法。在查找定义表中规定将使用的算法。
查找定义表是管理树搜索存储器的主结构。查找定义表是一个内部存储器结构并且含有用于建立树的128个项。查找定义表包含用于定义树所存在的物理存储器(例如，DRAM、SRAM、内部RAM)、是否使能高速缓存、关键字和叶子的长度以及要执行的搜索动作类型的各种项。查找定义表是用三个分立的随机存取存储器实现的—一个只能由通用处理器式树处理器(GTH)访问的RAM以及二个彼此完全相同可由所有皮处理器访问的RAM。
散列函数104的输出总是一个176位的数字，其具有在原始输入关键字102和散列函数104的输出之间存在一对一的对应关系的特性。如后面所解释，该特性使从直接表108之后开始的树的深度最小。
若树允许色彩(图4的例子为这种情况)，把16位的彩色寄存器插入到176位散列函数输出中，其结果是一个192位的数，称为“散列关键字106”。在直接表108后面直接出现该插入。若直接表108含有2N个项，在位位置N处插入该16位的彩色值，如图4中所示。在“散列关键字106”寄存器106中存储散列函数的输出和插入的色彩值。若某树不允许色彩，则不修改地取用176位的散列函数，并对散列输出附中16个零以产生192位的最后的“散列关键字”。
可使用色彩以在多个独立的树之间共享单个直接表108。例如，色彩的一种使用可以是MAC源地址(SA)表中的VLAN ID。在这种情况下，输入关键字102会是MAC SA，而色彩124会是VLAN ID(由于VLAN ID为12位，色彩的四个位将不使用，即，置为零)。在散列函数104后，所使用的模式为48+16＝64位。现在色彩是模式的一部分并可区分不同VLAN的MAC地址。
散列函数104定义成使它的输出中的大部分熵位于最高的位组中。“散列关键字”寄存器106的N个最高位用于计算进入直接表(DT)108的索引。
对于SMT树，输入关键字和色彩一起构成一个192位的输入模式。从这个角度，应把色彩寄存器看成是关键字寄存器的延伸。SMT树必须把色彩使能位置成“0”。另外，SMT树必须使用散列函数，该散列函数取176位的输入关键字102以及16位的色彩寄存器124并且生成一个192位的“散列关键字”106，从而关键字形成176个最左侧的位而色彩形成16个最右侧(LSB)的位。这样，用于SMT树的散列函数并不真正是一个散列函数，而是一个把色彩用作为关键字的延伸的装置。
为达到存储以及搜索的高效性，本实现使用下述数据结构：
a.需要搜索的模式/关键字；
b.直接表(DT)项；
c.模式搜索控制块(PSCB)；
d.叶子；
e.最后比较操作；以及
f.比较表项。
DT表是基于关键字的前“N”位的第一地址位置。它包括下面说明的3个部分。PSCB项是中间节点位置。叶子项是搜索结果的地址单元。比较表项说明叶子/模式比较参数。如后面进一步说明那样，DT项或者具有用宽度一和高度一定义的形状或者具有宽度为一高度为二的形状。
PSCB代表树中的分支。在本优选实施例中，存在分支0和分支1。从一PSCB发出的分支数量是一个取决于用于指定分支的位数的变量。若使用n位，则在该PSCB处定义2n条分支。每个PSCB还和一个位位置p相关。从PSCB通过分支0可达到的叶子在位置p处都具有“0”，而通过分支1可达到的叶子在位置p处都具有“1”。另外，从某PSCB可到达的所有叶子具有位0，...，p-1相等的模式，即，这些模式从位置p开始不同。和一PSCB相关的位位置存储在前一个PSCB中或存储在一DT项中并称为NBT(即，要检查的下一位)。PSCB项的格式和DT项的格式相同。在随机存取存储器中实现它。
从而，在树中仅在位模式不同的位置处插入PSCB。这允许有效的搜索操作，因为PSCB的数量以及由此的搜索性能只取决于树中的叶子的数量而和模式的长度无关。PSCB寄存器格式在图12中描述。
在SMT树中，PSCB后面的第一个叶子必须具有在查找定义表中定义的形状。叶子链中的任何其它中具有通过链接指针中的5个位定义的形状，该指针是叶子中的NLASMT字段。
DT项和PSCB项的格式是相同的并且包括下列部分：
a.2位的SCB(搜索控制块)。
b.NPA(下个模式地址)：指向下个PSCB地址或LCBA(叶子控制块地址)：指向叶子/结果。
c.NBT(下一个或下一组要检查的位)：可以是下一对或者一组为“x”(x＝1或n)个的要检查的位。根据存储效率等确定要检查的位的数量。
d.直接叶子。
该实现下的每个项为36位宽并且包含三种可能现行定义的项格式中的一种格式：
a.空DT项：SCB＝00和NPA＝0并且NBT是无效的或为零。
b.NPA/NBT有效：SCB＝00以及NPA和NBT是有效的。对于DT项，NPA指向第一中间节点并且NBT指向要检查的位或位组。在PSCB项的情况下，NPA指向链中的其它节点。
c.LCBA有效：SCB＝01。该LCBA指向一个相关的叶子地址，即，搜索结果。
d.直接叶子：SCB＝10并且该数据的其余部分含有搜索结果或叶子。叶子数据的一部分可包括叶子地址的链接以支持大型搜索结果存储。
对于DT项和PSCB项的存储分配：除了总是包括2**no_of_bits_to_be_tested个的地址即按对/组之外，SMT PSCB的结构和SMT DT项的结构相同。在存储器中相邻地这些地址对或组并且用作为查找搜索树的分支/转移指针。
SMT树中的叶子的格式包括包含着二种模式的控制信息。这二种模式用于定义范围比较。SMT中的叶子可利用NLASMT链接起来。图13示出用于SMT树的格式。当达到PSCB后面的第一个叶子时，进行最后比较操作。当回送OK时，停止搜索。然而，当该最后比较操作回送KO并存在非零的NLASMT字段时，读下个叶子并进行另一次最后比较操作。继续该处理，直至最后比较回送OK或者保存的NLASMT等于零，在后一种情况下该搜索回送KO。
软件管理树搜索的高层算法流程如下：
1.读DT项。
a.若SCB＝00并且NPA和NBT是有效的则读NPA和NBT以生成下个PSCB地址；
b.若NBT无效并且直接叶子有效，读叶子内容并转到叶子评估步骤；
c.若NBT无效和/或不存在叶子，回送KO；即，搜索结果为失败并设置完成标记。
2.叶子评估：比较模式(关键字)和该叶子中存储的模式。SMT永远包含二个模式。这二个模式用于定义范围比较。而且，SMT中的叶子可以链接(即，利用表示下个叶子地址的NLASMT)。当在PSCB后面击中第一个叶子时，进行最后比较操作。当其回送OK(成功)时，在OK下结束搜索。然而，当该最后比较操作回送KO(失败)并且存在非零即有效NLASMT字段时，读下一个叶子并进行另一次最后比较操作。继续该操作，直至最后比较回送OK(成功)或者NLASMT字段不再有效，在后一种情况下搜索回送KO(失败)。
本文中所描述的位/寄存器宽度值是示例性的并可改变为不同的值以优化可使用的存储器、性能要求等等。
搜索从访问直接表108，即从直接表读某DT项开始。用来读该DT项的地址是从寄存器106中的“散列关键字”的N个最高位计算的，如根据查找定义表中定义的树特性那样。DT项可看成是树的根。实际的树数据结构取决于树类型。对SMT树采用扩充的Patricla树数据结构。
图6中示出使用一个8项DT 108的一个例子。可以看出，通过利用DT 108可减少搜索时间，即，必须要访问的PSCB的数量，从而，通过加大DT尺寸，可在存储器使用和搜索性能之间做出折衷。
对于性能原因，读DT项仅查找它含有对某叶子的指针然后又必须读出该叶子本身这是低效的。对于许多DT项可能具有单个叶子的FM，这种情况常常会发生。直接叶子的概念允许在更多存储器使用和更好性能之间进行折衷。
一个树可以启用直接叶子，这一点在查找定义表表中规定。在图7中示出启用直接叶子的树和禁用直接叶子的树之间的差别。当启用直接叶子并且某DT项含有单个叶子时，把该叶子130直接存储在该DT项本身中。反之，该DT项将含有一个对该叶子的指针。
定形是树搜索存储器(TSM)的一个特性并用于规定如何在TSM中存储对象，例如叶子或PSCB。形状是通过参数宽度和高度定义的。对象的高度表示存储该对象的连续地址单元的数量。对象的宽度表示存储该对象的连续存储体(bank)的数量。对于宽度和高度，硬件自动地读适当数量的单元。从皮代码的观点来看，对象是访问的原子单元。对于存储在SRAM中的对象，宽度必须总是为1。以于DRAM中的对象，宽度可能大于1。足够小的适应单个存储器单元的对象被定义为高度为一和宽度为一。禁用直接叶子的DT项的形状总是为(宽度＝1，高度＝1)。当在动态随机存取存储器中存储该DT项时，它准确地占据64位。启用直接叶子的DT项的形状和叶子的形状相同，该形状在查找定义表中规定。通常，这造成DT 108使用更多的存储器。这还使叶子的形状对DT项地址计算造成影响。
在读了一DT项后并假定该DT项不包含直接叶子而且也不是空的，通过在该DT项处开始对该树的查找继续搜索。沿树查找可能通过几个PSCB(模式搜索控制块)，直到到达一个叶子为止。
当在FM树中的搜索期间遇到PSCB时，树搜索引擎硬件70会取决于“散列关键字”的位p的值继续在分支0或分支1上沿树查找。
图10示出本发明的软件管理树搜索算法的处理逻辑。该算法在逻辑框1000以输入关键字开始。在SMT搜索中，随意地可把输入关键字散列成散列关键字。散列函数可颠倒输入关键字中位的次序。例如，它可交换位1和位7。当使用散列函数时，它可以是可编程的，即，可把它编程为交换哪些位。如逻辑框1002中所示，接着读直接表。利用散列关键字的N个高位(其中N是可编程的)检索直接表。当被读的项是空的时，如判定框1004所指示搜索回送KO(未找到)。若在判定框中该项指向一个叶子，则处理在逻辑框1010以读该叶子的内容继续。否则，该项指向一个PSCB并如逻辑框1008中所示读PSCB的适当部分。对于SMT搜索，PSCB可具有FM PSCB的格式。替代地，它可具有更先进的格式如后面所说明那样。
从逻辑框1008处理返回判定框1006以判定是否找到叶子。当在判定框1006中找到叶子时，如逻辑1010所示读该叶子并且接着如逻辑框1012所示和输入关键字比较。若在判定框1014中存在叶子中存储的模式和输入关键字之间的匹配，则搜索回送OK(成功)并且把该叶子的内容传给应用，如结束框1018所示。若在判定框1014中不存在匹配，则如判定框1016中所示处理以判定是否存在下个叶子继续。若在叶子链中存在下个叶子，处理回到逻辑框1010以读该叶子的内容。反之，若不存在下个叶子，搜索回送KO(失败)，如结束框1020所指示。
叶子模式和散列关键字之间的比较操作要比FM搜索和LPM搜索下更为复杂。这种叶子含有二个模式，p1和p2。p1和p2中的散列关键字逻辑上各划分为N个字段。该比较操作包括N个必须都回送OK(成功)的子比较，这样总比较才能回送OK。可以根据二种方式执行每个子比较：(i)p1表示最小值而p2表示最大值，或者(ii)p1表示一个模式而p2表示一个屏蔽。在第一种情况下，当p1≤散列关键字≤p2时该子比较回送OK。在第二种情况下，当(散列关键字“与”p2)＝(p1“与”p2)时该子比较回送OK。可以以编码形式在叶子中存储各字段的定义(每个字段的长度和位置)以及每个字段的比较方式，或者可以在一个专用查找表中存储这些信息。在本优选实施例中，使用比较定义表，在叶子中存储该表的索引。
作为一种扩充，PSCB可含有2b个项，从而来自散列关键字的b个位选择从PSCB读哪个项。这在使用更多存储器的代价下提高性能。另外，还可扩充PSCB从而每个项包括一个或二个(p1和p2)按对叶子比较说明的相同方式操作的的模式。例如，假定PSCB含有长度为L的p1和p2，它们也存储在PSCB中。接着从散列关键字在由NBT给定的位置处取出L个位。把这些L个位说明成是一个整数I。当p1≤I≤p2时，使用来自下个PSCB的项1，反之使用来自下个PSCB的项0。
可使用高速缓存来提高树中的搜索性能。使用高速缓存可在以树为基础下启用查找定义表。在搜索期间，树搜索引擎70首先在高速缓存中检查以判定是否存在和“散列关键字”匹配的叶子。若找到这样的叶子，则返回，无需更多的搜索。若未找到这样的叶子，启动常规搜索。
对于树搜索引擎硬件70，高速缓存查找和常规搜索完全相同。即，把输入关键字散列成“散列关键字”，并进行直接表108访问。直接表108充当一个高速缓存。当高速缓存搜索回送OK(成功)时，搜索结束。反之，树搜索引擎70启动完整树中的第二次搜索-不同的只是不必进行散列操作。“散列关键字”寄存器106的内容被重新使用。
可在查找定义表中规定是否采用高速缓存搜索。若高速缓存搜索使用查找定义表项I并且搜索以KO(失败)结束，自动地利用查找定义表项I+1启动另一次搜索。原理上，这允许链接多次搜索，尽管建议在查找定义表项I+1之下存储完整的树。
树搜索引擎70提供FM树、LPM树和SMT树的硬件搜索操作。对于所有树类型，需要不同数量的软件以初始化和维护树。只有FM树和LPM树具有不必在控制点处理器34的介入下进行叶子的插入和去掉的能力。利用这种特性允许可扩缩的配置并且还具有若需要允许CP34插入或去掉叶子的灵活性。
SMT为CP提供一种建立遵循由CP定义的搜索机制的树结构的机制。其的一个例子应是IP5元过滤表，包含IP源地址(IPSA)、IP目的地地址(IPDA)、源端口、目的地端口和协议。和FM树以及LPM树不同，SMT提供对范围的支持。例如，可利用叶子规定源端口必须在100...110的范围内。
SMT树和FM/LPM树之间存在下述不同：
·SMT永远在叶子中包含二个模式。这二个模式用于定义范围比较，如后面所解释。
·可以利用下个叶子地址(NLASMT)字段链接SMT中的叶子。当命中PSCB后面的第一个叶子时，进行最后比较操作。当它回送OK(成功)时，用OK停止搜索。然而，当其回送KO(失败)并存在非零的NLASMT字段时，读下个叶子并进行另一次最后比较。继续这种处理，直至最后比较回送OK(成功)或者NLASMT字段等于零，在后一情况下搜索回送KO(失败)。
和FM树以及LPM树不同，SMT在每个叶子中含有二个长度相同的模式。出于比较操作的目的，可以逻辑地把输入关键字(以及类似地，把叶子中存储的二个模式)分割成多个字段。在图8中示出一个例子。对于每个字段，可以进行二种比较中的一种：
1.按屏蔽的比较。按叶子模式1中定义的屏蔽，比较输入关键字中的位组和叶子模式0中的位组。屏蔽中的“1”表示输入关键字中的相应位必须和模式0中的相应位相等，屏蔽中的“0”表示输入关键字中的相应位不影响比较。仅当所有的位比较OK，整个字段的比较才OK。
2.按范围的比较。把输入关键字中的位组看成是一个整数并且检查它是否在由Min和Max(二个边界点都在该范围内)给出的范围内。若是这样的情况，该字段比较OK，反之该字段比较KO。仅当所有的字段比较OK，整个最后比较才回送OK，反之最后比较回送KO。
在比较定义表中规定各个逻辑字段是如何定义的，图9中给出一个有关它的项格式的例子。作为默认，借助屏蔽字段比较字段，在比较定义表中存在一个作出其它规定的字段例外。
比较定义表中的每个项规定一个或二个范围比较。如下面所解释，可使用多个项规定多于二个的范围比较。每次范围比较是通过二个参数规定的：
·偏置，它是字段的第一个位的位置。偏置必须在16位的边界处并且可具有如下值：0、16、32、48、64、80、96、112或128。
·按位的字段长度。长度可具有如下值：8、16、24或32。
例如，对于图8中示的关键字，对源端口的按范围的比较应具有置成为64的偏置0和置成为16的最小/最大长度0，而对目的地端口的按范围的比较应具有置成为80的偏置1和置成为16的最小/最大长度1。若需要多于2个的范围比较，必须把继续位置成为1，这使得把比较定义表中的下个项用于另一个或二个按范围定义的比较，在叶子中规定比较定义表中的用于SMT比较的索引。
出于性能目的，建议尽可能少地使用按范围的比较。每次按范围的比较从执行一个额外的时钟周期(7.5nsec)为代价。从而，若范围是二的幂(即，128-256)，不需要按范围的比较并且这种类型的范围可以利用按屏蔽的比较操作来处理。
当一SMT最后比较失败并且叶子中的NLASMT字段非零时，TSE70读下个叶子并执行另一次最后比较操作，直至比较回送OK或者NLASMT等于零。
本发明可在硬件、软件或二者的结合下实现。任何类型的计算机系统或者其它适应用实现本文中说明的方法的设备都是适用的。典型的硬件和软件的组合可以是一个通用计算机系统，在装入和执行时其控制该计算机系统从而实现本文中说明的方法。本发明还可以植入计算机程序产品中，该产品具有所有能实现本文中所说明的各方法的特征，当把它装入计算机系统中时该产品能实现这些方法。
本语境下的计算机程序指令或计算机程序意味一组以任何语言、代码(即，皮代码指令)或符号表达的指令，这组指令的意图是使具有信息处理能力的系统直接地或在下述之一或二者出现下：a)转换成另一种语言、代码或符号；b)再生不同的实质格式，执行特定功能。
业内人士理解，对本发明的该优选实施例的许多修改是可能的，且不背离本发明的精神和范围。另外，有可能在不相应地使用其它特性下使用本发明的一些特性。上述对优选实施例的说明是出于示出本发明的原理的目的提供的并不是作出限制，因为本发明的范围只由附属权利要求书定义。

Claims (37)

1.一种通过计算机处理部件对软件管理树中的可变长度搜索关键字进行模式范围比较的方法，包括步骤：
从一请求应用读作为搜索串的输入关键字；
利用搜索关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引，其中每个非空表项含有一个指向搜索树中的下个分支或者一个叶子的指针，其中，N是大于1的整数；
确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支；
若该指针不指向对应搜索树的叶子，读下个分支内容；
当到达对应搜索树的叶子时读叶子内容，并把该叶子的用于定义叶子的内容的范围的第一模式和第二模式与搜索关键字进行比较以判定由该叶子的第一和第二模式定义的范围是否包括该搜索关键字；以及
若由该叶子的第一和第二模式定义的范围包括该搜索关键字，把找到的该叶子的内容回送给请求应用。
2.权利要求1的用于进行模式范围比较的方法，还包括利用可编程的散列函数散列输入关键字以形成搜索关键字。
3.权利要求1的用于进行模式范围比较的方法，其中代表搜索树的多个根节点的表含有2N个项。
4.权利要求1的用于进行模式范围比较的方法，其中计算机处理部件是网络处理器。
5.权利要求1的用于进行模式范围比较的方法，其中相应搜索树的下个分支的内容指向其他下个分支。
6.权利要求1的用于进行模式范围比较的方法，其中下个分支的内容指向相应搜索树的叶子。
7.权利要求1的用于进行模式范围比较的方法，还包括：若由该叶子的第一和第二模式定义的范围不包括搜索关键字并且不含有至另一个叶子的指针，回送不成功的指示。
8.权利要求1的用于进行模式范围比较的方法，还包括：若表的索引是一个空表项，回送不成功的指示。
9.权利要求1的用于进行模式范围比较的方法，还包括：把色彩寄存器的内容附加到搜索关键字上以提供最终搜索关键字。
10.权利要求1的用于进行模式范围比较的方法，还包括：把一串零附加到搜索关键字上以提供最终搜索关键字。
11.权利要求1的用于进行模式范围比较的方法，其中比较所述第一和第二模式的步骤包括按范围比较的操作，在其中把搜索关键字的位对待成一个整数以检查它是否在该第一和第二模式定义的范围内。
12.权利要求1的用于进行模式范围比较的方法，其中比较所述第一和第二模式的步骤包括按屏蔽比较的操作，在其中按叶子的第二模式规定的屏蔽把搜索关键字中的位和叶子的第一模式中的位进行比较。
13.权利要求1的用于进行模式范围比较的方法，还包括步骤：
若叶子包含至另一个叶子的链式指针，读另一个叶子中存储的第一和第二模式并把这些模式和搜索关键字比较；
若所存储的这些模式不包含搜索关键字并且不含有对链中下个叶子的指针，回送不成功的指示。
14.权利要求1的用于进行模式范围比较的方法，还包括步骤：
若叶子包含至另一个叶子的链式指针，读另一个叶子中存储的第一和第二模式并把这些模式和搜索关键字比较；
若所存储的这些模式包含该搜索关键字，回送成功的指示。
15.一种用于通过计算机处理部件对软件管理树中的可变长度搜索关键字进行模式范围比较的设备，包括：
用于从一请求应用读取作为搜索串的输入关键字的装置；
用于利用搜索关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引的装置，其中每个非空表项含有一个对搜索树中的下个分支或对一个叶子的指针，其中，N是大于1的整数；
用于确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支的装置；
用于在该指针不指向对应搜索树的叶子时读取下个分支内容的装置；
用于在到达对应搜索树的叶子时读叶子内容、并把该叶子的用于定义叶子的内容的范围的第一和第二模式和搜索关键字进行比较以判定由该叶子的第一和第二模式规定的范围是否包括该搜索关键字的装置，以及
用于在这些叶子模式包括该搜索关键字时把找到的该叶子的内容回送给请求应用的装置。
16.权利要求15的用于进行模式范围比较的设备，还包括利用可编程的散列函数散列输入关键字以形成搜索关键字的装置。
17.权利要求15的用于进行模式范围比较的设备，其中代表搜索树的多个根节点的表含有2N个项。
18.权利要求15的用于进行模式范围比较的设备，其中计算机处理部件是网络处理器。
19.权利要求15的用于进行模式范围比较的设备，其中相应搜索树的下个分支的内容指向其他下个分支。
20.权利要求15的用于进行模式范围比较的设备，其中下个分支的内容指向相应搜索树的叶子。
21.权利要求15的用于进行模式范围比较的设备，还包括：用于在这些叶子模式不包括搜索关键字并且不含有至另一个叶子的指针时回送不成功匹配指示的装置。
22.权利要求15的用于进行模式范围比较的设备，还包括：用于在对表的索引是一个空表项时回送不成功指示的装置。
23.权利要求15的用于进行模式范围比较的设备，还包括：用于把色彩寄存器的内容附加到搜索关键字上以提供最终搜索关键字的装置。
24.权利要求15的用于进行模式范围比较的设备，还包括：用于把一串零附加到搜索关键字上以提供最终搜索关键字的装置。
25.权利要求15的用于进行模式范围比较的设备，还包括用于按范围进行比较的装置，其中把搜索关键字的位对待成一个整数以检查它是否在该第一和第二模式定义的范围内。
26.权利要求15的用于进行模式范围比较的设备，还包括用于按屏蔽进行比较的装置，其中按叶子的第二模式规定的屏蔽把搜索关键字中的位和叶子的第一模式中的位进行比较。
27.权利要求15的用于进行模式范围比较的设备，还包括：
用于在叶子包含至另一个叶子的链式指针时读取另一个叶子中存储的第一和第二模式并把这些模式和搜索关键字比较的装置；
用于在所存储的这些模式不和搜索关键字匹配并且不含有对链中下个叶子的指针时回送不成功的指示的装置。
28.权利要求15的用于进行模式范围比较的设备，还包括：用于在叶子包含至另一个叶子的链式指针时读取另一个叶子中存储的第一和第二模式并把这些模式和搜索关键字比较的装置；
用于在所存储的这些模式和搜索关键字匹配时回送成功的指示的装置。
29.一种在半导体基片上实现的用于对软件管理树中的可变长度搜索关键字进行模式范围比较的系统，包括：
一个嵌入式处理器复合体，包括提供帧处理的多个协议处理器和一个内部控制点处理器；
多个可对每个协议处理器访问并提供高速模式搜索、数据操作和帧分析的硬件加速器协处理器；
多个存储多个表示至少一个搜索树的数据的可编程存储器部件，其中这些数据包括一个直接表、一个模式搜索控制块、一个比较表和一个包括一对要和搜索关键字比较的模式的叶子；以及
一个控制存储器仲裁器，其控制每个协议处理器对该多个存储器部件的访问；以及
一个和各协议处理器并行操作的以执行包括着存储器读、写和存储器范围检查的树搜索指令的树搜索引擎器，其中所述树搜索引掣器包括：
用于从一请求应用读取作为搜索串的输入关键字的装置；
用于利用搜索关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引的装置，其中每个非空表项含有一个对搜索树中的下个分支或对一个叶子的指针，其中，N是大于1的整数；
用于确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支的装置；
用于在该指针不指向对应搜索树的叶子时读取下个分支内容的装置；
用于在到达对应搜索树的叶子时读叶子内容、并把该叶子的用于定义叶子的内容的范围的第一和第二模式和搜索关键字进行比较以判定由该叶子的第一和第二模式规定的范围是否包括该搜索关键字的装置，以及
用于在这些叶子模式包括该搜索关键字时把找到的该叶子的内容回送给请求应用的装置。
30.权利要求29的在半导体基片上实现的用于进行模式范围比较的系统，其中该多个存储器部件还包括内部静态随机存取存储器、外部静态随机存取存储器和外部动态随机存取存储器中的至少一个。
31.权利要求29的在半导体基片上实现的用于进行模式范围比较的系统，其中该控制存储器仲裁器通过在该多个协议处理器和该多个存储器部件之间分配存储器周期管理控制存储器的操作。
32.权利要求29的在半导体基片上实现的用于进行模式范围比较的系统，其中每个协议处理器包括一个主数据缓冲器、一个暂存数据缓冲器和一组控制寄存器，用于数据存储操作。
33.权利要求29的在半导体基片上实现的用于进行模式范围比较的系统，还包括一个在搜索关键字上运算几何散列函数的散列盒部件。
34.权利要求29的在半导体基片上实现的用于进行模式范围比较的系统，还包括一个可编程搜索关键字寄存器和一个可编程散列关键字寄存器。
35.权利要求34的在半导体基片上实现的用于进行模式范围比较的系统，还包括一个可编程色彩关键字寄存器以能在多个独立的搜索树之间共享单个表数据结构。
36.权利要求35的在半导体基片上实现的用于进行模式范围比较的系统，其中，若启用色彩寄存器，把色彩寄存器的内容附加到散列输出以生成最终散列关键字。
37.权利要求35的在半导体基片上实现的用于进行模式范围比较的系统，其中，若不启用色彩寄存器，把与色彩寄存器位数相等数量的零附加到散列输出上以生成最终散列关键字。
CNB011162147A 2000-04-06 2001-04-05 对软件管理树进行模式范围比较的方法、装置和系统 Expired - Fee Related CN1195279C (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US09/545,100 US7107265B1 (en) 2000-04-06 2000-04-06 Software management tree implementation for a network processor
US09/545,100 2000-04-06

Publications (2)

Publication Number Publication Date
CN1316708A CN1316708A (zh) 2001-10-10
CN1195279C true CN1195279C (zh) 2005-03-30

Family

ID=24174892

Family Applications (1)

Application Number Title Priority Date Filing Date
CNB011162147A Expired - Fee Related CN1195279C (zh) 2000-04-06 2001-04-05 对软件管理树进行模式范围比较的方法、装置和系统

Country Status (4)

Country Link
US (1) US7107265B1 (zh)
JP (1) JP3651783B2 (zh)
KR (1) KR100429142B1 (zh)
CN (1) CN1195279C (zh)

Families Citing this family (33)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6675163B1 (en) 2000-04-06 2004-01-06 International Business Machines Corporation Full match (FM) search algorithm implementation for a network processor
US6947931B1 (en) * 2000-04-06 2005-09-20 International Business Machines Corporation Longest prefix match (LPM) algorithm implementation for a network processor
CN100367730C (zh) * 2001-02-14 2008-02-06 克利尔斯皮德科技有限公司 一种互连系统
US8195705B2 (en) * 2001-12-11 2012-06-05 International Business Machines Corporation Hybrid search memory for network processor and computer systems
AU2003268754A1 (en) * 2002-10-03 2004-04-23 In4S Inc. Bit string check method and device
US20040098510A1 (en) * 2002-11-15 2004-05-20 Ewert Peter M. Communicating between network processors
US8037102B2 (en) 2004-02-09 2011-10-11 Robert T. and Virginia T. Jenkins Manipulating sets of hierarchical data
US9646107B2 (en) 2004-05-28 2017-05-09 Robert T. and Virginia T. Jenkins as Trustee of the Jenkins Family Trust Method and/or system for simplifying tree expressions such as for query reduction
US7620632B2 (en) * 2004-06-30 2009-11-17 Skyler Technology, Inc. Method and/or system for performing tree matching
US7627591B2 (en) 2004-10-29 2009-12-01 Skyler Technology, Inc. Method and/or system for manipulating tree expressions
US7801923B2 (en) 2004-10-29 2010-09-21 Robert T. and Virginia T. Jenkins as Trustees of the Jenkins Family Trust Method and/or system for tagging trees
US7630995B2 (en) 2004-11-30 2009-12-08 Skyler Technology, Inc. Method and/or system for transmitting and/or receiving data
US7636727B2 (en) 2004-12-06 2009-12-22 Skyler Technology, Inc. Enumeration of trees from finite number of nodes
US8316059B1 (en) 2004-12-30 2012-11-20 Robert T. and Virginia T. Jenkins Enumeration of rooted partial subtrees
US8615530B1 (en) 2005-01-31 2013-12-24 Robert T. and Virginia T. Jenkins as Trustees for the Jenkins Family Trust Method and/or system for tree transformation
US7681177B2 (en) 2005-02-28 2010-03-16 Skyler Technology, Inc. Method and/or system for transforming between trees and strings
US7376809B2 (en) * 2005-03-09 2008-05-20 International Business Machines Corporation Systems and methods for multi-frame control blocks
US7466715B2 (en) * 2005-03-28 2008-12-16 International Business Machines Corporation Flexible control block format for frame description and management
US8356040B2 (en) 2005-03-31 2013-01-15 Robert T. and Virginia T. Jenkins Method and/or system for transforming between trees and arrays
US7899821B1 (en) 2005-04-29 2011-03-01 Karl Schiffmann Manipulation and/or analysis of hierarchical data
US7784094B2 (en) * 2005-06-30 2010-08-24 Intel Corporation Stateful packet content matching mechanisms
JP4891657B2 (ja) * 2006-05-29 2012-03-07 株式会社野村総合研究所 データ記憶システム、ファイル検索装置およびプログラム
US20090310544A1 (en) * 2008-06-12 2009-12-17 Praval Jain Method and system for increasing throughput in a hierarchical wireless network
US9203743B2 (en) * 2010-03-24 2015-12-01 Nec Corporation Packet forwarding system, control device, forwarding device and method and program for preparing processing rules
US8935508B1 (en) * 2010-08-30 2015-01-13 Qualcomm Incorporated Implementing pseudo content access memory
US20120066265A1 (en) * 2010-09-10 2012-03-15 Siemens Corporation Method and Apparatus for Supporting Multiple Users Working on a Project
CN103248649B (zh) * 2012-02-09 2016-08-24 宇龙计算机通信科技(深圳)有限公司 应用的分类管理方法、设备及系统
US10320955B1 (en) * 2012-08-30 2019-06-11 Keysight Technologies, Inc. Method for decoding data packets
JP6209098B2 (ja) * 2014-02-07 2017-10-04 富士通株式会社 データ管理プログラム、データ管理方法、及びデータ管理システム
US10333696B2 (en) 2015-01-12 2019-06-25 X-Prime, Inc. Systems and methods for implementing an efficient, scalable homomorphic transformation of encrypted data with minimal data expansion and improved processing efficiency
US20160335296A1 (en) * 2015-05-14 2016-11-17 Blue Sage Communications, Inc. Memory System for Optimized Search Access
CN107145493B (zh) * 2016-03-01 2020-11-24 创新先进技术有限公司 信息处理方法及装置
US10397116B1 (en) * 2017-05-05 2019-08-27 Amazon Technologies, Inc. Access control based on range-matching

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2698154B2 (ja) 1989-03-31 1998-01-19 アルプス電気株式会社 キートツプの製造方法
US5202986A (en) * 1989-09-28 1993-04-13 Bull Hn Information Systems Inc. Prefix search tree partial key branching
JPH05167640A (ja) 1991-12-11 1993-07-02 Oki Electric Ind Co Ltd 通信プロトコル実装方式
DE69422935T2 (de) 1994-06-30 2000-08-17 International Business Machines Corp., Armonk Verfahren und vorrichtung zum vergleichen von datensequenzen variabler länge
US5857196A (en) 1996-07-19 1999-01-05 Bay Networks, Inc. Method for storing a tree of potential keys in a sparse table
JP3284064B2 (ja) 1996-11-28 2002-05-20 日本電信電話株式会社 デジタル探索装置
JP3520709B2 (ja) 1997-03-13 2004-04-19 三菱電機株式会社 ネットワークアドレス検索方式
US5946679A (en) 1997-07-31 1999-08-31 Torrent Networking Technologies, Corp. System and method for locating a route in a route table using hashing and compressed radix tree searching
US6460120B1 (en) * 1999-08-27 2002-10-01 International Business Machines Corporation Network processor, memory organization and methods
US20030093613A1 (en) * 2000-01-14 2003-05-15 David Sherman Compressed ternary mask system and method
US6675163B1 (en) 2000-04-06 2004-01-06 International Business Machines Corporation Full match (FM) search algorithm implementation for a network processor

Also Published As

Publication number Publication date
US7107265B1 (en) 2006-09-12
KR100429142B1 (ko) 2004-04-29
JP2002024293A (ja) 2002-01-25
JP3651783B2 (ja) 2005-05-25
KR20010103587A (ko) 2001-11-23
CN1316708A (zh) 2001-10-10

Similar Documents

Publication Publication Date Title
CN1195279C (zh) 对软件管理树进行模式范围比较的方法、装置和系统
CN1148687C (zh) 用于网络处理器的全匹配搜索方法和设备
US7984038B2 (en) Longest prefix match (LPM) algorithm implementation for a network processor
Taylor Survey and taxonomy of packet classification techniques
Lakshminarayanan et al. Algorithms for advanced packet classification with ternary CAMs
Kumar et al. Advanced algorithms for fast and scalable deep packet inspection
Adler et al. Towards compressing web graphs
CN108370352B (zh) 使用网络处理器的高速灵活分组分类
US5946679A (en) System and method for locating a route in a route table using hashing and compressed radix tree searching
JP5265378B2 (ja) 高性能正規表現パターンマッチングのための方法および装置
Korman et al. Distributed verification of minimum spanning trees
US5995971A (en) Apparatus and accompanying methods, using a trie-indexed hierarchy forest, for storing wildcard-based patterns and, given an input key, retrieving, from the forest, a stored pattern that is identical to or more general than the key
US20040028046A1 (en) Logarithmic time range-based multifield-correlation packet classification
Sheil Median split trees: a fast lookup technique for frequently occuring keys
CN1794236A (zh) 高效的基于cam在分组有效载荷中进行串搜索的技术
US20070168377A1 (en) Method and apparatus for classifying Internet Protocol data packets
JP3570323B2 (ja) アドレスに関するプレフィクスの格納方法
CN1543150A (zh) 分组分类装置和使用字段级特里结构的方法
Mishra et al. PC-DUOS: Fast TCAM lookup and update for packet classifiers
Scarpazza et al. High-speed string searching against large dictionaries on the Cell/BE processor
Nottingham GPF: A framework for general packet classification on GPU co-processors
Zec Improving performance in software internet routers through compact lookup structures and efficient datapaths
GB2371381A (en) Tree based search method
Li et al. High-Performance Sorting-Based K-mer Counting in Distributed Memory with Flexible Hybrid Parallelism
Stefanakis Design and implementation of a range trie for address lookup

Legal Events

Date Code Title Description
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C06 Publication
PB01 Publication
C14 Grant of patent or utility model
GR01 Patent grant
REG Reference to a national code

Ref country code: HK

Ref legal event code: GR

Ref document number: 1059010

Country of ref document: HK

C17 Cessation of patent right
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20050330

Termination date: 20120405