Systems for statistics gathering and sampling in a packet processing system

• US 7,936,687 B1
• Filed: 04/28/2004
• Issued: 05/03/2011
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Yip, Michael, Parker, David K.
• Primary Examiner(s): Moe, Aung S
• Assistant Examiner(s): Haile, Awet
• Application Number:
  US10/834,573
• Time in Patent Office: 2,561 Days
• Field of Search: 370/230, 370/232, 370/253, 370/379, 370/394, 370/428, 370/429, 370/252, 370242-247, 709/224, 725/14, 398/11
• US Class Current: 370/252
• CPC Class Codes: H04L 12/56 Packet switching systems
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A system for statistically sampling packets is described. In this system, upon or after the occurrence of a predefined statistical event in relation to a packet, a pseudo-random value is obtained and compared to a predetermined threshold. Responsive to this comparison, the system selectively arranges to have the packet statistically sampled. A system for compiling statistics for packets undergoing processing by a packet processing system is described. In this system, upon or after the occurrence of a predefined statistical event in relation to a packet, a cumulative index for the packet is updated to reflect the current processing cycle for the packet. Upon or after completion of processing of the packet, whereupon the cumulative index may reflect more than one processing cycle, packet statistics are updated responsive to the cumulative index for the packet. A second system for compiling statistics for packets undergoing processing by a packet processing system is described. In this system, upon or after a predefined statistical event in relation to a packet, a partial statistics update request is queued. A statistics processor monitors the update requests in the queue for completion. Upon or after completion of a statistics update request, the statistics processor updates packet statistics responsive to the completed update request.

Claims

1. A packet processing system comprising:

a receive side packet bus to receive a plurality of packets for processing by the packet processing system, wherein a population of network traffic undergoing packet processing by the packet processing system is represented by the plurality of packets;

statistical sampling logic to generate a statistically accurate representation of the population of network traffic undergoing processing by the packet processing system based on sampling a statistically significant subset of the plurality of packets received by the packet processing system, in which the sampled statistically significant subset of the plurality of packets corresponds to less than a whole of the population of network traffic;

a Linear Feedback Shift Register (LFSR) to identify the sampling of the statistically significant subset of the plurality of packets received based on an LFSR threshold, wherein the LFSR threshold corresponds to a percentage of the plurality of packets to be sampled in a pseudo-random fashion via the LFSR based on an expected variance among the plurality of packets, the LFSR threshold corresponding to a relatively higher percentage when the expected variance among the plurality of packets is expected to be substantial and the LFSR threshold corresponding to a relatively lower percentage when the expected variance among the plurality of packets is expected to not vary substantially; and

statistics compiling logic to maintain statistics of the plurality of packets received by the packet processing system based on the generated statistically accurate representation of the population of network traffic derived from the subset.

2. The system of claim 1, further comprising:

a first memory for holding data representative of at least a portion of each of the plurality of packets received or a state representative of each of the plurality of packets, or both;

key derivation logic for deriving a key from the data held in the first memory; and

packet processing logic for processing the packet responsive to the key, including searching a second memory for an entry having a tag portion that matches the key, and indicating a hit condition representing a statistical event when the entry having the tag is found.

3. The system of claim 1, further comprising:

packet marking logic to mark each of the plurality of packets received for statistical processing, wherein each packet marked is marked responsive to the packet being identified via the LFSR of the packet processing system as part of the statistically significant subset of the plurality of packets.

4. The system of claim 1, further comprising:

a plurality of processing cycles to process the plurality of packets in cycles, wherein at least one packet from the statistically significant subset of the plurality of packets appears within the subset of the plurality of packets more than one time, each occurrence corresponding to a distinct cycle of the plurality of processing cycles.

5. The system of claim 1, further comprising:

completion logic to receive a partial statistics update request from a packet processor of the packet processing system and to further complete a partial statistics update responsive to the request.

6. In a packet processing system a method comprising:

receiving, via a receive side packet bus of the packet processing system, a plurality of packets for processing by the packet processing system, wherein a population of network traffic undergoing packet processing by the packet processing system is represented by the plurality of packets;

generating, via statistical sampling logic of the packet processing system, a statistically accurate representation of the population of network traffic undergoing processing by the packet processing system based on sampling a statistically significant subset of the plurality of packets received by the packet processing system, in which the sampled statistically significant subset of the plurality of packets corresponds to less than a whole of the population of network traffic;

identifying, via a Linear Feedback Shift Register (LFSR) of the packet processing system, the sampling of the statistically significant subset of the plurality of packets received based on an LFSR threshold, wherein the LFSR threshold corresponds to a percentage of the plurality of packets to be sampled in a pseudo-random fashion via the LFSR based on an expected variance among the plurality of packets, the LFSR threshold corresponding to a relatively higher percentage when the expected variance among the plurality of packets is expected to be substantial and the LFSR threshold corresponding to a relatively lower percentage when the expected variance among the plurality of packets is ex ectecl to not vary substantially; and

maintaining, via statistics compiling logic of the packet processing system, statistics of the plurality of packets received by the packet processing system based on the generated statistically accurate representation of the population of network traffic derived from the subset.

7. The method of claim 6 further comprising detecting the occurrence of a statistical event.

8. The method of claim 7 wherein detecting the occurrence of the statistical event comprises, for each of the plurality of packets received:

generating a key from the packet,

processing the packet responsive to the key including searching for an entry in a memory having a tag portion that matches the key, and

detecting the occurrence of the statistical event when an entry having a tag portion matching the key is found in the memory.

9. The method of claim 6, further comprising, for each of the plurality of packets received:

marking each packet for statistical processing responsive to the packet being identified, via the LFSR of the packet processing system, as part of the statistically significant subset of the plurality of packets.

10. The method of claim 6, further comprising:

processing the plurality of packets in cycles, wherein at least one packet from the statistically significant subset of the plurality of packets appears within the subset of the plurality of packets more than one time, each occurrence corresponding to a distinct cycle of processing.

11. The method of claim 6, further comprising:

receiving a partial statistics update request from a packet processor of the packet processing system; and

completing, via completion logic of the packet processing system, a partial statistics update responsive to the request.

12. A non-transitory computer-readable storage medium having instructions stored thereon that, when executed by a processor of a packet processing system, the instructions cause the packet processing system to perform a method comprising:

receiving a plurality of packets for processing by the packet processing system, wherein a population of network traffic undergoing packet processing by the packet processing system is represented by the plurality of packets;

generating a statistically accurate representation of the population of network traffic undergoing processing by the packet processing system based on sampling a statistically significant subset of the plurality of packets received by the packet processing system, in which the sampled statistically significant subset of the plurality of packets corresponds to less than a whole of the population of network traffic;

identifying, via a Linear Feedback Shift Register (LFSR) of the packet processing system, the sampling of the statistically significant subset of the plurality of packets received based on an LFSR threshold, wherein the LFSR threshold corresponds to a percentage of the plurality of packets to be sampled in a pseudo-random fashion via the LFSR based on an expected variance among the plurality of packets, the LFSR threshold corresponding to a relatively higher percentage when the expected variance among the plurality of packets is expected to be substantial and the LFSR threshold corresponding to a relatively lower percentage when the expected variance among the plurality of packets is expected to not vary substantially; and

maintaining statistics of the plurality of packets received by the packet processing system based on the generated statistically accurate representation of the population of network traffic derived from the subset.

13. The non-transitory computer-readable storage medium of claim 12, wherein the method further comprises:

detecting the occurrence of the a statistical event.

14. The non-transitory computer-readable storage medium of claim 13 wherein detecting the occurrence of the statistical event comprises, for each of the plurality of packets received:

generating a key from the packet;

processing the packet responsive to the key including searching for an entry in a memory having a tag portion that matches the key; and

detecting the occurrence of the statistical event when an entry having a the tag portion matching the key is found in the memory.

15. The non-transitory computer-readable storage medium of claim 12, wherein the method further comprises, for each of the plurality of packets received:

marking each packet for statistical processing responsive to the packet being identified, via the LFSR of the packet processing system, as part of the statistically significant subset of the plurality of packets.

16. The non-transitory computer-readable storage medium of claim 12, wherein the method further comprises:

processing the plurality of packets in cycles, wherein at least one packet from the statistically significant subset of the plurality of packets appears within the subset of the plurality of packets more than one time, each occurrence corresponding to a distinct cycle of processing.

17. The non-transitory computer-readable storage medium of claim 12, wherein the method further comprises:

receiving a partial statistics update request from a packet processor of the packet processing system; and

completing, via completion logic of the packet processing system, a partial statistics update responsive to the request.