SYSTEM AND METHOD FOR MANAGING ACKNOWLEDGEMENT MESSAGES IN A VERY LARGE COMPUTER NETWORK

• US 20120113986A1
• 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,520,676 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 1/1854 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

A multicast message may be distributed by receiving, at a first node in a multicast network, a multicast message from a parent node of the first node. The multicast message is transmitted to child nodes of the first node in the multicast network. A population of the child nodes to which the multicast message was transmitted is accessed and acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node are received. Child nodes revealed by the received acknowledgement messages are compared with child nodes determined to be among the population of child nodes to which the multicast message is expected to be received. Based on results of the comparison, a compressed non-acknowledging subset is identified and transmitted to the parent node.

Claims

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

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node;

comparing child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes by which the multicast message is expected to be received, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received; and

transmitting an indication of the non-acknowledging nodes to the parent node of the first node.

2. The method of claim 1 further comprising:

accessing a threshold of time and using the time threshold to invoke transmission of the indication of non-acknowledging nodes.

3. The method of claim 1 wherein receiving the multicast message from the parent node includes:

receiving the multicast message configuring the first node to employ a lack of acknowledgement (LACK) reporting configuration whereby the first node transmits an indication of the non-acknowledging nodes to the parent node.

4. The method of claim 1 wherein transmitting the multicast message to the child nodes includes transmitting to the child nodes that are associated with a specified subnet as identified by an address prefix.

5. The method of claim 4 further comprising:

determining that a second node in the child nodes does not belong to a specified subnet;

instructing the second node to join the specified subnet;

transmitting, in response to determining that the second node has joined the specified subnet, the multicast message to the second node.

11. The method of claim 1 further comprising determining a subset of child nodes from which acknowledgement messages are expected, wherein comparing includes comparing child nodes revealed by the received acknowledgement messages with child nodes from which acknowledgement messages are expected.

12. The method of claim 1 further comprising:

enabling the first 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. The method of claim 1 further comprising determining a subset of child nodes from which acknowledgement messages are expected, wherein comparing is between child nodes revealed by the received acknowledgement messages and child nodes from which acknowledgement messages are expected.

14. The method of claim 1 wherein the indication of non-acknowledging nodes being transmitted includes a summary of either of the acknowledging or the non-acknowledging nodes.

15. The method of claim 1 wherein the indication of non-acknowledging nodes is transmitted as a summary of nodes that have not acknowledged.

16. The method of claim 1 further comprising providing compressed information about the list of nodes that sent an acknowledgement message.

17. The method of claim 1, further comprising providing compressed information about the list of nodes that did not sent an acknowledgement message.

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

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node in the multicast network;

accessing a population of the child nodes by which the multicast message is expected to be received;

receiving, at the first node in the multicast network, acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node;

comparing child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes by which the multicast message was expected to be received;

identifying, based on results of the comparison of child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received; and

determining, based on identifying the non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received, a number of acknowledgement messages received on the first node relative to a size of the list of child nodes; and

transmitting the number of acknowledgement messages that have been received to the parent node.

7. The method of claim 6 further comprising:

accessing a threshold of time and using the time threshold to invoke transmission of the indication of non-acknowledging nodes.

8. The method of claim 7 wherein the threshold of time in the first node is automatically determined based on a combination of the number of children of the first node and the distance of the first node from a most distant child.

9. The method of claim 6 further comprising:

accessing a threshold of time and using the time threshold to invoke transmission of the indication of non-acknowledging nodes; and

configuring the first node to selectively retransmit the multicast message if less than a threshold number of acknowledgement messages are received within the threshold period of time.

10. The method of claims 6 further comprising enabling child nodes to act as a proxy to aggregate information related to the distribution of the multicast message.

18. The method of claim 6 further comprising:

determining whether content in the multicast message should be sent to each node in the non-acknowledging subset of less than all of the child nodes using a multicast format or a unicast format;

constructing an appropriate unicast or multicast message for each node in the non-acknowledging subset; and

transmitting the appropriate unicast or multicast message for each node in the non-acknowledging subset.

19. A method of distributing a multicast message in a wireless mesh network, the method comprising:

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node and to subsequent children in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, non-acknowledgement messages which reveal child nodes that are among a non-acknowledging subset of less than all of the children nodes of the first node;

comparing child nodes revealed by the received non-acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received non-acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received;

determining, based on identifying the non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received, whether to send a lack of acknowledgment (LACK) message; and

constructing a LACK message to be sent by the first node to be sent using an uplink to the parent node.

20. 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:

receive, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmit the multicast message to child nodes of the first node in the multicast network;

access a population of the child nodes to which the multicast message was transmitted;

receive, at the first node in the multicast network, acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node;

compare child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identify, based on results of the comparison of child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received; and

transmit an indication of the non-acknowledging nodes to the parent node of the first node.

21. 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:

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node;

comparing child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received; and

determining, based on identifying the non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received, a number of acknowledgement messages received on the first node relative to a size of the list of child nodes; and

transmitting the number of acknowledgement messages that have been received to the parent node.

22. The system of claim 21 wherein the threshold of time in the first node is automatically determined based on a combination of the number of children of the first node and the distance of the first node from a most distant child.

23. The system of claim 21 further comprising instructions that include:

accessing a threshold of time and using the time threshold to invoke transmission of the indication of non-acknowledging nodes; and

configuring the first node to selectively retransmit the multicast message if less than a threshold number of acknowledgement messages are received within the threshold period of time.

24. The system of claims 21 further comprising instructions that include enabling child nodes to act as a proxy to aggregate information related to the distribution of the multicast message.

25. The system of claim 21 further comprising instructions that include:

determining whether content in the multicast message should be sent to each node in the non-acknowledging subset of less than all of the child nodes using a multicast format or a unicast format;

constructing an appropriate unicast or multicast message for each node in the non-acknowledging subset; and

transmitting the appropriate unicast or multicast message for each node in the non-acknowledging subset.

26. 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:

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node and to subsequent children in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, non-acknowledgement messages which reveal child nodes that are among a non-acknowledging subset of less than all of the children nodes of the first node;

comparing child nodes revealed by the received non-acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received non-acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received;

determining, based on identifying the non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received, whether to send a lack of acknowledgment (LACK) message; and

constructing a LACK message to be sent by the first node to be sent using an uplink to the parent node.

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

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node;

comparing child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received; and

transmitting an indication of the non-acknowledging nodes to the parent node of the first node.

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

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, acknowledgement messages which reveal child nodes that are among an acknowledging subset of less than all of the child nodes of the first node;

comparing child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received; and

determining, based on identifying the non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received, a number of acknowledgement messages received on the first node relative to a size of the list of child nodes; and

transmitting the number of acknowledgement messages that have been received to the parent node.

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

receiving, at a first node in a multicast network, a multicast message from a parent node of the first node;

transmitting the multicast message to child nodes of the first node and to subsequent children in the multicast network;

accessing a population of the child nodes to which the multicast message was transmitted;

receiving, at the first node in the multicast network, non-acknowledgement messages which reveal child nodes that are among a non-acknowledging subset of less than all of the children nodes of the first node;

comparing child nodes revealed by the received non-acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted;

identifying, based on results of the comparison of child nodes revealed by the received non-acknowledgement messages with child nodes determined to be among the population of child nodes to which the multicast message was transmitted, a non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received;

determining, based on identifying the non-acknowledging subset of less than all of the child nodes from which the acknowledgement message has not yet been received, whether to send a lack of acknowledgment (LACK) message; and

constructing a LACK message to be sent by the first node to be sent using an uplink to the parent node.