Back to results
US 8,078,710 B2Granted
Method and apparatus for monitoring functions of distributed data
AssigneeAT&T Intellectual Property I, L.P.
InventorsGraham Cormode, Ke Yi
Life of this patent
Estimating the term…
Abstract
This invention discloses continuous functional monitoring of distributed network activity using algorithms based on frequency moment calculations given by Fp=Σimip. The frequency moment calculations are used to raise an alarm when a value exceeds a certain threshold. Frequency moments for p=0, 1, and 2 are described.
Claims20
A method of monitoring computer network activity comprising:
- reporting a selected network activity by a plurality of remote devices using a frequency moment Fp determined in accordance with
- Fp=Σimip
- where p represents an order of the frequency moment of 0, 1, or 2, i representing the selected network activity, and mi representing a dataset comprising a frequency associated with the selected network activity i from the plurality of remote devices;
- and
- providing a notification in response to Fp≧τ, where τ is a threshold value in response to the order of the frequency moment being 2, the frequency moment F2 being calculated in two phases of rounds, sketch algorithms being calculated to determine an estimate of a current norm of vectors, the plurality of remote devices sending a bit to a coordinator in response to a local vector exceeding a pre-determined bit threshold, the sketches being collected from each of the plurality of remote devices in response to receiving a pre-determined number of bits;
- causing the estimate of the current frequency moment F2 to exceed a pre-determined fraction of a global threshold in response to a summation of the sketches,
- dividing each round into sub-rounds, where each sub-round is completed on the receipt of a pre-determined threshold of a number of bits;
- transmitting an approximate sketch to the coordinator on the completion of each sub-round;
- initiating a new sub-round in response to the approximate sketch being less than a pre-defined threshold;
- changing an output value of the coordinator;
- and
- terminating the algorithm in response to the approximate sketch being equal to or exceeding the pre-defined threshold.
9 more elements
A method of monitoring computer network activity comprising:
- reporting a selected network activity by a plurality of remote devices using a frequency moment Fp determined in accordance with
- Fp=Σimip
- where p represents an order of the frequency moment of 0, 1, or 2, i representing the selected network activity, and mi representing a dataset comprising a frequency associated with the selected network activity i from the plurality of remote devices;
- and
- providing a notification in response to Fp≧τ, where τ is a threshold value, wherein the frequency moment is F2, the frequency moment calculation proceeding in two phases of rounds, comprising
- (a) a first phase with one sub-round per round, wherein a coordinator collects sketches from each device with a communication cost based on the number of devices;
- (i) the coordinator ends the round and computes a new threshold of sketches required to end a round, in response to the number of sketches equaling or exceeding a pre-determined threshold;
- (ii) the calculation proceeding to phase two in response to the new threshold equaling or exceeding the previous threshold by a predetermined fraction, otherwise another round of the first phase is performed;
- and
- (iii) first phase rounds are performed until the threshold permits advancing to the second phase;
- and
- (b) a second phase wherein the coordinator collects sketches from remote sites with a communication cost based on the number of remote devices divided by an error factor;
- and where
- (i) the remote sites continuously monitor the selected activity, and transmit sketches to the coordinator in response to the activity exceeding a pre-defined threshold;
- and
- (ii) when the server receives a number of sketches equal to the number of remote devices, a sub-round is completed and the remote sites transmit an approximate sketch to the coordinator;
- (iii) the coordinator starts a new sub-round in response to the approximate sketch being less than or equal to a pre-defined threshold;
- (iv) the coordinator ending the round in response to the approximate sketch being greater than a pre-defined threshold, and the coordinator setting an output value to 1 and the method terminating in response to the number of sketches exceeding the threshold of sketches required to end the algorithm.
15 more elements
A non-transient computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to:
- report a selected network activity by a plurality of remote devices using a frequency moment Fp determined in accordance with
- Fp=Σimip
- where p represents an order of the frequency moment of 0, 1, or 2, i representing the selected network activity, and mi representing a dataset comprising a frequency associated with the selected network activity i from the plurality of remote devices;
- and
- provide a notification in response to Fp≧τ, where τ is a threshold value in response to the order of the frequency moment being 2, the frequency moment F2 being calculated in two phases of rounds, sketch algorithms being calculated to determine an estimate of a current norm of vectors, the plurality of remote devices sending a bit to a coordinator in response to a local vector exceeding a pre-determined bit threshold, the sketches being collected from each of the plurality of remote devices in response to receiving a pre-determined number of bits;
- cause the estimate of the current frequency moment F2 to exceed a pre-determined fraction of a global threshold in response to a summation of the sketches;
- divide each round into sub-rounds, where each sub-round is completed on the receipt of a pre-determined threshold of a number of bits;
- transmit an approximate sketch to the coordinator on the completion of each sub-round;
- initiate a new sub-round in response to the approximate sketch being less than a pre-defined threshold;
- initiate a change in an output value of the coordinator;
- and
- terminate the algorithm in response to the approximate sketch being equal to or exceeding the pre-defined threshold.
9 more elements
Dependencies are inferred from the claim text.