Longest best match search

• US 20020059197A1
• Filed: 04/10/2001
• Published: 05/16/2002
• Est. Priority Date: 10/31/1997
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Milan Momirov, Van A. Hunter
• Inventors: Momirov, Milan, Hunter, Van A.
• Granted Patent: US 6,877,005 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: Y10S 707/922 Communications
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

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.

2. The method of claim 1, further comprising the step of performing a hash function on the masked address to produce an index into a hash table.

3. The method of claim 2, wherein the step of performing an address-sensitive decimation of the mask to update the mask comprises shortening the mask such that the application of the mask to the address will exclude enough data to cause the hash function to produce a result that is different from the former index.

4. The method of claim 3, wherein the step of shortening the mask such that the application of the mask to the address will exclude enough data to cause the hash function to produce a result that is different from the former index comprises shortening the length of the mask to X-Y bits, where X represents the bit position of the most significant bit in the address, and where Y represents the bit position of the least significant bit containing a one.

5. The method of claim 1, wherein the predetermined condition comprises a matching entry has been located or the length of the mask is equal to a predetermined threshold.

6. The method of claim 1, wherein one or more new masks are generated in parallel with the step of searching the forwarding database for a matching entry.

7. The method of claim 1, wherein each entry in the forwarding database includes N-bits of address and an associated mask length encoded in N+1 bits of address information, and the step of searching the forwarding database for a matching entry comprises the steps of:

determining the mask length associated with an entry based upon the location of a mask length identification marker within the address information;

comparing the mask length associated with the entry with the mask that has been applied to the address; and

if the mask length associated with the entry is less than or equal to the mask that has been applied to the address, then comparing a significant portion of the address information with the masked address, the significant portion of the address information being identified by the mask length associated with the entry.

8. The method of claim 7, wherein the mask length identification marker comprises the least significant bit in the address information containing a one, and wherein the step of determining the mask length associated with an entry based upon the location of a mask length identification marker within the address information comprises scanning the address information to locate the bit position of the least significant bit containing a one.

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.

10. The method of claim 9, wherein the step of shortening the search key to exclude the least significant bit containing a one comprises the steps of:

providing a mask of length X-Y, where X represents the bit position of the most significant bit in the search key, and where Y represents the bit position of the least significant bit containing a one; and

applying the mask to the search key.

11. The method of claim 9, wherein the search key comprises a destination Internet Protocol (IP) address.

12. The method of claim 19, wherein the search key comprises a source Internet Protocol (IP) address.

14. The method of claim 13, further comprising the step of performing a hash function on the portion of the address to produce an index into a hash table.

15. The method of claim 14, wherein the step of progressively shortening the mask based upon the address comprises, for each search iteration, shortening the mask such that the application of the mask to the address will exclude enough data to cause the hash function to produce a result that is different from the former index.

16. The method of claim 13, wherein the step of progressively shortening the mask based upon the address until a matching entry is located comprises, for each search iteration, shortening the length of the mask to X-Y bits, where X represents the bit position of the most significant bit in the address, and where Y represents the bit position of the least significant bit containing a one.

17. The method of claim 13, wherein each entry in the forwarding database includes N-bits of address and an associated mask length encoded in N+1 bits of address information, and the step of comparing a portion of the address indicated by a mask to entries in the forwarding database comprises the steps of:

determining the mask length associated with an entry based upon the location of a mask length identification marker within the address information;

comparing the mask length associated with the entry with the mask; and

if the mask length associated with the entry is less than or equal to the mask, then comparing a significant portion of the address information with the portion of the address indicated by the mask, the significant portion of the address information being identified by the mask length associated with the entry.

18. The method of claim 17, wherein the mask length identification marker comprises the least significant bit in the address information containing a one, and wherein the step of determining the mask length associated with an entry based upon the location of a mask length identification marker within the address information comprises scanning the address information to locate the bit position of the least significant bit containing a one.

19. The method of claim 13, wherein the address comprises a 32-bit or a 128-bit Internet Protocol (IP) address.

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.