Gravitational Parent Selection in Directed Acyclic Graphs

• US 20120230222A1
• Filed: 03/08/2011
• Published: 09/13/2012
• Est. Priority Date: 03/08/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shaffer, Shmuel, Vasseur, Jean-Philippe, Shetty, Sandeep Jay
• Granted Patent: US 9,210,045 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In one embodiment, a particular node in a computer network receives an indication of a number of child nodes of one or more potential parent nodes to the particular node in a primary directed acyclic graph (DAG). From this, the particular node selects a particular potential parent node with the highest number of child nodes as a secondary DAG parent for the particular node, and joins the secondary DAG at the selected secondary DAG parent (e.g., for multicast and/or broadcast message distribution). This may recursively continue, such that nodes gravitate toward parents with more children, potentially allowing parents with fewer children to relinquish their parental responsibilities.

Claims

1. A method, comprising:

receiving, at a particular node in a computer network, an indication of a number of child nodes of one or more potential parent nodes to the particular node in a directed acyclic graph (DAG);

selecting a particular potential parent node with the highest number of child nodes as a DAG parent for the particular node; and

joining the DAG by the particular node at the selected DAG parent.

2. The method as in claim 1, wherein two or more of the potential parent nodes have the same highest number of child nodes, wherein selecting comprises:

selecting one of the two or more potential parent nodes having the same highest number as the DAG parent.

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

determining that the particular node has only one available potential parent node; and

, in response,

selecting the one available potential parent node as the DAG parent; and

notifying the DAG parent that it is the only available potential parent node of the particular node.

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

utilizing the DAG for at least one of either multicast message distribution or broadcast message distribution.

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

notifying a previous parent of the particular node in the DAG of the selected DAG parent.

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

receiving a notification from a particular potential parent node that the particular potential parent node must be a parent node; and

, in response,

selecting the particular potential parent node as the DAG parent.

7. The method as in claim 6, wherein two or more of the potential parent nodes must be a parent node, wherein selecting comprises:

selecting one of the two or more potential parent nodes that must be a parent node as the DAG parent.

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

determining a particular number of child nodes that have joined the DAG at the particular node as their parent; and

advertising the particular number of child nodes into the network for the particular node.

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

adjusting the particular number of child nodes that is advertised with a phantom number of child nodes.

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

receiving a notification from a particular child node that the particular node must be a parent node to the particular child node; and

, in response,

advertising that the particular node must be a parent node into the network.

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

repeating distributed messages only in response to the particular node having one or more child nodes in the DAG.

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

selecting a plurality of DAG parents; and

joining the DAG by the particular node at the plurality of selected DAG parents.

13. An apparatus, comprising:

one or more network interfaces to communicate in a directed acyclic graph (DAG) in a computer network as a particular 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 an indication of a number of child nodes of one or more potential parent nodes to the particular node in the DAG;

select a particular potential parent node with the highest number of child nodes as a DAG parent for the particular node; and

join the DAG by the particular node at the selected DAG parent.

14. The apparatus as in claim 13, wherein two or more of the potential parent nodes have the same highest number of child nodes, wherein the process when executed is further operable to select one of the two or more potential parent nodes having the same highest number as the DAG parent.

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

receive a notification from a particular potential parent node that the particular potential parent node must be a parent node; and

, in response,

select the particular potential parent node as the DAG parent.

16. The apparatus as in claim 13, wherein the process when executed is further operable to utilize the DAG for at least one of either multicast message distribution or broadcast message distribution.

17. The apparatus as in claim 13, wherein the process when executed is further operable to notify a previous parent of the particular node in the DAG of the selected DAG parent.

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

determine a particular number of child nodes that have joined the DAG at the particular node as their parent; and

advertise the particular number of child nodes into the network for the particular node.

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

adjust the particular number of child nodes that is advertised with a phantom number of child nodes.

20. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor on a particular node in a directed acyclic graph (DAG) operable to:

receive an indication of a number of child nodes of one or more potential parent nodes to the particular node in the DAG;

select a particular potential parent node with the highest number of child nodes as a DAG parent for the particular node; and

join the DAG by the particular node at the selected DAG parent.

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

determine a particular number of child nodes that have joined the DAG at the particular node as their parent; and

advertise the particular number of child nodes into the network for the particular node.