MAINTAINING CONSISTENCY WITHIN A FEDERATION INFRASTRUCTURE

• US 20080288659A1
• Filed: 11/07/2007
• Published: 11/20/2008
• Est. Priority Date: 11/09/2006
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malkhi, Dahlia, Hasha, Richard L., Kakivaya, Gopala Krishna R., Xun, Lu
• Application Number:
  US11/936,589
• Publication Number:
  US 20080288659A1
• Time in Patent Office: Days
• US Class Current: 709/250
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• 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

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 include detecting a neighborhood of 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 indicates an intent to monitor the selected node. The joining node receives three indications, the first indicating 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, the second indicating acceptance of the joining node'"'"'s intent to monitor the selected node, the third indicating the first selected node'"'"'s intent to monitor the joining node. The joining node indicates acceptance of the selected node'"'"'s intent to monitor the joining node.

Claims

1. In a federation infrastructure of a ring of nodes configured for bi-directional routing, a method for maintaining ring consistency when a joining node joins the ring of nodes, the method comprising:

an act of a joining node detecting a neighborhood of a plurality of other nodes on the ring, the neighborhood including at least an immediately adjacent predecessor node and an immediately adjacent successor node;

an act of the joining node indicating to one of the immediately adjacent nodes selected from among the immediately adjacent predecessor node and an immediately adjacent successor node, the intent of the joining node to take id-space ownership for a portion of the id-space between the joining node and the selected immediately adjacent node;

an act of the joining node indicating an intent to monitor the selected immediately adjacent node;

an act of the joining node receiving a first indication from the selected immediately adjacent node indicating 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 immediately adjacent node;

an act of the joining node receiving a second indication from the as selected immediately adjacent node indicating acceptance of the joining node'"'"'s intent to monitor the selected immediately adjacent node;

an act of the joining node receiving a third indication from the selected immediately adjacent node indicating the first selected immediately adjacent node'"'"'s intent to monitor the joining node; and

an act of the joining node indicating acceptance of the selected immediately adjacent node'"'"'s intent to monitor the joining node.

2. The method of claim 1, further comprising:

an act of the joining node receiving an indication from the other immediately adjacent node indicating id-space ownership for the portion of id-space between the joining node and the other immediately adjacent node;

an act of the joining node receiving an indication from the other immediately adjacent node indicating the other immediately adjacent node'"'"'s intent to monitor the joining node;

an act of the joining node indicating to the other immediately adjacent node the intent of the joining node to establish id-space ownership for a portion of the id-space between the joining node and the other immediately adjacent node;

an act of the joining node indicating an intent to monitor the other immediately adjacent node; and

an act of the joining node receiving an indication from the other immediately adjacent node indicating the other immediately adjacent node'"'"'s intent to monitor the joining node.

3. The method of claim 1, wherein the act of the joining node indicating to one of the immediately adjacent nodes selected from among the immediately adjacent predecessor node and an immediately adjacent successor node, the intent of the joining node to take id-space ownership for a portion of the id-space between the joining node and the selected immediately adjacent node comprises an act of sending a token request to a selected immediately adjacent node from among the immediately adjacent predecessor node and an immediately adjacent successor node, the token request including:

a node identifier such that only the node with the node identifier is capable of replying; and

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

4. The method of claim 1, wherein the first, second and third indications are combined in a single indication.

5. The method of claim 4, wherein receiving the single indication comprises an act of receiving a first token transfer from the selected immediately adjacent node, the first token transfer including:

the joining node'"'"'s ownership range of unoccupied node identifiers in the ring of nodes between the joining node and the selected immediately adjacent node;

a second time-to-live duration value, the second time-to-live duration value indicative of a duration for which the selected immediately adjacent node can assume a monitoring relationship with the joining node is active; and

a first establish grant indicative of the selected immediately adjacent node monitoring the joining node.

6. The method of claim 1, wherein the act of the joining node indicating acceptance of the selected immediately adjacent node'"'"'s intent to monitor the joining node comprises an act of sending an acknowledgement message to the selected immediately adjacent node, the acknowledgement message including:

a first ownership range between the joining node and the selected immediately adjacent node; and

a second establish grant indicative of the joining node monitoring the selected immediately adjacent node.

7. The method of claim 2, wherein the act of the joining node receiving an indication from the other immediately adjacent node that indicates id-space ownership for the portion of id-space between the joining node and the other immediately adjacent node indicates the other immediately adjacent node'"'"'s intent to monitor the joining node comprises an act of receiving a second token transfer from the other immediately adjacent node, the second token transfer including:

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

8. The method of claim 7, wherein the act of act of the joining node as indicating to the other immediately adjacent node the intent of the joining node to establish id-space ownership for a portion of the id-space between the joining node and the other immediately adjacent node comprises an act of sending an establishment request to establish a second ownership range between the joining node and the other immediately adjacent node, the establishment request including:

a fourth time-to-live duration, the fourth time-to-live duration indicative of a duration for which the joining node can assume a monitoring relationship with the other immediately adjacent node is active; and

a third establish grant indicative of the joining node monitoring the other immediately adjacent node.

9. The method of claim 7, wherein the act of the joining node receiving an indication from the other immediately adjacent node indicating the other immediately adjacent node'"'"'s intent to monitor the joining node comprises an act of receiving a fourth establish grant for the establishment request, the fourth establish grant indicative of the other adjacent node monitoring the joining node.

10. The method of claim 1, further comprising:

an act of the joining node receiving a negative acknowledge (NAK) message from at least one of the nodes on the ring, the NAK message including an indication of the NAK sender'"'"'s view of the ring; and

an act of updating the joining node'"'"'s view of the neighborhood based on the NAK sender'"'"'s view of the ring.

11. In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a first selected immediately adjacent node and a second selected immediately adjacent node, a method for maintaining ring consistency when a joining node joins the ring of nodes between the first and second immediately adjacent nodes, the method comprising:

an act of a first selected immediately adjacent node receiving an indication from the joining node indicating the intent of the joining node to take id-space ownership for a portion of the id-space between the joining node and the first selected immediately adjacent node;

an act of the first selected immediately adjacent node receiving an indication from the joining node of the joining node'"'"'s intent to monitor the selected immediately adjacent node;

an act of the first selected immediately adjacent node sending a first indication to the joining node indicating 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 first selected immediately adjacent node;

an act of the first selected immediately adjacent node sending a second indication to the joining node indicating acceptance of the joining node'"'"'s intent to monitor the selected immediately adjacent node;

an act of the first selected immediately adjacent node sending a third indication to the joining node indicating the first selected immediately adjacent node'"'"'s intent to monitor the joining node; and

an act of the first selected immediately adjacent node receiving an indication from the joining node indicating acceptance of the first selected immediately adjacent node'"'"'s intent to monitor the joining node.

12. The method of claim 11, further comprising:

an act of the first selected immediately adjacent node indicating to a second selected immediately adjacent node the first node'"'"'s intent to terminate any monitoring relationships with the second selected immediately adjacent node;

an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node indicating the second node'"'"'s intent to terminate any monitoring relationships with the first selected immediately adjacent node; and

an act of the first selected immediately adjacent node acknowledging the second node'"'"'s intent to terminate.

13. The method of claim 11, further comprising:

an act of receiving an introduction message from the joining node, the introduction message including an expected ownership range of node identifiers indicated as being owned by the joining node; and

an act of sending an acknowledgment message to the joining node, the acknowledgement message including an indication that the range of node identifiers identified by the joining node is consistent with the selected immediately adjacent node'"'"'s range of node identifiers.

14. In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a first selected immediately adjacent node and a second selected immediately adjacent node, a method for maintaining ring consistency when a joining node joins the ring of nodes between the first and second immediately adjacent nodes, the method comprising:

an act of a first selected immediately adjacent node, selected from among the immediately adjacent predecessor node and an immediately adjacent successor node, indicating to the joining node id-space ownership for the portion of id-space between the joining node and the first selected immediately adjacent node;

an act of the first selected immediately adjacent node indicating the first selected immediately adjacent node'"'"'s intent to monitor the joining node;

an act of the first selected immediately adjacent node receiving an indication of the joining node'"'"'s intent to establish id-space ownership for a portion of the id-space between the joining node and the first selected immediately adjacent node;

an act of the first selected immediately adjacent node receiving an indication of the joining node'"'"'s intent to monitor the first selected immediately adjacent node; and

an act of the first selected immediately adjacent node indicating to the joining node the first selected node'"'"'s intent to monitor the joining node.

15. The method of claim 14, further comprising:

an act of the first selected immediately adjacent node receiving an indication from a second selected immediately adjacent node indicating the second node'"'"'s intent to terminate any monitoring relationships with the first selected immediately adjacent node;

an act of the first selected immediately adjacent node indicating to the second selected immediately adjacent node the first node'"'"'s intent to terminate any monitoring relationships with the second selected immediately adjacent node; and

an act of the first selected immediately adjacent node receiving an acknowledgment acknowledging the first node'"'"'s intent to terminate.

16. The method of claim 15, further comprising an act of the first selected immediately adjacent node acknowledging the indication from the second selected immediately adjacent node.

17. In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a leaving node, a first selected immediately adjacent node, and a second selected immediately adjacent node, the first and second nodes being immediately adjacent to and the leaving node on the ring, a method for maintaining ring consistency when the leaving node leaves the ring of nodes, the method comprising:

an act of the first selected immediately adjacent node receiving an indication of the leaving node'"'"'s act of leaving the ring of nodes;

an act of the first selected immediately adjacent node sending an indication to the second selected immediately adjacent node indicating an intent to assume the leaving node'"'"'s id-space ownership for a portion of the id-space between the leaving node and the first selected immediately adjacent node;

an act of the first selected immediately adjacent node sending an indication to the second selected immediately adjacent node indicating establishment of at least a one-way monitoring relationship between the first selected immediately adjacent node and the second selected immediately adjacent node;

an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node indicating acceptance of the first node'"'"'s intent to assume id-space ownership for a portion of the id-space between the leaving node and the first selected immediately adjacent node; and

an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node indicating establishment of at least a one-way monitoring relationship between the second selected immediately adjacent node and the first selected immediately adjacent node.

18. The method of claim 17, wherein the act of the first selected immediately adjacent node receiving an indication of the leaving node'"'"'s act of leaving the ring of nodes comprises the first selected immediately adjacent node receiving a departure message from at least one of the nodes on the ring of nodes, the departure message including an ownership range of node identifiers indicated as being owned by the leaving node.

19. The method of claim 18, wherein the act of the first selected immediately adjacent node sending an indication to the second selected immediately adjacent node indicating an intent to assume the leaving node'"'"'s id-space ownership for a portion of the id-space between the leaving node comprises:

an act of the first selected immediately adjacent node sending a first establishment request the second selected immediately adjacent node to establish an ownership range between the first selected immediately adjacent node and the second selected immediately adjacent node, the first establishment request including a first time-to-live duration, the first time-to-live duration indicative of a duration for which the first selected immediately adjacent node can assume a monitoring relationship with the second selected immediately adjacent node is active; and

an act of the first adjacent node receiving a first establish grant for the first establishment request, the first establish grant indicative of the second adjacent node monitoring the first selected immediately adjacent node.

20. The method of claim 19, wherein the act of an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node that indicates acceptance of the first node'"'"'s intent to assume id-space ownership for a portion of the id-space between the leaving node and comprises:

an act of the first adjacent node receiving a second establishment request from the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node, the second establishment request including a second time-to-live duration, the second time-to-live duration indicative of a duration for which the second adjacent node can assume a monitoring relationship with the first adjacent node is active; and

an act of the first adjacent node sending a second establish grant for the second establishment request, the second establish grant indicative of the first adjacent node monitoring the second adjacent node.