Broadcasting communication within a rendezvous federation

• US 7,730,220 B2
• Filed: 08/17/2006
• Issued: 06/01/2010
• Est. Priority Date: 10/22/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hasha, Richard L., Kakivaya, Gopala Krishna R., Xun, Lu
• Primary Examiner(s): Jagannathan; Melanie
• Assistant Examiner(s): CHANG, STEPHANIE L
• Application Number:
  US11/465,316
• Publication Number:
  US 20070002774A1
• Time in Patent Office: 1,384 Days
• Field of Search: 709/228, 709/251, 709/222, 709/207, 709/238, 709/243, 370/222, 370/254, 370/258, 370/390, 370/400
• US Class Current: 709/251
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 67/563 Data redirection of data network streams

Abstract

The present invention extends to methods, systems, and computer program products for broadcasting communication within a rendezvous federation. Embodiments of the invention include inter-ring and intra-ring communication. Inter-ring communication includes sending a message to destination rings included in a node'"'"'s Collateral Ring Set entry table. When a node identifies a destination ring that has not yet received a message, the node can send a ring notification message. The ring notification message propagates towards a publishing node until a responsible node in the message path to the publishing node is identified. The responsible node updates its entry table to include the ring and forwards the message to the destination ring. Intra-ring communication can include recursively partitioning ranges of nodes within a ring and forwarding the message to nodes included the partitioned ranges.

Claims

1. At a computer system, a method for broadcasting a message within a sub-ring of nodes included in a federation infrastructure, the federation infrastructure represented by a linked list of nodes, the linked list of nodes partitioned into a hierarchical tree of rings including a root ring and a plurality of lower sub-ring levels of sub-rings, the root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, wherein nodes of the same equivalence class within the same lower sub-ring level have the same value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring within the hierarchical tree, wherein nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, the method comprising:

an act of a node within hierarchical tree of rings accessing a message, the node having membership in a sub-ring, the sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the message for delivery to a range of nodes within a specified sub-ring the node is a member of;

an act of the node accessing a routing table for the node, the routing table including a plurality of routing partner nodes for each sub-ring in the spine of sub-rings, including the specified sub-ring;

an act of the node broadcasting the message within the specified sub-ring in a manner that distributes the resource burden for broadcasting the message across a plurality of nodes that are members of the specified sub-ring, including;

an act of the node partitioning the range of nodes in the specified sub-ring into a plurality of sub ranges, including at least a first and second sub range;

an act of the node forwarding the message along with an indication of first sub ranges to a first routing partner node within the first sub range; and

an act of the node forwarding the message along with an indication of the second sub range to a second routing partner node within the second sub range.

2. The method as recited in claim 1, further comprising:

an act of the first routing partner node receiving the message along with first sub range, the first sub range indicating nodes that the first routing partner node is responsible for within the specified sub-ring;

an act of the first routing partner node accessing another routing table for the first routing partner node, the other routing table including a successor node, a predecessor node, one or more neighborhood nodes, an plurality of routing partner nodes for the first routing partner node for each sub-ring in the spine of sub-rings, including the specified sub-ring;

an act of the first routing partner node further broadcasting the message within the specified sub-ring in a manner that distributes the resource burden for broadcasting the message across a plurality of nodes that are members of the specified sub-ring, including;

an act of first routing partner partitioning the first sub range into plurality of further sub ranges;

an act of forwarding the message along with one of the further sub ranges to another routing partner node of the routing partner node with the further sub range; and

an act of forwarding the message to at least one of the successor node, the predecessor node, and a neighborhood node of the receiving routing partner node within the specified sub-ring.

3. The method as recited in claim 1, wherein the act of a node within the hierarchical tree of rings accessing a message comprises an act of an entry node for the specified sub-ring receiving the message through inter-ring communication from another sub-ring, the other sub-ring being at a different sub-ring level relative to the specified sub-ring within the hierarchical tree of rings.

4. The method as recited in claim 3, wherein the act of an entry node for the specified sub-ring receiving the message through inter-ring communication comprises an act of the entry node receiving a compensation message from node in the other sub-ring.

5. The method as recited in claim 3, wherein the act of an entry node for the specified sub-ring receiving the message through inter-ring communication comprises an act of receiving a message that is to be broadcast to all nodes in the root ring along with a broadcast control information, the broadcast control information including a reached ring list, a responsible ring indicator, and a parent entry node indicator, the reached ring list indicating destination rings in the hierarchical ring infrastructure that are considered to have already received the message and that are designated as destinations to receive the message, the responsible ring indicator indicating rings the entry node is responsible for, and the parent entry node indicator indicating the entry node'"'"'s parent entry node in the distribution path.

6. The method as recited in claim 5, further comprising:

an act of the entry node referring to a collateral ring set (“

CRS”

) entry table, the collateral ring set (“

CRS”

) entry table one or more collateral sub-rings relative to the specified sub-ring within the hierarchical tree of ring, a collateral sub-ring being one of;

a peer sub-ring to the specified sub-ring or a peer sub-ring to another sub-ring in the spine of sub-rings.

7. The method as recited in claim 6, further comprising:

an act of matching the other rings to corresponding entry nodes in the other rings;

an act of comparing matched entries in the collateral ring set (“

CRS”

) entry node table to the reached ring list; and

an act of determining based on the comparison that the message has not been sent to all the rings in the collateral ring set (“

CRS”

) entry table.

8. The method as recited in claim 6, further comprising:

an act of identifying based on the comparison any rings that have not yet received the message that the entry node is responsible for sending the message to; and

an act of forwarding the message to the identified rings.

9. The method as recited in claim 6, further comprising:

an act of identifying based on the comparison any rings that have not yet received the message that the entry node is not responsible for sending the message to; and

an act of sending a ring notification message to the entry node'"'"'s parent entry node.

10. The method as recited in claim 3, further comprising:

an act of the entry node receiving a ring notification message from another node in the specified sub-ring, the ring notification message identifying another sub-ring in the hierarchical tree of rings that, from the perspective of the other node, has not yet received the message.

11. The method as recited in claim 10, further comprising:

an act of the entry node determining that it is responsible for forwarding the message to the identified sub-ring has not yet received the message; and

an act of sending the message to the identified sub-ring in response to receiving the ring notification message.

12. The method as recited in claim 10, further comprising:

an act of the entry node determining that it is not responsible for forwarding the message to the identified sub-ring; and

an act of forwarding the ring notification message to the entry node'"'"'s parent entry node in the message path in response to receiving the ring notification message.

13. The method as recited in claim 3, wherein the act of an entry node for the specified sub-ring receiving the message through inter-ring communication comprises an act of a entry node for a leaf ring in the hierarchical tree of rings receiving inter-ring communication from another sub-ring, the leaf ring being at the bottom of the spine of sub-rings the node is a member of.

14. The method as recited in claim 3, wherein the act of an entry node for the specified sub-ring receiving the message through inter-ring communication comprises an act of a entry node for a a sub-ring at an intermediate sub-ring level in the hierarchical tree of rings infrastructure receiving inter-ring communication from another sub-ring.

15. At a computer system, a method for broadcasting a message to one or more sub-rings of nodes in a federation infrastructure, the federation infrastructure represented by a linked list of nodes, the linked list of nodes partitioned into a hierarchical tree of rings including a root ring and a plurality of lower sub-ring levels of sub-rings, the root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, wherein nodes of the same equivalence class within the same lower sub-ring level have the same value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring within the hierarchical tree, wherein nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, the method comprising:

an act of a node accessing a message that is to be broadcast to one or more destination sub-rings in the federation infrastructure, the node having membership in a specified sub-ring, the specified sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the specified sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the specified sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the one or more destination sub-rings being collateral sub-rings relative to the specified sub-ring within the hierarchical tree of rings, a collateral sub-ring being one of;

a peer sub-ring to the specified sub-ring or a peer sub-ring to another sub-ring in the spine of sub-rings;

an act of the node accessing an entry table for the node, the entry table containing any known entry nodes into the one or more destination sub-rings;

an act of the current node constructing broadcast control information including a reached ring list identifying any destination sub-rings that had known entry nodes in the entry table, a responsible ring indicator indicating a specified sub-ring the current node is responsible for, and a parent entry node indicator indicating a parent entry node that was the last entry node to access the message before the node accessed the message; and

an act of the node sending inter-ring communication that includes the message and the broadcast control information to an entry node into at least one of the destination collateral sub-rings to propagate the message for further intra-ring broadcasting within the at least one of the destination collateral sub-rings.

16. The method as recited in claim 15, wherein the act of a the node accessing a message that is to be broadcast to one or more destination sub-rings comprises an act of a publishing node originating a message that is to be broadcast to the one or more destination sub-rings.

17. The method as recited in claim 15, wherein the act of a node accessing a message that is to be broadcast to one or more destination sub-rings comprises an act of a publishing node receiving a message from an entity that is external to the hierarchical tree of rings.

18. The method as recited in claim 15, wherein the act of a node accessing a message that is to be broadcast to one or more destination sub-rings comprises an act of an entry node in the specified sub-ring receiving the message from a parent entry node in another sub-ring, the sub-ring level of the other sub-ring being above the sub-ring level of specified sub-ring within the hierarchical tree of rings.

19. The method as recited in claim 15, wherein the act of a node accessing a message that is to be broadcast to one or more destination sub-rings comprises an act of a node accessing a message that is to be broadcast to one or more leaf rings in the hierarchical tree of rings, the leaf rings being at the lowest sub-ring level of the hierarchical tree of rings.

20. The method as recited in claim 15, wherein the act of a node accessing a message that is to be broadcast to one or more destination sub-rings in comprises an act of a node accessing a message that is to be broadcast to one or more sub-rings of various intermediate sub-ring levels within the hierarchical tree of rings.

21. The method as recited in claim 15, wherein the act of a node accessing a message that is to be broadcast to one or more destination sub-rings comprises an act of a node accessing a message that is to be broadcast to less than all the sub-rings in the hierarchical tree of rings based on proximity restriction information.

22. The method as recited in claim 15, further comprising:

an act of the node using intra-ring distribution to broadcast the message within at least one sub-ring of the spine of sub-rings.

23. The method as recited in claim 15, further comprising:

an act of the node receiving a ring notification message from another node in another sub-ring subsequent to sending the inter-ring communication to the one or more sub-rings, the ring notification message identifying a further sub-ring that, from the perspective of the other node, has not yet received the message.

24. The method as recited in claim 23, wherein the act of the node receiving a ring notification message from another node in another sub-ring comprises an act of the node receiving a ring notification message from another node somewhere in the spine of sub-rings.

25. The method as recited in claim 23, wherein the act of the node receiving a ring notification message from another node in another sub-ring comprises an act of the node receiving a ring notification message from an entry node for another sub-ring in the hierarchical tree or rings.

26. The method as recited in claim 23, further comprising:

an act of the current determining that it is responsible for sending the message to the identified sub-ring; and

an act of forwarding the message to the identified sub-ring.

27. The method as recited in claim 23, further comprising:

an act of the node updating its entry table to include the identified node.

28. The method as recited in claim 15, wherein the act of the node sending inter-ring communication that includes the message and the broadcast control information to an entry node into at least one of the destination collateral sub-rings comprises an act of sending inter-ring communication that includes the message and the broadcast control information to a plurality of destination collateral sub-rings in a collateral ring set (“

CRS”

) for the node in accordance with values for one or more of the proximity criteria.

29. At a computer system, a method for broadcasting a message between a plurality of sub-rings in a federation infrastructure, the federation infrastructure represented by a linked list of nodes, the linked list of nodes partitioned into a hierarchical tree of rings including a root ring and a plurality of lower sub-ring levels of sub-rings, the root ring including all the nodes in the linked list of nodes, the plurality of lower sub-ring levels arranged relative to one another within the hierarchical tree in accordance with a plurality of different proximity criteria, each lower sub-ring level in the hierarchical tree of rings including a plurality of different sub-rings, each different sub-ring within each lower sub-ring level representing a corresponding different equivalence class of nodes respectively based on assigned values for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, wherein nodes of the same equivalence class within the same lower sub-ring level have the same value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring within the hierarchical tree, wherein nodes of different equivalence classes within the same lower sub-ring level have at least one different value for the one or more of the plurality of different proximity criteria used to arrange the lower sub-ring level within the hierarchical tree, the method comprising:

an act of a node receiving a message and associated broadcast control information, the message to be broadcast to one or more destination sub-rings in the hierarchical tree of rings, the node having membership in a sub-ring, the sub-ring being one of a plurality of sub-rings at a lower sub-ring level arranged within the tree hierarchy based on the plurality of proximity criteria, membership in the sub-ring also indicative of membership in other sub-rings in each of one or more other sub-ring levels between the lower sub-ring level and the root ring, the sub-rings in each of the one or more other sub-ring levels indicative of a ring path forming a spine of sub-rings the node is a member of from the sub-ring to the root ring based on values for one or more of the plurality of proximity criteria, the broadcast control information including a reached ring list indicating destination sub-rings that the message has already been considered to have reached and a parent entry node indicator indicating a parent entry node that was the last entry node to access the message;

an act of the node accessing a corresponding entry node table that identifies entry nodes for one or more collateral sub-rings in the collateral ring set (“

CRS”

) of the sub-ring, each collateral sub-ring being one of;

a peer sub-ring to the sub-ring or a peer sub-ring to another sub-ring in the spine of sub-rings;

an act of the node identifying at least one destination sub-ring in the receiving node'"'"'s collateral ring set (“

CRS”

) that does not appear to have received the message according to information in the reached ring list;

an act of the node sending the message to any identified destination rings the node is responsible for; and

an act of the node identifying at least one destination sub-ring the node is not responsible for and that is not included in the reached ring list for the message;

an act of the node sending a ring notification message back to the parent entry node, the ring notification message identifying the at least one destination sub-ring that the node is not responsible for and identifying at least one corresponding entry node for the at least one sub-destination ring that the node is not responsible for.

30. The method as recited in claim 29, wherein the act of a receiving node receiving a message that is to be broadcast to one or more destination sub-rings of the hierarchical tree of rings comprises an act of a node receiving a message that is to be broadcast to leaf sub-rings of the hierarchical tree of rings.

31. The method as recited in claim 29, wherein the act of a receiving node receiving a message that is to be broadcast to one or more destination sub-rings of the hierarchical tree of rings comprises an act of a node receiving a message that is to be broadcast to sub-rings at a specified sub-ring level within the hierarchical tree of rings.

32. The method as recited in claim 29, wherein the act of a node receiving a message that is to be broadcast to one or more destination sub-rings of the hierarchical tree of rings comprises an act of a node receiving a message that is to be broadcast to one or more destination sub-rings at a variety of different sub-ring levels within the hierarchical tree of rings in accordance with values for one or more of the plurality of proximity criteria.

33. The method as recited in claim 29, further comprising:

an act of the node sending a reply to a parent entry node of the node acknowledging receipt of the message.

34. The method as recited in claim 29, further comprising:

an act of the node using intra-ring communication to broadcast the message within a one of the sub-rings in the spine of sub-rings.

35. The method as recited in claim 34, wherein the act of the node using intra-ring communication to broadcast the message within one of the sub-rings in the spine of sub-rings comprises an act of the node using intra-ring communication to broadcast the message within a leaf sub-ring, the leaf sub-ring at a lowest possible sub-ring level of the hierarchical tree of rings.