Maintaining membership within a federation infrastructure

• US 7,362,718 B2
• Filed: 12/17/2004
• Issued: 04/22/2008
• 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., Rodeheffer, Thomas Lee
• Primary Examiner(s): Patel; Ajit
• Application Number:
  US11/016,446
• Publication Number:
  US 20060088039A1
• Time in Patent Office: 1,222 Days
• Field of Search: 370/254, 370/255, 370/256, 370/389, 370/401, 370/400, 370/410, 370/395.54, 709/232, 709/200, 709238-244
• US Class Current: 370/254
• 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 current node in a federating infrastructure, a method for the current node to maintain membership within the federation infrastructure, the method comprising:

an act of sending a first ping message to a neighborhood node, the first ping message indicating to the neighborhood node the current node is participating as a neighbor of the neighborhood node and including routing partner and neighborhood nodes'"'"' state of the current node;

an act of receiving a second ping message from a neighborhood node, the second ping message indicating to the current node at least that the neighborhood node originating the second ping message is participating as a neighbor of the current node and including routing partner and neighborhood nodes'"'"' state of the originating neighborhood node;

an act of proximally routing an update request message to a processing routing node, the update request message indicating to the processing routing node that the current node is participating as a routing partner of the routing node and including at least the current node'"'"'s neighborhood nodes'"'"' identities; and

an act of receiving an update response message from the processing routing node, the update response indicating to the current node that the processing routing node is participating as a routing partner of the current node and including at least the processing routing partner'"'"'s neighborhood nodes'"'"' identities.

2. The method as recited in claim 1 wherein the act of sending a first ping message to a neighborhood node comprises an act of periodically repeating the sending of a first ping message.

3. The method as recited in claim 2, wherein the act of periodically repeating the sending of a first ping message comprises an act of accessing the frequency of the periodic repeating applicable to the proximal ring into which the first ping message is to be sent.

4. The method as recited in claim 2, wherein the act of periodically repeating the sending of the first ping message comprises an act of periodically repeating the sending of the first ping message based on a ping distribution pattern.

5. The method as recited in claim 4, wherein the act of periodically repeating the sending of the first ping message based on a ping distribution pattern comprises an act of periodically repeating the sending of the first ping message based on a ping distribution pattern applicable to the proximity ring the first ping is to be sent to.

6. The method as recited in claim 2, wherein the act of periodically repeating the sending of a first ping message comprises an act of periodically repeating the sending of the first ping message to nodes in both directions on the ring relative to the current node.

7. The method as recited in claim 1, wherein the act of receiving a second ping message from a neighborhood node comprises an act of considering the lack of a ping from the originating neighborhood node being received periodically as an indication that communications have failed between the current node and the originating neighborhood node.

8. The method as recited in claim 7, wherein the act of considering the lack of a ping from the originating neighborhood node being received periodically as an indication that communications have failed between the current node and the originating neighborhood node comprises an act of accessing configuration state associated with the proximal ring on which the ping message was expected by the current node.

9. The method as recited in claim 1, wherein the act receiving a second ping message from a neighborhood node comprises an act of current node receiving an indication that the neighborhood node directly sending the second ping message to the current node is participating as a neighbor of the current node not withstanding that the neighborhood node that directly sent the second ping message may not be the originating node of the second ping message.

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

an act of the current node forwarding the second ping message.

11. The method as recited in claim 10, wherein the act of the current node forwarding the second ping message comprising an act of forwarding the second ping message to a plurality of other nodes.

12. The method as recited in claim 10, wherein the act of the current node forwarding the second ping message comprises an act of forwarding the second ping message based on a ping distribution pattern.

13. The method as recited in claim 12, wherein the act of forwarding the second ping message based on a ping distribution pattern comprises an act of forwarding the second ping message based on a ping distribution pattern applicable to the proximity ring the send ping message is to be sent to.

14. The method as recited in claim 12, wherein the act of forwarding the second ping message based on a ping distribution pattern comprises an act of forwarding the second ping message to a plurality of other nodes on a ring in a direction away from an originating node of the second ping message.

15. The method as recited in claim 1, wherein the act of proximally routing an update request message to a perfect routing node comprises an act of periodically re-routing an update message.

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

an act of the current node being configured to expect to receive update messages periodically.

17. The method as recited claim 16, further comprising:

an act of the current node detecting a communications failure in response to not receiving an expected update message from a sending routing partner.

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

an act of appropriately updating node information to indicate that the current node and the neighborhood node are participating as neighbors and that the current node and the routing node are participating as routing partners.

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

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

an act of including any obtained application specific neighborhood data in the first ping message such that the application specific neighborhood data is piggybacked in the first ping message.

20. The method as recited in claim 19, wherein the act of querying an application component associated with the current node to obtain application specific neighborhood data comprises an act of querying an application component for application state information that is to be shared with corresponding application components associated with other nodes.

21. The method as recited in claim 19, wherein the act of querying an application component for application state information that is to be shared with corresponding application components associated with other nodes comprises an act of querying an application component for sequenced application state information.

22. The method as recited in claim 1, wherein the act of sending a first ping message to a neighborhood node comprises an act of sending a first ping message to a neighborhood node in one of a plurality of proximity rings the current node participates in.

23. The method as recited in claim 1, wherein the act of sending a first ping message to a neighborhood node comprises an act of sending a first ping message that indicates any neighborhood nodes and routing partners for the current node.

24. The method as recited in claim 23, wherein the act of sending a first ping message that indicates any neighborhood nodes and routing partners for the current node comprises an act of a first ping message that indicates, via a liveness header, any neighborhood nodes and routing partners for the current node.

25. The method as recited in claim 1, wherein the act of receiving a second ping message from at least one neighborhood node comprises an act of receiving a second ping message from a neighborhood node in one of a plurality of proximity rings the current node participates in.

26. The method as recited in claim 1, wherein the act of receiving a second ping message from at least one neighborhood node comprises an act of receiving a second ping message that indicates any neighborhood nodes and routing partners of a neighborhood node that originated the second ping message.

27. The method as recited in claim 1, wherein the act of receiving a second ping message from at least one neighborhood node comprises an act of receiving a second ping message that includes application specific neighborhood data piggybacked within the second ping message.

28. The method as recited in claim 27, wherein the act of receiving a second ping message that includes piggybacked application specific neighborhood data comprises an act of receiving a second ping message having sequenced application state information.

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

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

30. The method as recited in claim 1, wherein the act of sending an update message to a routing node comprises an act of routing an update message to a perfect routing node identity in one of a plurality of proximity rings the current node participates in.

31. The method as recite in claim 1, further comprising:

an act of accessing application specific data from an application component associated with the current node; and

an act of piggybacking the accessed application specific data in the update request message prior to sending the update request message.

32. The method as recited in claim 1, wherein the act of receiving an update response message from the routing node comprises an act of receiving an update response message that includes application specific data piggybacked within the update response.

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

an act of offering the application specific data to an application component associated with the current node.

34. The method as recited in claim 1, wherein the act of receiving an update response from the routing node comprising an act of receiving an update response form a routing node in one of a plurality of proximity rings the current node participates in.

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

an act of the current node determining that its view of the federation infrastructure has become unbalanced.

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

an act of one or more nodes in the federation infrastructure exchanging synchronization messages to rebalance at least the current node'"'"'s view of the federation infrastructure.

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

an act of the one or more nodes exchanging update messages to rebalance at least the current node'"'"'s view of the federation infrastructure.

38. 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 at least a node ID, an Instance ID, a phase value, and a freshness value.

39. The method as recited in claim 38, wherein one or more of the liveness headers further includes at least an identifying color and weight.

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

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

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

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

43. The method as recited in claim 41, wherein a phase value further includes a phase unknown indication.

44. A computer program product for use at a current node in a federating infrastructure, the computer program product for implementing a method for the current node to maintain 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 the current node to perform the following:

send a first ping message to a neighborhood node, the first ping message indicating to the neighborhood node the current node is participating as a neighbor of the neighborhood node and including routing partner and neighborhood nodes'"'"' state of the current node;

receive a second ping message from a neighborhood node, the second ping message indicating to the current node at least that the neighborhood node originating the second ping message is participating as a neighbor of the current node and including routing partner and neighborhood nodes'"'"' state of the originating neighborhood node;

proximally route an update request message to a processing routing node, the update request message indicating to the processing routing node that the current node is participating as a routing partner of the routing node and including at least the current node'"'"'s neighborhood nodes'"'"' identities; and

receive an update response message from the processing routing node, the update response indicating to the current node that the processing routing node is participating as a routing partner of the current node and including at least the processing routing partner'"'"'s neighborhood nodes'"'"' identities.