Longest best match search

• US 6,877,005 B2
• Filed: 04/10/2001
• Issued: 04/05/2005
• Est. Priority Date: 10/31/1997
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Momirov, Milan, Hunter, Van A.
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/832,708
• Publication Number:
  US 20020059197A1
• Time in Patent Office: 1,456 Days
• Field of Search: 707/205, 707/3, 707/10, 707/100, 708/497, 702/122, 709/247, 709/224, 709/239
• US Class Current: 707/747
• 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:

(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; and

(c) performing an address-sensitive decimation of the mask to produce a 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 so that the application of the mask to the address will exclude data to cause the hash function to produce a result that is different from the former index by 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.

4. The method of claim 1, further comprising:

(d) repeating operations (a)-(c) with the new mask until a predetermined condition has been met.

5. The method of claim 4, 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 4, wherein one or more now masks are generated in parallel with the 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:

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 and any lesser significant bits containing a zero than the least significant bit containing the 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 9, wherein the search key comprises a source Internet Protocol (IP) address.

13. A method or forwarding data comprising:

(A) receiving a search key;

(B) producing a masked search key by applying a mask to a portion of the search key starting at a least significant bit of the search key until a least significant bit of the masked search key containing a logic one value;

(C) performing a hash function on the masked search key to produce an index;

(D) comparing information stored within a bin of a forwarding mechanism, the bin being addressed by the index;

(E) determining whether a length of the mask is greater than a predetermined threshold concurrently with (C) and (D); and

(F) repeating (B-E) for another search iteration if the information does not match the masked search key and the length of the mask is greater than the predetermined threshold.

14. The method of claim 13, wherein, for each search iteration, the mask of the search key is shortened to exclude enough data to cause the hash function to produce a result that is different from a former index.

15. The method of claim 14, wherein the shortening of the mask comprises, for each search iteration, shortening the length of the mask to X-Y bits, where X represents the bit position of a most significant bit in the search key and Y represents a bit position of the least significant bit in the search key containing a logic one value.

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

17. An address relocation unit for improving a longest match search, comprising:

a hash table including a plurality of bins;

a hash generator to produce an index from an input address and a mask, the index being used to recover data stored in a first bin of the plurality of bins;

circuitry to determine whether the data recovered from the first bin compares with the address; and

a mask decimation logic coupled to the hash generator, the mask decimation logic to shorten the mask supplied to the hash generator so that the hash generator produces a new index that differs from the index if the data recovered fails to compare with a portion of the address identified by the mask.

18. A method of locating an entry in a forwarding database corresponding to a longest match of a search key, the method comprising:

performing a function on the search key to produce a current index;

searching a first location in a table identified by the current index for an entry that matches the search key; and

if no entry is found that matches the search key, each subsequent search iteration performing the following;

shortening the search key to exclude data to cause the function to produce a result that differs from the current index,

updating the current index with the result, and

searching a second location in the table that is identified by the current index.

19. The method of claim 18, wherein the performing of the function includes the performing of a hash function.

20. The method of claim 18, wherein each subsequent search iteration being performed if no entry is found that matches a length of the search key is greater than a predetermined length.

21. The method of claim 20, wherein the searching of the first location includes searching of a bin of a plurality of bins associated with the table.

23. The method of claim 21, wherein each subsequent search iteration being performed if no entry is found that matches a length of the search key is greater than a predetermined length.

22. A method of locating an entry in a forwarding database corresponding to a longest match of a search key, the method comprising:

generating indices for a hash table performing a hash function on the search key to produce a current index into a hash table;

searching a first bin in the hash table identified by the current index for an entry that matches the search key; and

if no entry has been found that matches the search key, for each subsequent search iteration;

shortening the search key to exclude data to cause the hash function to produce a result that is different than the current index,

updating the current index with the result, and

searching a different bin in the hash table that is identified by the current index.