Method and apparatus for monitoring functions of distributed data

• US 8,307,080 B2
• Filed: 11/23/2011
• Issued: 11/06/2012
• Est. Priority Date: 12/21/2007
• Status: Active Grant

• Current Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Yi, Ke
• Primary Examiner(s): Nguyen, Thuong
• Application Number:
  US13/303,996
• Publication Number:
  US 20120066383A1
• Time in Patent Office: 349 Days
• Field of Search: 709/224, 707/758, 715/736, 714/47.2
• US Class Current: 709/224
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A method and system of monitoring computer network activity including determining a first phase frequency estimate, associated with a first frequency vector, determined in response to receiving first bits from a first plurality of remote computer network devices. The first bits received from the first plurality of remote devices in response to satisfying a first activity threshold. Also, determining a second phase frequency estimate associated with a second frequency vector and determined in response to receiving second bits from a second plurality of remote devices. The second bits received from the second plurality of remote devices in response to a second activity threshold being satisfied. The second phase frequency estimate determined in response to the first phase frequency estimate exceeding a global threshold. Further, providing a frequency moment F_p in response to the second phase frequency estimate exceeding a refined threshold.

Claims

1. A method of monitoring computer network activity comprising:

determining a first phase estimate of a second order frequency moment corresponding to activity associated with a plurality of remote computer network devices, the first phase estimate being determined by calculating a first sum of estimates of first frequency vectors received from the plurality of remote computer network devices, the first phase estimate determined in response to receiving a first quantity of bits from the plurality of remote computer network devices, the first quantity of bits being received from the plurality of remote computer network devices in response to a first activity threshold being satisfied, the first activity threshold being associated with the activity associated with the plurality of remote computer network devices;

determining a second phase estimate of the second order frequency moment, the second phase estimate being determined by calculating a second sum of estimates of second frequency vectors received from the plurality of remote computer network devices, the second phase estimate determined in response to receiving a second quantity of bits from the plurality of remote computer network devices, the second quantity of bits being received in response to a second activity threshold being satisfied, the second activity threshold being associated with the activity associated with the plurality of remote computer network devices, the second phase estimate being determined in response to the first phase estimate exceeding a pre-determined fraction of a global threshold; and

providing an alarm in response to the second order frequency moment exceeding the global threshold.

2. The method of claim 1, wherein at least one of the first and second activity thresholds are at least partially generated randomly.

3. The method of claim 1, wherein the first and second activity thresholds are satisfied by individual remote computer network devices.

4. The method of claim 1, wherein the pre-determined fraction of the global threshold is greater than 1.

5. The method of claim 1, wherein the first and second quantity of bits represents a quantity of remote computer network devices.

6. The method of claim 1, wherein the first activity threshold represents a communication cost and the second activity threshold represents the communication cost divided by an error factor.

7. The method of claim 1, wherein determining the second phase estimate of the second order frequency moment further comprises receiving, prior to receipt of the second frequency vectors, a third sum of estimates of third frequency vectors from the plurality of remote computer network devices, the third sum of estimates of third frequency vectors being less than the global threshold.

8. A non-transitory computer-readable storage medium storing instructions that, when executed by a processing device, cause the processing device to provide an alarm associated with a computer network activity by performing a computer process comprising:

determining a first phase estimate of a second order frequency moment corresponding to activity associated with a plurality of remote computer network devices, the first phase estimate being determined by calculating a first sum of estimates of first frequency vectors received from the plurality of remote computer network devices, the first phase estimate determined in response to receiving a first quantity of bits from the plurality of remote computer network devices, the first quantity of bits being received from the plurality of remote computer network devices in response to a first activity threshold being satisfied, the first activity threshold being associated with the activity associated with the plurality of remote computer network devices;

determining a second phase estimate of the second order frequency moment, the second phase estimate being determined by calculating a second sum of estimates of second frequency vectors received from the plurality of remote computer network devices, the second phase estimate determined in response to receiving a second quantity of bits from the plurality of remote computer network devices, the second quantity of bits being received in response to a second activity threshold being satisfied, the second activity threshold being associated with the activity associated with the plurality of remote computer network devices, the second phase estimate being determined in response to the first phase estimate exceeding a pre-determined fraction of a global threshold; and

providing an alarm in response to the second order frequency moment exceeding the global threshold.

9. The non-transitory computer-readable storage medium according to claim 8, wherein at least one of the first and second activity thresholds are at least partially generated randomly.

10. The non-transitory computer-readable storage medium according to claim 8, wherein the first and second activity thresholds are satisfied by individual remote computer network devices.

11. The non-transitory computer-readable storage medium according to claim 8, wherein the pre-determined fraction of the global threshold is greater than 1.

12. The non-transitory computer-readable storage medium according to claim 8, wherein the first and second quantity of bits represents a quantity of remote computer network devices.

13. The non-transitory computer-readable storage medium according to claim 8, wherein the first activity threshold represents a communication cost and the second activity threshold represents the communication cost divided by an error factor.

14. The non-transitory computer-readable storage medium according to claim 8, wherein determining the second phase estimate of the second order frequency moment further comprises receiving, prior to receipt of the second frequency vectors, a third sum of estimates of third frequency vectors from the plurality of remote computer network devices, the third sum of estimates of third frequency vectors being less than the global threshold.

15. A system to monitor computer network activity, the system comprising:

a user interface;

a processing device operatively coupled to the user interface and a computer network the computer network including remote computer network devices; and

a computer-readable storage medium storing instructions that, when executed by the processing device, cause the processing device to provide an alarm associated with a computer network activity by performing a computer process comprising;

determining a first phase estimate of a second order frequency moment corresponding to activity associated with a plurality of remote computer network devices, the first phase estimate determined in response to receiving a first quantity of bits from the plurality of remote computer network devices, the first quantity of bits being received from the plurality of remote computer network devices in response to a first activity threshold being satisfied, the first activity threshold being associated with the activity associated with the plurality of remote computer network devices, the first phase estimate being determined by summing sketches of first frequency vectors received from the plurality of remote computer network devices;

determining a second phase estimate of the second order frequency moment, the second phase estimate being determined by summing sketches of second frequency vectors received from the plurality of remote computer network devices, the second phase estimate determined in response to receiving a second quantity of bits from the plurality of remote computer network devices, the second quantity of bits being received in response to a second activity threshold being satisfied, the second activity threshold being associated with the activity associated with the plurality of remote computer network devices, the second phase estimate being determined in response to the first phase estimate exceeding a pre-determined fraction of a global threshold; and

providing an alarm in response to the second order frequency moment exceeding the global threshold.

16. The system as defined by claim 15, wherein at least one of the first and second activity thresholds are at least partially generated randomly.

17. The system as defined by claim 15, wherein the first and second activity thresholds are satisfied by individual remote computer network devices.

18. The system as defined by claim 15, wherein the first and second quantity of bits represents a quantity of remote computer network devices.

19. The system as defined by claim 15, wherein determining the second phase estimate of the second order frequency moment further comprises receiving, prior to receipt of the second frequency vectors, a third sum of estimates of third frequency vectors from the plurality of remote computer network devices, the third sum of estimates of third frequency vectors being less than the global threshold.