发明申请
US20050177552A1 Full match (FM) search algorithm implementation for a network processor
失效
网络处理器的完全匹配(FM)搜索算法实现
- 专利标题: Full match (FM) search algorithm implementation for a network processor
- 专利标题(中): 网络处理器的完全匹配(FM)搜索算法实现
-
申请号: US10650397申请日: 2003-08-28
-
公开(公告)号: US20050177552A1公开(公告)日: 2005-08-11
- 发明人: Brian Bass , Jean Calvignac , Marco Heddes , Antonios Maragkos , Piyush Patel , Michael Siegel , Fabrice Verplanken
- 申请人: Brian Bass , Jean Calvignac , Marco Heddes , Antonios Maragkos , Piyush Patel , Michael Siegel , Fabrice Verplanken
- 主分类号: G06F17/30
- IPC分类号: G06F17/30 ; H04L12/46 ; H04L12/56 ; G06F7/00
摘要:
Novel data structures, methods and apparatus for finding a full match between a search pattern and a pattern stored in a leaf of the search tree. A key is input, a hash function is performed on the key, a direct table (DT) is accessed, and a tree is walked through pattern search control blocks (PSCBs) until reaching a leaf. The search mechanism uses a set of data structures that can be located in a few registers and regular memory, and then used to build a Patricia tree structure that can be manipulated by a relatively simple hardware macro. Both keys and corresponding information needed for retrieval are stored in the Patricia tree structure. The hash function provides an n->n mapping of the bits of the key to the bits of the hash key.