Scalable high speed IP routing lookups

• US 6,018,524 A
• Filed: 09/09/1997
• Issued: 01/25/2000
• Est. Priority Date: 09/09/1997
• Status: Expired due to Term

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Turner, Jonathan, Varghese, George, Waldvogel, Marcel
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Previl, Daniel
• Application Number:
  US08/926,370
• Time in Patent Office: 868 Days
• Field of Search: 370/312, 370/352, 370/355, 370/356, 370/389, 370/395, 370/432, 370/472, 709/238, 709/242, 707/2, 707/7, 371/67.1
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus for an exponentially faster technique than is presently utilized in routers for looking-up destination addresses and matching them to a prefix in order to determine an output data link for routing of the data message to a destination. The basic algorithm includes arranging the prefix and corresponding output data link information in sub-databases arranged by prefix length and then using a multi-step prefix length binary search algorithm to sort through the sub-databases to determine a best matching prefix for routing of the data packet. Various refinements of the basic algorithm are disclosed to further enhance the search time including adding markers representative of sub-database entries having a longer prefix length and also various searching methodologies to minimize the number of searching steps including rope searching in various formats. Thus, methodologies are disclosed for building the sub-databases, as appropriate to implement the corresponding novel search routines and perform the novel search routines themselves, and the router which implements all of the foregoing. Many of the inventive features disclosed herein are applicable to other routing DPJ protocols such as OSI Routing, call routing and telephone DPJ networks, and string matching problems.

Claims

1. A method of routing data packets through an electronic routing device, said data packets having an address indicative of a desired destination, and said routing device having a database of prefix entries arranged in multiple sub-databases each of which contains entries corresponding to prefixes having the same length, each of said entries corresponding to a desired output data link, said method comprising the steps of:

a) reading the destination address of a data packet desired to be routed,

searching for a matching entry in the sub-database corresponding to the median prefix length of the set of all available prefix lengths,

c) 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,

d) 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,

e) repeating steps b) and c) until there are no more sub-databases to search, and

f) routing the data packet to an output data link corresponding to said matched prefix entry contained in said database.

2. The method of claim 1 further comprising the steps of:

a) assigning a default output data link at the beginning of each search, and

b) substituting a new best output data link corresponding to a matching entry for any previously assigned output data link upon making a match.

3. The method of claim 2 wherein any sub-database may include marker entries corresponding to prefix entries in a longer prefix length sub-database, and wherein any sub-database prefix entry may also be a marker, and further comprising the step of assigning as a final output data link that output data link which corresponds to any matching prefix only.

4. The method of claim 3 wherein the step of assigning a final output data link upon making a prefix only match includes the step of terminating the search.

5. The method of claim 3 wherein each marker includes a set of desired sub-databases for the next search step, said set including only those sub-databases that contain an entry that is an extension of said marker, and wherein the next search step includes searching as before said set of desired sub-databases for a matching entry.

6. The method of claim 5 wherein said set of desired sub-databases includes only the median sub-databases corresponding to additional searching steps, and wherein all further search steps include searching as before only in said desired sub-databases.

7. The method of claim 5 wherein said desired sub-databases include 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.

8. 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.

9. The router of claim 8 wherein the multi-step prefix length binary search includes the steps of assigning a default output data link at the beginning of each search, and substituting a new best output data link corresponding to a matching entry for any previously assigned output data link upon making a match.

10. The router of claim 9 wherein any sub-database may include marker entries corresponding to prefix entries in a longer prefix length sub-database, and wherein any sub-database prefix entry may also be a marker entry, and wherein the multi-step prefix length binary search further comprises the step of assigning as a final output data link that output data link which corresponds to any matching prefix only.

11. The router of claim 10 wherein each marker includes a set of desired sub-databases for the next search step, said set including only those sub-databases that contain an entry that is an extension of said marker, and wherein the next search step includes searching as before said set of desired sub-databases for a matching entry.

12. The router of claim 10 wherein said desired sub-databases include 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.

13. The router of claim 10 wherein said set of desired sub-databases includes only the median sub-databases corresponding to additional searching steps, and wherein all further search steps include searching as before only in said desired sub-databases.

14. 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.

15. The method of claim 14 further comprising the step of arranging the plurality of sub-databases into the architecture of a trie for determining the corresponding longest matching prefix of X.

16. The method of claim 15 in which the longest matching prefix associated with an entry X is determined when X is inserted by doing a multi-step search on the sub-database contents that have been inserted before X is inserted.