Balancing distances between nodes on a token ring

• US 10,965,540 B2
• Filed: 12/19/2019
• Issued: 03/30/2021
• Est. Priority Date: 02/06/2017
• Status: Active Grant

• Current Assignee: New Relic
• Original Assignee: New Relic
• Inventors: Urbanski, Jan
• Primary Examiner(s): Chou, Alan S
• Application Number:
  US16/721,495
• Publication Number:
  US 20200136922A1
• Time in Patent Office: 467 Days
• Field of Search: 709223
• CPC Class Codes: H04L 12/417 with deterministic access, e.g. token passing
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based

Abstract

Nodes on a token ring are rebalanced from an initial condition to a condition in which the load is optimally distributed based on a specified level of balance. Nodes are treated as electrically charged particles for purposes of the simulation and are assigned simulation values based on proportions between the size of the cluster, the computing power of the nodes, and the specified level of balance. A simulation module performs the rebalancing simulation by assigning the specified values to the particles and outputting, for each corresponding node, a token indicating the particle'"'"'s final position and the position of the node on the token ring. The tokens are input to a redistribution module, which rebalances the cluster based on the generated tokens.

Claims

1. A method for determining an optimal rebalancing of nodes on a token ring, the method comprising:

receiving, from a client device, an instruction to rebalance nodes on a token ring;

receiving an initial condition of the token ring, the initial condition indicating a number and distribution of the nodes on the token ring and a measure of computing power of each node;

generating recommended rebalancing parameters for the token ring, the rebalancing parameters including simulation values for performing a rebalancing simulation;

performing the rebalancing simulation based on the initial condition and the rebalancing parameters; and

determining, for each node, a final simulation position of the node on the token ring.

2. The method of claim 1, further comprising rebalancing the nodes based on the final simulation positions.

3. The method of claim 1, wherein the recommended simulation values are based at least in part on the initial condition of the token ring.

4. The method of claim 3, further comprising generating an estimated transaction cost for performing the simulation using the recommended simulation values.

5. The method of claim 1, wherein the nodes are represented as charged particles and wherein the simulation values include:

a charge coefficient of each node, a static friction coefficient of each node, a terminal velocity of the nodes, and a length of the simulation.

6. The method of claim 1, wherein the rebalancing parameters include a level of balance of the token ring.

7. The method of claim 6, wherein the level of balance is indicated by a maximum transaction cost for the rebalancing.

8. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations comprising:

receiving, from a client device, an instruction to rebalance nodes on a token ring;

receiving an initial condition of the token ring, the initial condition indicating a number and distribution of the nodes on the token ring and a measure of computing power of each node;

generating recommended rebalancing parameters for the token ring, the rebalancing parameters including simulation values for performing a rebalancing simulation;

performing the rebalancing simulation based on the initial condition and the rebalancing parameters; and

determining, for each node, a final simulation position of the node on the token ring.

9. The non-transitory computer-readable storage medium of claim 8, further comprising rebalancing the nodes based on the final simulation positions.

10. The non-transitory computer-readable storage medium of claim 8, wherein the recommended simulation values are based at least in part on the initial condition of the token ring.

11. The non-transitory computer-readable storage medium of claim 10, further comprising generating an estimated transaction cost for performing the simulation using the recommended simulation values.

12. The non-transitory computer-readable storage medium of claim 8, wherein the nodes are represented as charged particles and wherein the simulation values include:

a charge coefficient of each node, a static friction coefficient of each node, a terminal velocity of the nodes, and a length of the simulation.

13. The non-transitory computer-readable storage medium of claim 8, wherein the rebalancing parameters include a level of balance of the token ring.

14. The non-transitory computer-readable storage medium of claim 13, wherein the level of balance is indicated by a maximum transaction cost for the rebalancing.

15. A system comprising:

a computer processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations comprising;

receiving, from a client device, an instruction to rebalance nodes on a token ring;

receiving an initial condition of the token ring, the initial condition indicating a number and distribution of the nodes on the token ring and a measure of computing power of each node;

generating recommended rebalancing parameters for the token ring, the rebalancing parameters including simulation values for performing a rebalancing simulation;

performing the rebalancing simulation based on the initial condition and the rebalancing parameters; and

determining, for each node, a final simulation position of the node on the token ring.

16. The system of claim 15, further comprising rebalancing the nodes using based on the final simulation positions.

17. The system of claim 15, wherein the recommended simulation values are based at least in part on the initial condition of the token ring.

18. The system of claim 15, wherein the nodes are represented as charged particles and wherein the simulation values include:

a charge coefficient of each node, a static friction coefficient of each node, a terminal velocity of the nodes, and a length of the simulation.

19. The system of claim 15, wherein the rebalancing parameters include a level of balance of the token ring.

20. The system of claim 19, wherein the level of balance is indicated by a maximum transaction cost for the rebalancing.