Search
Patexia Research
Issue Date Oct 21, 2021
Claim this application
PDF Unavailable

Patent Application - SELF-ELECTION PROCESSES IN MANAGED SUBNETS IMPLEMENTING MODIFIED SWIM PROTOCOLS > Claims

  • 1. A method of self-election of a node in a subnet, the method comprising: receiving, by a first node of a plurality of nodes in a subnet, a first ping message, the first ping message being unicast from a second node of the plurality of nodes in the subnet, wherein the first ping message includes direct information related to the second node and indirect information related to a third node of the plurality of nodes in the subnet;updating a first status of the second node in a status list stored at the first node consistent with the direct information;determining whether statuses have been received from a threshold number of nodes of the plurality of nodes in the status list;responsive to the threshold number of nodes being received, performing a local election operation, wherein the local election operation includes: determining a current election score of the first node based on election rules associated with identifying a particular node from the plurality of nodes in the subnet to provide a service;comparing the current election score to determined election scores of the threshold number of nodes; andresponsive to the current election score being greater than the determined election scores: changing a current election state of the first node to a selected state for the service;communicating a response message to the second node, wherein the response message includes the current election state of the first node and indirect information related to one or more nodes of the plurality of nodes, and the response message is configured to indicate that the first node is an elected node for exclusive execution of the service in the subnet; andexecuting, by the first node, the service in the subnet without oversight by an administration device; andpropagating a second ping message to at least one randomly identified additional node of the plurality of nodes, the second ping message including direct information regarding the first node and indirect information regarding at least one other node of the plurality of nodes.
    • 2. The method of claim 1, further comprising: communicating a multicast ping message to a subset of nodes of the plurality of nodes in the subnet;responsive to failure to receive a response message to the multicast ping message, communicating a broadcast ping message to the plurality of nodes in the subnet;responsive to failure to receive a response message to the broadcast ping message, listening for an address resolution protocol (ARP) message; andresponsive to failure to receive a response based on the ARP listening, determining that the first node is an initial node of the subnet.
    • 3. The method of claim 1, wherein: the propagating includes at each Scalable, Weakly-Consistent, Infection-Style, Processes Group Membership Protocol (SWIM) period of a plurality of SWIM periods: randomly identifying one or more receiving nodes from a receiving node pool;randomly identifying one or more ancillary nodes from an ancillary node pool;generating a ping message for a current SWIM period that includes indirect information related to the identified ancillary nodes and direct information of the first node;communicating the ping message to each of the identified receiving nodes;removing the identified ancillary nodes from the ancillary node pool; andremoving the identified receiving nodes from the receiving node pool; andfollowing communication of one of the ping messages to each of the plurality of nodes, the receiving node pool and the ancillary node pool are repopulated with all of the plurality of nodes except the first node; anda number of SWIM periods in the plurality of SWIM periods is related to a number of nodes in the plurality of nodes.
      • 4. The method of claim 3, further comprising: determining whether the received indirect information regarding the third node is new to the status list; andresponsive to the received indirect information being new to the status list, setting a number of the one or more receiving nodes identified during each SWIM period to include at least three receiving nodes.
    • 5. The method of claim 1, further comprising responsive to the threshold number of nodes not being received, continuing to receive ping messages, and updating the status list, wherein: the direct information includes a first election state and a first machine state of the second node,the indirect information includes a second election state and a second machine state of the third node; andthe direct information and the indirect information are weighted differently.
    • 6. The method of claim 1, further comprising: determining whether the third node is removed from the status list; andresponsive to a determination that the third node is removed from the status list, prioritizing communication of a third ping message including the current election state from the first node to the third node above communication of the third ping message to any other node of the plurality of nodes to ensure the third node is not simultaneously elected to execute the service.
    • 7. The method of claim 1, further comprising responsive to either a third ping message from a fifth node being a first communication received at the first node from the fifth node; or a change in the current election state of the first node and a fifth node of the plurality of nodes was previously selected to execute the service in the subnet prior to the change in the current election state, prioritizing communication of a third ping message from the first node to the fifth node above communication of the third ping message to any other node of the plurality of nodes.
    • 8. The method of claim 1, further comprising: determining whether the indirect information received in the first ping message is older than current status information of a second status of the third node in the status list;responsive to the indirect information being older than the current status information of the second status, not updating the second status with the indirect information and including in the response message, the current status information of the third node such that the second node is able to communicate the current status information instead of the indirect information; andresponsive to the current status information of the second status being older than the indirect information, updating the second status of the third node in the status list consistent with status information in the indirect information.
    • 9. The method of claim 1, wherein: the first ping message is one of multiple ping messages received by the first node;each ping message of the multiple ping messages includes a node number that indicates a number of nodes the transmitting node has identified in the subnet; andthe determining whether statuses of a threshold number of nodes are update includes averaging the number of nodes reported in the node numbers of the multiple ping messages and applying a threshold number to an averaged number of nodes.
    • 10. The method of claim 1, further comprising responsive to the current election score being greater than the determined election scores: creating a new time stamp for the current election state; andappending the new time stamp to information representative of the current election state,wherein: the new time stamp is a monotonic increase of a previous time stamp attached to a previous election state of the first node; andthe response message includes the new time stamp with the current election state.
  • 11. A non-transitory computer-readable medium having encoded therein programming code executable by one or more processors to perform or control performance of operations of self-election of a node in a subnet, the operations comprising: receiving, by a first node of a plurality of nodes in a subnet, a first ping message, the first ping message being unicast from a second node of the plurality of nodes in the subnet, wherein the first ping message includes direct information related to the second node and indirect information related to a third node of the plurality of nodes in the subnet;updating a first status of the second node in a status list stored at the first node consistent with the direct information;determining whether statuses have been received from a threshold number of nodes of the plurality of nodes in the status list;responsive to the threshold number of nodes being received, performing a local election operation, wherein the local election operation includes: determining a current election score of the first node based on election rules associated with identifying a particular node from the plurality of nodes in the subnet to provide a service;comparing the current election score to determined election scores of the threshold number of nodes; andresponsive to the current election score being greater than the determined election scores: changing a current election state of the first node to a selected state for the service;communicating a response message to the second node, wherein the response message includes the current election state of the first node and indirect information related to one or more nodes of the plurality of nodes, and the response message is configured to indicate that the first node is an elected node for exclusive execution of the service in the subnet; andexecuting, by the first node, the service in the subnet without oversight by an administration device; andpropagating a second ping message to at least one randomly identified additional node of the plurality of nodes, the second ping message including direct information regarding the first node and indirect information regarding at least one other node of the plurality of nodes.
    • 12. The non-transitory computer-readable medium of claim 11, wherein the operations further comprise: communicating a multicast ping message to a subset of nodes of the plurality of nodes in the subnet;responsive to failure to receive a response message to the multicast ping message, communicating a broadcast ping message to the plurality of nodes in the subnet;responsive to failure to receive a response message to the broadcast ping message, listening for an address resolution protocol (ARP) message; andresponsive to failure to receive a response based on the ARP listening, determining that the first node is an initial node of the subnet.
    • 13. The non-transitory computer-readable medium of claim 11, wherein: the propagating includes at each Scalable, Weakly-Consistent, Infection-Style, Processes Group Membership Protocol (SWIM) period of a plurality of SWIM periods: randomly identifying one or more receiving nodes from a receiving node pool;randomly identifying one or more ancillary nodes from an ancillary node pool;generating a ping message for a current SWIM period that includes indirect information related to the identified ancillary nodes and direct information of the first node;communicating the ping message to each of the identified receiving nodes;removing the identified ancillary nodes from the ancillary node pool; andremoving the identified receiving nodes from the receiving node pool; andfollowing communication of one of the ping messages to each of the plurality of nodes, the receiving node pool and the ancillary node pool are repopulated with all of the plurality of nodes except the first node; anda number of SWIM periods in the plurality of SWIM periods is related to a number of nodes in the plurality of nodes.
      • 14. The non-transitory computer-readable medium of claim 13, wherein the operations further comprise: determining whether the received indirect information regarding the third node is new to the status list; andresponsive to the received indirect information being new to the status list, setting a number of the one or more receiving nodes identified during each SWIM period to include at least three receiving nodes.
    • 15. The non-transitory computer-readable medium of claim 11, wherein: the operations further comprise responsive to the threshold number of nodes not being received, continuing to receive ping messages, and updating the status list;the direct information includes a first election state and a first machine state of the second node;the indirect information includes a second election state and a second machine state of the third node; andthe direct information and the indirect information are weighted differently.
    • 16. The non-transitory computer-readable medium of claim 11, wherein the operations further comprise: determining whether the third node is removed from the status list; andresponsive to a determination that the third node is removed from the status list, prioritizing communication of a third ping message including the current election state from the first node to the third node above communication of the third ping message to any other node of the plurality of nodes to ensure the third node is not simultaneously elected to execute the service.
    • 17. The non-transitory computer-readable medium of claim 11, wherein the operations further comprise prioritizing communication of a third ping message from the first node to a fifth node above communication of the third ping message to any other node of the plurality of nodes responsive to either: a third ping message from the fifth node being a first communication received at the first node from the fifth node; ora change in the current election state of the first node and the fifth node of the plurality of nodes was previously selected to execute the service in the subnet prior to the change in the current election state.
    • 18. The non-transitory computer-readable medium of claim 11, wherein the operations further comprise: determining whether the indirect information received in the first ping message is older than current status information of a second status of the third node in the status list;responsive to the indirect information being older than the current status information of the second status, not updating the second status with the indirect information and including in the response message, the current status information of the third node such that the second node is able to communicate the current status information instead of the indirect information; andresponsive to the current status information of the second status being older than the indirect information, updating the second status of the third node in the status list consistent with status information in the indirect information.
    • 19. The non-transitory computer-readable medium of claim 11, wherein: the first ping message is one of multiple ping messages received by the first node;each ping message of the multiple ping messages includes a node number that indicates a number of nodes the transmitting node has identified in the subnet; andthe determining whether statuses of a threshold number of nodes are update includes averaging the number of nodes reported in the node numbers of the multiple ping messages and applying a threshold number to an averaged number of nodes.
    • 20. The non-transitory computer-readable medium of claim 11, wherein: the operations further comprise responsive to the current election score being greater than the determined election scores: creating a new time stamp for the current election state; andappending the new time stamp to information representative of the current election state, andthe new time stamp is a monotonic increase of a previous time stamp attached to a previous election state of the first node; andthe response message includes the new time stamp with the current election state.
Menu