Method and system for identifying congestion and anomalies in a network

• US 6,684,247 B1
• Filed: 04/04/2000
• Issued: 01/27/2004
• Est. Priority Date: 04/04/2000
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures II LLC (Intellectual Ventures LLC)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Weerahandi, Samaradasa, Martija, Ricardo, Santos, Elisa M.
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Mirza, Adnan
• Application Number:
  US09/542,301
• Time in Patent Office: 1,393 Days
• Field of Search: 709/223, 709/224, 709/225, 709/226, 703/2
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

Methods and systems are provided for identifying congestion and anomalies at individual nodes, links, and segments in a network. In accordance with an embodiment of the invention, a monitoring station determines for each link in the network a statistical model based on a harmonic analysis. The monitoring station collects from each link metric data. The monitoring station then selects for each link a model that includes one or more harmonic components. By estimating parameters of the harmonic components, the monitoring station then captures the periodicity of the collected metric data in the harmonic components of the model. The monitoring station uses the model to estimate the state of the network from which estimated values of the metric data are determined. The monitoring station then determines whether congestion or anomalies exist in the links based on the estimated metrics.

Claims

1. A method for identifying a congestion or an anomaly in a network, said method comprising the steps of:

determining a statistical model based on a harmonic analysis;

estimating a metric associated with one of a link, a node, or a segment in the network based on the determined model;

identifying one or more congestion or anomalies in the link, node, or segment based on the estimated metric; and

wherein the determining step comprises the steps of

collecting metric data from the network;

selecting a model that includes one or more harmonic components; and

capturing a periodicity of the collected data in the harmonic components of the selected model.

2. The method of claim 1, wherein the estimating step comprises the step of estimating behavior of the metric based on the determined model.

3. A method for identifying a congestion or an anomaly in a network, said method comprising the steps of:

determining a statistical model based on a harmonic analysis;

estimating a metric associated with one of a link, node, or segment in the network based on the determined model; and

identifying one or more congestion or anomalies in the link, node, or segment based on the metric,

wherein the determining step comprises the steps of collecting from the network data relating to the metric;

selecting a model that includes one more harmonic components; and

capturing periodicity of the collected data in the harmonic components of the selected model, said capturing step comprising the steps of

dividing a frequency range into a plurality of intervals;

determining a plurality of Fourier frequencies;

determining values of a periodogram associated with the determined Fourier frequencies, respectively;

classifying the determined Fourier frequencies according to the intervals;

identifying in each of the intervals the determined values of the periodogram that are highest;

selecting the classified Fourier frequencies that correspond to the identified highest values and that are statistically significant; and

estimating values of parameters of the harmonic components based on the collected data.

4. A method for identifying a congestion in a network, said method comprising the steps of:

determining a statistical model based on a harmonic analysis;

estimating a metric associated with one of a link, node, or segment in the network based on the determined model; and

identifying a congestion in the link, node, or segment based on the estimated metric, said step of identifying a congestion comprising the steps of

determining an average of the metric based on the determined model;

determining a variance of the metric based on the determined model;

determining a z-value based on the average, the variance, and a predetermined threshold;

determining a p-value corresponding to the determined z-value; and

identifying the congestion when the p-value is smaller than a predetermined significance.

5. A method for identifying an anomaly in a network, said method comprising the steps of:

determining a statistical model based on a harmonic analysis;

estimating a metric associated with one of a link, a node, or a segment in the network based on the determined model; and

identifying an anomaly in the link, node, or segment based on the estimated metric, the step of identifying an anomaly comprising the steps of

determining a difference between a measured metric and the estimated metric;

determining a first diagnostic for detecting a persistent step change in the measured metric based on the determined difference;

determining a second diagnostic for detecting a persistent slope change in the measured metric based on the determined difference;

determining a first p-value associated with the first diagnostic;

determining a second p-value associated with the second diagnostic; and

identifying the anomaly when the first p-value or the second p-value is smaller than a predetermined significance.

6. A method for identifying a congestion or an anomaly in a network, said method comprising the steps of:

receiving metric data associated with one of one or more links, nodes, or segments in the network;

capturing a periodicity of the received metric data in a statistical model that includes harmonic components;

estimating metric data associated with the links, nodes, or segments in the network based on the statistical model; and

identifying one or more congestion or anomalies in one of the one more of the links, nodes or segments based on the estimated metric data.

7. A computer-readable medium capable of configuring a computer to perform a method for identifying a congestion or an anomaly in a network, said method comprising the steps of:

determining a statistical model based on a harmonic analysis by collecting from the network data relating to a metric associated with one of a link, node, or segment in the network, selecting a model that includes one or more harmonic components, and capturing a periodicity of the collected data in the harmonic components of the selected model;

estimating one or more metrics associated with one of one of the one or more links, nodes or segments in the network based on the determined statistical model; and

identifying one or more congestion or anomalies in the links, nodes, or segments based on the estimated metrics.

8. A system for identifying a congestion or an anomaly in a network, said system comprising:

a memory including code for determining a statistical model based on a harmonic analysis, for estimating one or more metrics associated with one of one or more links, nodes, or segments in the network based on the determined statistical model, and for identifying one or more congestion or anomalies in the links, nodes, or segments based on the estimated metrics; and

a processor for running the code.