Longest best match search
First Claim
1. A method of locating an entry in a forwarding database corresponding to a longest match of an address, the method comprising the steps of:
- a) applying a mask to the address to determine a masked address that is to be used for purposes of locating a matching entry in the forwarding database;
b) searching the forwarding database for an entry that matches the masked address;
c) performing an address-sensitive decimation of the mask to produce a new mask; and
d) until a predetermined condition has been met, repeating steps a-c with the new mask.
6 Assignments
0 Petitions
Accused Products
Abstract
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.
-
Citations
22 Claims
-
1. A method of locating an entry in a forwarding database corresponding to a longest match of an address, the method comprising the steps of:
-
a) applying a mask to the address to determine a masked address that is to be used for purposes of locating a matching entry in the forwarding database;
b) searching the forwarding database for an entry that matches the masked address;
c) performing an address-sensitive decimation of the mask to produce a new mask; and
d) until a predetermined condition has been met, repeating steps a-c with the new mask. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method of locating an entry in a forwarding database corresponding to a longest match of a search key, the method comprising the steps of:
-
a) searching the forwarding database for an entry that matches the search key; and
b) if no entry matches the search key, then 1) scanning the search key to locate the least significant bit containing a one, 2) shortening the search key to exclude the least significant bit containing a one, 3) searching the forwarding database for an entry that matches the search key, and 4) repeating steps 1-3 until the search key is equal to a predetermined length or until the longest match is located. - View Dependent Claims (10, 11, 12, 14, 15, 16, 17, 18, 19)
-
-
13. A method of forwarding data comprising the steps of:
-
receiving data at a port;
extracting an address from the data;
searching a forwarding database 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 progressively shortening the mask based upon the address until a matching entry is located; and
forwarding the data to a destination associated with the matching entry.
-
-
20. A method of locating an entry in a forwarding database corresponding to a longest match of a search key, the method comprising the steps of:
-
a) performing a hash function on the search key to produce a current index into a hash table;
b) searching a first bin in the hash table identified by the current index for an entry that matches the search key; and
c) while no entry is found that matches the search key and while the search key is greater than a predetermined length, with each subsequent search iteration performing the steps of 1) shortening the search key to exclude just enough data to cause the hash function to produce a result that is different than the current index;
2) updating the current index with the result of the hash function on the shortened search key; and
3) searching a different bin in the hash table that is identified by the current index.
-
-
21. A method of locating an entry in a forwarding database corresponding to a longest match of a search key, the method comprising the steps of:
-
a) generating indices for a hash table performing a hash function on the search key to produce a current index into a hash table;
b) searching a first bin in the hash table identified by the current index for an entry that matches the search key; and
c) while no entry has been found that matches the search key and while the length of the search key is greater than a predetermined length, with each subsequent search iteration performing the steps of 1) shortening the search key to exclude just enough data to cause the hash function to produce a result that is different than the current index;
2) updating the current index with the result of the hash function on the shortened search key; and
3) searching a different bin in the hash table that is identified by the current index.
-
-
22. A networking device comprising:
-
a backplane; and
a plurality of input/output (I/O) interfaces coupled to the backplane, each of the plurality of I/O cards comprising a plurality of ports, a forwarding and filtering mechanism coupled to the plurality of ports, the forwarding and filtering mechanism configured to forward data based upon the results of a longest match search of a forwarding database for an entry corresponding to an address contained within the data, where;
a mask is applied to the address to determine a masked address to be used for purposes of searching the forwarding database, the forwarding database is searched for entries that match the masked address, and subsequent masks are produced based upon an address-sensitive decimation of the mask.
-
Specification