Determining sampling rate from randomly sampled events

Patent metadata

Field	Value
Publication number	US-9401853-B2
Application number	US-201314034862-A
Country	US
Kind code	B2
Filing date	Sep 24, 2013
Priority date	Sep 24, 2013
Publication date	Jul 26, 2016
Grant date	Jul 26, 2016

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.

First claim

What is claimed is:

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 forwar

Assignees

• IBM

Inventors

• Agarwal Kanak B
• Carter John B
• Dixon Colin K
• Rasley Jeffrey T

Classifications

• H04L49/208

  Port mirroring · CPC title

• H04L43/04

  Processing captured monitoring data, e.g. for logfile generation · CPC title

• H04L43/0894

  Packet rate · CPC title

• H04L43/024 Primary

  by adaptive sampling · CPC title