发明名称 |
Full match (FM) search algorithm implementation for a network processor |
摘要 |
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.
|
申请公布号 |
US7120630(B2) |
申请公布日期 |
2006.10.10 |
申请号 |
US20030650397 |
申请日期 |
2003.08.28 |
申请人 |
INTERNATIONAL BUSINESS MACHINES CORPORATION |
发明人 |
BASS BRIAN MITCHELL;CALVIGNAC JEAN LOUIS;HEDDES MARCO C.;MARAGKOS ANTONIOS;PATEL PIYUSH CHUNILAL;SIEGEL MICHAEL STEVEN;VERPLANKEN FABRICE JEAN |
分类号 |
G06F7/00;G06F17/30;H04L12/46;H04L12/56 |
主分类号 |
G06F7/00 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|