Reliable broadcast in a federation of nodes

• US 9,832,104 B2
• Filed: 02/11/2010
• Issued: 11/28/2017
• Est. Priority Date: 02/11/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sinha, Rishi Rakesh, Xun, Lu, Kakivaya, Gopala Krishna Reddy
• Primary Examiner(s): DUONG, DUC T
• Application Number:
  US12/703,799
• Publication Number:
  US 20110194558A1
• Time in Patent Office: 2,847 Days
• Field of Search: None
• CPC Class Codes: H04L 45/16 Multipoint routing

Abstract

Architecture that provides reliable communications of broadcast data (e.g., a message) in a collection of nodes. Each node in the collection is assigned a range of identifiers in a token. The union of the tokens for all nodes is the entire identifier range space. Each node that receives a reliable broadcast message from an originator node acknowledges receipt of the message using its token. One or more intermediate nodes forward the message from the originator node to other nodes with which the originator node has no direct communications (multi-level node structure). The indirect nodes each send acknowledgements back to the parent nodes (which can be an intermediate node) which combine the tokens to ensure the entire range space for the associated assigned token range is covered. The originator node ultimately receives tokens to compute if all nodes have received the message.

Claims

1. A computing device, comprising:

a memory and a hardware processor, wherein the memory and the hardware processor are respectively configured to store and execute computer-executable instructions, wherein the instructions upon execution cause the computing device to perform operations, the operations comprising;

broadcasting a message to nodes of a collection of nodes;

assigning distinctive ranges of identifiers to the nodes as tokens, wherein a set of tokens from at least one of neighbor nodes or routing nodes, of the collection of nodes, is accumulated at an intermediate node, and wherein the intermediate node determines if the message has been received at each of the at least one of the neighbor nodes or the routing nodes;

receiving at least one separate acknowledgement and at least one consolidated acknowledgement from the nodes of the collection of nodes using the set of tokens;

determining if the message was received by a particular node of the collection nodes based on the set of tokens; and

declaring reliable broadcast of the message based on the at least one separate acknowledgement and the at least one consolidated acknowledgement from the nodes of the collection.

2. The computing device of claim 1, wherein a distinctive range of identifiers is a token that identifies nodes in a neighborhood.

3. The computing device of claim 1, wherein the tokens include distinctive ranges of identifiers that identify routing nodes of the collection.

4. The computing device of claim 3, wherein a routing node is configured to broadcast the message to associated child nodes identified in a broadcast range assigned to the routing node.

5. The computing device of claim 1, wherein the operations further comprise:

resending the message to one or more nodes from which acknowledgements of message receipt are not received.

6. A method, the method comprising acts of:

receiving a message broadcast from an originator node to nodes of a neighborhood and routing nodes, of a collection of nodes, wherein each neighbor node of the neighborhood and each routing node is assigned a distinctive range of identifiers as a token;

receiving a corresponding broadcast range that identifies nodes targeted for the message;

consolidating acknowledgments of receipt of the message from multiple nodes of the neighbor nodes and the routing nodes, as a consolidated confirmation of acknowledgments from the multiple nodes that received the message;

returning the consolidated confirmation to the originator node that broadcasts the message, wherein the consolidated confirmation represents receipt of the message by the nodes associated with the routing node that were targeted for the message; and

resending the message to nodes in ranges absent in the consolidated confirmation.

7. The method of claim 6, further comprising resending the message to a node of the collection in response to not receiving a token of acknowledgement from the node of the collection.

8. A computer-implemented communications method executing with a processor and memory, the method comprising:

receiving a broadcast message at a routing node of a collection of nodes, wherein each node of the collection is assigned a distinctive range of identifiers as a token;

routing the broadcast message to targeted nodes based on a routing token, the targeted nodes comprising at least nodes in a neighborhood of the routing node and other nodes;

receiving acknowledgments of receipt of the message from at least some of the targeted nodes;

determining which of the targeted nodes received the message based on the acknowledgments of receipt;

consolidating the acknowledgments into a consolidated confirmation;

returning the consolidated confirmation;

receiving broadcast identifiers; and

splitting the broadcast identifiers to accommodate at least one of neighbor nodes or other routing nodes.

9. The method of claim 8, further comprising receiving a broadcast range assignment that identifies child nodes targeted to receive the message.

10. The method of claim 8, further comprising receiving the broadcast identifiers at routing nodes and at neighbor nodes.

11. The method of claim 8, further comprising creating the ranges of identifiers for nodes as disjointed ranges the union of which encompasses all the nodes of the collection.

12. The method of claim 8, further comprising resending the message to a particular targeted node in response to not receiving an acknowledgement from the particular targeted node.

13. The method of claim 8, further comprising assigning the ranges of identifiers to nodes of the collection as tokens and counting the tokens to determine if the message was received by all targeted nodes of the collection.

14. A computer-readable physical storage device having computer-executable instructions stored therein, that when executed by a processor cause a computing device to perform actions, the actions comprising:

broadcasting a message to nodes of a collection of nodes;

assigning distinctive ranges of identifiers to the nodes as tokens, wherein a set of tokens from at least one of neighbor nodes or routing nodes of the collection of nodes is accumulated at an intermediate node, and the intermediate node determines if the message has been received at each of the at least one of neighbor nodes or the routing nodes;

receiving at least one separate acknowledgement and at least one consolidated acknowledgement from the nodes of the collection of nodes using the set of tokens;

determining if the message was received by a particular node of the collection nodes based on the set of tokens; and

sending a consolidated confirmation representing delivery of the broadcast to a plurality of the neighbor nodes or routing nodes based on the set of tokens.

15. A computer-implemented communications method of managing a distributed collection of nodes having an originator node that broadcasts a message to other nodes of the collection, comprising acts of:

assigning distinctive ranges of identifiers to the nodes as tokens;

accumulating a set of tokens from associated neighbor nodes or routing nodes at an intermediate node;

determining, at the intermediate node, if the message has been received at each of the associated neighbor nodes or routing nodes based on the accumulated set of tokens; and

sending a consolidated confirmation representing delivery of the broadcast to a plurality of the associated neighbor nodes or routing nodes based on the accumulated set of tokens.

16. A computer-readable physical storage device comprising computer-executable instructions that when executed by a processor, cause the processor to perform a method comprising acts of:

receiving a message broadcast from an originator node to neighbor nodes of a neighborhood and routing nodes of a collection of nodes, wherein each neighbor node of the neighborhood and each routing node are associated with distinctive ranges of identifiers as tokens;

receiving a corresponding broadcast range that identifies nodes targeted for the message;

accumulating at an intermediate node a set of tokens from neighbor nodes or routing nodes;

determining at the intermediate node, if the message has been received at each of the neighbor nodes or routing nodes based on the accumulated set of tokens;

sending a confirmation to the originator node that represents receipt of the message by the nodes targeted for the message; and

resending the message to at least one node for which receipt of the message was not determined to have been received.

17. A computer-implemented communications system, comprising:

routing nodes configured to receive a message broadcast from an originator node to neighborhood nodes and other routing nodes, wherein the other routing nodes and neighborhood nodes each receive a corresponding broadcast range that identifies nodes targeted to receive the broadcast message, and the other routing nodes each send a confirmation to the originator node which represents that corresponding targeted child nodes received the message; and

intermediate nodes each configured to accumulate confirmations from the other routing nodes and neighborhood nodes in corresponding broadcast ranges that are targeted to receive the broadcast message, the intermediate nodes determine if the message has been received at each of the associated neighbor nodes or the routing nodes, the intermediate nodes send consolidated confirmations to the originator node as to delivery of the broadcast.

18. A computer-readable physical storage device comprising computer-executable instructions that when executed by a processor, cause the processor to perform a method comprising acts of:

receiving a broadcast message at a routing node and nodes of a neighborhood of the routing node, of a collection of nodes, wherein each node of the collection is assigned a distinctive range of identifiers as a token;

routing the broadcast message to targeted nodes comprising the nodes of the neighborhood and other nodes based on a routing token;

receiving acknowledgments of receipt of the message from targeted nodes;

determining which of the targeted nodes received the message based on the acknowledgments of receipt;

consolidating the acknowledgments as a consolidated confirmation; and

transmitting the consolidated confirmation to an originator of the broadcast message, wherein the consolidated confirmation represents receipt of the message by the nodes associated with the routing node that were targeted for the message.

19. A computer-implemented communications method, comprising acts of:

after all nodes are joined in a collection of nodes, receiving a message and a corresponding broadcast range with the message, from an originator node, the broadcast range identifies nodes targeted for the message, the targeted nodes comprise a routing node and child nodes of the routing node;

consolidating confirmations of receipt of the message, as tokens, the tokens received from the child nodes that received the message and neighbor nodes of the routing node that received the message, based on the broadcast range of the message, the routing node determining if the message has been received at each of the child nodes and the neighbor nodes based on the consolidation of the tokens;

sending an acknowledgment from the routing node to the originator node as to receipt of the message by the child nodes and the neighbor nodes associated with the routing node and targeted for the message; and

configuring a hardware processor to execute instructions stored in a hardware memory, the instructions executed to enable the acts of receiving the message, consolidating, and sending the acknowledgement.

20. A computer-readable physical storage device comprising computer-executable instructions that when executed by a processor, cause the processor to perform a method comprising acts of:

after all nodes are joined in a collection of nodes, receiving a message and a corresponding broadcast range with the message, from an originator node, the broadcast range identifies nodes targeted for the message, the targeted nodes comprise a routing node and child nodes of the routing node;

consolidating confirmations of receipt of the message, as tokens, the tokens received from the child nodes that received the message and neighbor nodes of the routing node that received the message, based on the broadcast range of the message, the routing node determining if the message has been received at each of the child nodes and the neighbor nodes based on the consolidation of the tokens; and

sending an acknowledgment from the routing node to the originator node as to receipt of the message by the child nodes and the neighbor nodes associated with the routing node and targeted for the message.

21. A computer-readable physical storage device comprising computer-executable instructions that when executed by a processor enable a communications system to serve as a routing node of a collection of nodes, controlling the system to perform:

after all nodes are joined into the collection of nodes, receiving a message broadcast to neighbor nodes and other nodes associated with the routing node, the message accompanied by a broadcast range which identifies the neighbor nodes and the other nodes targeted for the message;

receiving and consolidating confirmations of receipt of the message as a set of tokens, the tokens received from the other nodes of a routing node that received the message and the neighbor nodes of the routing node that received the message, the routing node determines if the message has been received at each of the neighbor nodes and the other nodes associated with the routing node based on the set of tokens; and

sending an acknowledgement from the routing node to an originator node of the message as to receipt of the message by nodes designated in the broadcast range.

22. A computer-implemented communications system serving as a routing node of a collection of nodes, the system comprising:

a hardware processor configured to process data;

a data storage device configured to store instructions which, upon execution of the instructions by the hardware processor, control the communications system to perform;

after all nodes are joined into the collection of nodes, receiving a message broadcast to neighborhood nodes and other nodes associated with the routing node, the message accompanied by a broadcast range which identifies the neighborhood nodes and the other nodes targeted for the message;

consolidating confirmations of receipt of the message, as tokens, the tokens received from the neighborhood nodes that received the message and other nodes associated with the routing node that received the message, the routing node determines if the message has been received at each of the neighborhood nodes and the other nodes associated with the routing node based on the set of tokens; and

sending an acknowledgement from the routing node to an originator node of the message as to receipt of the message by nodes designated in the broadcast range.

23. A method, the method comprising:

receiving, by a computing device, a message broadcast to neighbor nodes and other nodes associated with the computing device routing node, the message accompanied by a broadcast range which identifies the neighbor nodes and the other nodes targeted for the message;

receiving and consolidating confirmations of receipt of the message as a set of tokens, the tokens received from the other nodes associated with the computing device that received the message and the neighbor nodes associated with the computing device that received the message;

determining, by the computing device, if the message has been received at each of the neighbor nodes and the other nodes associated with the computing device based on the set of tokens; and

sending an acknowledgement from the computing device to an originator node of the message as to receipt of the message by nodes designated in the broadcast range.

24. The method of claim 23, the method comprising:

forwarding the message to one or more nodes from which acknowledgements of message was not received.

25. The method of claim 23, wherein the computing device is acting as a routing node for nodes in a neighborhood of the computing device.