Reliable multicast in low-power and lossy networks

Patent metadata

Field	Value
Publication number	US-2016277201-A1
Application number	US-201514661301-A
Country	US
Kind code	A1
Filing date	Mar 18, 2015
Priority date	Mar 18, 2015
Publication date	Sep 22, 2016
Grant date	—

Abstract

In one embodiment, a device in a network sends a first multicast message to a plurality of destinations in the network. The first multicast message includes a first bitmap that identifies the destinations. The device receives one or more acknowledgements from a subset of the destinations. The device determines a retransmission bitmap that identifies those of the plurality of destinations that did not acknowledge the first multicast message, based on the received one or more acknowledgements. The device sends a retransmission multicast message to those of the plurality of destinations that did not acknowledge the first multicast message. The retransmission multicast message includes the retransmission bitmap.

First claim

What is claimed is:

1 . A method comprising:
sending, by a device in a network, a first message to a plurality of destinations in the network, wherein the first multicast message includes a first bitmap that identifies the destinations; receiving, at the device, one or more acknowledgements from a subset of the destinations; determining, by the device, a retransmission bitmap that identifies those of the plurality of destinations that did not acknowledge the first multicast message, based on the received one or more acknowledgements; and sending, by the device, a retransmission multicast message to those of the plurality of destinations that did not acknowledge the first multicast message, wherein the retransmission multicast message includes the retransmission bitmap.

2 . The method as in claim 1 , wherein receiving, at the device, one or more acknowledgements from the subset of destinations comprises:
receiving, at the device, at least one aggregated acknowledgement that includes an aggregated bitmap that identifies two or more of the destinations that acknowledged the first multicast message.

3 . The method as in claim 2 , wherein the aggregated acknowledgement is generated by a particular node in the network after expiration of a timer maintained by the particular node.

4 . The method as in claim 1 , wherein the first bitmap and the retransmission bitmap identify a particular destination in the plurality of destinations by a specific bit in the bitmaps that is set by the device.

5 . The method as in claim 1 , further comprising:
assigning, by the device, each node in the network to a specific bit of a bitmap that represents the devices in the network; and setting, by the device, the single unique bit associated with a particular destination in the bitmap that represents the devices in the network

6 . The method as in claim 1 , wherein determining, by the device, the retransmission bitmap that identifies those of the plurality of destinations that did not acknowledge the first multicast message comprises:
aggregating, by the device, acknowledgement bitmaps included in the acknowledgements received by the device into a second bitmap; and determining, by the device, the retransmission bitmap as a difference between the first bitmap and the second bitmap.

7 . A method comprising:
forwarding, by a node in a network, a first multicast message to a plurality of destinations based on a first bitmap included in the first multicast message, wherein the first bitmap identifies the plurality of destinations; receiving, at the node, acknowledgements from two or more of the plurality of destinations, wherein a particular received acknowledgement includes an acknowledgement bitmap that identifies a particular one of the plurality of destinations that acknowledged receipt of the multicast message; aggregating, by the node, the received acknowledgements by aggregating the acknowledgement bitmaps into an aggregated bitmap, wherein the aggregated bitmap identifies those of the plurality of destinations that acknowledged receipt of the first multicast message; and providing, by the node, an aggregated acknowledgement that includes the aggregated bitmap to a source of the multicast message.

8 . The method as in claim 7 , wherein the received acknowledgements are aggregated by the node in response to expiration of a timer maintained by the node.

9 . The method as in claim 7 , wherein the node is a destination of the multicast message, and wherein the node sets a bit in the aggregated bitmap that is uniquely associated with the node.

10 . The method as in claim 7 , further comprising:
receiving, at the node, a retransmission multicast message that includes a retransmission bitmap that identifies those of the plurality of destinations that did not acknowledge the first multicast message; and forwarding, by the node, the retransmission multicast message to those of the plurality of destinations that did not acknowledge the first multicast message.

11 . An apparatus, comprising:
one or more network interfaces to communicate with a computer network; a processor coupled to the one or more network interfaces and configured to execute a process; and a memory configured to store the process executable by the processor, the process when executed operable to: send a first multicast message to a plurality of destinations in the network, wherein the first multicast message includes a first bitmap that identifies the destinations; receive one or more acknowledgements from a subset of the destinations; determine a retransmission bitmap that identifies those of the plurality of destinations that did not acknowledge the first multicast message, based on the received one or more acknowledgements; and send a retransmission multicast message to those of the plurality of destinations that did not acknowledge the first multicast message, wherein the retransmission multicast message includes the retransmission bitmap.

12 . The apparatus as in claim 11 , wherein the apparatus receives the one or more acknowledgements from the subset of destinations by:
receiving at least one aggregated acknowledgement that includes an aggregated bitmap that identifies two or more of the destinations that acknowledged the first multicast message.

13 . The apparatus as in claim 12 , wherein the aggregated acknowledgement is generated by a particular node in the network after expiration of a timer maintained by the particular node.

14 . The apparatus as in claim 11 , wherein the first bitmap and the retransmission bitmap identify a particular destination in the plurality of destinations by a specific bit in the bitmaps that is set by the device.

15 . The apparatus as in claim 11 , wherein the process when executed is further operable to:
assign each node in the network to a unique bit of a bitmap that represents the devices in the network; and set the single unique bit associated with a particular destination in the bitmap that represents the devices in the network

16 . The apparatus as in claim 11 , wherein the apparatus determines the retransmission bitmap by:
aggregating acknowledgement bitmaps included in the one or more acknowledgements received by the apparatus into a received bitmap; and determining the retransmission bitmap as a difference between the first bitmap and the received bitmap.

17 . An apparatus, comprising:
one or more network interfaces to communicate with a computer network; a processor coupled to the one or more network interfaces and configured to execute a process; and a memory configured to store the process executable by the processor, the process when executed operable to:
forward a first multicast message to a plurality of destinations based on a first bitmap included in the first multicast message, wherein the first bitmap identifies the plurality of destinations;
receive acknowledgements from two or more of the plurality of destinations, wherein a particular received acknowledgement includes an acknowledgement bitmap that identifies one of the plurality of destinations that acknowledged receipt of the multicast message;
aggregate the received acknowledgements by aggregating acknowledgement bitmaps into an aggregated bitmap, wherein the aggregated bitmap identifies those of the plurality of destinations that acknowledged receipt of the first multicast message; and
provide an aggregated acknowledgement that includes the aggregated bitmap to a source of the multicast message.

18 . The apparatus as in claim

Assignees

• Cisco Tech Inc

Inventors

• Thubert Pascal
• Wijnands Ijsbrand
• Shepherd Gregory

Classifications

• H04W72/30

  Resource management for broadcast services · CPC title

• H04W52/0219

  where the power saving management affects multiple terminals · CPC title

• H04L12/1881 Primary

  with schedule organisation, e.g. priority, sequence management · CPC title

• H04W72/005

  Electricity · mapped topic

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title