Predictive time allocation scheduling for TSCH networks

• US 9,800,506 B2
• Filed: 07/21/2014
• Issued: 10/24/2017
• Est. Priority Date: 07/21/2014
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Thubert, Pascal, Wetterwald, Patrick
• Primary Examiner(s): Moutaouakil, Mounir
• Application Number:
  US14/336,250
• Publication Number:
  US 20160021011A1
• Time in Patent Office: 1,191 Days
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/25 with rate being modified by the source upon detecting a change of network conditions
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/121 for groups of terminals or users
• CPC Class Codes: H04W 72/52 based on load

Abstract

In one embodiment, a device in a network receives one or more time slot usage reports regarding a use of time slots of a channel hopping schedule by nodes in the network. The device predicts a time slot demand change for a particular node based on the one or more time slot usage reports. The device identifies a time frame associated with the predicted time slot demand change. The device adjusts a time slot assignment for the particular node in the channel hopping schedule based on predicted demand change and the identified time frame associated with the predicted time slot demand change.

Claims

1. A method, comprising:

receiving, at a device in a network, one or more time slot usage reports regarding a use of time slots of a channel hopping schedule by nodes in the network;

predicting, via a learning machine model hosted on the device, a burst of traffic for a particular node based on the one or more time slot usage reports;

predicting, via the learning machine model hosted on the device, a time slot demand change for the particular node based on the predicted burst of traffic by detecting time-based patterns in the one or more time slot usage reports;

identifying, by the device, a time frame associated with the predicted time slot demand change; and

prior to the predicted burst of traffic, adjusting, by the device, a time slot assignment for the particular node in the channel hopping schedule based on the predicted demand change and the identified time frame associated with the predicted time slot demand change.

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

receiving, at the device, feedback regarding the adjusted time slot assignment; and

in response to receiving the feedback, readjusting the time slot assignment based on the received feedback.

3. The method as in claim 1, wherein adjusting the time slot assignment comprises:

instructing the particular node to use a specified set of time slots for communication.

4. The method as in claim 1, wherein adjusting the time slot assignment comprises:

notifying a parent of the particular node of the predicted time slot demand change and associated time period, wherein the parent generates an updated time slot assignment for the particular node to use during the time period.

5. The method as in claim 1, wherein the one or more time slot usage reports are received from a parent node of the particular node, wherein the parent node monitors time slot usage by the particular node.

6. The method as in claim 1, wherein the one or more time slot usage reports are based on a notification from the particular node that the particular node has experienced a queuing delay.

7. A method, comprising:

providing, by a network node, one or more time slot usage reports to a time slot usage prediction engine regarding a use of time slots of a channel hopping schedule by one or more child nodes of the network node, the prediction engine hosting a learning machine model;

receiving, at the network node, a predicted time slot usage change from the prediction engine based on a predicted burst of traffic for the one or more child nodes, the predicted burst of traffic based on detection of time-based patterns in the one or more time slot usage reports;

generating, by the network node, one or more updated time slot assignments for the one or more child nodes based on the predicted time slot usage change; and

providing, by the network node, the one or more updated time slot assignments to the one or more child nodes prior to the predicted burst of traffic.

8. The method as in claim 7, wherein providing the one or more time slot usage reports comprises:

monitoring, by the network node, time slot usage of a channel hopping schedule by the one or more child nodes;

generating, by the network node, an aggregated time slot usage report based on the monitored time slot usage; and

providing the aggregated time slot usage report to the time slot usage prediction engine.

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

receiving, at the network node, a notification that a particular child node has delayed traffic due to the particular child node not having sufficient time slot allocations.

10. The method as in claim 7, wherein a time slot usage report is provided after expiration of a timer.

11. The method as in claim 7, wherein the predicted time slot usage change is associated with a time period.

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

providing an updated time slot assignment to a particular child node for use during the time period; and

after expiration of the time period, reverting the particular child node to a previously used time slot assignment.

13. An apparatus, comprising:

one or more network interfaces to communicate with a 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;

receive one or more time slot usage reports regarding a use of time slots of a channel hopping schedule by nodes in the network;

predict, via a learning machine model, a burst of traffic for a particular node based on the one or more time slot usage reports;

predict, via the learning machine model, a time slot demand change for the particular node based on the predicted burst of traffic by detecting time-based patterns in the one or more time slot usage reports;

identify a time frame associated with the predicted time slot demand change; and

prior to the predicted burst of traffic, adjust a time slot assignment for the particular node in the channel hopping schedule based on the predicted demand change and the identified time frame associated with the predicted time slot demand change.

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

receive feedback regarding the adjusted time slot assignment; and

in response to receiving the feedback, readjust the time slot assignment based on the received feedback.

15. The apparatus as in claim 13, the time slot assignment is adjusted by:

instructing the particular node to use a specified set of time slots for communication.

16. The apparatus as in claim 13, wherein the time slot assignment is adjusted by:

notifying a parent of the particular node of the predicted time slot demand change and associated time period, wherein the parent generates an updated time slot assignment for the particular node to use during the time period.

17. The apparatus as in claim 13, wherein the one or more time slot usage reports are received from a parent node of the particular node, wherein the parent node monitors time slot usage by the particular node.

18. The apparatus as in claim 13, wherein the one or more time slot usage reports are based on a notification from the particular node that the particular node has experienced a queuing delay.

19. An apparatus, comprising:

one or more network interfaces to communicate with a 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;

provide one or more time slot usage reports to a time slot usage prediction engine regarding a use of time slots of a channel hopping schedule by one or more child nodes of the network node, the prediction engine hosting a learning machine model;

receive a predicted time slot usage change from the prediction engine based on a predicted burst of traffic for the one or more child nodes, the predicted burst of traffic based on detection of time-based patterns in the one or more time slot usage reports;

generate one or more updated time slot assignments for the one or more child nodes based on the predicted time slot usage change; and

provide the one or more updated time slot assignments to the one or more child nodes prior to the predicted burst of traffic.

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

monitor time slot usage of a channel hopping schedule by the one or more child nodes;

generate an aggregated time slot usage report based on the monitored time slot usage; and

provide the aggregated time slot usage report to the time slot usage prediction engine.

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

receive a notification that a particular child node has delayed traffic due to the particular child node not having sufficient time slot allocations.

22. The apparatus as in claim 19, wherein a time slot usage report is provided after expiration of a timer.

23. The apparatus as in claim 19, wherein the predicted time slot usage change is associated with a time period.

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

providing an updated time slot assignment to a particular child node for use during the time period; and

after expiration of the time period, reverting the particular child node to a previously used time slot assignment.

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

receive one or more time slot usage reports regarding a use of time slots of a channel hopping schedule by nodes in the network;

predict, via a learning machine model, a burst of traffic for a particular node based on the one or more time slot usage reports;

predict, via a learning machine model, a time slot demand change for the particular node based on the predicted burst of traffic by detecting time-based patterns in the one or more time slot usage reports;

identify a time frame associated with the predicted time slot demand change; and

prior to the predicted burst of traffic, adjust a time slot assignment for the particular node in the channel hopping schedule based on the predicted demand change and the identified time frame associated with the predicted time slot demand change.

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

provide one or more time slot usage reports to a time slot usage prediction engine regarding a use of time slots of a channel hopping schedule by one or more child nodes of the network node, the prediction engine hosting a learning machine model;

receive a predicted time slot usage change from the prediction engine based on a predicted burst of traffic for the one or more child nodes, the predicted burst of traffic based on detection of time-based patterns in the one or more time slot usage reports;

generate one or more updated time slot assignments for the one or more child nodes based on the predicted time slot usage change; and

provide the one or more updated time slot assignments to the one or more child nodes prior to the predicted burst of traffic.