METHODS, SYSTEMS, AND COMPUTER PROGRAM PRODUCTS EXTRACTING NETWORK BEHAVIORAL METRICS AND TRACKING NETWORK BEHAVIORAL CHANGES

• US 20090106174A1
• Filed: 10/18/2007
• Published: 04/23/2009
• Est. Priority Date: 10/18/2007
• Status: Active Grant

• Current Assignee: Viavi Solutions, Inc. (Lumentum Holdings Inc.)
• Original Assignee: Trendium, Inc (Lumentum Holdings Inc.)
• Inventors: Battisha, Mohamed, Meleis, Hanafy, Richardson, Kevin, Samineni, Satya, Serghini, Salah
• Granted Patent: US 8,028,061 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/0856 by backing up or archiving configuration information
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/5054 Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/06 Generation of reports

Abstract

A network behavioral metric is extracted from a communication network based on a relevancy of the metric to network behavior by identifying a network metric x that is defined as a random variable that represents a quantitative measure of a network behavior accumulated over a period of time, selecting a network feature, generating a metric disintegration model for the network metric x comprising at least one normal behavior probability distribution function for the metric x for each value of the network feature, respectively, and at least one abnormal behavior probability distribution function for the metric x for each value of the network feature, respectively, increasing a number of the values of the metric x that indicates normal network behavior and/or abnormal network behavior based on the metric disintegration model, and selecting a network metric x as a behavioral metric based on a relevancy η of the network metric x to the network behavior. Embodiments for tracking network behavioral changes are also provided.

Claims

1. A method of extracting a communication network behavioral metric based on a relevancy of the metric to network behavior, comprising:

identifying a network metric x that is defined as a random variable that represents a quantitative measure of a network behavior accumulated over a period of time;

selecting a network feature;

generating a metric disintegration model for the network metric x comprising at least one normal behavior probability distribution function for the metric x for each value of the network feature, respectively, and at least one abnormal behavior probability distribution function for the metric x for each value of the network feature, respectively;

increasing a number of the values of the metric x that indicates normal network behavior and/or abnormal network behavior based on the metric disintegration model; and

selecting a network metric x as a behavioral metric based on a relevancy η

of the network metric x to the network behavior;

wherein the relevancy η

is given as follows;

$\mathrm{\eta <br><br>}=\frac{<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sn}}<br><br>+<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sa}}<br><br>}{<br><br>\mathrm{\Phi <br><br>}<br><br>}$

Φ

is a sample space of all possible values of x;

Φ

_sn is a subset of Φ

based on the values of x that indicates normal network behavior;

Φ

_sa is a subset of Φ

based on the values of x that indicates abnormal network behavior.

2. The method of claim 1, wherein the network metric x is selected from one of a plurality of metric categories comprising volume of network activity metrics, network performance characteristic metrics, network fault metrics, network element activity log metrics, and/or user audit log metrics.

3. The method of claim 2, wherein the network feature is selected from one of a plurality of feature categories network specific features, network independent features, network exterior behavioral element features, and time machine features.

4. The method of claim 3, further comprising:

analyzing the network and its interfaces with external neighbors to identify behavioral elements;

assigning each of the identified behavioral elements to one of the plurality of metric categories and/or plurality of feature categories; and

identifying any parent-child relationships between behavioral elements in each of the plurality of metric categories and plurality of feature categories.

5. The method of claim 4, further comprising:

for each behavioral element in the plurality of metric categories examining each of the behavioral elements in each of the plurality of feature categories to determine if the examined feature category behavioral element can be used in the metric disintegration model for that metric category behavioral element.

6. A method for tracking network behavioral changes, comprising:

selecting a network metric x that is defined as a random variable that represents a quantitative measure of a network behavior accumulated over a period of time;

predicting a current value F_t of the network metric x using an Adaptive Exponentially Weighted Moving-Average (AEWMA) formula as follows;

F_t=F_t-1+λ

_te_t, where

e_t=x_t−

F_t-1, and

λ

_t is a weight parameter;

determining an upper and a lower control limit for network metric x based on a previously estimated value F_t-1 of the network metric x;

observing the current value for the network metric x_t;

determining that the network'"'"'s behavior is normal if the current value for the network metric x_t does not fall outside the upper and the lower control limits; and

determining that the network'"'"'s behavior is abnormal if the current value for the network metric x_t falls outside the upper and the lower control limits.

7. The method of claim 6, further comprising:

generating a Tracking Signal (TS_t) based on the forecasting error;

determining a backward difference ∇

TS_t as follows if the network'"'"'s behavior is determined to be normal;

∇

TS_t=TS_t−

TS_t-1;

determining if the backward difference ∇

TS_t switches signs from a previously generated backward difference;

setting the weight parameter λ

_t to TS_t if backward difference switches signs; and

setting the weight parameter λ

_t to one of {λ

_tp or λ

_t or λ

_tn} so as to minimize e_tp, e_t, and e_tn below;

F_tp=λ

_tpe_t+F_tp-1;

F_t=λ

_te_t+F_t-1;

F_tn=λ

_tne_t+F_tn-1;

where λ

_tp=(λ

_t+δ

) and λ

_tn=(λ

_t−

δ

);

F_t-1 is a predicted current value of the network metric x;

e_tp=(x_t−

F_tp-1);

e_t=(x_t−

F_t-1);

e_tn=(x_t−

F_tn-1);

δ

is selected from the set {0.25, 0.20, 0.15, 0.10, 0.05, 0.03, 0.00}.

8. The method of claim 7, wherein TS_t is given by the following equation:

${\mathrm{TS}}_t=<br><br>\frac{E_t}{{\mathrm{MAD}}_t}<br><br>;<br><br>$

where E_t=δ

e_t+(1−

β

)E_t-1;

MAD_t=β

|e_t|+(1−

β

)MAD_t-1;

0<

β

<

1.

9. The method of claim 6, wherein the upper and the lower control limits for the network metric x are given by the following equation:

F_t-1±

K_TSd_t-1;

where K_TS is a multiplication constant;

d_t=γ

|x_t−

F_t-1|+(1−

γ

)d_t-1;

where d_t is a predicted deviation, and γ

is a weight constant;

0<

γ

<

1.0.

10. The method of claim 6, further comprising:

signaling that the network'"'"'s behavior is abnormal when the network'"'"'s behavior is determined to be abnormal; and

reporting the abnormal period of network behavior upon determining that the network'"'"'s behavior has returned to normal.

11. The method of claim 10, further comprising:

performing a real time analysis of traffic on the network responsive to the signal that the network'"'"'s behavior is abnormal.

12. The method of claim 6, wherein selecting the network metric x comprises:

selecting a network feature;

generating a metric disintegration model for the network metric x comprising at least one normal behavior probability distribution function for the metric x for each value of the network feature, respectively, and at least one abnormal behavior probability distribution function for the metric x for each value of the network feature, respectively;

increasing a number of the values of the metric x that indicates normal network behavior and/or abnormal network behavior based on the metric disintegration model;

selecting the network metric x as a behavioral metric based on a relevancy η

of the network metric x to the network behavior;

wherein the relevancy η

is given as follows;

$\mathrm{\eta <br><br>}=\frac{<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sn}}<br><br>+<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sa}}<br><br>}{<br><br>\mathrm{\Phi <br><br>}<br><br>}$

Φ

is a sample space of all possible values of x;

Φ

_sn is a subset of Φ

based on the values of x that indicates normal network behavior;

Φ

_sa is a subset of Φ

based on the values of x that indicates abnormal network behavior.

13. A system for extracting a communication network behavioral metric based on relevancy of the metric to network, comprising:

a Network Behavior Anomaly Detection (NBAD) module that is configured to identify a network metric x that is defined as a random variable that represents a quantitative measure of a network behavior accumulated over a period of time, select a network feature, generate a metric disintegration model for the network metric x comprising at least one normal behavior probability distribution function for the metric x for each value of the network feature, respectively, and at least one abnormal behavior probability distribution function for the metric x for each value of the network feature, respectively, increase a number of the values of the metric x that indicates normal network behavior and/or abnormal network behavior based on the metric disintegration model, and select a network metric x as a behavioral metric based on a relevancy η

of the network metric x to the network behavior;

wherein the relevancy η

is given as follows;

$\mathrm{\eta <br><br>}=\frac{<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sn}}<br><br>+<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sa}}<br><br>}{<br><br>\mathrm{\Phi <br><br>}<br><br>}$

Φ

is a sample space of all possible values of x;

Φ

_sn is a subset of Φ

based on the values of x that indicates normal network behavior;

Φ

_sa is a subset of Φ

based on the values of x that indicates abnormal network behavior.

14. The system of claim 13, wherein the network metric x is selected from one of a plurality of metric categories comprising volume of network activity metrics, network performance characteristic metrics, network fault metrics, network element activity log metrics, and/or user audit log metrics.

15. The system of claim 14, wherein the network feature is selected from one of a plurality of feature categories network specific features, network independent features, network exterior behavioral element features, and time machine features.

16. The system of claim 15, wherein the NBAD module is further configured to analyze the network and its interfaces with external neighbors to identify behavioral elements, assign each of the identified behavioral elements to one of the plurality of metric categories and/or plurality of feature categories and identify any parent-child relationships between behavioral elements in each of the plurality of metric categories and plurality of feature categories.

17. The system of claim 16, wherein the NBAD module is further configured to, for each behavioral element in the plurality of metric categories, examine each of the behavioral elements in each of the plurality of feature categories to determine if the examined feature category behavioral element can be used in the metric disintegration model for that metric category behavioral element.

18. A system for tracking network behavioral changes, comprising:

a Network Behavior Anomaly Detection (NBAD) module that is configured to select a network metric x that is defined as a random variable that represents a quantitative measure of a network behavior accumulated over a period of time, predict a current value F_t of the network metric x using an Adaptive Exponentially Weighted Moving-Average (AEWMA) formula as follows;

F_t=F_t-1+λ

_te_t where

e_t=x_t−

F_t-1, and

λ

_t is a weight parameter,

determine an upper and a lower control limit for network metric x based on a previously estimated value F_t-1 of the network metric x, observe a current value for the network metric x_t, determine that the network'"'"'s behavior is normal if the current value for the network metric x_t does not fall outside the upper and the lower control limits, and determine that the network'"'"'s behavior is abnormal if the current value for the network metric x_t falls outside the upper and the lower control limits.

19. The system of claim 18, wherein the NBAD is further configured to generate a Tracking Signal (TS_t) based on the forecasting error, determine a backward difference ∇

TS_t as follows if the network'"'"'s behavior is determined to be normal;

∇

TS_t=TS_t−

TS_t-1,

determine if the backward difference ∇

TS_t switches signs from a previously generated backward difference, set the weight parameter λ

_t to TS_t if backward difference switches signs, and set the weight parameter λ

_t to one of {λ

_tp or λ

_t or λ

_tn} so as to minimize e_tp, e_t, and e_tn below;

F_tp=λ

_tpe_t+F_tp-1;

F_t=λ

_te_t+F_t-1;

F_tn=λ

_tne_t+F_tn-1;

where λ

_tp=(λ

_t+δ

) and λ

_tn=(λ

_t−

δ

);

F_t-1 is a predicted current value of the network metric x;

e_tp=(x_t−

F_tp-1);

e_t=(x_t−

F_t-1);

e_tn=(x_t−

F_tn-1);

δ

is selected from the set {0.25, 0.20, 0.15, 0.10, 0.05, 0.03, 0.00}.

20. The system of claim 19, wherein TS_t is given by the following equation:

${\mathrm{TS}}_t=<br><br>\frac{E_t}{{\mathrm{MAD}}_t}<br><br>;<br><br>$

where E_t=β

e_t+(1−

β

)E_t-1;

MAD_t=β

|e_t|+(1−

β

)MAD_t-1;

0<

β

<

1.

21. The system of claim 18, wherein the upper and the lower control limit for the network metric x are given by the following equation:

F_t-1±

K_TSd_t-1;

where K_TS is a multiplication constant;

d_t=γ

x_t−

F_t-1|+(1−

γ

)d_t-1;

where d_t is a predicted deviation, and γ

is a weight constant;

0<

γ

<

1.0.

22. A computer program product for tracking network behavioral changes, comprising:

a computer readable storage medium having computer readable program code embodied therein, the computer readable program code comprising;

computer readable program code configured to select a network metric x that is defined as a random variable that represents a quantitative measure of a network behavior accumulated over a period of time;

computer readable program code configured to predict a current value F_t of the network metric x using an Adaptive Exponentially Weighted Moving-Average (AEWMA) formula as follows;

F_t=F_t-1+λ

_te_t, where

e_t=x_t−

F_t-1, and

λ

_t is a weight parameter;

computer readable program code configured to determine an upper and a lower control limit for network metric x based on a previously estimated value F_t-1 of the network metric x;

computer readable program code configured to observe a current value for the network metric x_t, determine that the network'"'"'s behavior is normal if the current value for the network metric x_t does not fall outside the upper and the lower control limits; and

computer readable program code configured to determine that the network'"'"'s behavior is abnormal if the current value for the network metric x_t falls outside the upper and the lower control limits.

23. The computer program product of claim 22, wherein the computer readable program code configured to select the network metric x comprises:

computer readable program code configured to select a network feature;

computer readable program code configured to generate a metric disintegration model for the network metric x comprising at least one normal behavior probability distribution function for the metric x for each value of the network feature, respectively, and at least one abnormal behavior probability distribution function for the metric x for each value of the network feature, respectively;

computer readable program code configured to increase a number of the values of the metric x that indicates normal network behavior and/or abnormal network behavior based on the metric disintegration model;

computer readable program code configured to select the network metric x as a behavioral metric based on a relevancy η

of the network metric x to the network behavior;

wherein the relevancy η

is given as follows;

$\mathrm{\eta <br><br>}=\frac{<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sn}}<br><br>+<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{sa}}<br><br>}{<br><br>\mathrm{\Phi <br><br>}<br><br>}$

Φ

is a sample space of all possible values of x;

Φ

_sn is a subset of Φ

based on the values of x that indicates normal network behavior;

Φ

_sa is a subset of Φ

based on the values of x that indicates abnormal network behavior.