Multicast Message Retransmission

• US 20120117438A1
• 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: Shaffer, Shmuel, Vasseur, Jean-Philippe, Shetty, Sandeep Jay
• Granted Patent: US 8,583,978 B2
• Time in Patent Office: Days
• US Class Current: 714/749
• CPC Class Codes: H04L 1/1825 Adaptation of specific ARQ protocol parameters according to transmission conditions
• CPC Class Codes: H04L 1/1867 Arrangements specially adapted for the transmitter end
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 2001/0097 Relays

Abstract

In one implementation, a method of distributing a multicast message in a wireless mesh network includes receiving a multicast message from a parent node of an intermediate node. The method includes transmitting the multicast message to child nodes of the intermediate node. The method includes storing the multicast message in a cache at the intermediate node. The method includes intercepting an acknowledgement message from each acknowledging child node within an acknowledging subset of less than all of the child nodes. The method includes accessing information indicating a population of the child nodes to which the multicast message transmission was directed. The method includes comparing the acknowledging subset of the child nodes with the population of the child nodes. The method includes identifying a non-acknowledging subset of less than all of the child nodes. The method includes retransmitting the multicast message to the non-acknowledging subset of the child nodes.

Claims

1. A method of distributing a multicast message in a Low power and Lossy Networks (LLN), the method comprising:

receiving, at an intermediate node in a multicast network, a multicast message from a parent node of the intermediate node, wherein the multicast network is a directed acyclic graph and the parent node is located closer to a root node of the directed acyclic graph than the intermediate node;

transmitting the multicast message to child nodes of the intermediate node in the multicast network, wherein the child nodes are located further from the root node of the directed acyclic graph than the intermediate node;

storing the multicast message in a cache at the intermediate node;

receiving, at the intermediate node in the multicast network, an acknowledgement message from each acknowledging child node within an acknowledging subset of less than all of the child nodes of the intermediate node, wherein the acknowledgement message indicates that the acknowledging child node successfully received the multicast message;

accessing information indicating a population of the child nodes to which the multicast message transmission was directed;

comparing the acknowledging subset of the child nodes revealed by the acknowledgement messages with the population of the child nodes to which the multicast message transmission was directed;

identifying, based on results of the comparison between the acknowledging subset of the child nodes revealed by the acknowledgement messages with the population of the child nodes to which the multicast message transmission was directed, a non-acknowledging subset of less than all of the child nodes; and

retransmitting, from the cache at the intermediate node, the multicast message to the non-acknowledging subset of the child nodes.

2. The method of claim 1, further comprising:

receiving, at the intermediate node, a cache indicator in the multicast message;

determining, based on the received cache indicator, that the multicast message should be stored in the cache; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the multicast message should be stored in the cache.

3. The method of claim 1, further comprising:

receiving, at the intermediate node, a cache message that is separate from the multicast message;

determining, based on the received cache message, that the multicast message should be stored in the cache; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the multicast message should be stored in the cache.

4. The method of claim 1, further comprising:

determining that the intermediate node is at least a threshold number of nodes away from the parent node; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the intermediate node is at least the threshold number of nodes away from the parent node.

5. The method of claim 4, wherein the threshold number of nodes is based on a proximity of the intermediate node to the root node of the multicast network.

6. The method of claim 1, further comprising:

determining that the multicast message is a critical message; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the multicast message is a critical message.

7. The method of claim 1, wherein the storing of the multicast message in the cache at the intermediate node occurs automatically along a multicast distribution path.

8. The method of claim 1, wherein retransmitting the multicast message to the non-acknowledging subset of the child nodes includes transmitting the multicast message as a unicast message.

9. The method of claim 1, wherein retransmitting the multicast message to the non-acknowledging subset of the child nodes includes retransmitting the multicast message to only those portions of the multicast network for which an acknowledgement message has not been received.

10. The method of claim 1, further comprising:

configuring the intermediate node to be a caching node, and

storing the multicast message in response to the intermediate node being configured to be a caching node.

11. The method of claim 1 wherein the multicast message is stored for a limited period of time.

12. The method of claim 1 wherein the intermediate node listens for a limited period of time and then generates a report after the expiration of the limited period of time.

29. The method of claim 1 further comprising:

enabling the intermediate node to intercept an acknowledgement message;

recording an indication of the acknowledgement message for use in subsequent reporting; and

terminating transmission of the acknowledgment messages.

13. A system configured to distribute a multicast message in a LLN, the system comprising a processor and instructions that when executed on a processor cause the processor to perform operations that include:

receiving, at an intermediate node in a multicast network, a multicast message from a parent node of the intermediate node, wherein the multicast network is a directed acyclic graph and the parent node is located closer to a root node of the directed acyclic graph than the intermediate node;

transmitting the multicast message to child nodes of the intermediate node in the multicast network, wherein the child nodes are located further from the root node of the directed acyclic graph than the intermediate node;

storing the multicast message in a cache at the intermediate node;

receiving, at the intermediate node in the multicast network, an acknowledgement message from each acknowledging child node within an acknowledging subset of less than all of the child nodes of the intermediate node, wherein the acknowledgement message indicates that the acknowledging child node successfully received the multicast message;

accessing information indicating a population of the child nodes to which the multicast message transmission was directed;

comparing the acknowledging subset of the child nodes revealed by the acknowledgement messages with the population of the child nodes to which the multicast message transmission was directed;

identifying, based on results of the comparison between the acknowledging subset of the child nodes revealed by the acknowledgement messages with the population of the child nodes to which the multicast message transmission was directed, a non-acknowledging subset of less than all of the child nodes; and

retransmitting, from the cache at the intermediate node, the multicast message to the non-acknowledging subset of the child nodes.

14. The system of claim 13, further comprising instructions that include:

receiving, at the intermediate node, a cache indicator in the multicast message;

determining, based on the received cache indicator, that the multicast message should be stored in the cache; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the multicast message should be stored in the cache.

15. The system of claim 13, further comprising instructions that include:

receiving, at the intermediate node, a cache message that is separate from the multicast message;

determining, based on the received cache message, that the multicast message should be stored in the cache; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the multicast message should be stored in the cache.

16. The system of claim 13, further comprising instructions that include:

determining that the intermediate node is at least a threshold number of nodes away from the parent node; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the intermediate node is at least the threshold number of nodes away from the parent node.

17. The system of claim 16, wherein the threshold number of nodes is based on a proximity of the intermediate node to the root node of the multicast network.

18. The system of claim 13, further comprising instructions that include:

determining that the multicast message is a critical message; and

wherein the storing of the multicast message in the cache at the intermediate node occurs in response to determining that the multicast message is a critical message.

19. The system of claim 13, wherein the storing of the multicast message in the cache at the intermediate node occurs automatically along a multicast distribution path.

20. The system of claim 13, wherein retransmitting the multicast message to the non-acknowledging subset of the child nodes includes transmitting the multicast message as a unicast message.

21. The system of claim 13, wherein retransmitting the multicast message to the non-acknowledging subset of the child nodes includes retransmitting the multicast message to only those portions of the multicast network for which an acknowledgement message has not been received.

22. The system of claim 13, further comprising instructions that include:

configuring the intermediate node to be a caching node, and

storing the multicast message in response to the intermediate node being configured to be a caching node.

23. The system of claim 13 wherein the multicast message is stored for a limited period of time.

24. The system of claim 13 wherein the intermediate node listens for a limited period of time and then generates a report after the expiration of the limited period of time.

25. A computer program on a computer readable medium to distribute a multicast message in a LLN, the computer program comprising instructions that when executed on a processor cause the processor to perform operations that include:

receiving, at an intermediate node in a multicast network, a multicast message from a parent node of the intermediate node, wherein the multicast network is a directed acyclic graph and the parent node is located closer to a root node of the directed acyclic graph than the intermediate node;

transmitting the multicast message to child nodes of the intermediate node in the multicast network, wherein the child nodes are located further from the root node of the directed acyclic graph than the intermediate node;

storing the multicast message in a cache at the intermediate node;

receiving, at the intermediate node in the multicast network, an acknowledgement message from each acknowledging child node within an acknowledging subset of less than all of the child nodes of the intermediate node, wherein the acknowledgement message indicates that the acknowledging child node successfully received the multicast message;

accessing information indicating a population of the child nodes to which the multicast message transmission was directed;

comparing the acknowledging subset of the child nodes revealed by the acknowledgement messages with the population of the child nodes to which the multicast message transmission was directed;

identifying, based on results of the comparison between the acknowledging subset of the child nodes revealed by the acknowledgement messages with the population of the child nodes to which the multicast message transmission was directed, a non-acknowledging subset of less than all of the child nodes; and

retransmitting, from the cache at the intermediate node, the multicast message to the non-acknowledging subset of the child nodes.

26. A method of distributing a multicast message in a LLN, the method comprising:

analyzing the topology of a LLN based on a directed acyclic graph (DAG) for the LLN, the DAG identifying a number of children and a distance from children to a DAG root;

identifying candidate nodes to becoming store and forward multicasting nodes based on at least the number of the children and the distance from the children to the DAG root; and

filtering the candidate nodes based on a relative distance to other candidate nodes within the DAG and a relative distance between a specified candidate node and the DAG root.

27. A system with a processor that distributes a multicast message in a LLN, the system also comprising instructions on a computer readable medium that when executed on a processor cause the processor to perform instructions that include:

analyzing the topology of a LLN based on a directed acyclic graph (DAG) for the LLN, the DAG identifying a number of children and a distance from children to a DAG root;

identifying candidate nodes to becoming store and forward multicasting nodes based on at least the number of the children and the distance from the children to the DAG root; and

filtering the candidate nodes based on a relative distance from to other candidate nodes within the DAG and a relative distance between a specified candidate node and the DAG root.

28. A computer program stored on a computer readable medium comprising instructions that when executed on a processor cause the processor to perform operations that include:

analyzing the topology of a LLN based on a directed acyclic graph (DAG) for the LLN, the DAG identifying a number of children and a distance from children to a DAG root;

identifying candidate nodes to becoming store and forward multicasting nodes based on at least the number of the children and the distance from the children to the DAG root; and

filtering the candidate nodes based on a relative distance from to other candidate nodes within the DAG and a relative distance between a specified candidate node and the DAG root.