Classless interdomain routing using binary content addressable memory having mask bits and mask valid bits

• US 7,213,101 B1
• Filed: 01/25/2005
• Issued: 05/01/2007
• Est. Priority Date: 04/09/2001
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US11/043,750
• Time in Patent Office: 826 Days
• Field of Search: 711/108, 711/128, 365/49, 370/392
• US Class Current: 711/108
• 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/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

A method and apparatus for using a binary CAM array to implement Classless Interdomain Routing (CIDR) Address processing. A binary CAM array is segmented into a plurality of array groups, each of which includes a number of rows of binary CAM cells, a group global mask circuit, and a mask valid bit indicating whether the group global mask circuit stores a valid group global mask.

Claims

1. A content addressable memory (CAM), comprising:

a plurality of CAM array groups each including a plurality of rows of binary CAM cells;

a plurality of group global mask circuits, each coupled to a corresponding one of the CAM array groups;

a plurality of mask valid bits, each indicating whether a valid group global mask is stored in a corresponding group global mask circuit; and

an index circuit having first inputs each coupled to a match line of a corresponding row of binary CAM cells, second inputs coupled to the group global mask circuits, and an output to generate an index of a highest priority match.

2. The CAM of claim 1, wherein each group global mask indicates a classless inter-domain routing (CIDR) prefix for data stored in a corresponding CAM array group.

3. The CAM of claim 1, wherein the group global masks stored in the group global mask circuits indicate relative priorities of data stored in corresponding CAM array groups.

4. The CAM of claim 3, wherein the priority assigned to each CAM array group is unrelated to the CAM array group'"'"'s physical location relative to other CAM array groups.

5. A content addressable memory (CAM), comprising:

a plurality of CAM array groups each including a plurality of rows of binary CAM cells;

a plurality of group global mask circuits, each coupled to a corresponding one of the CAM array groups;

a plurality of mask valid bits, each indicating whether a valid group global mask is stored in a corresponding group global mask circuit; and

an index circuit having first inputs to receive a number of data valid bits indicating whether valid data is stored in corresponding rows of binary CAM cells, second inputs to receive the mask valid bits, and an output to generate a next free address (NFA) for new data to be stored in the CAM.

6. The CAM of claim 5, wherein the NFA indicates an available row in a CAM array group that has the same priority as the new data.

7. The CAM of claim 5, further comprising:

a priority table having a plurality of rows, each for storing the priority of a corresponding CAM array group.

8. A content addressable memory (CAM) including a number of array groups, each array group comprising:

a plurality of rows of binary CAM cells;

a group global mask circuit for storing a group global mask;

a mask valid bit for indicating whether the group global mask is valid; and

an index circuit having first inputs to receive match information corresponding to the rows of binary CAM cells, second inputs to receive priority information from the group global mask circuits, and an output to generate an index of a highest priority match.

9. The CAM of claim 8, wherein each group global mask selectively masks data stored in a corresponding array group.

10. The CAM of claim 8, wherein each group global mask indicates a classless inter-domain routing (CIDR) prefix for data stored in a corresponding array group.

11. The CAM of claim 8, wherein at least two of the group global masks are unique.

12. The CAM of claim 8, wherein each group global mask indicates a priority of a corresponding array group relative to other array groups.

13. The CAM of claim 12, wherein the priority assigned to each array group is unrelated to the array group'"'"'s physical location relative to other array groups.

14. A content addressable memory (CAM) including a number of array groups, each array group comprising:

a plurality of rows of binary CAM cells;

a group global mask circuit for storing a group global mask;

a mask valid bit for indicating whether the group global mask is valid; and

an index circuit having first inputs to receive a number of data valid bits indicating whether valid data is stored in corresponding rows of CAM cells, second inputs to receive the mask valid bits, and an output to generate a next free address (NFA) for new data to be stored in the CAM.

15. The CAM of claim 14, wherein the NFA indicates an available row in a CAM array group that has the same priority as the new data.

16. The CAM of claim 14, further comprising:

a priority table having a plurality of rows, each for storing the priority of a corresponding array group.

17. A method for providing a next free address (NFA) for a content addressable memory (CAM) having a number of array groups, each array group including a plurality of rows of CAM cells, comprising:

providing a number of data valid bits, each indicating whether a corresponding row of CAM cells stores valid data;

providing a number of mask valid bits, each indicating whether a corresponding array group stores a valid group global mask; and

generating the NFA in response to the data valid bits and the mask valid bits using an index circuit.

18. The method of claim 17, wherein the group global masks indicate relative priorities of data stored in corresponding CAM array groups.