Address lookup in packet data communication networks

• US 6,052,683 A
• Filed: 02/24/1998
• Issued: 04/18/2000
• Est. Priority Date: 02/24/1998
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Corporation
• Inventors: Irwin, George Frank
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/028,506
• Time in Patent Office: 784 Days
• Field of Search: 707/1-536, 341/51-106, 704/9-10
• US Class Current: 707/758
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

An apparatus for performing an address lookup to find a longest matching prefix for an N-bit input address in a packet data communication system that includes a memory (e.g. RAM) for storing a table containing a predefined portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix. A binary search algorithm is used for selecting a specific prefix value from the prefix search list to structure the N-bit input address to form a search value. A search algorithm (e.g. a content addressable memory) is used for performing an associative search on the search value to find the longest matching prefix. The two types of memories (RAM and CAM) each provide specific functions. The RAM is used as a lookup table to provide an N/x-bit (0<x<N) binary decoding tree, and the CAM is used to provide an associative search of network addresses that are stored in logical bins that have a specific network prefix. By using the binary search algorithm that is guided by the lookup table data, the CAM can be probed to find the longest matching prefix.

Claims

1. An apparatus for performing an address lookup to find a longest matching prefix for an N-bit input address in a packet data communication system, comprising:

a memory for storing a table containing a predefined portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix;

an algorithm for selecting a specific prefix value in the prefix search list to structure the N-bit input address to form a search value; and

a search algorithm for performing an associative comparison of the search value to address entries in a table having the specific prefix value.

2. The apparatus of claim 1, wherein the predefined portion is the first N/2-bit portion of the N-bit address.

3. The apparatus of claim 1, wherein the memory is a lookup table implemented in random access memory.

4. The apparatus of claim 1, wherein the search algorithm is implemented in a content addressable memory containing a table of addresses with associated prefix values.

5. The apparatus of claim 1, wherein the prefix search list includes a portion for representing the prefix value having an initial longest matching prefix.

6. The apparatus of claim 5, wherein the prefix search list includes means for designating one of the prefix values in the prefix search list a priority prefix.

7. The apparatus of claim 6, wherein the algorithm is directed to select the priority prefix as the selected prefix value.

8. The apparatus of claim 5, wherein the algorithm is directed to select a midpoint prefix value for the prefix search list as the selected prefix value.

9. The apparatus of claim 1, wherein the search algorithm is implemented in a content addressable memory containing a table of addresses with associated prefix values.

10. The apparatus of claim 1, wherein x=2.

11. An apparatus for performing a longest matching prefix search of a network address for an N-bit input address in a packet data communication system, comprising:

a memory for storing a table containing an N/x-bit portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix, wherein each of said prefix values represent at least one possible network address match to the N-bit input address;

a binary search algorithm for selecting a specific prefix value in the prefix search list to mask the N-bit input address to form a search value; and

a search algorithm for performing an associative comparison of the search value to address entries in a table having the specific prefix value, where 0<

x<

N.

12. The apparatus of claim 11, wherein the memory is a lookup table implemented in random access memory.

13. The apparatus of claim 11, wherein the prefix search list includes a portion for representing the prefix value having an initial longest matching prefix.

14. The apparatus of claim 13, wherein the prefix search list includes means for designating one of the prefix values in the prefix search list a priority prefix.

15. The apparatus of claim 14, wherein the means for designating is a algorithm for determining a prefix value that is associated with more of the possible network addresses than the sum total of the possible network addresses of the other prefix values in the prefix search list.

16. The apparatus of claim 15, wherein the algorithm is directed to select the priority prefix in the prefix search list as the selected prefix value.

17. A method of performing an address lookup to find a longest matching prefix for an N-bit input address in a packet data communication system, comprising:

(a) storing a table containing a predefined portion of an N-bit address with an associated prefix search list containing prefix values that are candidates for the longest matching prefix;

(b) selecting a target prefix value in the prefix search list to structure the N-bit input address to form a search value; and

(c) performing an associative comparison of the search value to address entries in a table having the target prefix value.

18. The method of claim 17, wherein the predefined portion is the first N/2-bit portion of the N-bit address.

19. The method of claim 18, wherein the step of storing a table is implemented as a N/2-bit binary decoding tree.

20. The method of claim 19, wherein the prefix search list includes a portion for representing the prefix value having an initial longest matching prefix.

21. The method of claim 20, wherein the prefix search list includes means for designating one of the prefix values in the prefix search list a priority prefix.

22. The method of claim 21, wherein the step of selecting is directed to select the priority prefix as the selected prefix value.

23. The method of claim 17, wherein the step of selecting is directed to select a mid-point prefix value from the prefix search list as the selected prefix value.

24. The method of claim 17, wherein the step of performing the associative comparison is implemented in a content addressable memory containing the table of addresses with associated prefix values.

25. The method of claim 17, wherein steps (b) and (c) are performed until the longest matching prefix is found from the prefix search list.

26. The method of claim 17, wherein steps (b) and (c) are performed until the prefix search list is exhausted.