Mixed distributed/centralized routing techniques based on closed-loop feedback from a learning machine to avoid dark zones

• US 9,426,040 B2
• Filed: 01/27/2014
• Issued: 08/23/2016
• 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): Kizou, Hassan
• Assistant Examiner(s): DAYA, TEJIS A
• Application Number:
  US14/164,469
• Publication Number:
  US 20150195126A1
• Time in Patent Office: 939 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 99/00 Subject matter not provided for in other groups of this subclass
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/365 Dynamic adaptation of the packet size
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

In one embodiment, a routing topology of a network including nodes interconnected by communication links is determined, and activity in the network is monitored to determine a normal behavior of the communication links. Weak communication links in the network that deviate from the determined normal behavior are detected, and it is then determined whether the weak communication links are spatially correlated based on the determined topology of the network. In response to the weak communication links being spatially correlated, a region of the network affected by the weak communication links is identified as a dark zone that is to be avoided when routing data packets in the network.

Claims

1. A method, comprising:

determining a routing topology of a network including nodes interconnected by communication links;

monitoring activity in the network to determine a normal behavior of the communication links;

detecting weak communication links in the network that deviate from the determined normal behavior;

determining whether the weak communication links are spatially correlated based on the determined topology of the network;

in response to the weak communication links being spatially correlated, identifying a region of the network affected by the weak communication links as a dark zone that is to be substantially avoided when routing data packets in the network;

identifying one or more nodes in the network substantially within the dark zone; and

sending an instruction to the one or more nodes to locally reroute a data packet received by the one or more nodes, such that the dark zone is substantially avoided when forwarding the data packet.

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

adjusting the routing topology such that the dark zone is substantially avoided when routing data packets in the network.

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

removing a set of communication links and nodes substantially within the dark zone from a routing topology database; and

computing, based on the set of removed communication links and nodes, one or more of a set of disconnected nodes and a path cost increase.

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

modifying the set of removed communication links and nodes so as to limit the path cost increase.

5. The method as in claim 3, further comprising:

modifying the set of removed communication links and nodes so as to limit the set of disconnected nodes.

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

receiving a low-priority packet from one of the one or more nodes; and

determining whether the dark zone is still active based on the received packet.

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

determining a path cost increase limit for the one or more nodes when locally rerouting the data packet; and

including an indication of the path cost increase limit in the instruction.

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

determining an amount of time for which the weak communication links deviate from the determined normal behavior.

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

monitoring activity of each communication link in the network.

10. The method as in claim 1, wherein the weak communication links are characterized by an abnormally low performance metric, the performance metric relating to one or more of an expected transmission count (ETX), a received signal strength index (RSSI), and a link quality index (LQI).

11. 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;

determining a routing topology of the network including nodes interconnected by communication links;

monitoring activity in the network to determine a normal behavior of the communication links;

detecting weak communication links in the network that deviate from the determined normal behavior;

determining whether the weak communication links are spatially correlated based on the determined topology of the network;

in response to the weak communication links being spatially correlated, identifying a region of the network affected by the weak communication links as a dark zone that is to be substantially avoided when routing data packets in the network;

identifying one or more nodes in the network substantially within the dark zone; and

sending an instruction to the one or more nodes to locally reroute a data packet received by the one or more nodes, such that the dark zone is substantially avoided when forwarding the data packet.

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

adjusting the routing topology such that the dark zone is substantially avoided when routing data packets in the network.

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

removing a set of communication links and nodes substantially within the dark zone from a routing topology database; and

computing, based on the set of removed communication links and nodes, one or more of a set of disconnected nodes and a path cost increase.

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

modifying the set of removed communication links and nodes so as to limit the path cost increase.

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

modifying the set of removed communication links and nodes so as to limit the set of disconnected nodes.

16. The apparatus as in claim 11, wherein the process further comprises:

receiving a low-priority packet from one of the one or more nodes; and

determining whether the dark zone is still active based on the received packet.

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

determining a path cost increase limit for the one or more nodes when locally rerouting the data packet; and

including an indication of the path cost increase limit in the instruction.

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

determining an amount of time for which the weak communication links deviate from the determined normal behavior.

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

monitoring activity of each communication link in the network.

20. The apparatus as in claim 11, wherein the weak communication links are characterized by an abnormally low performance metric, the performance metric relating to one or more of an expected transmission count (ETX), a received signal strength index (RSSI), and a link quality index (LQI).

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

determining a routing topology of a network including nodes interconnected by communication links;

monitoring activity in the network to determine a normal behavior of the communication links;

detecting weak communication links in the network that deviate from the determined normal behavior;

determining whether the weak communication links are spatially correlated based on the determined topology of the network;

in response to the weak communication links being spatially correlated, identifying a region of the network affected by the weak communication links as a dark zone that is to be substantially avoided when routing data packets in the network;

identifying one or more nodes in the network substantially within the dark zone; and

sending an instruction to the one or more nodes to locally reroute a data packet received by the one or more nodes, such that the dark zone is substantially avoided when forwarding the data packet.