Method for longest prefix matching in a content addressable memory

• US 6,237,061 B1
• Filed: 01/05/1999
• Issued: 05/22/2001
• Est. Priority Date: 01/05/1999
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Nataraj, Bindiganavale S., Khanna, Sandeep, Srinivasan, Varadarajan
• Primary Examiner(s): Bragdon, Reginald G.
• Assistant Examiner(s): Tran, Denise
• Application Number:
  US09/225,918
• Time in Patent Office: 868 Days
• Field of Search: 365/49, 711/108, 711/164, 711/212, 707/3, 707/6, 707/7, 370/389, 370/392, 370/471, 370/475, 709/220, 709/226, 709/238
• 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

Abstract

A ternary content addressable memory is employed to perform a longest prefix match search. Each CAM cell within the ternary CAM has an associated mask cell so that the CAM cells may be individually masked so as to effectively store either a logic 0, a logic 1, or a don'"'"'t care for compare operations. For example, Classless Inter-Domain Routing (CIDR) addresses are pre-sorted and loaded into the ternary CAM such that the CAM entry having the longest prefix is located at the lowest numerical address or index of the ternary CAM, and the CAM entry with the shortest prefix is located at the highest numerical address or index. The prefix portions of the CIDR addresses are used to set the mask cells associated with each CAM entry such that during compare operations, only the unmasked prefix portion of each CAM entry is compared to an incoming destination address stored as the CAM search key. Since each CAM entry is masked according to an associated prefix value, the ternary CAM requires only one search operation to locate the CAM entry having the longest matching prefix.

Claims

1. A method of determining which of a plurality of CIDR addresses stored in a ternary content addressable memory (CAM) has a longest matching prefix with a comparand of said ternary CAM, each of said CIDR addresses having first and second address fields of varying lengths and having a prefix value indicative of a number of bits in said first address field, said ternary CAM having a plurality of CAM words and a corresponding plurality of mask words, said method comprising the steps of:

loading said plurality of CIDR addresses into respective ones of said plurality of CAM words in a predetermined order such that increasing numerical CAM word addresses correspond to CIDR addresses having decreasing prefix values;

for each CIDR address loaded in the previous step, setting bit values of said corresponding mask word according to said prefix of said CIDR address such that bits of said second address field of each CIDR address are individually masked by said corresponding mask word; and

comparing said comparand to said respective first address fields of said plurality of CIDR addresses in a single compare operation.

2. The method of claim 1, wherein said first address field corresponds to a network ID.

3. The method of claim 2, wherein said second address field corresponds to a host ID.

4. The method of claim 1, wherein said CIDR address is a 32-bit binary address.

5. The method of claim 1, wherein said CIDR address is of the form IPv4/Z, where IPv4 comprises said first and second address fields and Z comprises said prefix.

6. The method of claim 1, wherein a mask bit value of logic 1 masks a corresponding bit of said CIDR address.

7. The method of claim 1, wherein a mask bit value of logic 0 masks a corresponding bit of said CIDR address.