Maintaining consistency within a federation infrastructure

• US 9,647,917 B2
• Filed: 04/08/2015
• Issued: 05/09/2017
• Est. Priority Date: 10/22/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hasha, Richard L., Xun, Lu, Kakivaya, Gopala Krishna R., Malkhi, Dahlia
• Primary Examiner(s): CONAWAY, JAMES E
• Application Number:
  US14/681,620
• Publication Number:
  US 20150244602A1
• Time in Patent Office: 762 Days
• Field of Search: 709201, 709220-222, 709251
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 45/02 Topology update or 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/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/141 Setup of application sessions admission control or resource allocation in data switching networks H04L47/70

Abstract

The present invention extends to methods, systems, and computer program products for a joining node to join a ring of nodes within a rendezvous federation. Embodiments of the invention include establishing a neighborhood of multiple nodes on the ring of nodes. The joining node indicates its intent to take id-space ownership for a portion of the id-space between the joining node and a selected immediately adjacent node. The joining node initiates a one-way monitoring relationship with the selected immediately adjacent node. The joining node receiving an indication from the selected immediately adjacent node that indicates acceptance of the joining node'"'"'s intent to take id-space ownership for a portion of the id-space between the joining node and the selected node and indicates establishment of a one-way monitoring relationship between the selected node and the joining node. The joining node agrees to participate in a one-way monitoring relationship with the selected node.

Claims

1. A method, implemented by a first node in a ring of nodes of a federation infrastructure, for maintaining ring consistency when the first node joins the ring of nodes, the method comprising:

sending, to a second node in the ring of nodes that is immediately adjacent to the first node in the ring of nodes, an identifier range of a portion of id-space in the ring of nodes between the first node and the second node over which the first node intends to take ownership;

initiating a monitoring relationship with the second node, including establishing a monitor side time-to-live value and a monitor side time-to-die value with the second node, the monitoring relationship presumed to be active during a duration of the monitor side time-to-live value, the second node suspected to have failed if the monitor side time-to-die value is reached without the first node having received a renew request from the second node;

receiving, from the second node, an indication of acceptance by the second node of the first node'"'"'s intent to take id-space ownership for the identifier range of the portion of id-space in the ring between the first node and the second node; and

receiving, from the second node, an indication of establishment of the monitoring relationship between the second node and the first node.

2. The method as recited in claim 1, wherein sending, to the second node, the identifier range of the portion of id-space in the ring of nodes between the first node and the second node over which the first node intends to take ownership comprises:

sending, to the second node, a request that includes a node identifier of the second node such that only the second node, having the node identifier, is capable of responding to the request.

3. The method as recited in claim 1, wherein sending, to the second node, the identifier range of the portion of id-space in the ring of nodes between the first node and the second node over which the first node intends to take ownership comprises:

sending, to the second node, a time-to-live duration value indicative of a duration for which the first node can assume the monitoring relationship with the second node is active.

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

sending, to the second node, an indication of the first nodes'"'"' agreement to participate in the monitoring relationship with the second node.

5. The method as recited in claim 1, wherein establishing the monitor side time-to-live value and the monitor side time-to-die value with the second node comprises negotiating the monitor side time-to-live value and the monitor side time-to-die value with the second node.

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

sending, to a third node that is also immediately adjacent to the first node in the ring of nodes, an additional identifier range of a portion of id-space in the ring between the first node and the third node over which the first node intends to take ownership; and

receiving, from the third node, an indication of acceptance by the third node of the first node'"'"'s intent to take id-space ownership for the additional identifier range of the portion of id-space in the ring between the first node and the third node.

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

receiving, from a third node that is also immediately adjacent to the first node in the ring of nodes, an indication of establishment of a monitoring relationship between the third node and the first node.

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

receiving, from a third node that is also immediately adjacent to the first node in the ring of nodes, a time-to-live duration value indicative of a duration for which the third node can assume a monitoring relationship with the first node is active.

9. A system, comprising:

one or more hardware processors; and

one or more hardware storage devices having stored thereon computer-executable instructions that are configured to be executed by the one or more processors, and to configure the system as a joining node in a federation infrastructure, the joining node being configured for maintaining ring consistency when the joining node joins the ring of nodes, comprising the joining node being configured to;

send, to a first adjacent node in the ring of nodes, an identifier range of a portion of id-space in the ring of nodes between the joining node and the first adjacent node over which the joining node intends to take ownership;

initiate a monitoring relationship with first adjacent node, including establishing a monitor side time-to-live value and a monitor side time-to-die value with first adjacent node, the monitoring relationship presumed to be active during a duration of the monitor side time-to-live value, the first adjacent node suspected to have failed if the monitor side time-to-die value is reached without the joining node having received a renew request from the first adjacent node;

receive, from the first adjacent node, an indication of acceptance by the first adjacent node of the joining node'"'"'s intent to take id-space ownership for the identifier range of the portion of id-space in the ring between the joining node and the first adjacent node; and

receive, from the first adjacent node, an indication of establishment of the monitoring relationship between the first adjacent node and the joining node.

10. The system as recited in claim 9, wherein the joining node is also configured to:

send a request to the first adjacent node that includes a node identifier of the first adjacent node such that only the first adjacent node, having the node identifier, is capable of responding to the request.

11. The system as recited in claim 9, wherein the joining node is also configured to:

send, to the first adjacent node, a first time-to-live duration value indicative of a duration for which the joining node can assume the monitoring relationship with the first adjacent node is active.

12. The system as recited in claim 9, wherein the joining node is also configured to:

send, to the first adjacent node, an indication of the joining nodes'"'"' agreement to participate in the monitoring relationship with the first adjacent node.

13. The system as recited in claim 9, wherein the joining node is also configured to:

negotiate the monitor side time-to-live value and the monitor side time-to-die value with the first adjacent node.

14. The system as recited in claim 9, wherein the joining node is also configured to:

send, to a second adjacent node, an additional identifier range of a portion of id-space in the ring between the joining node and the second adjacent node over which the joining node intends to take ownership; and

receive, from the second adjacent node, an indication of acceptance by the second adjacent node of the joining node'"'"'s intent to take id-space ownership for the additional identifier range of the portion of id-space in the ring between the joining node and the second adjacent node.

15. The system as recited in claim 9, wherein the joining node is also configured to:

receive, from a second adjacent node, an indication of establishment of a monitoring relationship between the joining node and the second adjacent node.

16. The system as recited in claim 9, wherein the joining node is also configured to:

receive, from a second adjacent node, a time-to-live duration value indicative of a duration for which the second adjacent node can assume a monitoring relationship with the joining node is active.

17. A method, implemented by a first adjacent node in a ring of nodes of a federation infrastructure, for maintaining ring consistency when a joining node joins the ring of nodes, the method comprising:

receiving, from the joining node, which is immediately adjacent to the first adjacent node in the ring of nodes, an identifier range of a portion of id-space in the ring of nodes between the joining node and the first adjacent node over which joining node intends to take ownership;

receiving, from the joining node, an indication of the joining node'"'"'s intent to initiate a monitoring relationship with the first adjacent node;

sending, to the joining node, an indication of acceptance of the monitoring relationship with the joining node, and establishing a monitor side time-to-live value and a monitor side time-to-die value with the joining node, the monitoring relationship presumed to be active during a duration of the monitor side time-to-live value, the first adjacent node suspected to have failed if the monitor side time-to-die value is reached without the joining node having received a renew request from the first adjacent node;

sending, to the joining node, an indication of acceptance by the first adjacent node of the joining node'"'"'s intent to take id-space ownership for the identifier range of the portion of id-space in the ring between the joining node and the first adjacent node; and

sending, to the joining node, an indication of establishment of the monitoring relationship between the first adjacent node and the joining node.

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

indicating, to a second adjacent node that is also immediately adjacent to the joining node in the ring of nodes, the first adjacent node'"'"'s intent to terminate any monitoring relationship with the second adjacent node.

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

receiving, from the second adjacent node, an indication of the second adjacent node'"'"'s intent to terminate any monitoring relationship with the first adjacent node.

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

receiving, from the joining node, a time-to-live duration value indicative of a duration for which the joining node can assume a monitoring relationship with the first adjacent node is active.