Balancing distances between nodes on a token ring

• US 10,560,341 B2
• Filed: 02/06/2018
• Issued: 02/11/2020
• 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:
  US15/890,010
• Publication Number:
  US 20180227191A1
• Time in Patent Office: 735 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;

receiving user input including rebalancing parameters, the rebalancing parameters including simulation values for performing a rebalancing simulation;

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

generating, for each node, a token indicating a final simulation position of the node on the token ring; and

rebalancing the nodes using the generated tokens.

2. The method of claim 1, further comprising generating recommended simulation values based on the initial condition of the token ring.

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

4. 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.

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

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

7. 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;

receiving user input including rebalancing parameters, the rebalancing parameters including simulation values for performing a rebalancing simulation;

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

generating, for each node, a token indicating a final simulation position of the node on the token ring; and

rebalancing the nodes using the generated tokens.

8. The non-transitory computer-readable storage medium of claim 7, further comprising generating recommended simulation values based on the initial condition of the token ring.

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

10. The non-transitory computer-readable storage medium of claim 7, 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.

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

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

13. 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;

receiving user input including rebalancing parameters, the rebalancing parameters including simulation values for performing a rebalancing simulation;

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

generating, for each node, a token indicating a final simulation position of the node on the token ring; and

rebalancing the nodes using the generating tokens.

14. The system of claim 13, further comprising generating recommended simulation values based on the initial condition of the token ring.

15. The system of claim 13, 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.

16. The system of claim 13, wherein the rebalancing parameters include a desired level of balance of the token ring.

17. The system of claim 16, wherein the desired level of balance is indicated by a maximum transaction cost for the rebalancing.