Determining sampling rate from randomly sampled events

• US 10,009,236 B2
• Filed: 06/08/2016
• Issued: 06/26/2018
• 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.
• Primary Examiner(s): Taylor, Nicholas
• Assistant Examiner(s): Roy, Sanjoy
• Application Number:
  US15/176,316
• Publication Number:
  US 20160294647A1
• Time in Patent Office: 748 Days
• 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 estimated data packet rate, the method comprising:

receiving, from a network forwarding device, a set of sampled data packets from a sequence of data packets, via a mirror port of the network forwarding device, at least by performing a mirroring of data packets from a plurality of normal ports of the network forwarding device to the mirror port of the network forwarding device from which the data packets are randomly sampled as a result of a number of data packets mirrored to the mirror port exceeding a saturation limit of the mirror port, to generate the set of sampled data packets, wherein at least a subset of the sampled data packets in the set of sampled data packets have associated data packet sequence values indicating a position of the sampled data packets within the sequence of data packets;

grouping, by the data processing system, the sampled data packets of the set of sampled data packets into a plurality of data packet groups based on a common characteristic of the data packets;

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

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

2. The method of claim 1, wherein the sequence of data packets 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 network forwarding device is a network switch or network router, and wherein the data packet groups are data flows through normal ports of the network switch or network router from which the data packets are sampled.

4. The method of claim 1, wherein the estimated data packet 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.

5. The method of claim 1, wherein the network forwarding device is a switch and wherein the switch comprises a plurality of normal ports that are configured to be mirrored to the mirror port.

6. The method of claim 1, wherein calculating an estimated data packet rate comprises:

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

combining, across the data packet groups, the estimates of a total number of data packets in the data packet groups to generate a sum total estimate of data packets in the sequence of data packets;

determining a total number of sampled data packets sampled from the sequence of data packets;

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

determining the estimated data packet rate based on the sampling rate for the sequence of data packets.

7. The method of claim 6, wherein determining the estimated data packet rate based on the sampling rate for the sequence of data packets comprises calculating an estimate of a total number of data packets in the sequence of data packets based on a mathematical product of the sampling rate for the sequence of data packets and the total number of sampled data packets sampled from the sequence of data packets.

8. The method of claim 6, wherein the sequence of data packets 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 data packet rate for each subsequent quantum of time based on the sequence values of data packets in one or more of the previous quanta.

18. The method of claim 1, further comprising:

receiving, by the network forwarding device, a sequence of data packets via the plurality of normal ports;

mirroring, by the network forwarding device, data packets of the sequence of data packets to the mirror port;

dropping, by the network forwarding device, data packets that exceed the saturation limit of the mirror port such that the data packets not dropped are the set of sampled data packets; and

transmitting, by the network forwarding device, the set of sampled data packets to the data processing system.

19. The computer program product of claim 1, wherein a portion of the computer readable program is executed by the network forwarding device, and wherein the portion of the computer readable program causes the network forwarding device to:

receive a sequence of data packets via the plurality of normal ports;

mirror data packets of the sequence of data packets to the mirror port;

drop data packets that exceed the saturation limit of the mirror port such that the data packets not dropped are the set of sampled data packets; and

transmit the set of sampled data packets to the data processing system.

9. 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, from a network forwarding device comprising a plurality of normal ports and a mirror port, a set of sampled data packets from a sequence of data packets via the mirror port, wherein data packets of the set of sampled data packets are randomly sampled as a result of a number of data packets mirrored to the mirror port exceeding a saturation limit of the mirror port, and wherein at least a subset of data packets in the sequence of data packets have associated data packet sequence values indicating a position of the data packet within the sequence of data packets;

group the data packets into a plurality of data packet groups based on a common characteristic of the data packets;

determine, for each data packet group, sequence values of sampled data packets associated with the data packet group; and

calculate, for each data packet group, an estimated data packet rate based on the sequence values of the sampled data packets associated with the data packet group and the total number of data packets in the sequence of data packets.

10. The computer program product of claim 9, wherein the sequence of data packets 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.

11. The computer program product of claim 9, wherein the network forwarding device is a network switch or network router, and wherein the data packet groups are data flows through normal ports of the network switch or network router from which the data packets are sampled.

12. The computer program product of claim 11, wherein the estimated data packet 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.

13. The computer program product of claim 11, wherein the network forwarding device is a switch, and wherein the switch comprises a plurality of normal ports that are configured to be mirrored to the mirror port.

14. The computer program product of claim 9, wherein the computer program product causes the computing device to calculate an estimated data packet rate at least by:

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

combining, across the data packet groups, the estimates of a total number of data packets in the data packet groups to generate a sum total estimate of data packets in the sequence of data packets;

determining a total number of sampled data packets sampled from the sequence of data packets;

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

determining the estimated data packet rate based on the sampling rate for the sequence of data packets.

15. The computer program product of claim 14, wherein the computer readable program causes the computing device to determine the estimated data packet rate based on the sampling rate for the sequence of data packets comprises calculating an estimate of a total number of data packets in the sequence of data packets based on a mathematical product of the sampling rate for the sequence of data packets and the total number of sampled data packets sampled from the sequence of data packets.

16. The computer program product of claim 14, wherein the sequence of data packets 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 data packet rate for each subsequent quantum of time based on the sequence values of data packets in one or more of the previous quanta.

17. A system 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, from a network forwarding device comprising a plurality of normal ports and a mirror port, a set of sampled data packets from a sequence of data packets via the mirror port, wherein data packets of the set of sampled data packets are randomly sampled as a result of a number of data packets mirrored to the mirror port exceeding a saturation limit of the mirror port, and wherein at least a subset of data packets in the sequence of data packets have associated data packet sequence values indicating a position of the data packet within the sequence of data packets;

group the data packets into a plurality of data packet groups based on a common characteristic of the data packets;

determine, for each data packet group, sequence values of sampled data packets associated with the data packet group; and

calculate, for each data packet group, an estimated data packet rate based on the sequence values of the sampled data packets associated with the data packet group and the total number of data packets in the sequence of data packets.

20. The system of claim 17, further the network forwarding device, wherein the network forwarding device operates to:

receive a sequence of data packets via the plurality of normal ports;

mirror data packets of the sequence of data packets to the mirror port;

drop data packets that exceed the saturation limit of the mirror port such that the data packets not dropped are the set of sampled data packets; and

transmit the set of sampled data packets to the data processing system.