Partially-ordered cams used in ternary hierarchical address searching/sorting

• US 7,139,867 B2
• Filed: 08/22/2003
• Issued: 11/21/2006
• Est. Priority Date: 10/08/1998
• Status: Expired due to Fees

• Current Assignee: Round Rock Research LLC
• Original Assignee: Micron Technology, Inc.
• Inventors: Feldmeier, David, Arnold, Tyler
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US10/645,604
• Publication Number:
  US 20040039845A1
• Time in Patent Office: 1,187 Days
• Field of Search: 711/108, 711/117, 711/202, 711/219, 711/100, 711/154, 710/65, 712/224
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

An apparatus and method that utilizes partial ordering of ternary hierarchical addresses and their associated masks entries in both binary and ternary content addressable memories (CAMs) for providing fast searches and while reducing address table size used in the processing of communication system (e.g., Internet Protocol (IP), layer-3 switches and ATM switches using E.164 addressing) addresses for identifying the source and destination of each digital packet data.

Claims

1. A binary content addressable memory (CAM) for storing ternary hierarchical addresses of a communication system therein and wherein each ternary hierarchical address comprises a communication system address and associated communication system address mask, said binary CAM comprising a plurality of entries wherein:

each entry comprises;

(1) a first value comprising the logically ANDed communication system address and its associated mask; and

(2) a second value comprising the logically ANDed complement of said communication system address and its associated mask; and

wherein each entry is positioned in said CAM based on the number of contiguous ones in said associated mask.

2. The binary CAM of claim 1 wherein entries having the most amount of contiguous ones in said associated mask are located at the top of said CAM and wherein entries having the least amount of contiguous ones in said associated mask are located at the bottom of said CAM.

3. The binary CAM of claim 2 wherein said first value comprises n bits and said second value comprises n bits and wherein each one of said bits in said first value has an associated bit in said second value, said each one of said bits and said associated bit forming a binary pair, said binary pair representing one bit of said address as two bits in said CAM.

4. The binary CAM of claim 3 wherein a 1 in said ternary hierarchical address is represented as 10 in said CAM, wherein a 0 in said ternary hierarchical address is represented as 01 in said CAM, and wherein a don'"'"'t care in said ternary hierarchical address is represented as 00 in said CAM.

5. The binary CAM of claim 3 wherein said first value is stored in an upper portion of said entry and said second value is stored in a lower portion of said entry.

6. The binary CAM of claim 5 wherein said entry comprises 64 bits and wherein n is 32.

7. A binary content addressable memory (CAM) for storing ternary hierarchical addresses of a communication system therein and wherein each ternary hierarchical address comprises a communication system address and associated communication system address mask, said binary CAM comprising a plurality of entries wherein:

each entry comprises a two bit representation for each bit in said ternary hierarchical address; and

wherein each entry is positioned in said CAM based on the number of contiguous ones in said associated mask.

8. The binary CAM of claim 7 wherein:

(a) a 1 in said ternary hierarchical address is represented by said two bit representation in said CAM as 10;

(b) a 0 in said ternary hierarchical address is represented by said two bit representation in said CAM as 01; and

(c) a don'"'"'t care in said ternary hierarchical address in represented by said two bit representation in said CAM as 00.

9. The binary CAM of claim 8 wherein entries having the most amount of contiguous ones in said associated mask are located at the top of said CAM and wherein entries having the least amount of contiguous ones in said associated mask are located at the bottom of said CAM.

10. A method for storing ternary hierarchical addresses of a communication system in a binary CAM wherein each ternary hierarchical address comprises a communication system address and associated communication system address mask, said method comprising the steps of:

logically ANDing each communication system address and its associated mask to form a first value;

logically ANDing the complement of each communication system address and its associated address mask to form a second value; and

storing said first value and said second value in an entry in said binary CAM based on the number of contiguous ones in said address mask.

11. The method of claim 10 wherein said step of storing said first value and said second value at a location comprises arranging entries such that entries having the most contiguous ones in said associated mask are located at the top of said CAM and wherein entries having the least amount of contiguous ones in said associated mask are located at the bottom of said CAM.

12. The method of claim 11 wherein said first value comprises n bits and said second value comprises n bits and wherein said step of storing said first value and said second value comprises associating each one of said bits in said first value with one bit in said second value to form a binary pair, said binary pair representing one bit of said address as two bits in said CAM.

13. The method of claim 12 wherein said step of representing one bit of said ternary hierarchical address as two bits in said CAM comprises:

(a) utilizing 10 in said CAM to represent a 1 in said ternary hierarchical address;

(b) utilizing 01 in said CAM to represent a 0 in said ternary hierarchical address; and

(c) utilizing 00 in said CAM to represent a don'"'"'t care in said ternary hierarchical address.

14. The method of claim 12 wherein said step of storing said first value and said second value comprises storing said first value in an upper portion of said entry and storing said second value in a lower portion of said entry.

15. The method of claim 14 wherein said entry comprises 64 bits and wherein said step of storing said first value and said second value comprises storing said first value in the upper 32 bits and storing said second value in the lower 32 bits.

16. A method of storing for storing ternary hierarchical addresses of a communication system in a binary CAM wherein each ternary hierarchical address comprises a communication system address and associated communication system address mask, said method comprising the steps of:

(a) generating a CAM entry for each ternary hierarchical address by;

(1) identifying that portion of each ternary hierarchical address that are don'"'"'t cares;

(2) representing each bit in said ternary hierarchical address using bits in said CAM wherein;

(i) a 1 in said ternary hierarchical address is represented as 10 in said CAM;

(ii) a 0 in said ternary hierarchical address is represented as 01 in said CAM; and

(iii) a don'"'"'t care in said ternary hierarchical address is represented as 00 in said CAM;

(b) positioning each CAM entry in said CAM based on the number of contiguous ones in said associated mask.

17. The method of claim 16 wherein said step of positioning each CAM entry in said CAM comprises arranging entries such that entries having the most contiguous ones in said associated mask are located at the top of said CAM and wherein entries having the least amount of contiguous ones in said associated mask are located at the bottom of said CAM.

18. A method of searching a binary CAM to find a match for a ternary hierarchical address of a communication system, said binary CAM comprising entries of ternary hierarchical addresses, each ternary hierarchical address entry comprising a communication system address and an associated communication system address mask, said entries of ternary hierarchical addresses being stored in said binary CAM as a first value and a second value, said first value comprising the communication system address logically ANDed with said address mask and said second value comprising the complement of said communication system address logically ANDed with said address mask, and wherein all of said entries are ordered in said binary CAM based on the number of contiguous ones in said mask, said method comprising the steps of:

(a) loading a first register with the communication system address to be searched along with the complement of the communication system address;

(b) loading a second register with the communication system address to be searched along with the complement of the communication system address;

(c) associating each bit of said first register with one bit of said second register and with one bit of each entry in said binary CAM;

(d) determining whether a bit match occurs between corresponding bits of said first register and each entry in said binary CAM as qualified by said corresponding bit of said second register; and

(e) obtaining a match between the desired ternary hierarchical address and one of said entries based on the greatest number of matches of corresponding bits of said first register and each entry in said binary CAM.

19. The method of claim 18 wherein said step of determining whether a bit match occurs between corresponding bits of said first register and each entry in said binary CAM as qualified by said corresponding bit of said second register comprises declaring a bit match between corresponding bits of said first register and each entry in said binary CAM:

(1) if the corresponding bit in said second register is a 1;

or

(2) if the corresponding bit in said second register is a 0 and the corresponding bits of said first register and each entry in said binary CAM are identical.

20. The method of claim 19 wherein said steps of loading a first and second register comprises loading the communication system address to be searched in an upper portion of said registers and loading said complement of the communication system address in a lower portion of said registers.

21. The method of claim 20 wherein said first and second registers comprise 64 bits and wherein said steps of loading said first and second registers comprises loading the communication system address to be searched in the upper 32 bits of said registers and loading said complement of the communication system address in said lower 32 bits of said registers.

22. A method of searching a binary CAM to find a match for a ternary hierarchical address of a communication system, said binary CAM comprising entries of ternary hierarchical addresses, each ternary hierarchical address comprising a communication system address and an associated communication system address mask, each ternary hierarchical address entry being stored in said binary CAM whereby 10 is stored in said entry for every 1 in said ternary hierarchical address, 01 is stored in said entry for every 0 in said ternary hierarchical address, and 00 is stored in said entry for every don'"'"'t care in said ternary hierarchical address, and wherein all of said entries are ordered in said binary CAM based on the number of contiguous ones in said mask, said method comprising the steps of:

(a) loading a first register and second register with the communication system address to be searched by;

(1) loading a 10 in said first and second registers for every 1 in the ternary hierarchical address to be searched;

(2) loading a 01 in said first and second registers for every 0 in the ternary hierarchical address to be searched;

(3) loading a 00 in said first and second registers for every don'"'"'t care in the ternary hierarchical address to be searched;

(b) associating each bit of said first register with one bit of said second register and with one bit of each entry in said binary CAM;

(c) declaring a bit match between corresponding bits of said first register and each entry in said binary CAM;

(1) if the corresponding bit in said second register is a 1;

or

(2) if the corresponding bit in said second register is a 0 and the corresponding bits of said first register and each entry in said binary CAM are identical; and

(d) obtaining a match between the desired ternary hierarchical address and one of said entries based on the greatest number of matches of corresponding bits of said first register and each entry in said binary CAM.

23. A method for maintaining a sorted CAM to enable longest matches in a single search cycle when hierarchical addresses are added to, or deleted from, the CAM in a communication system utilizing hierarchical addresses and associated address masks, said method comprising the steps of:

(a) segmenting the CAM into blocks wherein each block corresponds to a single hierarchical mask and wherein said blocks are arranged in the CAM such that the lowest CAM addresses contain the highest hierarchical masks and the highest CAM addresses contain the lowest hierarchical masks;

(b) storing hierarchical addresses according to said block having a corresponding hierarchical mask; and

(c) tracking the first address and the next free address of each of said blocks and the size of each of said blocks.

24. A content addressable memory (CAM) of a communications system utilizing ternary hierarchical addressing and associated address masks, said CAM comprising:

a plurality of address entries and associated address masks that are arranged in said CAM by mask number, with address entries having the highest mask number being located at address entry locations at the top of the CAM and address entries having the lowest mask number being located at address entry locations at the bottom of the CAM, said mask number being defined as the number of contiguous ones in an associated address mask.

27. A content addressable memory (CAM) of a communication system as defined in claim 24 wherein said plurality of address entries comprises:

a first group of address entries sharing a first said address mask and a second group of address entries sharing a second said address mask, said first and second groups being located at different locations of the CAM.

28. A content addressable memory (CAM) of a communication system as defined in claim 27 further comprising at least one vacant address entry location disposed within said CAM between said first and second groups of address entries.

25. An apparatus for storing a plurality of address entries and associated address masks in a communication system utilizing ternary hierarchical addressing and associated address masks, said apparatus comprising:

a binary CAM;

a binary-encoded ternary converter coupled to said binary CAM wherein said binary-encoded ternary converter converts each ternary value into a corresponding binary-encoded ternary value to form said address entries; and

wherein said plurality of address entries and associated address masks are arranged in said binary CAM in a plurality of address entry groups, each address entry group having a respective mask number, with said address entry group having the highest mask number being located at the highest location of the CAM and said address entry group having the lowest mask number being located at the lowest location of the CAM, said mask number being defined as the number of contiguous ones in an associated address mask.

29. An apparatus for storing a plurality of address entries and associated address masks in a communication system as defined in claim 25 further comprising:

at least one vacant address entry location within said CAM adjacent at least one of said address entry groups.

26. A method for accelerating the routing of hierarchical addressing in a communication system which utilizes ternary hierarchical addressing and associated address masks, said method comprising the steps of:

(a) obtaining communication system hierarchical addresses and associated masks to form a plurality of address entries; and

(b) storing said plurality of address entries in a content-addressable memory (CAM) device by mask number wherein said mask number is defined as the number of contiguous ones in an associated address mask and wherein address entries having the highest mask number are stored in address entry locations at the highest location of the CAM and address entries having the lowest mask number are stored at address entry locations at the lowest location of the CAM.

30. A method for accelerating the routing of hierarchical addressing in a communication system as defined in claim 26 further comprising the steps of:

receiving an address value in a comparand register of said CAM;

matching a further plurality of addresses, including a subset of said communication system hierarchical addresses, to said address value; and

outputting an ouyut hierarchical address of said further plurality of addresses according to respective storage locations of said further plurality of addresses.

31. A method for accelerating the routing of hierarchical addressing in a communication system as defined in claim 30 wherein said output hierarchical address of said further plurality has a storage location lowest among said respective storage locations of said further plurality of addresses.

32. A method for accelerating the routing of hierarchical addressing in a communication system as defined in claim 30 wherein said further plurality of said communication system hierarchical addresses each includes at least one identical bit.