Patent ID: 6018524
Filing Date: 2000-01-25
Classification: H04L,Y10S

Abstract:
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.