Subfederation creation and maintenance in a federation infrastructure

• US 8,392,515 B2
• Filed: 06/25/2009
• Issued: 03/05/2013
• Est. Priority Date: 10/22/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kakivaya, Gopala Krishna R., Xun, Lu, Hasha, Richard L.
• Primary Examiner(s): Mirza, Adnan
• Application Number:
  US12/491,841
• Publication Number:
  US 20090319684A1
• Time in Patent Office: 1,349 Days
• Field of Search: 709/206, 709/223
• US Class Current: 709/206
• CPC Class Codes: H04L 12/42 Loop networks
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/4541 Directories for service discovery
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053

Abstract

A computational system determines that a joining node in the federation infrastructure desires to join an identified subfederation within the federation infrastructure. The system accesses the joining node'"'"'s group table, where the group table includes membership information identifying subfederations within the federation infrastructure. Each node in the federation maintains neighborhood information for each subfederation of which the node is aware. The system determines that no entry for the identified subfederation exists in the joining node'"'"'s group table and, based on the determination, routes a group join message to a rendezvous point within the federation infrastructure. The rendezvous point checks its group table for an entry corresponding to the identified subfederation. The system also receives an indication from the rendezvous point indicating that the rendezvous point'"'"'s group table does not include a corresponding entry for the identified subfederation and that the joining node is the first member of the identified subfederation.

Claims

1. In a federation infrastructure comprising a plurality of nodes that each include one or more processors and system memory and that are organized into a ring of nodes, the plurality of nodes being configured to route messages to one another through the ring, each of the plurality of nodes storing a routing table that includes one or more of a predecessor node of said node in the ring of nodes, a successor node of said node in the ring of nodes, or a plurality of neighbor nodes of said node in the ring of nodes including one or more first neighbor nodes in a first direction of said node in the ring of nodes and one or more second neighbor nodes in a second opposite direction of said node in the ring of nodes, a method for forming a subfederation within the federation infrastructure, the method comprising:

an act of determining that a joining node selected from the plurality of nodes in the federation infrastructure desires to join an identified subfederation within the federation infrastructure;

an act of the joining node accessing a first group table corresponding to the joining node, the first group table including membership information identifying zero or more subfederations within the federation infrastructure, each subfederation comprising a subset of the plurality of nodes in the federation infrastructure that are organized into a sub-ring, wherein each of the plurality of nodes in the federation maintains neighborhood information for each subfederation of which the node is aware;

an act of the joining node determining that no entry for the identified subfederation exists in the joining node'"'"'s first group table;

based on the determination, an act of the joining node routing a group join message to a rendezvous point comprising one of the plurality of nodes in the federation infrastructure, such that the rendezvous point checks a second group table corresponding to the rendezvous point for an entry corresponding to the identified subfederation; and

an act of the joining node receiving an indication from the rendezvous point indicating that the rendezvous point'"'"'s second group table does not include a corresponding entry for the identified subfederation and that the joining node is the first member of the identified subfederation.

2. The method of claim 1, wherein, based on the information accessed in the first group table, the joining node determines that an entry for the identified subfederation exists in the joining node'"'"'s first group table.

3. The method of claim 2, further comprising an act of the joining node routing a group join message to the closest known node in the identified subfederation.

4. The method of claim 3, wherein the node that received the group join message replies to the joining node indicating its neighborhood information for the identified subfederation, such that the joining node can learn about its neighborhood in the subfederation.

5. The method of claim 3, wherein the node that received the group join message replies to the joining node indicating its routing partner for the identified subfederation, such that the joining node can learn about its routing partner nodes in the subfederation.

6. The method of claim 1, wherein the joining node receives an indication from the rendezvous point indicating that the rendezvous point'"'"'s group table includes a corresponding entry for the identified subfederation and further indicating the identity of at least one node in the identified subfederation.

7. The method of claim 1, further comprising an act of the rendezvous point forwarding the group join message to the closest node in the identified existing subfederation.

8. The method of claim 1, wherein the neighborhood comprises the closest N nodes in the subfederation on both the successor and the predecessor sides of the node, and wherein N is a configurable neighborhood size.

9. The method of claim 1, wherein the entry in each node'"'"'s group table includes a group node instance ID which is incremented each time a node joins a group, such that if a node joins a group shortly after the node departs that same group, other nodes will know that the join occurred later than the depart.

10. The method of claim 1, wherein group table information is appended to an existing federation infrastructure message.

11. The method of claim 10, wherein the joining node updates its group table using information received as part of a federation infrastructure message.

12. The method of claim 10, further comprising an act of partitioning the group table such that each federation infrastructure message propagates a portion of the group table.

13. The method of claim 1, wherein the subfederation comprises substantially all of the characteristics and functionality of the underlying federation infrastructure.

14. In a federation infrastructure comprising a plurality of nodes that each include one or more processors and system memory and that are organized into a ring of nodes, the plurality of nodes being configured to route messages to one another through the ring, each of the plurality of nodes storing a routing table that includes one or more of a predecessor node of said node in the ring of nodes, a successor node of said node in the ring of nodes, or a plurality of neighbor nodes of said node in the ring of nodes including one or more first neighbor nodes in a first direction of said node in the ring of nodes and one or more second neighbor nodes in a second opposite direction of said node in the ring of nodes, a method for departing a subfederation within the federation infrastructure, the method comprising:

an act of determining that a departing node selected from the plurality of nodes is a member node of a subfederation within a federation infrastructure, the subfederation comprising a subset of the plurality of nodes in the federation infrastructure that are organized into a sub-ring including the departing node; and

an act of the member node routing a group depart message to the member node'"'"'s successor and predecessor nodes in the subfederation, such that at least one of the successor and predecessor nodes performs the following;

updates a corresponding group table to include a no-longer-participating indication indicating that the departing member node is no longer participating in the subfederation; and

removes and associated entry in the group table corresponding to the departing member node after a time period has expired.

15. The method of claim 14, wherein liveness information corresponding to the departing member node indicates that the member node is in either a shutdown state or an unknown state.

16. The method of claim 15, further comprising:

an act of determining that at least one node in the subfederation includes liveness information in its group table indicating that the departing member node is unavailable;

an act of determining that the departing member node is currently available; and

an act of overriding the liveness information upon determining that the departing member node is available.

17. The method of claim 14, wherein at least one of the successor and predecessor nodes propagates the no-longer-participating indication for the departing member node to one or more other nodes in the subfederation.

18. In a federation infrastructure comprising a plurality of federation nodes that each include one or more processors and system memory and that are organized into a ring of nodes, the plurality of federation nodes being configured to route messages to one another through the ring, each of the plurality of federation nodes storing a routing table that includes one or more of a predecessor node of said node in the ring of nodes, a successor node of said node in the ring of nodes, or a plurality of neighbor nodes of said node in the ring of nodes including one or more first neighbor nodes in a first direction of said node in the ring of nodes and one or more second neighbor nodes in a second opposite direction of said node in the ring of nodes, a method for maintaining a subfederation in the federation infrastructure, the method comprising:

an act of a first member node of the plurality of federation nodes of the federation infrastructure receiving one or more federation infrastructure messages from at least one other federation node of the plurality of federation nodes;

an act of the first member node determining from group table information appended to the federation infrastructure messages that a second member node that is a member of a subfederation in the federation infrastructure is no longer active, the subfederation comprising a subset of the plurality of federation nodes in the federation infrastructure that are organized into a sub-ring including the second member node; and

an act of the first member node sending a group depart message on behalf of the second member node to predecessor and successor nodes of those subfederations of which the member node was a member indicating that the second member node has departed the subfederation.

19. The method of claim 18, wherein the first member node is not a member of the subfederation of which the second member node is a member.

20. The method of claim 18, further comprising an act of the first member node notifying a rendezvous point that the second member node has departed the federation.

21. A computer program product comprising one or more computer storage devices having stored thereon computer executable instructions that, when executed by one or more processors, implement a method for forming a subfederation within a federation infrastructure that comprises a plurality of nodes that are organized into a ring of nodes, the plurality of nodes being configured to route messages to one another through the ring, each of the plurality of nodes storing a routing table that includes one or more of a predecessor node of said node in the ring of nodes, a successor node of said node in the ring of nodes, or a plurality of neighbor nodes of said node in the ring of nodes including one or more first neighbor nodes in a first direction of said node in the ring of nodes and one or more second neighbor nodes in a second opposite direction of said node in the ring of nodes, the method comprising:

an act of determining that a joining node selected from the plurality of nodes in the federation infrastructure desires to join an identified subfederation within the federation infrastructure;

an act of the joining node accessing a first group table corresponding to the joining node, the first group table including membership information identifying zero or more subfederations within the federation infrastructure, each subfederation comprising a subset of the plurality of nodes in the federation infrastructure that are organized into a sub-ring, wherein each of the plurality of nodes in the federation maintains neighborhood information for each subfederation of which the node is aware;

an act of the joining node determining that no entry for the identified subfederation exists in the joining node'"'"'s first group table;

based on the determination, an act of the joining node routing a group join message to a rendezvous point comprising one of the plurality of nodes in the federation infrastructure, such that the rendezvous point checks a second group table corresponding to the rendezvous point for an entry corresponding to the identified subfederation; and

an act of the joining node receiving an indication from the rendezvous point indicating that the rendezvous point'"'"'s second group table does not include a corresponding entry for the identified subfederation and that the joining node is the first member of the identified subfederation.

22. The computer program product of claim 21, wherein the one or more computer storage devices comprise a computer system that includes the one or more processors.

23. A computer program product comprising one or more computer storage devices having stored thereon computer executable instructions that, when executed by one or more processors, implement a method for maintaining a subfederation in a federation infrastructure that comprises a plurality of federation nodes that are organized into a ring of nodes, the plurality of federation nodes being configured to route messages to one another through the ring, each of the plurality of federation nodes storing a routing table that includes one or more of a predecessor node of said node in the ring of nodes, a successor node of said node in the ring of nodes, or a plurality of neighbor nodes of said node in the ring of nodes including one or more first neighbor nodes in a first direction of said node in the ring of nodes and one or more second neighbor nodes in a second opposite direction of said node in the ring of nodes, the method comprising:

an act of a first member node of the plurality of federation nodes of the federation infrastructure receiving one or more federation infrastructure messages from at least one other federation node of the plurality of federation nodes;

an act of the first member node determining from group table information appended to the federation infrastructure messages that a second member node that is a member of a subfederation in the federation infrastructure is no longer active, the subfederation comprising a subset of the plurality of federation nodes in the federation infrastructure that are organized into a sub-ring including the second member node; and

an act of the first member node sending a group depart message on behalf of the second member node to predecessor and successor nodes of those subfederations of which the member node was a member indicating that the second member node has departed the subfederation.

24. The computer program product of claim 23, wherein the one or more computer storage devices comprise a computer system that includes the one or more processors.