MIXED CENTRALIZED/DISTRIBUTED ALGORITHM FOR RISK MITIGATION IN SPARSELY CONNECTED NETWORKS

• US 20140219103A1
• Filed: 07/29/2013
• Published: 08/07/2014
• Est. Priority Date: 02/05/2013
• 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
• Granted Patent: US 9,565,111 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

In one embodiment, techniques are shown and described relating to a mixed centralized/distributed algorithm for risk mitigation in sparsely connected networks. In particular, in one embodiment, a management node determines one or more weak point nodes in a shared-media communication network, where a weak point node is a node traversed by a relatively high amount of traffic as compared to other nodes in the network. In response to determining that a portion of the traffic can be routed over an alternate acceptable node, the management node instructs the portion of traffic to reroute over the alternate acceptable node.

Claims

1. A method, comprising:

determining one or more weak point nodes in a shared-media communication network, wherein a weak point node is a node traversed by a relatively high amount of traffic as compared to other nodes in the network;

determining whether a portion of the traffic can be routed over an alternate acceptable node; and

if so, instructing the portion of traffic to reroute over the alternate acceptable node.

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

instructing the alternate acceptable node how much rerouted traffic it is allowed to accept without being classified as a weak point node.

3. The method as in claim 1, wherein instructing comprises:

directing a particular node to instruct neighbors of the particular node to reroute over the alternate acceptable node.

4. The method as in claim 1, wherein a weak point node is a node at least a certain depth away from a root node of a directed acyclic graph (DAG).

5. The method as in claim 1, wherein the amount of traffic of a particular weak point node is based on actual traffic traversing the particular weak point.

6. The method as in claim 1, wherein the amount of traffic of a particular weak point node is based on a number of children of the particular weak point node in a directed acyclic graph (DAG).

7. The method as in claim 1, wherein the traffic is classified as important traffic.

8. The method as in claim 7, wherein important traffic is determined based on a traffic characteristic selected from a group consisting of:

traffic type;

traffic class;

traffic destination address; and

a differentiated services code point (DSCP) value of the traffic.

9. The method as in claim 1, wherein determining the one or more weak points comprises an anomaly detection algorithm.

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

determining the alternate acceptable node by probing a subset of nodes within a location from which the traffic originates.

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

ensuring that the alternate acceptable node does not become a weak point node after the portion of traffic is rerouted.

12. The method as in claim 1, wherein the alternate acceptable node is determined to be acceptable based on characteristics selected from a group consisting of:

the alternate acceptable node not already being a weak point node;

a maximum cost increase between a particular weak point node and the alternate acceptable node;

a maximum cost for using the alternate acceptable node;

a maximum delay increase between a particular weak point node and the alternate acceptable node;

a maximum delay for using the alternate acceptable node; and

a maximum quality decrease between a particular weak point node and the alternate acceptable node.

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

determining the portion of traffic to sufficiently declassify a corresponding weak point node from being a weak point node once the portion of traffic is rerouted.

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

iteratively instructing portions of traffic to reroute over alternate acceptable nodes until all possible weak point nodes in the network are declassified from being weak point nodes.

15. The method as in claim 1, wherein instructing comprises:

instructing the portion of traffic to reroute according to a timer based on a number of children of neighbors of the weak point nodes, wherein the timer is longer when the number of children is higher, and shorter when the number of children is lower.

16. The method as in claim 15, wherein a particular node may be declassified from being a weak point node before all of the portion of traffic has been rerouted, the method further comprising, in response:

ceasing rerouting of a remaining portion of traffic for the particular node now declassified from being a weak point node.

17. An apparatus, comprising:

one or more network interfaces to communicate with a shared-media communication network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine one or more weak point nodes in the shared-media communication network, wherein a weak point node is a node traversed by a relatively high amount of traffic as compared to other nodes in the network;

determine whether a portion of the traffic can be routed over an alternate acceptable node; and

if so, instruct the portion of traffic to reroute over the alternate acceptable node.

18. The apparatus as in claim 17, wherein the process when executed is further operable to:

instruct the alternate acceptable node how much rerouted traffic it is allowed to accept without being classified as a weak point node.

19. The apparatus as in claim 17, wherein a weak point node is a node at least a certain depth away from a root node of a directed acyclic graph (DAG), wherein the amount of traffic of a particular weak point node is based on a number of children of the particular weak point node in a DAG, and wherein the traffic is classified as important traffic.

20. The apparatus as in claim 17, wherein the process when executed is further operable to:

determine the alternate acceptable node by probing a subset of nodes within a location from which the traffic originates.

21. The apparatus as in claim 17, wherein the process when executed is further operable to:

ensure that the alternate acceptable node does not become a weak point node after the portion of traffic is rerouted.

22. The apparatus as in claim 17, wherein the process when executed to instruct is further operable to:

instruct the portion of traffic to reroute according to a timer based on a number of children of neighbors of the weak point nodes, wherein the timer is longer when the number of children is higher, and shorter when the number of children is lower.

23. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

determine one or more weak point nodes in a shared-media communication network, wherein a weak point node is a node traversed by a relatively high amount of traffic as compared to other nodes in the network;

determine whether a portion of the traffic can be routed over an alternate acceptable node; and

if so, instruct the portion of traffic to reroute over the alternate acceptable node.