A method and apparatus for efficiently performing a longest match search
are provided. According to one aspect of the present invention, an entry
in a forwarding database, a routing table, or the like is located using an
improved longest match search. A mask is applied to an address, such as a
destination Internet Protocol (IP) address, to determine a masked address
that is to be used for purposes of locating a matching entry in the
forwarding database. The forwarding database is searched for an entry that
matches the masked address. Subsequent masks are produced by performing an
address-sensitive decimation of the former mask. For example, the former
mask may be shortened based upon the location of the least significant bit
containing a one in the masked address. According to another aspect of the
present invention, data forwarding employs the improved longest match
search. Data is received at a port. An address is extracted from the data.
A forwarding database is searched for a longest match for the address by
comparing a portion of the address indicated by a mask to entries in the
forwarding database and using progressively shorter masks, determined
based upon the masked address, for each subsequent search until a matching
entry is located. If a matching entry is found, the data is forwarded to a
destination associated with the matching entry.
