Triggering reroutes using early learning machine-based prediction of failures

• US 9,774,522 B2
• Filed: 01/27/2014
• Issued: 09/26/2017
• Est. Priority Date: 01/06/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Mermoud, Grgory, Dasgupta, Sukrit
• Primary Examiner(s): Kao, Jutai
• Application Number:
  US14/164,567
• Publication Number:
  US 20150195192A1
• Time in Patent Office: 1,338 Days
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/2007 using redundant communication media
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 41/0836 to enhance reliability, e.g. reduce downtime
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, network metrics are collected and analyzed in a network having nodes interconnected by communication links. Then, it is predicted whether a network element failure is relatively likely to occur based on the collected and analyzed network metrics. In response to predicting that a network element failure is relatively likely to occur, traffic in the network is rerouted in order to avoid the network element failure before it is likely to occur.

Claims

1. A method, comprising:

collecting and analyzing, by a machine learning device executing a machine learning time series analysis, network metrics in a network having nodes interconnected by communication links;

predicting, by the machine learning time series analysis on the machine learning device, whether a network element failure of any one of the other nodes in the network is likely to occur based on the collected and analyzed network metrics;

generating and sending, by the machine learning device, an instruction to any one of the other nodes in the network to pre-compute alternate communication routes local to each respective node, wherein the instructions instruct the one or more nodes to pre-compute alternate communication routes local to each respective node taking into account at least a class of service, a path cost stretch of alternate paths, and probability of failures; and

in response to predicting that a network element failure of any one of the other nodes in the network is likely to occur, proactively rerouting, by the machine learning device, traffic in the network in order to avoid the network element failure before the failure is likely to occur.

2. The method as in claim 1, further comprising:

receiving information regarding an alternate communication route of a node in the network; and

rerouting the traffic in the network based on the alternate communication route of the node.

3. The method as in claim 1, wherein the rerouting of traffic is based on one or more of a type of traffic, a path cost of an alternate communication route, and a probability of network element failure.

4. The method as in claim 1, further comprising:

calculating a probability of network element failure; and

predicting that the network element failure is likely to occur when the calculated probability exceeds a predetermined threshold.

5. The method as in claim 1, wherein the network element failure involves one or more of a failed node and a failed communication link.

6. The method as in claim 1, further comprising:

determining a routing topology of the network; and

rerouting the traffic in the network based on the determined routing topology.

7. The method as in claim 1, further comprising:

constructing a predictive model based on the collected and analyzed network metrics and results of past predictions, wherein

the predicting of whether the network element failure is likely to occur is based further on the predictive model.

8. The method as in claim 7, further comprising:

receiving feedback regarding an accuracy of the predictive model; and

refining the predictive model based on the received feedback, wherein

the feedback involves whether the predicted network element failure actually occurred or information in response to a probe sent to nodes in the network upon expiration of a predetermined duration.

9. The method as in claim 1, wherein the collected and analyzed network metrics are network element failure indicators.

10. The method as in claim 1, wherein the collected and analyzed network metrics include one or more of battery life, a weather condition, traffic volume, communication link quality, signal strength, a location of a node or communication link, a distance of a communication link, and a transmission success rate.

11. The method as in claim 1, wherein the predicting of whether the network element failure is likely to occur is performed by a learning machine (LM).

12. An apparatus, comprising:

one or more network interfaces that communicate with a network;

a processor coupled to the one or more network interfaces and configured to execute a process; and

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

collecting and analyzing network metrics in the network having nodes interconnected by communication links;

predicting, by a machine learning time series analysis, whether a network element failure of any one of the other nodes in the network is likely to occur based on the collected and analyzed network metrics;

generating and sending an instruction to any one of the other nodes in the network to compute alternate communication routes local to each respective node, wherein the instructions instruct the one or more nodes to pre-compute alternate communication routes local to each respective node taking into account at least a class of service, a path cost stretch of alternate paths, and probability of failures; and

in response to predicting that a network element failure of any one of the other nodes in the network is likely to occur, proactively rerouting traffic in the network in order to avoid the network element failure before the failure is likely to occur.

13. The apparatus as in claim 12, wherein the process further comprises:

receiving information regarding an alternate communication route of a node in the network; and

rerouting the traffic in the network based on the alternate communication route of the node.

14. The apparatus as in claim 12, wherein the rerouting of traffic is based on one or more of a type of traffic, a path cost of an alternate communication route, and a probability of network element failure.

15. The apparatus as in claim 12, wherein the process further comprises:

calculating a probability of network element failure; and

predicting that the network element failure is likely to occur when the calculated probability exceeds a predetermined threshold.

16. The apparatus as in claim 12, wherein the network element failure involves one or more of a failed node and a failed communication link.

17. The apparatus as in claim 12, wherein the process further comprises:

determining a routing topology of the network; and

rerouting the traffic in the network based on the determined routing topology.

18. The apparatus as in claim 12, wherein the process further comprises:

constructing a predictive model based on the collected and analyzed network metrics and results of past predictions, wherein

the predicting of whether the network element failure is likely to occur is based further on the predictive model.

19. The apparatus as in claim 18, wherein the process further comprises:

receiving feedback regarding an accuracy of the predictive model; and

refining the predictive model based on the received feedback, wherein

the feedback involves whether the predicted network element failure actually occurred or information in response to a probe sent to nodes in the network upon expiration of a predetermined duration.

20. The apparatus as in claim 12, wherein the collected and analyzed network metrics are network element failure indicators.

21. The apparatus as in claim 12, wherein the collected and analyzed network metrics include one or more of battery life, a weather condition, traffic volume, communication link quality, signal strength, a location of a node or communication link, a distance of a communication link, and a transmission success rate.

22. The apparatus as in claim 12, wherein the apparatus is a learning machine (LM).

23. A tangible non-transitory computer readable medium storing program instructions that cause a computer to execute a process, the process comprising:

collecting and analyzing network metrics in a network having nodes interconnected by communication links;

predicting, by a machine learning time series analysis, whether a network element failure of any one of the other nodes in the network is likely to occur based on the collected and analyzed network metrics;

generating and sending an instruction to any one of the other nodes in the network to pre-compute alternate communication routes local to each respective node, wherein the instructions instruct the one or more nodes to pre-compute alternate communication routes local to each respective node taking into account at least a class of service, a path cost stretch of alternate paths, and probability of failures; and

in response to predicting that a network element failure of any one of the other nodes in the network is likely to occur, proactively rerouting traffic in the network in order to avoid the network element failure before the failure is likely to occur.