Data packet filter using contents addressable memory (CAM) and method

• US 6,252,872 B1
• Filed: 05/24/2000
• Issued: 06/26/2001
• Est. Priority Date: 05/24/2000
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Tzeng, Shrjie
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/578,070
• Time in Patent Office: 398 Days
• Field of Search: 370/363, 370/360, 370/368, 370/371, 370/374, 370/381, 370/390, 370/391, 370/392, 370/412, 370/449, 370/352, 370/395
• US Class Current: 370/360
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A method of identifying a target data packet from a series of data packets being received or transmitted by a communications device, each data packet having a series of data values. The method having the steps of establishing a condition for the target data packet, the condition having a particular data position value and an associated particular data value; storing the particular data position value in a first content addressable memory, the first content addressable memory receiving a value related to a data position of a data value and the first content addressable memory generating a position match indicator; storing the particular data value in a second content addressable memory, the second content addressable memory receiving the data value and the second content addressable memory generating the data value match indicator; comparing the position match indicator and the data value match indicator to determine if the condition for the target data packet has been satisfied by the transmitted data value. Also discussed are various embodiments of port filter devices to implement the method.

Claims

1. A method of identifying a target data packet from a series of data packets being received or transmitted by a communications device, each data packet having a series of data values, comprising the steps of:

(a) establishing at least one condition for the target data packet, each of the at least one condition specifying a particular data value being located in a particular position of the target data packet;

(b) determining whether a present data value from a data packet is located in the particular position specified by any of the at least one condition and generating a position match indicator;

(c) determining whether the present data value contains the particular data value specified by any of the at least one condition and generating a data value match indicator;

(d) comparing the position match indicator for the present data value and the data value match indicator for the present data value and generating a positive condition match indicator for the present data value when both the position match indicator and the data value match indicator are positive; and

(e) generating a positive evaluation result indicative of the presence of the target data packet when an alive indicator associated with a last condition match indicator of the present data value is alive, the alive indicator associated with a last condition match indicator being alive when a last condition and any preceding conditions of the at least one condition have sequentially been satisfied by the data packet and the data packet thereby having generated a positive match indicator for each of the at least one condition.

2. The method according to claim 1, further comprising the steps of:

storing a value related to the particular position in a first content addressable memory, the first content addressable memory receiving a value related to the position of the data value and the first content addressable memory generating the position match indicator; and

storing the particular data value in a second content addressable memory, the second content addressable memory receiving the data value and the second content addressable memory generating the data value match indicator.

3. The method according to claim 2, wherein the second content addressable memory is a ternary content addressable memory.

4. The method according to claim 1, further comprising the steps of:

establishing criteria related to the target data packet, and

translating the criteria into a the particular data value and associated particular position to derive the at least one condition used to identify the target data packet.

5. The method according to claim 1, wherein the particular position is a byte position of the data values.

6. The method according to claim 1, wherein steps (b) and (c) are conducted independently of one another and simultaneously for each present data value.

7. The method according to claim 1, further comprising the step of strobing the evaluation result upon the receipt of an end of packet indication.

8. A method of identifying a target data packet from a series of data packets being received or transmitted by a communications device, each data packet having a series of data values, comprising the steps of:

establishing a plurality of conditions for the target data packet, each condition having a particular data position value and an associated particular data value;

storing associated particular data position values and particular data values from the conditions in associated pairs of content addressable memory addresses, each pair of addresses having a first address located in a first content addressable memory and a second address located in a second content addressable memory, the first content addressable memory receiving a value related to a data position of a data value and the first content addressable memory generating a position match indicator, and the second content addressable memory receiving the data value and the second content addressable memory generating a data value match indicator;

comparing the position match indicator and the data value match indicator to determine if one of the conditions for the target data packet has been satisfied by the transmitted data value; and

updating an alive register having a series of values, each value associated with one of the pair of addresses being used to store each of the conditions, each value of the alive register based on an associated value of the comparison of the position match indicator and the data value match indicator.

9. The method according to claim 8, wherein the second content addressable memory is a ternary content addressable memory.

10. The method according to claim 8, further comprising the step of grouping pairs of addresses from the first and second content addressable memories into at least one template.

11. The method according to claim 10, further comprising the step of setting a cascade value for each template, the cascade value being selectable to combine a pair of templates if a number of conditions for the target data packet exceeds the number of grouped pairs of addresses for a first of the paired templates.

12. The method according to claim 8, further comprising the step of setting a last register associated with a pair of addresses being used to store a last of the conditions for identifying the target data packet.

13. The method according to claim 12, further comprising the step of strobing a comparison of the set last register and an alive register value associated with the set last register upon receipt of an end of packet indication to determine whether the target data packet was received or transmitted by the communications device.

14. The method according to claim 8, wherein the value of each alive register is dependent on the value of the previous alive resister.

15. The method according to claim 14, further comprising the steps of monitoring the value of a last register to determine when a data value having a position matching the particular data position contained in a last of the plurality of conditions has been received or transmitted, and generating an evaluation result indicating whether the target data packet has been received based on the value of the alive register associated with the last register.

16. The method according to claim 8, further comprising the steps of:

establishing criteria related to the target data packet, and

translating the criteria into the particular data value and the associated particular data position to derive the condition.

17. The method according to claim 8, wherein the particular data position value corresponds to a byte position of the data values.

18. The method according to claim 8, further comprising the step of strobing at least one value of the alive register upon receipt of an end of packet indication to determine whether the target data packet was received or transmitted by the communications device.

19. A port filter for identifying at least one target data packet from a plurality of data packets comprising:

a first content addressable memory having a plurality of entries, the first content addressable memory storing a position value in each of the plurality of entry addresses;

a second content addressable memory having a plurality of entries, the second content addressable memory storing an expected data value in each of the plurality of entry addresses, the entries of the first content addressable memory and the second content addressable memory being logically paired such that the values stored in each pair of entries correspond to a condition used to identify the at least one target data packet; and

an alive indication memory, the alive indication memory being progressively updated as a data packet is being received or transmitted to indicate whether each condition has been satisfied by the received or transmitted data packet.

20. The port filter according to claim 19, wherein each data packet consists of a series of data values, the port filter determining whether the data values of the incoming data packets match the conditions to determine if the expected data values are present in associated data value positions of the data packet.

21. The port filter according to claim 19, wherein the second content addressable memory is a ternary content addressable memory.

22. The port filter according to claim 19, wherein associated sets of entry addresses from the first content addressable memory and the second content addressable memory are grouped into templates.

23. The port filter according to claim 22, wherein each template has a cascade register, a value of the cascade register being selectable to combine a pair of templates if a set of conditions for one template has more conditions than pairs of entries.

24. The port filter according to claim 19, further comprising a last register for each pair of entries, a value of each last register being selectable to indicate which pair of associated entries is being used to store a last of a set of conditions for identifying the target data packet.

25. The port filter according to claim 19, wherein the alive indication memory include an alive register for each pair of entries, a value of each alive register being selectable to indicate if a data value matching an associated condition has been received by the port filter.

26. The port filter according to claim 25, wherein the value of each alive register is dependent on the value of the previous alive register.

27. The port filter according to claim 19, wherein the port filter is associated with a communications port of a data packet switch.

28. The port filter according to claim 19, further comprising a processor, the processor receiving criteria related to the target data packet from a user and the processor populating the first and second content addressable memories with values to establish a template of conditions used to identify the target data packet.

29. The port filter according to claim 19, wherein the port filter generates an evaluation result for each incoming data packet, the evaluation result indicative of whether each incoming data packet is the at least one target data packet.