USING STATISTICAL AND HISTORICAL INFORMATION OF TOPOLOGY METRICS IN CONSTRAINED NETWORKS

• US 20150023174A1
• Filed: 07/22/2013
• Published: 01/22/2015
• Est. Priority Date: 07/22/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Dasgupta, Sukrit, Vasseur, Jean-Philippe, Mermoud, Grgory
• Granted Patent: US 9,356,875 B2
• Time in Patent Office: Days
• US Class Current: 370/236
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Statistical and historical values of performance metrics are actively used to influence routing decisions for optimum topologies in a constrained network. Traffic service level is constantly monitored and compared with a service level agreement. If deviation exists between the monitored traffic service level and the terms of the service level agreement, stability metrics are used to maintain paths through the network that meet the terms of the traffic service level agreement or that improve the traffic flow through the network. Backup parent selection for a node in the network is performed based on previous performance of backup parents for the node.

Claims

1. A method, comprising:

in a low power and lossy network (LLN) comprising a plurality of nodes, calculating a rate of change for parents of a node, the rate of change being a ratio of a number of changes in parent node observed for the node and a total number of observations of the node;

calculating a parent preference for the node, the parent preference being a proportion of instances in which the node'"'"'s most frequent parent is observed for the node and a total number of observations of the node; and

overriding a local next-hop algorithm for the node by selecting a parent node for the node based on at least one of the calculated rate of change for parents of the node and the calculated parent preference for the node.

2. The method of claim 1, wherein the selection of the parent node is permanent.

3. The method of claim 1, wherein the selection of the parent node is for a predetermined duration of time after which the node returns to executing the local next-hop algorithm to select parent nodes.

4. The method of claim 1, wherein calculating a rate of change for parents of the node and calculating a parent preference for the node occur upon receipt of messages from the node comprising parent information for the node.

5. The method of claim 1, wherein calculating a rate of change for parents of the node and calculating a parent preference for the node occur at a root node of a directed acyclic graph of nodes that comprise the node.

6. The method of claim 5, further comprising comparing traffic levels across the nodes of the directed acyclic graph against a service level requirement to determine deviation from the service level requirement before overriding the local next-hop algorithm.

7. The method of claim 5, further comprising:

examining the node in the directed acyclic graph of nodes to determine that variability in backup parent node designations for the node exceeds a predetermined threshold; and

instructing the node to select specified backup parent nodes in response to determining that the variability in backup parent node designations for the node exceeds the predetermined threshold.

8. The method of claim 1, wherein overriding the local next-hop algorithm for the node comprises communicating routing information to the node, the routing information identifying a specific node so that a preferred parent is selected as the parent node.

9. The method of claim 8, wherein the parent node is selected to increase stability of the LLN.

10. The method of claim 1, further comprising instructing the node to remain in communication with a particular parent node having a minimal transmission delay compared to other potential parent nodes.

11. The method of claim 1, further comprising performing a global override of a best next-hop selection used by nodes in the LLN including the node.

12. The method of claim 1, wherein the override of the local next-hop algorithm is performed when the calculated rate of change for parents of the node exceeds a predetermined value.

13. The method of claim 1, wherein the override of the local next-hop algorithm is performed when the calculated parent preference for the node exceeds a predetermined value.

14. An apparatus, comprising:

one or more network interfaces to communicate with a low power and lossy network (LLN);

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 by the processor operable to;

determine a rate of change for parents of a node, the rate of change being a ratio of a number of changes in parent node observed for the node and a total number of observations of the node;

determine a parent preference for the node, the parent preference being a proportion of instances in which the node'"'"'s most frequent parent is observed for the node and a total number of observations of the node;

determine that one of the rate of change of parents for the node and the parent preference for the node exceeds a corresponding threshold; and

override a local next-hop algorithm for the node by selecting a parent node for the node in response to determining that one of the rate of change of parents for the node and the parent preference for the node exceeds a corresponding threshold.

15. The apparatus of claim 14, wherein the process when executed is further operable to determine the rate of change for parents of the node and to determine the parent preference for the node based upon receipt of messages from the node comprising parent information for the node.

16. The apparatus of claim 14, wherein the process when executed is further operable to override the local next-hop algorithm for the node by communicating routing information to the node, the routing information identifying a specific node so that a preferred parent is selected as the parent node.

17. The apparatus of claim 14, wherein the process when executed is further operable to compare traffic levels across the nodes of a directed acyclic graph against a service level requirement to determine deviation from the service level requirement before overriding the local next-hop algorithm.

18. The apparatus of claim 14, wherein the process when executed is further operable to perform a global override of a best next-hop selection used by nodes in the LLN including the node.

19. The apparatus of claim 14, wherein the wherein the parent node is selected to increase stability of the LLN.

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

in a low power and lossy network comprising a plurality of nodes, determine a rate of change for parents of a node, the rate of change being a ratio of a number of changes in parent node observed for the node and a total number of observations of the node;

determine a parent preference for the node, the parent preference being a proportion of instances in which the node'"'"'s most frequent parent is observed for the node and a total number of observations of the node; and

override a local next-hop algorithm for the node by selecting a parent node for the node based on at least one of the determined rate of change for parents of the node and the determined parent preference for the node.