DISTRIBUTED ARBITRATION OF TIME CONTENTION IN TSCH NETWORKS

• US 20160021006A1
• Filed: 07/17/2014
• Published: 01/21/2016
• Est. Priority Date: 07/17/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Wetterwald, Patrick, Thubert, Pascal
• Granted Patent: US 9,774,534 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a parent node in a network observes time slot usage of a channel hopping schedule by one or more child nodes of the parent node to communicate with the parent node. The parent node also identifies high priority traffic from a particular child node. The parent node detects time contention for the high priority traffic based on an indication that at least a portion of the traffic has been rerouted by a particular child node to a different parent node. In response to detecting the time contention, the parent node adjusts a communication strategy used by the one or more child nodes.

Claims

1. A method, comprising:

observing, by a parent node in a network, time slot usage of a channel hopping schedule by one or more child nodes of the parent node to communicate with the parent node;

identifying, by the parent node, high priority traffic from a particular child node;

detecting, by the parent node, time contention for the high priority traffic based on an indication that at least a portion of the traffic has been rerouted by a particular child node to a different parent node; and

adjusting, by the parent node, a communication strategy used by the one or more child nodes in response to detecting the time contention.

2. The method as in claim 1, wherein adjusting the communication strategy comprises:

increasing, by the parent node, a number of time slots in the channel hopping schedule that are allocated to the particular child node.

3. The method as in claim 1, wherein adjusting the communication strategy comprises:

determining, for each of the one or more child nodes, a percentage of traffic that is rerouted by a child node; and

adjusting time slot assignments for the one or more child nodes in the channel hopping schedule based on the percentages of traffic rerouted by the one or more child nodes.

4. The method as in claim 1, wherein the indication that the traffic has been rerouted comprises observed acknowledgement messages sent from the different parent node to the one or more child nodes.

5. The method as in claim 1, wherein the indication that the traffic has been rerouted comprises one or more notifications sent by the one or more child nodes to the parent node.

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

receiving connectivity data from the particular child node;

identifying one or more sibling nodes of the particular child node from the connectivity data; and

sending an instruction to the particular child node to route traffic to the one or more sibling nodes.

7. The method as in claim 6, wherein the instruction specifies a time period during which the traffic is to be routed to the one or more sibling nodes.

8. The method as in claim 1, wherein the time contention is detected based in part on a determination that the particular child node experienced a queuing delay.

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

receiving feedback information from the particular child node regarding traffic sent from the child node to a node that differs from the parent node; and

forwarding the feedback information to a predictive time schedule path computation element (PCE) device.

10. An apparatus, comprising:

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

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

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

observe time slot usage of a channel hopping schedule by one or more child nodes of the apparatus to communicate with the apparatus;

identify high priority traffic from a particular child node;

detect time contention for the high priority traffic based on an indication that at least a portion of the traffic has been rerouted by a particular child node to a different parent node; and

adjust a communication strategy used by the one or more child nodes in response to detecting the time contention.

11. The apparatus as in claim 10, wherein the communication strategy is adjusted by:

increasing a number of time slots in the channel hopping schedule that are allocated to the particular child node.

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

receive data indicative of traffic being rerouted by the one or more child nodes to a different parent node;

determine, for each of the one or more child nodes, a percentage of traffic that is rerouted by a child node; and

adjust time slot assignments for the one or more child nodes in the channel hopping schedule based on the percentages of traffic rerouted by the one or more child nodes.

13. The apparatus as in claim 10, wherein the indication that the traffic has been rerouted comprises observed acknowledgement messages sent from the different parent node to the one or more child nodes.

14. The apparatus as in claim 10, wherein the indication that the traffic has been rerouted comprises one or more notifications sent by the one or more child nodes to the parent node.

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

receive connectivity data from the particular child node;

identify one or more sibling nodes of the particular child node from the connectivity data; and

send an instruction to the particular child node to route traffic to the one or more sibling nodes.

16. The apparatus as in claim 15, wherein the instruction specifies a time period during which the traffic is to be routed to the one or more sibling nodes.

17. The apparatus as in claim 16, wherein the time period is based on a detected periodicity of the time contention.

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

receive feedback information from the particular child node regarding traffic sent from the child node to a node that differs from the apparatus; and

forward the feedback information to a predictive time schedule path computation element (PCE) device.

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

observe time slot usage of a channel hopping schedule by one or more child nodes of the apparatus to communicate with a parent node;

identify high priority traffic from a particular child node;

detect time contention for the high priority traffic based on an indication that at least a portion of the traffic has been rerouted by a particular child node to a different parent node; and

,

adjust a communication strategy used by the one or more child nodes in response to detecting the time contention.

20. The computer-readable media as in claim 19, wherein the software when executed is further operable to:

increase a number of time slots in the channel hopping schedule that are allocated to the particular child node.