Discovering liveness information within a federation infrastructure

• US 7,466,662 B2
• Filed: 12/17/2004
• Issued: 12/16/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): Chan; Wing F
• Assistant Examiner(s): Jones; Prenell P
• Application Number:
  US11/016,422
• Publication Number:
  US 20060087985A1
• Time in Patent Office: 1,460 Days
• Field of Search: 370/390, 370/258, 370/392, 370/400, 370/338, 370/254, 370/389, 370/331, 709/251, 709/203, 709/238, 709/207, 714/47, 714/48, 713/171
• 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 federation infrastructure, a method for discovering liveness information for another node in the federation infrastructure, the method comprising:

an act of receiving a message from a sending node, the message including at least one liveness header representing state information for a participating node in the federation infrastructure, the state information including at least a participating node ID, an instance ID, a phase value, and a freshness value, the instance ID identifying an instance of the participating node, the phase value identifying an expressed phase of the participating node, the phase value including an expressed phase-state value and a phase.unknown indication, the phase-unknown indication indicating if the phase-state value was actually known to the sending node at the time indicated by the freshness value, the freshness value indicating how recently the instance ID and phase value where identified;

an act of accessing at least a current instance ID, current phase value, and current freshness value for the participating node maintained at the current node;

an act of comparing at least the received instance ID, the received phase value, and the received freshness value to the current instance ID, the current phase value, and the current freshness value respectively at a current node; and

an act of determining if state information for the participating node is to be updated at the current node based on the comparison.

2. The method as recited in claim 1, wherein the act of receiving the first messages comprises an act of receiving a message that includes a plurality of liveness headers for the same node, wherein each liveness header for the same node is for a different proximal ring that the same node is participating in an aliased fashion.

3. The method as recited in claim 1, where in the act of receiving a first message from a sending node comprises an act of receiving a first message from the participating node.

4. The method as recited in claim 1 wherein the act of receiving a message from a sending node comprises an act of receiving at least one liveness header that includes a weight value and a color value.

5. The method as recited in claim 1, wherein the act of receiving a message from a sending node comprises an act of receiving a message from a sending node in one of a plurality of proximity rings the current node participates in.

6. The method as recited in claim 1, wherein the act of accessing at least a current instance ID, current phase value, and current freshness value for the participating node maintained at the current node comprises an act of accessing a corresponding current color value.

7. The method as recited in claim 1, wherein the act of comparing at least the received instance ID, received phase value, and received freshness value to the current instance ID, the current phase value, and the current freshness value respectively comprises an act of comparing within a common color context.

8. The method as recited in claim 1, wherein the act of comparing at least the received instance ID, received phase value, and received freshness value to the current instance ID, the current phase value, and the current freshness value respectively comprises an act of comparing a received color value and a current color value.

9. The method as recited in claim 8, wherein the act of comparing a received color value and a current color value comprises an act of the comparing the received color value and the current color value prior to comparing at least the received instance ID, received phase value, and received freshness value to the current instance ID, the current phase value, and the current freshness value respectively.

10. The method as recited in claim 1, wherein the act of comparing at least the received instance ID, received phase value, and received freshness value to the current instance ID, the current phase value, and the current freshness value respectively comprises an act of determining that the received instance ID is greater than the current instance ID for the participating node.

11. The method as recited in claim 1, wherein the act of comparing at least the received instance ID, received phase value, and received freshness value to the current instance ID, the current phase value, and the current freshness value respectively comprises an act of determining that the received phase value is more advanced than the current phase value for the participating node within the context of a common Instance Id value of the participating node.

12. The method as recited in claim 11, wherein the act of determining that the received phase value is more advanced than the current phase value for the participating node comprises an act determining that the received phase-state value is more advanced in an ordered list of phase-state values.

13. The method as recited in claim 12, wherein the act of act determining that the received phase-state value is more advanced in an ordered list of phase-state values comprises an act determining that the received phase-state value is more advanced in an ordered list of phase-state values that advances forward through an inserting phase, a syncing phase, a routing phase, and an operating phase in order.

14. The method as recited in claim 12, wherein the act of determining that the received phase-state value is more advanced than the current phase-state value for the participating node comprises an act determining that the phase.unknown indication for at least one of the received phase-state values and the current phase-state value indicates that the phase-state value was known at the time indicated by the corresponding freshness value.

15. The method as recited in claim 1, wherein the act of comparing the received instance ID, received phase value, and received freshness value to the current instance ID, the current phase value, and the current freshness value respectively comprises an act of determining that the first freshness value is greater than the current freshness value for the participating node within a common phase value within a common Instance Id value.

16. The method as recited in claim 1, further comprising an act of determining that the current freshness value has decayed over time.

17. The method as recited in claim 16, wherein the act of determining that the current freshness value has decayed over time comprises an act of the current freshness value decaying non-linearly based on the current phase value.

18. The method as recited in claim 1, further comprising an act of determining that the received freshness value decayed as the received freshness value traveled from the sending node.

19. The method as recited in claim 18, wherein the act of determining that the received freshness value decayed as the received freshness value traveled from the sending node comprises an act of the received freshness value decaying non-linearly based on the received phase value.

20. The method as recited in claim 1, wherein the act of determining if state information for the participating node is to be updated based on the comparison comprises an act of determining that state information for the participating node is stale based on at least one of the received instance ID, the received phase value, and the received freshness value, subsequent to receiving the message.

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

an act of detecting the presence of a communication failure between the current node and the participating node, subsequent to updating current state information for the participating node with state information included in the at least one liveness header.

22. The method as recited in claim 21, wherein the act of detecting the presence of a communication failure between the current node and the participating node comprises an act of an application component associated with the current node generating a node down event to a function component at the current node.

23. The method as recited in claim 21, wherein the act of detecting the presence of a communication failure between the current node and the participating node comprises at least one of a transport messaging protocol indicating that a message could not be delivered to the participating node, of failing to receive an expected message, and of failing to receive an expected periodic message.

24. The method as recited in claim 23, wherein the act of detecting the presence of a communication failure between the current node and the participating node further comprises at least one of an application indicating communication has been lost and of a message indicating that the participating node is in an unknown state.

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

an act of routing a liveness-down message with the destination property set to the id of the failed node and indicating with a liveness header that the failed node phase value includes phase.unknown.

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

an act of a node receiving a node-liveness-down message for a failed node, the node-liveness-down message not destined for the node, the node being in neighborhood of the receiving node a node-liveness-down message is destined for.

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

an act of sourcing a departure message for that failed node into the failed node'"'"'s neighborhood by the node receiving a node-liveness-down message.

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

an act of the function layer registering with an associated application component to receive node down events; and

an act of the application component invoking the function layer to propagate the registration as a remote registration to other peer nodes within a federation infrastructure.

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

an act of updating the current state information with state information included in the message.

30. The method as recited in claim 29, wherein the act of updating the current state information with state information included in the message comprises an act of maintaining at least the current phase and also indicating if the participating node is in an unknown phase.

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

an act of receiving a second message from a second different sending node, the message including a second liveness header representing state information for the participating node, the second liveness header including at least a second instance ID, a second phase value, and a second freshness value, the second instance ID identifying an instance of the participating node, the second phase value identifying an expressed phase of the participating node, the second phase value including a second phase-state value and a second phase.unknown indication, the second phase-unknown indication indicating if the second phase-state value was actually known to the second sending node at the time indicated by the freshness value, the second freshness value indicating how recently the second instance ID and second phase value where identified;

an act of comparing at least the second instance ID, the second phase value, and the second freshness value to the current instance ID, the current phase value, and the current freshness value respectively; and

an act of determining if state information for the participating node is to be updated based on the comparison.

32. The method as recited in claim 31, wherein the act of receiving a second message from a second different sending node comprises an act of receiving at least one liveness header that includes a weight value and a color value.

33. The method as recited in claim 31, wherein the act of comparing the second instance ID, second phase value, and second freshness value to the current instance ID, the current phase value, and the current freshness value respectively comprises an act of comparing within a common color context.

34. A computer program product for use at a current node in a federation infrastructure, the computer program product for implementing a method for discovering liveness information for another node in the federation infrastructure, 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:

receiving a message from a sending node, the message including at least one liveness header representing state information for a participating node in the federation infrastructure, the state information including at least a participating node ID, an instance ID, a phase value, and a freshness value, the instance ID identifying an instance of the participating node, the phase value identifying an expressed phase of the participating node, the phase value including an expressed phase-state value and a phase.unknown indication, the phase-unknown indication indicating if the phase-state value was actually known to the sending node at the time indicated by the freshness value, the freshness value indicating how recently the instance ID and phase value where identified;

access at least a current instance ID, current phase value, and current freshness value for the participating node maintained at the current node;

compare at least the received instance ID, the received phase value, and the received freshness value to the current instance ID, the current phase value, and the current freshness value respectively at a current node; and

determine if state information for the participating node is to be updated at the current node based on the comparison.