Method and apparatus for longest prefix matching in processing a forwarding information database
AssigneeISIC Corporation
InventorMihailo M. 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.
Claims24
A prefix search key apparatus for storing a prefix key of a preassigned length comprising:
- a plurality of memory banks, the number of memory banks determined by at least the number of ordinates within an n-dimension representation, the n-dimension representation defining a coordinate system, each bank associated with one of the ordinates within the n-dimension representation, each bank having at least a number of memory locations equal to the largest valid value for its associated ordinate, each ordinate representing a memory location within the associated memory bank;
- a format module for masking out one or more bits from an incoming key, the number of bits to be masked determined by the first prefix key length assigned to the prefix search key apparatus;
- and
- a conversion module for converting the masked key into an n-dimension representation having a plurality of ordinates, the conversion module storing the masked key into one memory location as referenced by one of the plurality of ordinates.
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 bits 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.