Determining sampling rate from randomly sampled events

• US 9,401,853 B2
• Filed: 09/24/2013
• Issued: 07/26/2016
• Est. Priority Date: 09/24/2013
• Status: Expired due to Fees

• 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.
• Primary Examiner(s): Taylor, Nicholas
• Assistant Examiner(s): Roy, Sanjoy
• Application Number:
  US14/034,862
• Publication Number:
  US 20150089045A1
• Time in Patent Office: 1,036 Days
• US Class Current: 1/1
• 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, wherein;

the events are sampled data packets and wherein receiving the sequence of events comprises sampling the data packets from a network switch or network router,

the sampled data packets are sampled at least by performing mirroring of data packets from a plurality of normal ports of the network switch or network router to a mirror port from which the data packets are sampled,

the event groups are data flows through the plurality of normal ports of the network switch or network router thereby representing a plurality of data flows,

all data packets flowing through the plurality of normal ports are mirrored to the mirror port and a random amount of data packets are sampled from each normal port of the plurality of normal ports as a result of the mirroring based on a data flow rate of the data flow flowing through the normal port and a saturation limit of the mirror port, wherein data packets mirrored to the mirror port in excess of the saturation limit of the mirror port are dropped while data packets mirrored to the mirror port equal to or less than the saturation limit are sampled, and

calculating the estimated event rate comprises estimating a total number of data packets flowing through each data flow in the plurality of data flows based on an estimate of data packets dropped due to oversaturation of the mirror port.

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 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 sampling rate.

4. 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 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.

5. The method of claim 4, 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.

6. The method of claim 4, 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.

7. A computer program product comprising a non-transitory computer readable 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 the sequence values of the events associated with the event group and the total number of events in the sequence of events, wherein;

the events are sampled data packets and wherein receiving the sequence of events comprises sampling the data packets from a network switch or network router,

the sampled data packets are sampled at least by performing mirroring of data packets from a plurality of normal ports of the network switch or network router to a mirror port from which the data packets are sampled,

the event groups are data flows through the plurality of normal ports of the network switch or network router thereby representing a plurality of data flows,

all data packets flowing through the plurality of normal ports are mirrored to the mirror port and a random amount of data packets are sampled from each normal port of the plurality of normal ports as a result of the mirroring based on a data flow rate of the data flow flowing through the normal port and a saturation limit of the mirror port, wherein data packets mirrored to the mirror port in excess of the saturation limit of the mirror port are dropped while data packets mirrored to the mirror port equal to or less than the saturation limit are sampled, and

calculating the estimated event rate comprises estimating a total number of data packets flowing through each data flow in the plurality of data flows based on an estimate of data packets dropped due to oversaturation of the mirror port.

8. The computer program product of claim 7, 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.

9. The computer program product of claim 7, 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.

10. The computer program product of claim 7, wherein the estimated event rate is a calculated estimated 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 sampling rate.

11. The computer program product of claim 7, 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.

12. The computer program product of claim 7, 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 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.

13. The computer program product of claim 12, 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.

14. The computer program product of claim 12, 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.

15. 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 the sequence values of the events associated with the event group and the total number of events in the sequence of events, wherein;

the events are sampled data packets and wherein receiving the sequence of events comprises sampling the data packets from a network switch or network router,

the sampled data packets are sampled at least by performing mirroring of data packets from a plurality of normal ports of the network switch or network router to a mirror port from which the data packets are sampled,

the event groups are data flows through the plurality of normal ports of the network switch or network router thereby representing a plurality of data flows,

all data packets flowing through the plurality of normal ports are mirrored to the mirror port and a random amount of data packets are sampled from each normal port of the plurality of normal ports as a result of the mirroring based on a data flow rate of the data flow flowing through the normal port and a saturation limit of the mirror port, wherein data packets mirrored to the mirror port in excess of the saturation limit of the mirror port are dropped while data packets mirrored to the mirror port equal to or less than the saturation limit are sampled, and

calculating the estimated event rate comprises estimating a total number of data packets flowing through each data flow in the plurality of data flows based on an estimate of data packets dropped due to oversaturation of the mirror port.