Method and Apparatus for Longest Prefix Matching in Processing a Forwarding Information Database
AssigneeISIC Corporation
InventorMihailo Stojancic
Life of this patent
Estimating the term…
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.
Claims16
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.
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.
Dependencies are inferred from the claim text.