Method and apparatus for network-level anomaly inference

• US 8,145,745 B1
• Filed: 12/28/2005
• Issued: 03/27/2012
• Est. Priority Date: 12/28/2005
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Greenberg, Albert Gordon, Roughan, Matthew, Zhang, Yin, Ge, Zihui
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): Kim, Hee
• Application Number:
  US11/321,218
• Time in Patent Office: 2,281 Days
• Field of Search: 709/224
• US Class Current: 709/224
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity

Abstract

Method and apparatus for network-level anomaly inference in a network is described. In one example, link load measurements are obtained for multiple time intervals. Routing data for the network is obtained. Link level anomalies are extracted using temporal analysis on the link load measurements over the multiple time intervals. Network-level anomalies are inferred from the link-level anomalies.

Claims

1. A method of network-level anomaly inference in a network, comprising:

obtaining link load measurements for multiple time intervals, wherein each of the link load measurements is a load measurement for a link;

obtaining routing data for the network;

extracting link level anomalies using temporal analysis of the link load measurements over the multiple time intervals for the link; and

inferring network-level anomalies from the link level anomalies and the routing data by reconstructing origin-destination flow anomalies by solving a series of ill-posed linear inverse problems.

2. The method of claim 1, wherein the temporal analysis comprises an autoregressive integrated moving average modeling.

3. The method of claim 1, wherein the temporal analysis comprises a principle components analysis.

4. The method of claim 1, wherein the temporal analysis comprises a fourier analysis.

5. The method of claim 1, wherein the temporal analysis comprises a wavelet analysis.

6. The method of claim 1, wherein the network-level anomalies are inferred using an inference algorithm.

7. The method of claim 1, wherein the network-level anomalies are inferred using non-constant routing matrices.

8. Apparatus for network-level anomaly inference in a network, comprising:

means for obtaining link load measurements for multiple time intervals, wherein each of the link load measurements is a load measurement for a link;

means for obtaining routing data for the network;

means for extracting link level anomalies using temporal analysis of the link load measurements over the multiple time intervals for the link; and

means for inferring network-level anomalies from the link level anomalies and the routing data by reconstructing origin-destination flow anomalies by solving a series of ill-posed linear inverse problems.

9. The apparatus of claim 8, wherein the temporal analysis comprises an autoregressive integrated moving average modeling.

10. The apparatus of claim 8, wherein the temporal analysis comprises a principle components analysis.

11. The apparatus of claim 8, wherein the temporal analysis comprises a fourier analysis.

12. The apparatus of claim 8, wherein the temporal analysis comprises a wavelet analysis.

13. The apparatus of claim 8, wherein the network-level anomalies are inferred using an inference algorithm.

14. The apparatus of claim 8, wherein the network-level anomalies are inferred using non-constant routing matrices.

15. A non-transitory computer readable medium having stored thereon instructions that, when executed by a processor, cause the processor to perform a method of network-level anomaly inference in a network, comprising:

obtaining link load measurements for multiple time intervals, wherein each of the link load measurements is a load measurement for a link;

obtaining routing data for the network;

extracting link level anomalies using temporal analysis of the link load measurements over the multiple time intervals for the link; and

inferring network-level anomalies from the link level anomalies and the routing data by reconstructing origin-destination flow anomalies by solving a series of ill-posed linear inverse problems.

16. The non-transitory computer readable medium of claim 15, wherein the temporal analysis comprises an autoregressive integrated moving average modeling.

17. The non-transitory computer readable medium of claim 15, wherein the temporal analysis comprises a principle components analysis.

18. The non-transitory computer readable medium of claim 15, wherein the temporal analysis comprises a fourier analysis.

19. The non-transitory computer readable medium of claim 15, wherein the temporal analysis comprises a wavelet analysis.

20. The non-transitory computer readable medium of claim 15, wherein the network-level anomalies are inferred using an inference algorithm.