Patent ID: 6449256
Filing Date: 2002-09-10
Classification: H04L

Abstract:
A method for routing a data packet applied to an input port of an electronic router, the data packet including routing information comprising a plurality of routing fields, said plurality of routing fields including a destination address field containing a destination address, and the electronic router having a plurality of outputs, each output corresponding to an output link, and a routing database including filter entries, each filter entry having a corresponding cost and an associated output link, the routing database comprising a plurality of sub-databases and a crossproduct database, each sub-database corresponding to a different routing field of a data packet and including prefix filters encompassing all possible values of routing fields corresponding to the sub-databases, and the crossproduct database comprising a database of output data links corresponding to crossproduct terms of prefixes contained in the crossproduct database;said method comprising the steps of: (a) operating the router to perform a crossproducting search on the routing information included in the data packet to find a least-cost matching filter in the routing database and its corresponding output link, said operating step comprising: searching for one of a longest matching prefix or a narrowest enclosing range for each routing field in the data packet in sub-databases corresponding to the routing fields, each search producing a search result; concatenating the search results into a crossproduct term; and searching for an output link corresponding to the crossproduct term in the crossproduct database; and (b) routing the data packet to an output of the router corresponding to the output link found in the crosproducting search.