Method and Apparatus for Longest Prefix Matching in Processing a Forwarding Information Database

Abstract

A hardware circuit implemented on a DRAM foundry is provided for finding the longest prefix key match. The hardware circuit includes the use of prefix search engines to store prefix keys. Each prefix search engine may advantageously include an n-dimension memory for fast efficient access. Each prefix search engine is preassigned to store prefix keys having a specific length. Based on the preassignment and the n-dimensional memory, the hardware circuit matches the longest prefix key stored in the prefix search engines by comparing all prefix search engines in parallel.

1 . A prefix search key system for determining the longest prefix key match with an incoming key, the system comprising: 
 a plurality of prefix search engines storing one or more keys of an assigned length;    a means for assigning to each prefix search engine a prefix key length to limit the length of prefix keys stored at each prefix search engine, each prefix search engine masking one or more hits from the incoming key defining one or more masked keys, the number of one or more bits masked determined by the prefix key length assigned, each prefix search engine outputting a match indication and a match result if a prefix search engine's masked key matches a stored key;    a priority controller maintaining the prefix length assignment for each prefix search engine, the priority controller receiving one or more match indications, the priority controller outputting a priority signal indicating which match result to select out of the prefix search engines having a match; and    a resulting index multiplexer receiving one or more match results and the priority signal, the resulting index multiplexer selecting the match results to output based on the priority signal.    
   
   
       2 . The system of  claim 1  further comprising: 
 a direct mapping module for mapping keys having short key lengths.    
   
   
       3 . The system of  claim 1  wherein the match result comprises a table entry.  
   
   
       4 . The system of  claim 1  wherein at least one of the plurality of prefix search engines stores a prefix key having the same lengths as at least another one of the plurality of prefix search engines.  
   
   
       5 . The system of  claim 1  wherein the means for assigning the prefix key length assigns to at least one prefix search engine a second prefix key length.  
   
   
       6 . The system of  claim 1  wherein each of the plurality of prefix search engines further comprise: 
 a demultiplexer for selecting one of two prefix keys stored in the same memory location.    
   
   
       7 . The system of  claim 1  wherein the incoming key comprises data extracted from an Internet protocol (IP) packet header.  
   
   
       8 . The apparatus of  claim 1  wherein the matched result includes a field wherein the field is a class numbers a virtual route numbers a virtual private network number, a type of service number, a pointer to another table entry, or a sequence of control bits.  
   
   
       9 . A method of determining the longest prefix key match in a database of prefix keys with an incoming key, the method comprising: 
 routing an incoming key to the plurality of prefix search engines;    masking one or more bits of the incoming key to define a masked key, the number of one or more bits masked determined by the prefix key length assigned to the respective prefix search engine;    converting the masked key to an n-dimension representation;    retrieving one or more prefix keys stored in memory locations referenced by the n-dimension representation;    reporting a match indication and a match result if the masked key matches a stored prefix key;    receiving one or more match indications and one or more match results; and    selecting the match result out of the prefix search engines reporting match indications from the prefix search engine configured to store the largest prefix key size.    
   
   
       10 . The method of  claim 9  further comprising: 
 populating a direct mapping module with prefix keys having a length shorter than key lengths configured.    
   
   
       11 . The method of  claim 9  wherein the match result comprises a table entry.  
   
   
       12 . The method of  claim 9  wherein at least one of the plurality of prefix search engines stores a prefix key having the same lengths as at least another one of the plurality of prefix search engines.  
   
   
       13 . The method of  claim 9  wherein the configuring step further comprises configuring to at least one prefix search engine a second prefix key length.  
   
   
       14 . The method of  claim 9  wherein the plurality of prefix search engines further comprise: 
 a demultiplexer for selecting one of two prefix keys stored in the same memory location.    
   
   
       15 . The method of  claim 9  wherein the incoming key comprises data extracted from an Internet protocol (IP) packet header.  
   
   
       16 . The apparatus of  claim 9  wherein the match result includes a field wherein the field is a class number, a virtual route number, a virtual private network number a type of service number, a pointer to another table entry, or a sequence of control bits.