用于网络处理器的全匹配搜索方法和设备

摘要

用于在搜索模式和搜索树的叶子中存储的模式之间寻找全匹配的新颖数据结构、方法和设备。输入关键字，对关键字运算散列函数，访问直接表(DT)并沿树执行模式搜索控制块(PSCB)直至到达叶子。该搜索机制使用一组可位于一些寄存器和常规存储器中的数据结构，并且接着用来建立一个可通过相对简单的宏硬件操纵的Patricia树结构。在该Patricia树结构中存储关键字以及检索所需的相应信息。散列函数提供从关键字的位组到散列关键字的位组的n→n变换。

主权项

1.一种通过网络处理器确定对可变长度搜索关键字的全匹配的方法，包括：读作为搜索串的输入关键字；利用散列函数散列输入关键字以生成散列关键字；利用散列关键字的N个最高有效位作为一个代表搜索树的多个根节点的表的索引，其中每个非空项含有一个指向搜索树中的下个分支或者一个叶子的指针；确定非空表项中的指针是否指向相应搜索树中的一个叶子或下个分支；若该指针不指向对应搜索树的叶子，读下个分支内容；当到达对应搜索树的叶子时读叶子内容，并把该叶子内的模式和散列关键字比较以判定叶子模式是否和散列关键字匹配；以及若叶子模式和散列关键字匹配，把找到的该叶子的内容回送给请求的应用。