Determining Sampling Rate from Randomly Sampled Events

• US 20150089045A1
• Filed: 09/24/2013
• Published: 03/26/2015
• Est. Priority Date: 09/24/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agarwal, Kanak B., Carter, John B., Dixon, Colin K., Rasley, Jeffrey T.
• Granted Patent: US 9,401,853 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 49/208 Port mirroring

Abstract

Mechanisms are provided for determining an event rate. The mechanisms sample a sequence of events to generate a set of sampled events. At least a subset of the sampled events have associated event sequence values indicating a position of the sampled event within the sequence of events. The mechanisms group the sampled events into a plurality of event groups based on a common characteristic of the events. The mechanisms determine, for each event group, sequence values of sampled events associated with the event group. The mechanisms calculate, for each event group, an estimated event rate based on the sequence values of the sampled events associated with the event group and the total number of events in the sequence of events.

Claims

1. A method, in a data processing system comprising a processor and a memory, for determining an event rate, the method comprising:

sampling, by the data processing system, a sequence of events, to generate a set of sampled events, wherein at least a subset of the sampled events in the set of sampled events have associated event sequence values indicating a position of the sampled event within the sequence of events;

grouping, by the data processing system, the sampled events into a plurality of event groups based on a common characteristic of the events;

determining, by the data processing system, for each event group, sequence values of sampled events associated with the event group; and

calculating, by the data processing system, for each event group, an estimated event rate based on the sequence values of the sampled events associated with the event group and the total number of events in the sequence of events.

2. The method of claim 1, wherein the sequence of events corresponds to a quantum of time in a series of quanta of time, and wherein the method is implemented for each quantum of time in the series of quanta of time.

3. The method of claim 1, wherein the events are sampled data packets sampled from a network switch, and wherein the event groups are data flows through ports of a network switch from which the data packets are sampled.

4. The method of claim 3, wherein the sampled data packets are randomly sampled from data packets received by the network switch over one or more normal ports and which have been mirrored to a mirror port to achieve sampling of the data packets.

5. The method of claim 3, wherein the estimated event rate is a sampling rate for sampling data packets of the sequence of data packets, and wherein the method further comprises:

verifying an operation of a data packet sampling algorithm based on the calculated estimated sampling rate.

6. The method of claim 3, wherein sampling a sequence of events, to generate a set of sampled events comprises:

sampling data packets of a data flow through a normal port of a network forwarding device of a network, wherein the sampling is performed at least by configuring the network forwarding device to implement port mirroring of the normal port to a designated mirror port of the network forwarding device.

7. The method of claim 6, wherein the network forwarding device is a switch and wherein the switch comprises a plurality of normal ports that are mirrored to the designated mirror port.

8. The method of claim 1, wherein calculating an estimated event rate comprises:

determining for each event group, an estimate of a total number of events in the event group based on the sequence values of the sampled events in the corresponding event group;

combining, across the event groups, the estimates of a total number of events in the event groups to generate a sum total estimate of events in the sequence of events;

determining a total number of sampled events sampled from the sequence of events;

calculating a sampling rate for the sequence of events based on a relationship of the sum total estimate of events in the sequence of events to the total number of sampled events sampled from the sequence of events; and

determining the estimated event rate based on the sampling rate for the sequence of events.

9. The method of claim 8, wherein determining the estimated event rate based on the sampling rate for the sequence of events comprises calculating an estimate of a total number of events in the sequence of events based on product of the sampling, rate for the sequence of events and the total number of sampled events sampled from the sequence of events.

10. The method of claim 8, wherein the sequence of events corresponds to a quantum of time in a series of quanta of time, wherein the method is implemented for each quantum of time in the series of quanta of time, and wherein the method adjusts the determination of the estimated event rate for each subsequent quantum of time based on the sequence values of events in one or more of the previous quanta.

11. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive a sequence of events, wherein at least a subset of events in the sequence of events have associated event sequence values indicating a position of the event within the sequence of events;

group the events into a plurality of event groups based on a common characteristic of the events;

determine, for each event group, sequence values of events associated with the event group; and

calculate, for each event group, an estimated event rate based on a the sequence values of the events associated with the event group and the total number of events in the sequence of events.

12. The computer program product of claim 11, wherein the sequence of events corresponds to a quantum of time in a series of quanta of time, and wherein the method is implemented for each quantum of time in the series of quanta of time.

13. The computer program product of claim 11, wherein the events are sampled data packets sampled from a network switch, and wherein die event groups are data flows through ports of a network switch from which the data packets are sampled.

14. The computer program product of claim 13, wherein the sampled data packets are randomly sampled from data packets received by the network switch over one or more normal ports and which have been mirrored to a mirror port to achieve sampling of the data packets.

15. The computer program product of claim 13, wherein the estimated event rate is a sampling rate for sampling data packets of the sequence of data packets, and wherein the computer program product further causes the computing device to:

verify an operation of a data packet sampling algorithm based on the calculated estimated sampling rate.

16. The computer program product of claim 13, wherein the computer program product causes the computing device to sample a sequence of events, to generate a set of sampled events at least by:

sampling data packets of a data flow through a normal port of a network forwarding device of a network, wherein the sampling is performed at least by configuring the network forwarding device to implement port mirroring of the normal port to a designated mirror port of the network forwarding device.

17. The computer program product of claim 11, wherein the computer program product causes the computing device to calculate an estimated event rate at least by:

determining for each event group, an estimate of a total number of events in the event group based on the sequence values of the sampled events in the corresponding event group;

combining, across the event groups, the estimates of a total number of events in the event groups to generate a sum total estimate of events in the sequence of events;

determining a total number of sampled events sampled from the sequence of events;

calculating a sampling rate for the sequence of events based on a relationship of the sum total estimate of events in the sequence of events to the total number of sampled events sampled from the sequence of events; and

determining the estimated event rate based on the sampling rate for the sequence of events.

18. The computer program product of claim 17, wherein the computer readable program causes the computing device to determine the estimated event rate based on the sampling rate for the sequence of events at least by calculating an estimate of a total number of events in the sequence of events based on product of the sampling rate for the sequence of events and the total number of sampled events sampled from the sequence of events.

19. The computer program product of claim 17, wherein the sequence of events corresponds to a quantum of time in a series of quanta of time, wherein the computer readable program is executed by the computing device for each quantum of time in the series of quanta of time, and wherein the computer readable program further causes the computing device to adjust the determination of the estimated event rate for each subsequent quantum of time based on the sequence values of events in one or more of the previous quanta.

20. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

receive a sequence of events, wherein at least a subset of events in the sequence of events have associated event sequence values indicating a position of the event within the sequence of events;

group the events into a plurality of event groups based on a common characteristic of the events;

determine, for each event group, sequence values of events associated with the event group; and

calculate, for each event group, an estimated event rate based on a the sequence values of the events associated with the event group and the total number of events in the sequence of events.