Method and apparatus for maintaining netflow statistics using an associative memory to identify and maintain netflows

• US 6,871,265 B1
• Filed: 02/20/2002
• Issued: 03/22/2005
• Est. Priority Date: 02/20/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Oren, Eyal, Ratinsky, Alon, Belz, David E.
• Primary Examiner(s): Anderson, Matthew
• Assistant Examiner(s): Thomas, Shane
• Application Number:
  US10/079,229
• Time in Patent Office: 1,126 Days
• Field of Search: 711/128, 711/136, 711/108, 711/133, 711/159, 711/160, 709/223, 709/224
• US Class Current: 711/128
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters

Abstract

Methods and apparatus are disclosed for maintaining netflow statistics using an associative memory to identify and maintain netflows. A lookup operation is performed on a set of associative memory entries to produce an associative memory result directly or after a subsequent memory read operation. In response to the associative memory result corresponding to a not found condition, an entry is added to the set of associative memory entries. Otherwise, a statistics entry in the set of statistics is updated based on the associative memory result. In one implementation, the associative memory is programmed with a set of permanent netflow entries and a set of dynamic or nonpermanent netflow entries, which are maintained in the form of a queue or ring buffer. In one embodiment, when the number of dynamic entries exceeds a threshold value, one or more of the dynamic entries and their corresponding statistics values are flushed.

Claims

1. A method comprising:

performing a lookup operation in an associative memory on a set of associative memory entries based on an item to generate an associative memory result directly or after a subsequent memory read operation;

evaluating the associative memory result;

in response to the associative memory result corresponding to a not found condition, adding an entry to the set of associative memory entries;

in response to the associative memory result corresponding to a found condition, updating a statistics entry in a set of statistics based on the associative memory result; and

in response to determining a number of entries within the set of associative memory entries exceeds a threshold, identifying a position of an oldest entry in the set of associative memory entries and after said identifying the position, retrieving a first statistics value corresponding to the position from the set of statistics;

wherein the set of associative memory entries is maintained as a queue.

2. The method of claim 1, wherein the item corresponds to a netflow, the netflow including a source address and a destination address, or the netflow including a source address, a destination address, and a port number.

3. The method of claim 1, further comprising adding or initializing an initial statistics value in the set of statistics in response to the associative memory result corresponding to the not found condition.

4. The method of claim 1, wherein the set of statistics is maintained in a second memory.

5. The method of claim 1, wherein the associative memory includes a binary or ternary content-addressable memory.

6. The method of claim 1, wherein said updating the statistics entry includes adding a byte count corresponding to the item to a current value of the statistics entry.

7. An apparatus comprising:

means for performing a lookup operation in an associative memory on a set of associative memory entries based on an item to generate an associative memory result after a subsequent memory read operation;

means for evaluating the associative memory result;

means for adding an entry to the set of associative memory entries in response to the associative memory result corresponding to a not found condition;

means for updating a statistics entry in a set of statistics based on the associative memory result in response to the associative memory result corresponding to a found condition; and

means for maintaining the set of associative memory entries as a queue.

8. The apparatus of claim 7, further comprising means for removing entries from the set of associative memory entries and for forwarding their corresponding statistics values from the set of statistics to a collection mechanism in response to a number of entries within the set of associative memory entries exceeding a threshold.

9. A method comprising:

programming an associative memory with a set of permanent associative memory entries within a set of associative memory entries;

initialing or adding a set of permanent statistic entries within a set of statistic entries in a memory device;

performing a lookup operation in the associative memory on the set of associative memory entries based on an item to generate an associative memory result directly or after a subsequent memory read operation;

evaluating the associative memory result;

in response to the associative memory result corresponding to a not found condition;

adding an entry to a set of nonpermanent associative memory entries within the set of associative memory entries; and

initializing or adding a corresponding initial statistics value to a set of nonpermanent statistics within the set of statistic entries;

in response to the associative memory result corresponding to a found condition, updating a statistics entry in the set of statistics based on the associative memory result; and

in response to an expiration of a timer, retrieving a plurality of statistics values from the set of statistics entries;

wherein the set of nonpermanent associative memory entries is maintained as a queue.

10. The method of claim 9, wherein the item corresponds to a netflow, the netflow including a source address and a destination address, or the netflow including a source address, a destination address, and a port number.

11. An apparatus comprising:

means for programming an associative memory with a set of permanent associative memory entries within a set of associative memory entries;

means for initializing a set of permanent statistic entries within a set of statistic entries in a memory device;

means for performing a lookup operation in the associative memory on the set of associative memory entries based on an item to generate an associative memory result directly or after a subsequent memory read operation;

means for evaluating the associative memory result;

means for adding an entry to a set of nonpermanent associative memory entries within the set of associative memory entries in response to the associative memory result corresponding to a not found condition;

means for updating a statistics entry in the set of statistics based on the associative memory result in response to the associative memory result corresponding to a found condition;

means for retrieving a plurality of statistics values from the set of statistics entries in response to an expiration of a timer; and

means for maintaining the set of nonpermanent associative memory entries as a queue.

12. The apparatus of claim 11, comprising means for removing an oldest entry from the set of nonpermanent associative memory entries in response to determining the number of entries within the set of nonpermanent associative memory entries exceeds a threshold.

13. A method comprising:

performing a lookup operation in an associative memory on a set of associative memory entries based on an item to generate an associative memory result directly or after a subsequent memory read operation;

evaluating the associative memory result;

in response to the associative memory result corresponding to a not found condition, adding an entry to the set of associative memory entries;

in response to the associative memory result corresponding to a found condition, updating a statistics entry in a set of statistics based on the associative memory result; and

in response to determining a number of entries within the set of associative memory entries exceeds a threshold, identifying a position of an oldest entry in the set of associative memory entries and after said identifying the position, retrieving a first statistics value corresponding to the position from the set of statistics;

wherein the set of associative memory entries is maintained as a ring buffer.

14. The method of claim 13, wherein the item corresponds to a netflow, the netflow including a source address and a destination address, or the netflow including a source address, a destination address, and a port number.

15. The method of claim 13, further comprising adding or initializing an initial statistics value in the set of statistics in response to the associative memory result corresponding to the not found condition.

16. The method of claim 13, wherein the set of statistics is maintained in a second memory.

17. The method of claim 13, wherein the associative memory includes a binary or ternary content-addressable memory.

18. The method of claim 13, wherein said updating the statistics entry includes adding a byte count corresponding to the item to a current value of the statistics entry.

19. An apparatus comprising:

means for performing a lookup operation in an associative memory on a set of associative memory entries based on an item to generate an associative memory result after a subsequent memory read operation;

means for evaluating the associative memory result;

means for adding an entry to the set of associative memory entries in response to the associative memory result corresponding to a not found condition;

means for updating a statistics entry in a set of statistics based on the associative memory result in response to the associative memory result corresponding to a found condition; and

means for maintaining the set of associative memory entries as a ring buffer.

20. The apparatus of claim 19, further comprising means for removing entries from the set of associative memory entries and for forwarding their corresponding statistics values from the set of statistics to a collection mechanism in response to a number of entries within the set of associative memory entries exceeding a threshold.

21. A method comprising:

programming an associative memory % with a set of permanent associative memory entries within a set of associative memory entries;

initializing or adding a set of permanent statistic entries within a set of statistic entries in a memory device;

performing a lookup operation in the associative memory on the set of associative memory entries based on an item to generate an associative memory result directly or after a subsequent memory read operation;

evaluating the associative memory result;

in response to the associative memory result corresponding to a not found condition;

adding an entry to a set of nonpermanent associative memory entries within the set of associative memory entries; and

initializing or adding a corresponding initial statistics value to a set of nonpermanent statistics within the set of statistic entries;

in response to the associative memory result corresponding to a found condition, updating a statistics entry in the set of statistics based on the associative memory result; and

in response to an expiration of a timer, retrieving a plurality of statistics values from the set of statistics entries;

wherein the set of nonpermanent associative memory entries is maintained as a ring buffer.

22. The method of claim 21, wherein the item corresponds to a netflow, the netflow including a source address and a destination address, or the netflow including a source address, a destination address, and a port number.

23. An apparatus comprising:

means for programming an associative memory with a set of permanent associative memory entries within a set of associative memory entries;

means for initializing a set of permanent statistic entries within a set of statistic entries in a memory device;

means for performing a lookup operation in the associative memory on the set of associative memory entries based on an item to generate an associative memory result directly or after a subsequent memory read operation;

means for evaluating the associative memory result;

means for adding an entry to a set of nonpermanent associative memory entries within the set of associative memory entries in response to the associative memory result corresponding to a not found condition;

means for updating a statistics entry in the set of statistics based on the associative memory result in response to the associative memory result corresponding to a found condition;

means for retrieving a plurality of statistics values from the set of statistics entries in response to an expiration of a timer; and

means for maintaining the set of nonpermanent associative memory entries as a ring buffer.

24. The apparatus of claim 23, comprising means for removing an oldest entry from the set of nonpermanent associative memory entries in response to determining the number of entries within the set of nonpermanent associative memory entries exceeds a threshold.