Invention Grant
US08599853B2 System and method for an exact match search using pointer based pipelined multibit trie traversal technique
有权
使用基于指针的流水线多位特技遍历技术进行精确匹配搜索的系统和方法
- Patent Title: System and method for an exact match search using pointer based pipelined multibit trie traversal technique
- Patent Title (中): 使用基于指针的流水线多位特技遍历技术进行精确匹配搜索的系统和方法
-
Application No.: US12761420Application Date: 2010-04-16
-
Publication No.: US08599853B2Publication Date: 2013-12-03
- Inventor: Madhusudan Chidambaram
- Applicant: Madhusudan Chidambaram
- Applicant Address: IN Bangalore
- Assignee: Wipro Limited
- Current Assignee: Wipro Limited
- Current Assignee Address: IN Bangalore
- Agency: LeClairRyan, a Professional Corporation
- Main IPC: H04L12/56
- IPC: H04L12/56

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.
Public/Granted literature
Information query