发明名称 |
Fast flexible search engine for longest prefix match |
摘要 |
A subprefix is selected from a prefix search tree that has a longest match to a search prefix. A binary search prefix is input to the root vertex of the tree, and is compared to the prefixes in selected hierarchy vertices. A bit is set in a search mask based on a least significant bit of a bit string in the search prefix that matches a longest bit string in a prefix in each vertex. A longest matching subprefix is selected from a string of most significant bits of the search prefix based on the lowest significant bit set in the search mask. A prefix mask is also provided for each prefix in the tree, and is useful in connection with construction of the search mask.
|
申请公布号 |
US6564211(B1) |
申请公布日期 |
2003.05.13 |
申请号 |
US20000679209 |
申请日期 |
2000.10.04 |
申请人 |
LSI LOGIC CORPORATION |
发明人 |
ANDREEV ALEXANDER E.;SCEPANOVIC RANKO |
分类号 |
G06F17/30;(IPC1-7):G06F17/30 |
主分类号 |
G06F17/30 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|