Dynamic Wake-up Time Adjustment Based on Designated Paths Through a Computer Network

• US 20120113863A1
• Filed: 11/09/2010
• Published: 05/10/2012
• Est. Priority Date: 11/09/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Shaffer, Shmuel, Shetty, Sandeep Jay
• Granted Patent: US 8,774,050 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/12 Arrangements for remote connection or disconnection of substations or of equipment thereof
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04W 40/005 Routing actions in the presence of nodes in sleep or doze mode
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, a computer network may include nodes and at least one root node. A first subset of the nodes may be located along a designated path (a directed acyclic graph (DAG)) through the computer network to the root node, where the first subset of nodes is configured to operate according to a first wake-up timer. A second subset of the nodes that are not along the designated path are in communication to at least one node of the first subset of nodes along the designated path, and operate according to a second wake-up timer that is longer than the first wake-up timer. In this manner, second subset of nodes may be awake less often, e.g., conserving energy.

Claims

1. A method, comprising:

accessing information revealing nodes in a computer network;

determining a designated path through the computer network to a root node, the designated path traversing a first subset of the nodes as a directed acyclic graph (DAG) toward the root node, wherein a second subset of the nodes in the computer network that are not along the designated path are configured to communicate with at least one node of the first subset of nodes along the designated path; and

notifying the nodes in the computer network of the designated path and whether each particular node is included in the first subset or second subset, wherein nodes in the first subset operate according to a first wake-up timer, and wherein nodes in the second subset operate according to a second wake-up timer that is longer than the first wake-up timer.

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

notifying at least the second subset of nodes of the second wake-up timer.

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

identifying one or more power constrained nodes of the nodes; and

determining the designated path to maximize a number of power constrained nodes within the second subset of nodes.

4. The method as in claim 3, further comprising:

prioritizing power constraints over at least one of either cost and delay when determining the designated path.

5. The method as in claim 1, wherein determining the designated path further comprises:

identifying one or more first nodes of the nodes that are more capable of being on the designated path than one or more second nodes; and

giving preference to including the first nodes on the designated path over the second nodes.

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

receiving a request to remove a particular node of the first subset of nodes from the designated path; and

determining a new designated path that does not include the particular node.

7. An apparatus, comprising:

one or more network interfaces;

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 nodes in a computer network;

determine a designated path through the computer network to a root node, the designated path traversing a first subset of the nodes as a directed acyclic graph (DAG) toward the root node, wherein a second subset of the nodes in the computer network are not along the designated path and are in communication with at least one node of the first subset of nodes along the designated path; and

notify the nodes in the computer network of the designated path and whether each particular node is in the first subset or second subset, wherein nodes in the first subset operate according to a first wake-up timer, and wherein nodes in the second subset operate according to a second wake-up timer that is longer than the first wake-up timer.

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

receive topology information from the nodes.

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

notify at least the second subset of nodes of the second wake-up timer.

10. The apparatus as in claim 7, wherein the process when executed to determine the designate path is further operable to:

identify one or more power constrained nodes of the nodes; and

determine the designated path to maximize a number of power constrained nodes within the second subset of nodes.

11. A method, comprising:

relaying, from a particular node in a computer network, topology information toward a root node according to a directed acyclic graph (DAG) routing process;

receiving, at the particular node, a notification of a designated path through the computer network, the designated path traversing a first subset of nodes as a DAG toward the root node, wherein a second subset of the nodes in the computer network are not along the designated path and are in communication with at least one node of the first subset of nodes along the designated path;

determining, from the notification, whether the particular node is in the first subset or second subset;

in response to the particular node being in the first subset, operating the particular node according to a first wake-up timer; and

in response to the particular node being in the second subset, operating the particular node according to a second wake-up timer that is longer than the first wake-up timer.

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

informing the root node of the particular node'"'"'s capability to be within the first subset of nodes along the designated path.

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

communicating from the particular node to a second particular node of the second subset by communicating a message preamble that is longer than the second wake-up timer.

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

determining, when the particular node is in the first subset along the designated path, that a power constraint of the particular node is below a threshold; and

, in response, requesting removal of the particular node from the designated path.

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

receiving a request at the particular node to locally remove a node from the designated path; and

, in response,

recomputing communication with the designated path.

16. The method as in claim 15, wherein recomputing comprises:

becoming a member of the first subset of nodes along the designated path.

17. An apparatus, comprising:

one or more network interfaces;

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;

relay topology information toward a root node according to a directed acyclic graph (DAG) routing process;

receive a notification of a designated path through the computer network, the designated path traversing a first subset of nodes as a DAG toward the root node, wherein a second subset of the nodes in the computer network are not along the designated path and are in communication with at least one node of the first subset of nodes along the designated path;

determine, from the notification, whether the apparatus is in the first subset or second subset;

operate according to a first wake-up timer in response to the apparatus being in the first subset; and

operate according to a second wake-up timer that is longer than the first wake-up timer in response to the apparatus being in the second subset.

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

determine, when the apparatus is in the first subset along the designated path, that a power constraint of the apparatus is below a threshold; and

, in response,

request removal of the apparatus from the designated path.

19. A system, comprising:

nodes in a computer network;

a root node in the computer network;

a first subset of the nodes, wherein a designated path through the computer network to the root node traverses the first subset of the nodes as a directed acyclic graph (DAG) toward the root node, the first subset of nodes configured to operate according to a first wake-up timer; and

a second subset of the nodes, wherein the second subset of nodes are not along the designated path and are in communication to at least one node of the first subset of nodes along the designated path, the second subset of nodes configured to operate according to a second wake-up timer that is longer than the first wake-up timer.

20. The system as in claim 19, wherein one or more of the nodes in the computer network are sensor devices.