Using ternary and binary content addressable memory stages to classify information such as packets

• US 7,602,787 B2
• Filed: 12/28/2005
• Issued: 10/13/2009
• Est. Priority Date: 05/21/2001
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R.
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Phan; Tri H
• Application Number:
  US11/322,135
• Publication Number:
  US 20060104286A1
• Time in Patent Office: 1,385 Days
• Field of Search: 370/392, 3703951-39521, 370/401, 370/469, 37039531-39532, 707 1- 7, 709/238, 711/108, 711200-221
• US Class Current: 370/392
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• 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
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Methods and apparatus are disclosed herein for classifying packets using ternary and binary content-addressable memory stages to classify packets. One such system uses a stage of one or more TCAMS followed by a second stage one or more CAMS (or alternatively some other binary associative memories such as hash tables or TRIEs) to classify a packet. One exemplary system includes TCAMs for handling input and output classification and a forwarding CAM to classify packets for Internet Protocol (IP) forwarding decisions on a flow label. This input and output classification may include, but is not limited to routing, access control lists (ACLs), quality of service (QoS), network address translation (NAT), encryption, etc. These IP forwarding decisions may include, but are not limited to IP source and destination addresses, protocol type, flags and layer 4 source and destination ports, a virtual local area network (VLAN) id and/or other fields.

Claims

1. A system for classifying a set of information for using in processing or forwarding the set of information, the system comprising:

a ternary content-addressable memory configured to receive the set of information and to perform a lookup operation with a search key based on the set of information to produce a first result; and

a binary content-addressable memory (CAM), coupled to the ternary content-addressable memory, configured to receive the first result and to perform a lookup operation with a search key based on the first result to generate one or more classification indications;

wherein the set of information includes one or more fields extracted from a header of a packet; and

wherein the set of information includes a group address for the packet.

2. The system of claim 1, wherein the set of information includes a source address and a destination address of the packet.

3. The system of claim 1, comprising selection logic, coupled to the binary content-addressable memory, configured to select among said generated classification indications.

4. The system of claim 3, wherein said selection logic includes a priority encoder.

5. The system of claim 1, comprising means for selecting among said generated classification indications.

6. A method for classifying a set of information for using in processing or forwarding the set of information, the method comprising:

performing a lookup operation in a ternary content-addressable memory with a search key based the set of information to produce a first result; and

subsequent to said ternary content-addressable memory lookup operation, performing a lookup operation in a binary content-addressable memory, coupled to the ternary content-addressable memory, with a search key based on the first result to generate one or more classification indications;

wherein the set of information includes one or more fields extracted from a header of a packet; and

wherein the set of information includes a group address for the packet.

7. The method of claim 6, comprising:

subsequent to said binary content-addressable memory lookup operation, selecting among said generated classification indications to produce a single classification indication.

8. A system for classifying a set of information for using in processing or forwarding the set of information, the system comprising:

a ternary content-addressable memory configured to receive the set of information and to perform a lookup operation with a search key based on the set of information to produce a first result;

a memory, coupled to the ternary content-addressable memory, configured to perform a lookup operation based on the first result to retrieve a second result; and

a binary content-addressable memory, coupled to the memory, configured to receive the second result and to perform a lookup operation with a search key based on the second result to generate one or more classification indications;

where in the set of information includes one or more fields extracted from a header of a packet;

wherein the set of information includes a group address for the packet.

9. The system of claim 8, wherein the set of information includes a source address and a destination address of the packet.

10. The system of claim 8, comprising selection logic, coupled to the binary content-addressable memory, configured to select among said generated classification indications.

11. The system of claim 10, wherein said selection logic includes a priority encoder.

12. The system of claim 8, comprising means for selecting among said generated classification indications.

13. A method for classifying a set of information for using in processing or forwarding the set of information, the method comprising:

performing a lookup operation in a ternary content-addressable memory with a search key based the set of information to produce a first result;

subsequent to said ternary content-addressable memory lookup operation, performing a lookup operation in a memory, coupled to the ternary content-addressable memory, based on the first result to retrieve a second result; and

subsequent to said memory lookup operation, performing a lookup operation in a binary content-addressable memory, coupled to the memory, with a search key based on the second result to generate one or more classification indications;

where in the set of information includes one or more fields extracted from a header of a packet; and

wherein the set of information includes a group address for the packet.

14. The method of claim 13, comprising:

subsequent to said binary content-addressable memory lookup operation, selecting among said generated classification indications to produce a single classification indication.