×

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
First Claim
Patent Images

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, andf) routing the data packet to an output data link corresponding to said matched prefix entry contained in said database.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×