Efficient Message Distribution for Directed Acyclic Graphs

• US 20120233326A1
• 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, Shetty, Sandeep Jay, Vasseur, Jean-Philippe
• Granted Patent: US 8,595,359 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: H04W 40/023 Limited or focused flooding to selected areas of a network
• 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 primary DAG receives a distributed message from distributing nodes, and from this, deterministically selects a distributing node as a distributing parent in a secondary DAG from which distributed messages are to be received. The particular node may then inform the deterministically selected distributing parent that it is being used by the particular node as its distributing parent, and if the selected distributing parent is not the particular node'"'"'s primary DAG parent, then the primary DAG parent is informed that it need not send distributed messages for the particular node. In another embodiment, a distributing node continues to repeat distributed messages in response to receiving notification that it is being used as a distributing parent, and if a primary DAG parent, prevents the repeating in response to receiving a notification from all of its child nodes that it need not send distributed messages.

Claims

1. A method, comprising:

receiving a distributed message from one or more distributing nodes at a particular node in a primary directed acyclic graph (DAG) in a computer network;

deterministically selecting a distributing node from the one or more distributing nodes as a distributing parent for a secondary DAG from which distributed messages are to be received;

informing the deterministically selected distributing node that the particular node is using the deterministically selected distributing node as the distributing parent; and

in response to the distributing parent not being a primary DAG parent of the to particular node, informing the primary DAG parent that the primary DAG parent need not send distributed messages for the particular node.

2. The method as in claim 1, wherein informing the primary DAG parent that the primary DAG parent need not send distributed messages for the particular node is further in response to receiving an acknowledgment from the distributing parent that the distributing parent will send distributed messages for the particular node.

3. The method as in claim 1, wherein deterministically selecting comprises:

determining an identification (ID) of the one or more distributing nodes; and

selecting the distributing parent as one of either the highest ID or lowest ID based on configuration shared with all nodes of the DAG.

4. The method as in claim 3, wherein the ID is a media access control (MAC) address.

5. The method as in claim 1, wherein the deterministically selected distributing node is a first distributing node, the method further comprising:

deterministically selecting a second distributing node as the distributing parent for the secondary DAG based on a topology change in the computer network;

informing the second distributing node that the particular node is using the second distributing node as the distributing parent; and

informing the first distributing node that the particular node is not using the first distributing node as the distributing parent.

6. The method as in claim 1, wherein deterministically selecting comprises:

deterministically selecting a plurality of distributing nodes to be a plurality of redundant distributing parents from which redundant distributed messages are to be received by the particular node.

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

determining that a distributed message is received by the particular node by fewer than the plurality of redundant distributing parents; and

in response, deterministically replacing those distributing parents from which a distributed message was not received.

8. The method as in claim 1, wherein deterministically selecting comprises:

limiting the deterministic selection of the distributing parent for the particular node from one or more distributing nodes that are at a same or lower rank in the primary DAG than the particular node.

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

receiving a request from the distributing parent to select a different distributing parent; and

in response, if a second distributing parent is available, selecting the second distributing parent.

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

receiving an indication that a particular distributing node of the one or more distributing nodes must be a distributing parent to at least one node in the secondary DAG; and

in response, selecting the particular distributing node as the distributing parent for the particular node.

11. The method as in claim 1, wherein the distributed message is selected from a group consisting of a broadcast message and a multicast message.

12. An apparatus, comprising:

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

determine a set of one or more distributing nodes from which a distributed message is received;

deterministically select a distributing node from the one or more distributing nodes as a distributing parent for a secondary DAG from which distributed messages are to be received;

inform the deterministically selected distributing node that the particular node is using the deterministically selected distributing node as the distributing parent; and

in response to the distributing parent not being a primary DAG parent of the particular node, inform the primary DAG parent that the primary DAG parent need not send distributed messages for the particular node.

13. The apparatus as in claim 12, wherein the process when executed is further operable to inform the primary DAG parent that the primary DAG parent need not send distributed messages for the particular node in further response to receiving an acknowledgment from the distributing parent that the distributing parent will send distributed messages for the particular node.

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

determine an identification (ID) of the one or more distributing nodes; and

select the distributing parent as one of either the highest ID or lowest ID based on configuration shared with all nodes of the primary DAG.

15. The method as in claim 14, wherein the ID is a media access control (MAC) address.

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

deterministically select a plurality of distributing nodes to be a plurality of redundant distributing parents from which redundant distributed messages are to be received by the particular node.

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

determine a set of one or more distributing nodes from which a distributed message is received;

deterministically select a distributing node from the one or more distributing nodes as a distributing parent for a secondary DAG from which distributed messages are to be received;

inform the deterministically selected distributing node that the particular node is using the deterministically selected distributing node as the distributing parent; and

in response to the distributing parent not being a primary DAG parent of the particular node, inform the primary DAG parent that the primary DAG parent need not send distributed messages for the particular node.

18. A method, comprising:

transmitting a distributed message from a distributing node in a primary directed acyclic graph (DAG) in a computer network;

in response to receiving a notification that a particular node is using the distributing node as a distributing parent, repeating distributed messages from the distributing node in a secondary DAG; and

in response to the distributing node being a primary DAG parent having received a notification from all child nodes of the primary DAG parent that the primary DAG parent need not send distributed messages for the respective child node, preventing repeating of distributed messages from the distributing node in the secondary DAG.

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

in response to receiving the notification that the particular node is using the distributing node as a distributing parent, sending an acknowledgment to the particular node that the distributing node is the distributing parent for the particular node.

20. The method as in claim 18, wherein the distributing node is a primary DAG parent, the method further comprising:

receiving, within the notification from a particular child node of the distributing node that the distributing node need not send distributed messages for the particular child node, a list of one or more distributing parents of the particular child node; and

preventing repeating of distributed messages from the distributing node in further response to the list of one or more distributing parents of the particular child node not containing any potential child nodes of the distributing node.

21. The method as in claim 18, further comprising:

in response to a number of particular nodes using the distributing node as a distributing parent being below a threshold, requesting that the particular nodes using the distributing node as a distributing parent select another distributing parent.

22. The method as in claim 18, further comprising:

determining that the distributing node must be a distributing parent for at least one particular node in the secondary DAG; and

in response, broadcasting an indication that the distributing node must be a distributing parent in the secondary DAG.

23. The method as in claim 18, wherein the distributed message is selected from a group consisting of a broadcast message and a multicast message.

24. An apparatus, comprising:

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

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;

transmit a distributed message into the computer network; and

set an operating state of the apparatus as;

i) a distributing parent state in response to receiving a notification that a particular node is using the apparatus as its distributing parent in a secondary DAG, the distributing parent operating state to repeat distributed messages on the secondary DAG; and

ii) a non-distributing node state in response to the apparatus being a primary DAG parent having received a notification from all child nodes of the apparatus that the apparatus need not send distributed messages for the respective child node, the non-distributing node operating state to prevent repeating of distributed messages from the apparatus on the secondary DAG.

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

receive, within the notification from a particular child node of the apparatus that the apparatus need not send distributed messages for the particular child node, a list of one or more distributing parents of the particular child node; and

set an operating state as the non-distributing parent in further response to the list of one or more distributing parents of the particular child node not containing any potential child nodes of the apparatus.

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

in response to a number of particular nodes using the apparatus as a distributing parent being below a threshold, request that the particular nodes using the apparatus as a s distributing parent select another distributing parent.

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

determine that the apparatus must be a distributing parent for at least one particular node in the secondary DAG; and

in response, broadcast an indication that the apparatus must be a distributing parent in the secondary DAG.

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

transmit a distributed message from the device;

in response to receiving a notification’

that a particular node is using the device as a distributing parent in a secondary DAG, repeat distributed messages from the device on the secondary DAG; and

in response to the device being a primary DAG parent having received a notification from all child nodes of the device that the device need not send distributed messages for the respective child node, prevent repeating of distributed messages from the device on the secondary DAG.