Dynamic Expelling of Child Nodes in Directed Acyclic Graphs in a Computer Network

• US 20120155276A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/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
• Granted Patent: US 8,503,309 B2
• Time in Patent Office: Days
• US Class Current: 370/237
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 28/0289 Congestion control load shedding arrangements in network planning H04W16/08; performing reselection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

In one embodiment, a parent node in a directed acyclic graph (DAG) in a computer network may detect congestion from its child nodes. In response, the parent node may determine particular child nodes to expel from the parent node based on the congestion, and notifies the expelled child nodes that they must detach from the parent node in response to dynamically detecting congestion (e.g., to find a new parent, excluding the parent node and optionally any nodes in the vicinity). In another embodiment, a child node receives a detach request packet from a current parent node that indicates that the child node is expelled from using the current parent node. In response, the child node triggers a new parent selection to select a new parent node that specifically excludes the current parent node (e.g., and optionally any nodes in the parent'"'"'s vicinity).

Claims

1. A method, comprising:

detecting congestion from a plurality of child nodes at a parent node in a directed acyclic graph (DAG) in a computer network;

determining one or more particular child nodes of the child nodes to expel from the parent node based on the congestion; and

notifying the one or more particular child nodes that the one or more particular child nodes must detach from the parent node in response to the congestion.

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

identifying a set of nodes within a vicinity of the parent node; and

notifying the one or more particular child nodes of the set of nodes and that the one or more particular child nodes are excluded from reattaching to any of the set of nodes in the vicinity of the parent node.

3. The method as in claim 1, wherein determining the one or more particular child nodes comprises:

identifying a set of child nodes of the plurality of child nodes most contributory to the congestion; and

selecting the one or more particular child nodes from the set of child nodes.

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

determining a length of time that the congestion is expected to last; and

setting the length of time for which the one or more particular child nodes must remain detached.

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

increasing the length of time for subsequent detected congestion.

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

in response to detecting congestion relief at the parent node, transmitting a reattach permission packet to at least one of the one or more particular child nodes to instruct the at least one child node that the at least one child nodes is allowed to reattach to the parent node.

7. The method as in claim 1, wherein determining the one or more particular child nodes comprises:

identifying a set of child nodes of the plurality of child nodes that have alternate parents; and

selecting the one or more particular child nodes from this set of child nodes.

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

clearing parent node routing table entries corresponding to the one or more particular child nodes.

9. An apparatus, comprising:

one or more network interfaces to communicate in a directed acyclic graph (DAG) in a computer network as a parent node;

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;

detect congestion at the apparatus from a plurality of child nodes;

determine one or more particular child nodes of the plurality of child nodes to expel from using the apparatus as their parent node based on the congestion; and

notify the one or more particular child nodes that the one or more particular child nodes must detach from the apparatus as their parent node in response to the congestion.

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

identify a set of nodes within a vicinity of the apparatus; and

notifying the one or more particular child nodes of the set of nodes and that the one or more particular child nodes are excluded from reattaching to any of the set of nodes in the vicinity of the apparatus.

11. The apparatus as in claim 9, wherein the process when executed to determine the one or more particular child nodes is operable to:

identify a set of child nodes of the plurality of child nodes most contributory to the congestion; and

select the one or more particular child nodes from the set of child nodes.

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

set a length of time for which the one or more particular child nodes must remain detached.

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

detect congestion relief; and

, in response,

transmit a reattach permission packet to at least one of the one or more particular child nodes to instruct the at least one child node that the at least one child node is allowed to reattach to the apparatus as its parent node.

14. The apparatus as in claim 9, wherein the process when executed to determine the one or more particular child nodes is operable to:

identify a set of child nodes of the plurality of child nodes that have alternate parents; and

select the one or more particular child nodes from the set of child nodes.

15. A method, comprising:

receiving, at a child node in a directed acyclic graph (DAG) in a computer network, a detach request packet from a current parent node of the child node, the detach request packet indicating that the child node is expelled from using the current parent node;

triggering a new parent selection in response to the detach request packet; and

, in response,

selecting a new parent node that specifically excludes the current parent node.

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

receiving notification of a set of nodes within a vicinity of the parent node; and

specifically excluding the set of nodes in the vicinity of the parent node from being selected as a new parent node.

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

reattaching to the current parent node upon one of either expiration of a set length of time for which the child node must remain detached or receiving a reattach permission packet that instructs the child node that it is allowed to reattach to the current parent node.

18. The method as in claim 17, wherein reattaching comprises:

reattaching to the current parent upon either of the timer expiration or the reattach permission packet after a certain delay.

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

in response to receiving the detach request packet from the current parent node, determining that the child node has no alternative parent nodes; and

, in response,

poisoning one or more sub-DAGs of the child node.

20. The method as in claim 15, wherein the received detach request packet is in response to congestion at the current parent node.

21. An apparatus, comprising:

one or more network interfaces to communicate in a directed acyclic graph (DAG) in a computer network as a child node to a current parent node;

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;

receive a detach request packet from the current parent node indicating that the apparatus is expelled from being a child node to the current parent node;

trigger a new parent selection in response to the detach request packet; and

select a new parent node that specifically excludes the current parent node in response to the detach request packet.

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

receive notification of a set of nodes within a vicinity of the parent node; and

specifically exclude the set of nodes in the vicinity of the parent node from being selected as a new parent node.

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

reattach to the current parent node upon one of either expiration of a set length of time for which the apparatus must remain detached or receiving a reattach permission packet that instructs the apparatus that it is allowed to reattach to the current parent node.

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

determine that the apparatus has no alternative parent nodes in response to receiving the detach request packet from the current parent node; and

, in response,

poison one or more sub-DAGs of the apparatus for which the apparatus is a parent node.