SUBFEDERATION CREATION AND MAINTENANCE IN A FEDERATION INFRASTRUCTURE

• US 20090319684A1
• Filed: 06/25/2009
• Published: 12/24/2009
• Est. Priority Date: 10/22/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hasha, Richard L., Kakivaya, Gopala Krishna R., Xun, Lu
• Granted Patent: US 8,392,515 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• 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. At a system including a processor and a memory, a method for forming a subfederation within a federation infrastructure, the method comprising:

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

an act of accessing the joining node'"'"'s group table, the group table including membership information identifying zero or more subfederations within the federation infrastructure, wherein each node in the federation maintains neighborhood information for each subfederation of which the node is aware;

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

based on the determination, an act of routing a group join message to a rendezvous point within the federation infrastructure, such that the rendezvous point checks its group table for an entry corresponding to the identified subfederation; and

an act of receiving 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.

2. The method of claim 1, wherein, based on the information accessed in the group table, the joining node determines that an entry for the identified subfederation exists in the joining node'"'"'s 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. At a system including a processor and a memory, a method for departing a subfederation within a federation infrastructure, the method comprising:

an act of determining that a departing node is a member node of a subfederation within a federation infrastructure; 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 its group table to include a no-longer-participating indication indicating that the departing member node is no longer participating in the subfederation; and

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

15. The method of claim 14, wherein the departing member node'"'"'s liveness information 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. At a system including a processor and a memory, a method for maintaining a subfederation in a federation infrastructure, the method comprising:

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

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; 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.