System and method using hierarchical parallel banks of associative memories

• US 7,245,623 B1
• Filed: 01/08/2002
• Issued: 07/17/2007
• Est. Priority Date: 01/08/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R.
• Primary Examiner(s): Chan; Wing
• Assistant Examiner(s): Haliyur; Venkatesh
• Application Number:
  US10/041,194
• Time in Patent Office: 2,016 Days
• Field of Search: 370/393, 370/397, 370/395.71, 370/395.72, 370/392, 370/401, 370/412, 709220-246, 711/108
• US Class Current: 370/393
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

Abstract

A system and method provide for efficient classification of long strings of data, such as network messages. The system, which may be a classification engine for use in a network device, is configured to include one or more stages having one or more banks of ternary content addressable memories (TCAMs). The TCAM banks of each stage are organized into one or more groups and each group processes the network messages for a different set of the network device'"'"'s ports. The system further includes at least one memory resource that is shared by the TCAM banks of all groups. That is, the parallel banks of TCAMs operate in a distributed fashion while the shared memory resource operates in a centralized fashion. Accordingly, the system can process network messages at high speed while minimizing the number of required components.

Claims

1. In a network device having a plurality of ports for receiving and sending network messages having a plurality of fields, a classification engine configured to examine the network messages for predefined criteria and to generate corresponding actions to be applied to network messages containing the predefined criteria, the classification engine comprising:

a plurality of associative memories arranged into one or more stages, the associative memories configured with at least some of the predefined criteria; and

a single, shared memory resource coupled to each of the plurality of associative memories of at least one stage, the shared memory resource configured with the actions to be applied to network messages,

whereby two or more associative memories of the one or more stages are organized into a parallel bank that can process the same field of different network messages at substantially the same time and for each network message return one of the actions stored in the single, shared memory resource.

2. The classification engine of claim 1 wherein the associative memories operate at a first access time and the shared memory resource operates at a second access time that is some multiple of the first access time.

3. The classification engine of claim 2 wherein the multiple is one of 2, 4 or 8.

4. The classification engine of claim 1 wherein the associative memories of at least one stage are ternary content addressable memories (TCAMs).

5. The classification engine of claim 1 having at least two stages and further comprising one or more random access memories (RAMs) configured to receive outputs from the associative memories of a first stage, wherein

the network messages have Internet Protocol (IP) address fields, and

the associative memories of the first stage process at least the network message'"'"'s IP addresses fields.

6. The classification engine of claim 5 wherein the associative memories of the first stage and the one or more RAMs cooperate to identify a uniform coordinate value sequence (UCVS) for the network message'"'"'s IP address fields.

7. The classification engine of claim 1 wherein the network message comply with the Internet Protocol version 6 (IPv6) specification standard.

8. The classification engine of claim 1 wherein the network message comply with the Internet Protocol version 4 (IPv4) specification standard.

9. The classification engine of claim 1 wherein the single, shared memory resource includes a synchronous random access memory (SRAM).

10. The classification engine of claim 1 wherein

a first associative memory included in a given parallel bank is configured to process only network messages for a first set of network device ports, and

a second associative memory included in the given parallel bank is configured to process only network messages for a second set of network device ports.

11. The classification engine of claim 1 wherein

the network device includes a forwarding engine, and

the actions are provided to the forwarding engine.

12. A network device for processing a plurality of network messages in parallel, the network device comprising:

a plurality of associative memories organized into a parallel bank, each associative memory including a first plurality of entries;

a shared memory resource including a second plurality of entries configured to store a plurality of actions to be applied to the network messages, wherein each of the first plurality of entries is configured to specify one of the second plurality of entries; and

a control logic configured to apply a plurality of fields from the network messages to the associative memories at substantially the same time and to match one of the fields to one of the first plurality of entries, and, in response thereto, to return one the plurality of actions stored in the shared memory resource.

13. The network device of claim 12 wherein the associative memories comprise ternary content addressable memories (TCAMs).

14. The network device of claim 12 wherein the plurality of associative memories further comprises:

a first associative memory configured to process network messages associated with a first port of the network device; and

a second associative memory configured to process network messages associated with a second port of the network device.

15. The network device of claim 12 wherein the first plurality of entries is an identical plurality of entries for each associative memory.

16. The network device of claim 12 wherein the plurality of fields comprises one predetermined field from each network message.

17. The network device of claim 16 wherein the predetermined field is configured to specify an Internet Protocol (IP) address.

18. The network device of claim 16 wherein the predetermined field is configured to specify a unique coordinate value sequence (UCVS).

19. The network device of claim 12 wherein the network messages comply with the Internet Protocol version 6 (IPv6) specification standard.

20. The network device of claim 12 wherein the associative memories comprise a hash table.

21. The network device of claim 12 wherein the associative memories are configured to operate at a predetermined access time and the shared memory resource is configured to operate at a multiple of the predetermined access time.

22. The network device of claim 12 further comprising:

a pre-parser logic circuit configured to extract the plurality of fields from the network messages; and

a message buffer circuit coupled to the control logic and to the associative memories, the message buffer circuit configured to store the plurality of fields.

23. The network device of claim 12 further comprising an intermediate stage between the associative memories and the shared memory resource, the intermediate stage comprising:

a plurality of intermediate shared memory resources configured to return a plurality of intermediate results, each intermediate shared memory resource comprising a third plurality of entries, wherein each of the first plurality of entries is further configured to specify one of the third plurality of entries, and wherein each of the third plurality of entries is configured to specify one of the plurality of intermediate results; and

a plurality of intermediate associative memories organized into an intermediate parallel bank, each intermediate associative memory comprising a fourth plurality of entries, wherein each of the fourth plurality of entries is configured to specify one of the second plurality of entries, and wherein the control logic is further configured to apply the intermediate results to the intermediate associative memories at substantially the same time, wherein each intermediate result specifies one of the plurality of actions by matching one of the fourth plurality of entries.

24. A method for processing a plurality of network messages in parallel, the method comprising:

extracting a predetermined field from each network message to provide a plurality of fields;

searching for the plurality of fields in a parallel bank of associative memories at substantially the same time, the associative memories comprising a first plurality of entries;

specifying a second plurality of entries in a shared memory resource in response to each field of the plurality of fields matching one entry of the first plurality of entries; and

applying each of a plurality of actions to a corresponding one of the plurality of network messages, wherein each action is associated with one of the second plurality of entries by the shared memory resource.

25. The method of claim 24 wherein the associative memories comprise ternary content addressable memories (TCAMs).

26. The method of claim 24 further comprising:

programming each associative memory with an identical plurality of entries as the first plurality of entries.

27. The method of claim 24 wherein the predetermined field is configured to specify one or more of a group consisting of a unique coordinate value sequence (UCVS), a port of a network device, and a Virtual Local Area Network Identifier (VLAN ID).

28. The method of claim 24 wherein the network messages comply with an Internet Protocol version 6 (IPv6) specification standard.

29. The method of claim 24 wherein an access control list comprises a plurality of associations between a plurality of criteria and the plurality of actions, the method further comprising:

storing the criteria in the first plurality of entries; and

specifying one of the second plurality of entries in the shared memory resource in response to one of the plurality of fields matching the criteria.

30. The method of claim 24 wherein the step of applying each of the plurality of actions to the corresponding one of the plurality of network messages further comprises modifying the predetermined field of the corresponding one of the plurality of network messages.

31. The method of claim 30 wherein the predetermined field comprises a flow label.

32. The method of claim 31 wherein the step of modifying the predetermined field of the corresponding one of the plurality of network messages further comprises:

replacing an Internet Protocol version 6 (IPv6) address with a unique coordinate value sequence (UCVS).

33. The method of claim 24 wherein the step of specifying the second plurality of entries in the shared memory resource further comprises:

specifying a third plurality of entries in a plurality of intermediate shared memory resources in response to the plurality of fields matching the first plurality of entries;

returning a plurality of intermediate results from the intermediate shared memory resources, the intermediate results associated with the third plurality of entries;

searching for the plurality of intermediate results in a plurality of intermediate associative memories, the intermediate associative memories comprising a fourth plurality of entries; and

specifying the second plurality of entries in the shared memory resource in response to the plurality of intermediate results matching the fourth plurality of entries.

34. A network device for processing a plurality of network messages in parallel, the network device comprising:

means for extracting a predetermined field from each network message to provide a plurality of fields;

means for searching for the plurality of fields in a parallel bank of associative memories at substantially the same time, the associative memories comprising a first plurality of entries;

means for specifying a second plurality of entries in a shared memory resource in response to each field of the plurality of fields matching one entry of the first plurality of entries; and

means for applying each of a plurality of actions to a corresponding one of the plurality of network messages, wherein each action is associated with one of the second plurality of entries by the shared memory resource.

35. Computer readable instructions encoded in one or more computer readable media for execution by a processor, and when executed operable to:

extract a predetermined field from each network message to provide a plurality of fields;

search for the plurality of fields in a parallel bank of associative memories at substantially the same time, the associative memories comprising a first plurality of entries;

specify a second plurality of entries in a shared memory resource in response to each field of the plurality of fields matching one entry of the first plurality of entries; and

apply each of a plurality of actions to a corresponding one of the plurality of network messages, wherein each action is associated with one of the second plurality of entries by the shared memory resource.

36. An apparatus comprising:

a plurality of associative memories organized into a parallel bank, each associative memory including a first plurality of entries;

a shared memory resource including a second plurality of entries configured to store a plurality of unique coordinate value sequences (UCVSs), wherein each of the first plurality of entries is configured to specify one of the second plurality of entries; and

a control logic configured to apply a plurality of fields from a network message to the associative memories at substantially the same time and to match one of the fields to one of the first plurality of entries, and, in response thereto, to return one the UCVS stored in the shared memory resource;

at least one additional associative memory; and

wherein the control logic is further configured to apply the returned one the UCVS along with at least one additional field from the network message to the additional associative memory to cause the return of an action.

37. The apparatus of claim 36 wherein the plurality of associative memories organized into the parallel bank are ternary content addressable memories (TCAMs).

38. The apparatus of claim 36 wherein the plurality of associative memories organized into the parallel bank further comprises:

a first associative memory configured to process a first field of the network message; and

a second associative memory configured to process a second different field of the network message.

39. The apparatus of claim 36 wherein the plurality of associative memories organized into the parallel bank are configured to operate at a predetermined access time and the shared memory resource is configured to operate at a multiple of the predetermined access time.

40. The apparatus of claim 36 further comprising:

a pre-parser logic circuit configured to extract the plurality of fields from the network message; and

a message buffer circuit coupled to the control logic and to the plurality of associative memories organized into the parallel bank, the message buffer circuit configured to store the plurality of fields.