Establishing membership within a federation infrastructure

• US 20060088015A1
• Filed: 12/17/2004
• Published: 04/27/2006
• 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., Rodeheffer, Thomas Lee
• Granted Patent: US 7,624,194 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• 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/1048 Departure or maintenance mechanisms

Abstract

The present invention extends to methods, systems, and computer program products for establishing and maintaining membership within a federation infrastructure. A joining node submits a join message to an existing federation infrastructure. The federation infrastructure routes the join message to a processing node. The processing node facilitates identification of predecessor, successor, neighborhood, and routing nodes (for the joining node) within a ring of nodes. The joining node exchanges messages with identified nodes to obtain state information for the identified nodes and other nodes within the ring. Nodes periodically exchange state information, including state information for other nodes, such that state information for the ring is efficiently propagated to all nodes in the ring even when communication between some nodes is lost. Instance IDs, phase values, and freshness values are used to determine when state information is stale and/or is to be updated.

Claims

1. At a joining node, a method for establishing membership within a federation infrastructure, the method comprising:

an act of sending a join message to a federation infrastructure, the destination property of the join message being the ID of the joining node;

an act of receiving a join response message from a federation infrastructure node that processed the join message, the join response identifying any prospective proximal predecessor nodes and any prospective proximal successor nodes corresponding to the joining node;

an act of sending a sync request to any identified immediate proximal predecessor nodes and any identified immediate proximal successor nodes;

an act of receiving a sync response message from any of the identified immediate proximal predecessor nodes and any of the identified immediate proximal successor nodes that processed the sync request, the received sync responses indicating any neighborhood nodes of the proximal predecessor nodes and any neighborhood nodes of the proximal successor nodes that processed the sync request; and

an act of computing proximal neighborhood nodes for the joining node based on a summarized view of the join response message and any sync response messages.

2. The method as recited in claim 1, wherein the act of sending a join message to a federation infrastructure comprises an act of sending a join message sufficient for determining the closest node to the joining node in all the proximity rings that are a part of the proximity branch to which the joining node belongs.

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

an act of the joining node transitioning to an inserting phase as a result of sending the join message.

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

an act of identifying an existing node that is part of the lowest ring the joining node is to participate in.

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

an act of the joining node invoking a numerical routing function to determine a node numerically closest to the joining node in each proximity ring the joining node is to participate in.

6. The method as recited in claim 1, wherein the act of receiving a join response message from a federation infrastructure node that processed the join message comprises an act of receiving a join response message identifying a predecessor node and a successor node per proximity ring in a proximity branch to which the joining node belongs.

7. The method as recited in claim 6, wherein the act of receiving a sync response message from a federation infrastructure node that processed the sync message comprises an act of receiving a sync response message that includes liveness information for one or more other nodes in the federation infrastructure.

8. The method as recited in claim 1, wherein the act of receiving a join response message from a federation infrastructure node that processed the join message comprises an act of receiving a join response that identifies any prospective routing partner nodes corresponding to the joining node.

9. The method as recited in claim 1, wherein the act of receiving a join response message from a federation infrastructure node that processed the join message comprises an act of receiving a join response message that includes liveness information for one or more other nodes in the federation infrastructure.

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

an act of processing the received join response message to identify a predecessor node and a successor node corresponding to the joining node in each proximity ring the joining node is to participate in.

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

an act of the joining node transitioning forward to a syncing phase subsequent to processing the received join response.

12. The method as recited in claim 1, wherein the act of sending a sync request to any identified immediate proximal predecessor nodes and any identified immediate proximal successor nodes comprises an act of sending a sync request that includes at least one of an identification of any neighborhood nodes of the joining node and an identification of any routing partner nodes of the joining node.

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

an act of querying an application component associated with the joining node to obtain application specific neighborhood data; and

an act of including any obtained application specific neighborhood data in a sync request such that the application specific neighborhood data is piggybacked in the sync request.

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

an act of querying an application component associated with the node processing the sync request to obtain application specific neighborhood data; and

an act of including any obtained application specific neighborhood data in a sync response such that the application specific neighborhood data is piggybacked in the sync response.

15. The method as recited in claim 1, wherein the act of receiving a sync response message from any of the identified immediate proximal predecessor nodes and any of the identified immediate proximal successor nodes that processed the sync request comprises an act of receiving a sync response message that identifies any routing partner nodes corresponding to the joining node.

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

an act of computing routing partner nodes for the joining node based on a summarized view of the join response message and any sync response messages.

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

an act of accessing piggybacked application specific neighborhood data from the received sync response; and

an act of offering the accessed application specific neighborhood data to an application component associated with the joining node.

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

an act of accessing piggybacked application specific neighborhood data from a sync request; and

an act of offering the accessed application specific neighborhood data to an application component associated with the joining node.

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

an act of determining that the sync phase for the joining node is complete; and

an act of the joining node transitioning forward to a routing phase.

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

an act of the joining node exchanging routing tables with at least one neighborhood node.

21. The method as recited in claim 20, further comprising:

an act of exchanging a routing table with at least one neighborhood node in each proximity ring the joining node is to participate in.

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

an act of exchanging at least neighborhood node information with computed routing partner nodes

23. The method as recited in claim 22, wherein the act of exchanging at least neighborhood node information with computed routing partner nodes comprises:

an act of the joining node sending an update message, including at least any joining node neighborhood nodes'"'"' liveness information, to routing partner nodes of the joining node; and

an act of the routing partner nodes processing the update message sending a corresponding update response message back to the joining node including at least any neighborhood nodes'"'"' liveness information of the processing routing partner nodes.

24. The method as recited in claim 23, wherein the act of the joining node sending an update message to routing partner nodes of the joining node comprises:

an act of routing the update message with the destination node id property set to a perfect routing partner id of the joining node.

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

an act of subscribing to liveness notification events for the computed routing partner nodes sent from an application component associated with the joining node.

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

an act of determining that the routing phase for the joining node is complete; and

an act of the joining node transitioning forward to an operating phase.

27. The method as recited in claim 1, wherein the joining node subsequently terminates membership in a proximal ring of the federation infrastructure, the method comprising:

an act of sending a departure message to one or more of the predecessor node, the successor node, and other neighborhood nodes in the proximal ring.

28. The method as recited in claim 1, wherein one or more of the sent and received messages includes one or more liveness headers, each liveness header identifying the state of a node in the federation infrastructure based on a node ID, an Instance ID, a phase value, and a freshness value.

29. The method as recited in claim 28, wherein one or more of the liveness headers further includes an identifying color and weight.

30. The method as recited in claim 28, wherein the Instance ID is ordered within the context of a given node ID

31. The method as recited in claim 28, wherein the Instance ID only advances in value for the contextual node as the contextual node reboots.

32. The method as recited in claim 28, wherein a phase value includes an ordered phase-state value that advances forward through a well defined set of phase-states.

33. The method as recited in claim 32, wherein the well defined set of phase-states are:

an inserting phase, a sync phase, a routing phase, and an operating phase in order.

34. The method as recited in claim 32, wherein the phase value further includes a phase.unknown indication.

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

an act of computing routing partners of the joining node based on a summarized view of join responses and sync responses.

36. At a federation infrastructure, a method for a joining a node to establish membership within the federation infrastructure, the method comprising:

an act of a receiving node in the federation infrastructure receiving a join message, the destination property of the join message being the ID of a joining node;

an act of routing the join message to a processing node having an ID numerically closer to the ID of the joining node than other nodes in the federation infrastructure;

an act of the processing node computing one or more predecessor nodes and one or more successor nodes for the joining node;

an act of the processing node computing one or more routing nodes for the joining node; and

an act of sending a join response that identifies at least the computed predecessor and successor nodes to the joining node.

37. The method as recited in claim 36, wherein the act of a receiving node in the federation infrastructure receiving a join message comprises an act of a receiving node in the lowest proximity ring the joining node is to participate in receiving the join message.

38. The method as recited in claim 36, wherein the act of routing the join message to a processing node having an ID numerically closer the ID of the joining node than other nodes in the federation infrastructure comprises an act of invoking a numeric routing function.

39. The method as recited in claim 36, wherein the act of the processing node computing one or more predecessor nodes and one or more successor nodes for the joining node comprises an act of computing a predecessor node and a successor node for each proximal ring the joining node is to participate in.

40. The method as recited in claim 36, wherein the act of the processing node computing one or more routing nodes for the joining node comprises an act of computing a first one or more routing nodes for a first level in a hierarchical tree of rings and computing a second one or more routing nodes for a second different level in the hierarchical tree of rings.

41. The method as recited in claim 36, wherein the act of sending a join response that identifies at least the computed predecessor and successor nodes to the joining node comprises an act of sending a join response that also identifies the computed one or more routing nodes.

42. A computer program product for use at a joining node, the computer program product for implementing a method for establishing membership within a federation infrastructure, the computer program product comprising one or more computer-readable media having stored thereon computer-executable instructions that, when executed by a processor, cause the joining node to perform the following:

send a join message to a federation infrastructure, the destination property of the join message being the ID of the joining node;

receive a join response message from a federation infrastructure node that processed the join message, the join response identifying any prospective proximal predecessor nodes and any prospective proximal successor nodes corresponding to the joining node;

send a sync request to any identified immediate proximal predecessor nodes and any identified immediate proximal successor nodes;

receive a sync response message from any of the identified immediate proximal predecessor nodes and any of the identified immediate proximal successor nodes that processed the sync request, the received sync responses indicating any neighborhood nodes of the proximal predecessor nodes and any neighborhood nodes of the proximal successor nodes that processed the sync request; and

compute proximal neighborhood nodes for the joining node based on a summarized view of the join response message and any sync response messages.

43. A computer program product for use at a federation infrastructure, the computer program product for implementing a method for a joining a node to establish membership within the federation infrastructure, the computer program product comprising one or more computer-readable media having stored thereon computer-executable instructions that, when executed by a processor, cause a processing node within the federation infrastructure to perform the following:

receive node in the federation infrastructure receiving a join message, the destination property of the join message being the ID of a joining node;

route the join message to a processing node having an ID numerically closer to the ID of the joining node than other nodes in the federation infrastructure;

compute one or more predecessor nodes and one or more successor nodes for the joining node;

compute one or more routing nodes for the joining node; and

send a join response that identifies at least the computed predecessor and successor nodes to the joining node.