Failure notification in rendezvous federation

• US 7,934,118 B2
• Filed: 04/27/2009
• Issued: 04/26/2011
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kakivaya, Gopala Krishna Reddy, Hunter, Jason T., Xun, Lu
• Primary Examiner(s): Chu; Gabriel L
• Application Number:
  US12/430,258
• Publication Number:
  US 20100107002A1
• Time in Patent Office: 729 Days
• Field of Search: None
• US Class Current: N/A
• CPC Class Codes: G06F 11/2025 using centralised failover control functionality
• CPC Class Codes: H04L 41/0659 by isolating or reconfiguring faulty entities

Abstract

Systems and methods that supply a global knowledge on what nodes are available in the system, via employing routing tokens that are analyzed by a centralized management component to infer status for the nodes. When nodes fail, the routing tokens associated therewith are acquired by neighboring nodes, and the global knowledge updated. Moreover, upon inferring a failed or down status for a node, a challenge can be sent to a node reporting such failure to verify actual failure(s).

Claims

1. A computer-implemented system comprising:

a collection of nodes of a network, the collection of nodes configured to participate in a federation and exchange tokens containing ranges of node identification; and

a centralized management component configured to

based on the tokens, maintain information regarding a status of the participating nodes,

analyze the information to infer a failure of at least one node of the collection of nodes, based on a change in a range of node identification information in a token received from another node of the collection of nodes, and

send a challenge message to the another node requesting information regarding a neighboring node in a range of identification information of the another node, to verify the failure.

2. The computer-implemented system of claim 1, wherein the centralized management component is configured to differentiate between different instances of a same node.

3. The computer-implemented system of claim 1, further comprising a mapping function configured to map node identities to nodes of the collection of nodes.

4. The computer-implemented system of claim 3, the mapping function further comprising a one-to-one mapping function definable from a value domain of node identities to the collection of nodes.

5. The computer-implemented system of claim 4, wherein the mapping function is configured to account for sparseness of nodes of the collection of nodes.

6. The computer-implemented system of claim 1, further comprising a recovery component configured to facilitate recovery of a token for a failed node.

7. The computer-implemented system of claim 1, wherein the range of the token is separable into two ranges for transfer to other tokens.

8. The computer-implemented system of claim 1, wherein tokens of nodes of the collection of nodes contain a consecutive range of IDs for the nodes of the collection of nodes.

9. The computer-implemented system of claim 1, further comprising a table configured to maintain information for each node, the information including a latest instance identifier of each node of the collection of nodes, and whether the latest instance is known to be failed or not.

10. A computer-implemented method comprising:

exchanging tokens among networked nodes participating in a federation, the tokens containing ranges of node identification;

based on the tokens, maintaining information regarding a status of the participating nodes;

analyzing the information; and

if the analyzing determines that a range of node identification reported by a node has changed, sending a challenge message to the reporting node requesting information concerning at least one other node covered by the range of the reporting node.

11. The computer-implemented method of claim 10, further comprising determining, based on a reply to the challenge message, whether the at least one other node has failed.

12. The computer-implemented method of claim 10, further comprising maintaining a token version for at least one of the tokens.

13. The computer-implemented method of claim 10, further comprising

defining a one-to-one mapping function from a value domain of node identities to the participating nodes;

and

maintaining global knowledge associated with

the one-to-one mapping function, and

a latest instance identifier of each node of the participating nodes, and whether the latest instance is known to be failed or not.

14. The computer-implemented method of claim 10, further comprising receiving from the reporting node, in reply to the challenge message, information regarding nodes known by the reporting node to have failed.

15. The computer-implemented method of claim 10, further comprising updating the information regarding the status of the participating nodes.

16. The computer-implemented method of claim 10, further comprising splitting a current token identification range if a new node joins the federation, by transferring a sub-range of the current token identification range to a token of the new node.

17. The computer-implemented method of claim 10, further comprising merging tokens if a node leaves a ring of the participating nodes.

18. The computer-implemented method of claim 10, further comprising updating an instance ID of a node of the participating nodes.

19. The computer-implemented method of claim 10, further comprising sending a probe message from one routing node of the participating nodes to another routing node of the participating nodes.

20. A computer-readable storage medium storing instructions to, if executed by a computing device, cause the computing device to perform operations comprising:

receiving a routing token from a node of a collection of nodes participating in a networked federation;

inferring, based on a change in a range of identification information in the routing token, that at least one other node in the collection of nodes has failed; and

sending a challenge message to the node sending the routing token, requesting information concerning a neighboring node within a range of identification information corresponding to the node sending the routing token, to verify that the at least one other node has failed.