METHOD AND APPARATUS FOR LONGEST PREFIX ADDRESS LOOKUP

摘要

A method and apparatus that constructs a "router database" and then uses the database to determine a longest match between a piece of target data, such as an address in a packet to be routed, and the database. The database contains a comparison table having a plurality of entries. In a first embodiment, each entry has up to k values, where 2 < = k < = N, where N is a number of comparison values in the database. In a second embodiment, each entry has up to k-1 values. During operation, various ones of the comparison table entries are loaded and compared to the address to determine a longest matching prefix in the router database. The comparison can be done in parallel.