Scalable high speed IP routing lookups

A router for data packets including a plurality of input data links for receiving incoming data packets, a plurality of output data links for dispatching outgoing data packets, an adjustable switch interconnected between said input data links and said output data links for adjustably connecting a selected one of said input data links to a selected one of said output data links, a data processor connected to said switch and having means for controlling said switch, and said data processor having a database of prefix entries which comprises multiple sub-databases each of which contains entries corresponding to prefixes having the same length, each of said entries having associated with it a desired output data link for routing of an incoming data packet, means for accessing said database for matching of a destination address of an incoming data packet with an entry, and means for adjusting said switch in response to a matching entry in said database to thereby route a data packet appearing at an input data link to a corresponding output data link, said accessing means including means for matching a destination address of an incoming data packet with a prefix entry using a multi-step prefix length binary search algorithm that includes the steps of:

• a) searching for a matching entry in the sub-database corresponding to the median prefix length of the set of all available prefix lengths,
• b) if no match is found, then searching in the sub-database corresponding as nearly as possible to the median prefix length of the sub-databases of prefix length strictly less than the sub-database just searched and strictly more than any previously searched sub-database,
• c) if a match is found, then searching in the sub-database corresponding as nearly as possible to the median prefix length of the sub-databases of prefix length strictly more than the sub-database just searched and strictly less than any previously searched sub-database, and
• d) repeating steps b) and c) until there are no more sub-databases to search.

A method for creating a database of entries for routing data packets from a plurality of arbitrary prefixes, each of said arbitrary prefixes having an arbitrary length and being indicative of a desired destination, said method comprising the steps of:

• a) determining the length of each prefix;
• b) assigning an entry corresponding to each prefix to a sub-database according to its prefix length so that the database is comprised of a plurality of sub-databases arranged by prefix length;
• c) inserting a marker entry containing the first Y bits of each prefix P corresponding to its associated entry in sub-database Y for each sub-database that would be searched before searching the P sub-database in a multi-step prefix length binary search, where Y is strictly less than P, including adding to each marker entry X an output data link address corresponding to a longest matching prefix of X;
• d) adding a prefix-cum-marker entry for each prefix P corresponding to its associated entry in sub-database L together with the associated output data link corresponding to P if there already is a marker entry corresponding to P;
• e) adding an indication for each non-marker prefix entry that the added output data link is the ultimate output data link;
• f) augmenting each marker entry X with a search field comprised of those sub-databases containing prefixes that are extensions of X, including limiting the search field to only those sub-databases that should be searched when no matches are found at each successive level of the multi-step prefix length binary search, and further including a multi-step procedure initialized with the plurality of prefixes corresponding to the entries to be inserted into the sub-databases and containing successive sub-steps of:
• 1) computing the sequence of sub-databases that are to be searched when no matches are found when doing a multi-step search in the current plurality of sub-databases,
• 2) terminating the building procedure if the current plurality is empty,
• 3) finding the median length M of the current plurality of sub-databases,
• 4) dividing said plurality of sub-databases into two pluralities, the first containing entries corresponding to all prefixes of length strictly less than M, and the second containing entries corresponding to all prefixes of length greater than M, and further sub-dividing said second plurality into multiple pluralities such that entries corresponding to prefixes containing the same first M bits is assigned to the same plurality,
• 5) inserting an entry X into sub-database M for each distinct value X of said first M bits and adding information to X that lists the output data link associated with the longest matching prefix of X, and
• 6) repeating steps 1) through 5) for each of the subdivided pluralities.