RELIABLE BROADCAST IN A FEDERATION OF NODES

• US 20110194558A1
• Filed: 02/11/2010
• Published: 08/11/2011
• Est. Priority Date: 02/11/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xun, Lu, Kakivaya, Gopala Krishna Reddy, Sinha, Rishi Rakesh
• Granted Patent: US 9,832,104 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• 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 computer-implemented communications system having a physical storage media, comprising:

a distributed collection of nodes having an originator node that broadcasts a message to other nodes of the collection;

an assignment component that assigns distinctive ranges of identifiers to the nodes as tokens; and

a confirmation component that determines if the message was received by the other nodes based on the associated tokens.

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

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

4. The system of claim 3, wherein a routing node further broadcasts the message to associated child nodes identified in a broadcast range assigned to the routing node.

5. The system of claim 1, wherein a set of tokens from associated neighbors and routing nodes is accumulated at an intermediate node, the intermediate node determines if the message has been received at each of the associated neighbors and routing nodes.

6. The system of claim 1, wherein the confirmation component receives separate acknowledgements and consolidated acknowledgements from the other nodes using the associated tokens.

7. The system of claim 1, wherein the originator node declares reliable broadcast of the message to all targeted nodes based on acknowledgements received from a subset of the other nodes.

8. The system of claim 1, further comprising a retry component that resends the message to one or more nodes from which acknowledgements of message receipt are not received.

9. A computer-implemented communications method executed in a processor and memory, comprising:

assigning distinctive ranges of identifiers as tokens to each of a node neighborhood and routing nodes of a collection;

broadcasting a message to nodes of the neighborhood and routing nodes from an originator node;

assigning a corresponding broadcast range to each of the routing nodes that identifies nodes targeted for the message;

receiving acknowledgments of receipt of the message at the originator node from collection nodes; and

determining reliable broadcast of the message based on the acknowledgements received.

10. The method of claim 9, further comprising:

assigning a range of identifiers in a token to nodes of a neighborhood; and

assigning distinctive ranges of identifiers to routing nodes in tokens.

11. The method of claim 9, further comprising:

consolidating acknowledgments from associated neighborhoods and associated routing nodes of the routing node as a consolidated confirmation; and

returning the consolidated confirmation and the acknowledgements to the originator node.

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

13. The method of claim 9, further comprising:

combining tokens received to determine if an entire identifier range space is covered; and

resending the message to nodes in ranges absent from the received tokens.

14. A computer-implemented communications method executing in a processor and memory, comprising:

assigning different ranges of identifiers to nodes of a collection as tokens;

broadcasting a message to the nodes from an originator node based on the identifiers;

receiving acknowledgments of receipt of the message at the corresponding nodes based on the identifiers;

consolidating acknowledgments at routing nodes as consolidated confirmations; and

returning the consolidated confirmations to the originator node.

15. The method of claim 14, further comprising assigning a broadcast range to each routing node that identifies child nodes targeted to receive the message.

16. The method of claim 14, further comprising assigning corresponding ranges of identifiers to routing nodes and neighbor nodes in tokens.

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

18. The method of claim 14, further comprising splitting a range of identifiers assigned to a routing node to accommodate at least one of neighbor nodes and other routing nodes associated with the routing node.

19. The method of claim 14, further comprising resending the message to a node in response to not receiving an acknowledgement from the node.

20. The method of claim 14, further comprising counting the tokens to determine if the message was received by all targeted nodes of the collection.