Maintaining Consistency Within A Federation Infrastructure

Abstract

Maintaining ring consistency when a node leaves a ring includes a first adjacent node to a leaving node receiving an indication, from the leaving node, indicating its intent to leave the ring. The first adjacent node sends a first indication to a second adjacent node indicating i) acceptance of the leaving node's intent to leave id-space ownership for a portion of the id-space between the leaving node and the first adjacent node, and ii) establishment of a one-way monitoring relationship between the first adjacent node and the second adjacent node. The first adjacent node receives a second indication, from the second adjacent node, indicating i) acceptance of the first adjacent node's intent to assume id-space ownership for the portion of the id-space between the leaving node and the first adjacent node, and ii) establishment of the one-way monitoring relationship between the second adjacent node and the first adjacent node.

What is claimed is: 
     
         1 . In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a leaving node, a first adjacent node adjacent to the leaving node on the ring, and a second adjacent node adjacent to the leaving node on the ring, a method for maintaining ring consistency when the leaving node leaves the ring of nodes, the method comprising:
 receiving, at the first adjacent node, an indication from the leaving node indicating the leaving node's intent to leave the ring of nodes;   sending, by the first adjacent node, a first indication to the second adjacent node that:
 indicates acceptance of the leaving node's intent to leave id-space ownership for a portion of the id-space between the leaving node and the first adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the first adjacent node and the second adjacent node; and 
   receiving, at the first adjacent node, a second indication from the second adjacent node that:
 indicates acceptance of the first adjacent node's intent to assume id-space ownership for the portion of the id-space between the leaving node and the first adjacent node; and 
 indicates establishment of the one-way monitoring relationship between the second adjacent node and the first adjacent node. 
   
     
     
         2 . The method of  claim 1 , wherein the first adjacent node receiving the indication from the leaving node indicating the leaving node's intent to leave the ring of nodes comprises:
 receiving, at the first adjacent node, a departure message from the leaving node, the departure message including an ownership range of node identifiers indicated as being owned by the leaving node.   
     
     
         3 . The method of  claim 1 , wherein the first adjacent node sending the first indication to the second adjacent node comprises:
 sending, by the first adjacent node, an establishment request to the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and   receiving, by the first adjacent node, an establish grant for the establishment request, the establish grant indicative of the second adjacent node monitoring the first adjacent node.   
     
     
         4 . The method of  claim 3 , wherein the establishment request includes a time-to-live duration, time-to-live duration indicative of a duration for which the first adjacent node can assume a monitoring relationship with the second adjacent node is active. 
     
     
         5 . The method of  claim 1 , wherein the first adjacent node receiving the second indication from the second adjacent node comprises:
 receiving, at the first adjacent node, an establishment request from the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and   sending, by the first adjacent node, an establish grant for the establishment request, the establish grant indicative of the first adjacent node monitoring the second adjacent node.   
     
     
         6 . The method of  claim 5 , the establishment request including a time-to-live duration, the 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. 
     
     
         7 . The method of  claim 1 , wherein one of both of the first adjacent node or the second adjacent node are immediately adjacent to the leaving node on the ring. 
     
     
         8 . The method of  claim 1 , wherein:
 the first adjacent node sending the first indication to the second adjacent node comprises:
 sending, by the first adjacent node, a first establishment request to the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and 
 receiving, by the first adjacent node, a first establish grant for the establishment request, the first establish grant indicative of the second adjacent node monitoring the first adjacent node, and 
   the first adjacent node receiving the second indication from the second adjacent node comprises:
 receiving, at the first adjacent node, a second establishment request from the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and 
 sending, by the first adjacent node, a second establish grant for the establishment request, the second establish grant indicative of the first adjacent node monitoring the second adjacent node. 
   
     
     
         9 . The method of  claim 8 , wherein the first establishment request includes a first time-to-live duration, first time-to-live duration indicative of a duration for which the first adjacent node can assume a monitoring relationship with the second adjacent node is active, and wherein the second establishment request includes 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. 
     
     
         10 . A computer system, comprising:
 one or more processors; and   one or more computer-readable media having stored thereon computer-executable instructions that are structured such that, when executed at the one or more processors, the computer-executable instructions configure the computer system as a first adjacent node in a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including i) a leaving node, ii) the first adjacent node, and iii) a second adjacent node, the first and second adjacent nodes being adjacent to the leaving node on the ring, the first adjacent node being configured to perform at least the following:   receive an indication from the leaving node indicating the leaving node's intent to leave the ring of nodes;   send a first indication to the second adjacent node that:
 indicates acceptance of the leaving node's intent to leave id-space ownership for a portion of the id-space between the leaving node and the first adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the first adjacent node and the second adjacent node; and 
   receive a second indication from the second adjacent node that:
 indicates acceptance of the first adjacent node's intent to assume id-space ownership for the portion of the id-space between the leaving node and the first adjacent node; and 
 indicates establishment of the one-way monitoring relationship between the second adjacent node and the first adjacent node. 
   
     
     
         11 . The computer system of  claim 10 , wherein receiving the indication from the leaving node indicating the leaving node's intent to leave the ring of nodes comprises:
 receiving a departure message from the leaving node, the departure message including an ownership range of node identifiers indicated as being owned by the leaving node.   
     
     
         12 . The computer system of  claim 10 , wherein sending the first indication to the second adjacent node comprises:
 sending an establishment request to the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and   receiving an establish grant for the establishment request, the establish grant indicative of the second adjacent node monitoring the first adjacent node.   
     
     
         13 . The computer system of  claim 12 , wherein the establishment request includes a time-to-live duration, time-to-live duration indicative of a duration for which the first adjacent node can assume a monitoring relationship with the second adjacent node is active. 
     
     
         14 . The computer system of  claim 10 , wherein receiving the second indication from the second adjacent node comprises:
 receiving an establishment request from the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and   sending an establish grant for the establishment request, the establish grant indicative of the first adjacent node monitoring the second adjacent node.   
     
     
         15 . The computer system of  claim 14 , the establishment request including a time-to-live duration, the 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. 
     
     
         16 . The computer system of  claim 10 , wherein one of both of the first adjacent node or the second adjacent node are immediately adjacent to the leaving node on the ring. 
     
     
         17 . The computer system of  claim 10 , wherein:
 sending the first indication to the second adjacent node comprises:
 sending a first establishment request to the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node; and 
 receiving a first establish grant for the establishment request, the first establish grant indicative of the second adjacent node monitoring the first adjacent node, and 
   receiving the second indication from the second adjacent node comprises:
 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; and 
 sending a second establish grant for the establishment request, the second establish grant indicative of the first adjacent node monitoring the second adjacent node. 
   
     
     
         18 . The computer system of  claim 17 , wherein the first establishment request includes a first time-to-live duration, first time-to-live duration indicative of a duration for which the first adjacent node can assume a monitoring relationship with the second adjacent node is active, and wherein the second establishment request includes 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. 
     
     
         19 . A computer program product comprising one or more computer-readable media having stored thereon computer-executable instructions that are structured such that, when executed at one or more processors, the computer-executable instructions configure a first adjacent node in a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including i) a leaving node, ii) the first adjacent node, and iii) a second adjacent node, the first and second adjacent nodes being adjacent to the leaving node on the ring, the first adjacent node being configured to perform at least the following:
 receive an indication from the leaving node indicating the leaving node's intent to leave the ring of nodes; 
 send a first indication to the second adjacent node that:
 indicates acceptance of the leaving node's intent to leave id-space ownership for a portion of the id-space between the leaving node and the first adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the first adjacent node and the second adjacent node; and 
 
 receive a second indication from the second adjacent node that:
 indicates acceptance of the first adjacent node's intent to assume id-space ownership for the portion of the id-space between the leaving node and the first adjacent node; and 
 indicates establishment of the one-way monitoring relationship between the second adjacent node and the first adjacent node. 
 
 
     
     
         20 . The computer program product of  claim 19 , wherein:
 sending the first indication to the second adjacent node comprises:
 sending a first establishment request to the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node, the first establishment request including a first time-to-live duration, first time-to-live duration indicative of a duration for which the first adjacent node can assume a monitoring relationship with the second adjacent node is active; and 
 receiving a first establish grant for the establishment request, the first establish grant indicative of the second adjacent node monitoring the first adjacent node, and 
   receiving the second indication from the second adjacent node comprises:
 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 
 sending a second establish grant for the establishment request, the second establish grant indicative of the first adjacent node monitoring the second adjacent node.