Using statistical and historical information of topology metrics in constrained networks

Patent metadata

Field	Value
Publication number	US-9356875-B2
Application number	US-201313947268-A
Country	US
Kind code	B2
Filing date	Jul 22, 2013
Priority date	Jul 22, 2013
Publication date	May 31, 2016
Grant date	May 31, 2016

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.

First claim

What is claimed is:

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;
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; and
instructing the node to remain in communication with a particular parent node having a minimal transmission delay compared to other potential parent nodes.

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 performing a global override of a best next-hop selection used by nodes in the LLN including the node.

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

12. 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.

13. 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, the determination being made at a root node of a directed acyclic graph of nodes that comprises 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;
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;
examine 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
instruct 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.

14. The apparatus of claim 13 , 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.

15. The apparatus of claim 13 , 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.

16. The apparatus of claim 13 , 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.

17. The apparatus of claim 13 , 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.

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

19. The apparatus of claim 13 , wherein the selection of the parent node is permanent.

20. The apparatus of claim 13 , 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.

21. The apparatus of claim 13 , 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.

22. The apparatus of claim 13 , 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.

23. The apparatus of claim 13 , 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.

24. The apparatus of claim 13 , 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.

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

26. 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 los

Assignees

• Cisco Tech Inc

Inventors

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

Classifications

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04L45/488

  using root node determination · CPC title

• H04L41/5019 Primary

  Ensuring fulfilment of SLA · CPC title

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/14

  Routing performance; Theoretical aspects · CPC title