Triggering reroutes using early learning machine-based prediction of failures

Patent metadata

Field	Value
Publication number	US-9774522-B2
Application number	US-201414164567-A
Country	US
Kind code	B2
Filing date	Jan 27, 2014
Priority date	Jan 6, 2014
Publication date	Sep 26, 2017
Grant date	Sep 26, 2017

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.

First claim

What is claimed is:

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 fail

Assignees

• Cisco Tech Inc

Inventors

• Vasseur Jean-Philippe
• Mermoud Grégory
• Dasgupta Sukrit

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• H04L41/147

  for predicting network behaviour · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L41/16

  using machine learning or artificial intelligence · CPC title

• G06F11/2007

  using redundant communication media · CPC title