Invention Grant
US08599853B2 System and method for an exact match search using pointer based pipelined multibit trie traversal technique 有权
使用基于指针的流水线多位特技遍历技术进行精确匹配搜索的系统和方法

System and method for an exact match search using pointer based pipelined multibit trie traversal technique
Abstract:
A method and system for finding an exact match for an N-bit wide address. A system for finding an exact match for an N-bit wide address in every clock cycle includes a label extraction module and one or more pipeline blocks. The label extraction module extracts K bits from the N-bit wide address. The extracted K bits are used by pipeline block 1 as a key to directly lookup a base node of multibit trie. The base node is included in first lookup table (LUT) and first LUT is configured to store pointers to leaf nodes of multibit trie. A pipeline block 2 searches a current LUT for match on next Q bits of remaining (N−K) bits to retrieve a current pointer. Then, pipeline block (N−K)/Q finds the exact match by retrieving a unique search index matching remaining (N−K) bits when the current pointer is not empty.
Information query
Patent Agency Ranking
0/0