System and method for an exact match search using pointer based pipelined multibit trie traversal technique

A method of finding an exact match for an incoming packet including an N-bit wide address in every clock cycle, comprising:

• extracting K bits from an N-bit wide address of the incoming information packet;
• using the extracted k bits as a key to directly lookup a base node of a multibit trie, wherein the base node is included in a first lookup table (LUT), wherein the first LUT is configured to store pointers to leaf nodes of the multibit trie, and wherein K is dependent on a number of entries in the first LUT;
• searching a current LUT for a match on a next Q bits of remaining (N−K) bits of the N-bit wide address to retrieve a current pointer pointing to a current level leaf node of the multibit trie, wherein Q is an integer not greater than (N−K);
• determining whether the current pointer is empty;
• and
• if the current pointer is not empty, finding the exact match of the N-bit wide address by retrieving a unique search index matching the remaining (N−K) bits in every clock cycle.

A non-transitory computer-readable storage medium having instructions for finding an exact match for an incoming packet including an N-bit wide address in every clock cycle, the instructions when executed by a computer, cause the computer to perform a method comprising:

• extracting K bits from an N-bit wide address of the incoming information packet;
• using the extracted k bits as a key to directly lookup a base node of a multibit trie, wherein the base node is included in a first lookup table (LUT), wherein the first LUT is configured to store pointers to leaf nodes of the multibit trie, and wherein K is dependent on a number of entries in the first LUT;
• searching a current LUT for a match on a next Q bits of remaining (N−K) bits of the N-bit wide address to retrieve a current pointer pointing to a current level leaf node of the multibit trie, wherein Q is an integer not greater than (N−K);
• determining whether the current pointer is empty;
• and
• if the current pointer is not empty, finding the exact match of the N-bit wide address by retrieving a unique search index matching the remaining (N−K) bits in every clock cycle.