Load balancing of network by maintaining in each computer information regarding current load on the computer and load on some other computers in the network

Claim 3

A method as claimed in claim 1, further comprising the step, when the first computer is overloaded, of using the information to determine a second computer that can accept extra load and transferring at least one task to the second computer.

Claim 4

A method as claimed in claim 1 further comprising the step, if a second computer higher up the tree, to which the first computer is logically linked, fails or is otherwise inoperative, of generating a new logical link to another computer in the network which has capacity for accepting new downward links.

Claim 5

A method as claimed in claim 1, wherein the step of maintaining includes: (i) using the periodic distribution of load information to determine whether or not the other computers to which the first computer is linked in the tree are operational, and (ii) marking the first computer, if one of the other computers lower in the tree to which the first computer is linked is not operational, as having capacity to accept new downward links.

Claim 6

A method as claimed in claim 1, further comprising the step of randomly permuting entries in the information, the entries relating to computers which have the same load and number of links separation from the computer, prior to the step of maintaining by causing the computer periodically to distribute.

Claim 7

A method as claimed in claim 1, further comprising the steps, if an entry corresponding to the computer appears first in its own sorted information, of: attaching a counter to the entry; initializing the counter to negative value of a spare load capacity of the computer; incrementing the counter, if that entry is still first, whenever the information is distributed; and removing that entry from the information, if the counter becomes positive; whereby a probability that the same entry will appear first in the information stored in different computers is reduced.

Claim 8

A method as claimed in claim 1, wherein: the step of causing periodically to distribute is executed according to a first period which includes a second period of periodic distribution of the information to the one computer higher up the tree; and the second period depends on a rate at which new tasks are created in the computer.

Claim 9

A method as claimed in claim 7, wherein, in the step of causing, the first period depends on a rate at which new tasks are created in the other computers to which the first computer is logically linked in the tree structure.

Claim 10

A method as claimed in claim 1, wherein, in the step of causing periodically to distribute, the information is distributed to one of the other computers which is lower in the tree in response to receipt by the first computer of the similar information from the other computer lower in the tree.

Claim 11

A method of operating a network of computers, comprising the step of: operating each computer of the network using the method as claimed in claim 1.

Claim 12

A method as claimed in claim 10, wherein the step of generating logical links includes assigning a rank to each computer, no two computers being assigned the same rank, each computer being linked to one computer of lower rank and a number of computers of higher rank to form the tree structure.

Claim 13

A computer comprising: means for operating in a network of similar such computers, means for logically linking the computer to similar such computers in a tree structure network, and for identifying the similar such computers; means for storing information regarding a load on the computer and loads on at least some of the similar such computers in the network; means for sending said information to the similar such computers to which the computer is logically linked; means for receiving similar information from said similar such computers to which the computer is logically linked, and for updating the stored information in accordance therewith; and means for selecting one of the similar such computers in the network having spare load capacity from said information, and for transferring tasks to the selected computer: wherein the means for storing includes means for maintaining information stored in the first computer, including a number of entries, each entry containing information regarding: (i) a load on one of the other computers in the network, (ii) a number of links in the tree separating that other computer from the first computer, and (iii) the one of the other computers, which are linked to the first computer, from which the entry was last received; and wherein, the computer further comprises means, operable when the first computer receives the similar information from one of the other computers to which it is linked, for: (a) incrementing a number of links value in each entry of the received similar information by one; (b) deleting entries in the received information which originated from the other computer; (c) deleting entries in the information already stored in the first computer which were received from the other computer; (d) merging the received similar information with the information already stored in the first computer; and (e) sorting the merged information in ascending order of load, entries with equal load being sorted in ascending order of number of links separation from the first computer.

Claim 14

A computer comprising: means for operating in a network of similar such computers, means for logically linking the computer to similar such computers in a tree structure network, and for identifying the similar such computers; means for storing information regarding a load on the computer and loads on at least some of the similar such computers in the network; means for sending said information to the similar such computers to which the computer is logically linked; means for receiving similar information from said similar such computers to which the computer is logically linked, and for updating the stored information in accordance therewith; and means for selecting one of the similar such computers in the network having spare load capacity from said information, and for transferring tasks to the selected computer: wherein the means for storing includes means for maintaining information stored in the first computer, including a number of entries, each entry containing information regarding: (i) a load on one of the other computers in the network, (ii) a number of links in the tree separating that other computer from the first computer, and (iii) the one of the other computers, which are linked to the first computer, from which the entry was last received; and wherein, the computer further comprises means, operable when the first computer receives the similar information from one of the other computers to which it is linked, for: (a) incrementing a number of links value in each entry of the received similar information by one; (b) deleting entries in the received information which originated from the other computer; (c) deleting entries in the information already stored in the first computer which were received from the other computer; (d) merging the received similar information with the information already stored in the first computer; and (e) sorting the merged information in ascending order of load, entries with equal load being sorted in ascending order of number of links separation from the first computer.

Claim 15

A computer as claimed in claim 12, further comprising: means for accessing a stored list of all the computers in the network; means for selecting a computer from the list as a candidate neighboring computer for linking in the tree structure; means for sending a message to the selected computer indicating a link request; means for establishing a logical link with the selected computer by updating the means for identifying if a positive response from the selected computer is received; means for receiving a message from one of the similar such computers indicating that a link is requested; and means for determining, on receipt of such a link request message, whether or not there is capacity for establishing a downward link, for sending a positive response to the one similar such computer which sent the link request message if there is such capacity and updating the identifying means accordingly.

Claim 16

A network of computers comprising a plurality of computers as claimed in claim 13.

Claim 17

A network of computers comprising a plurality of computers as claimed in claim 12.

Claim 18

A computer as claimed in claim 12, further comprising means, operable when the first computer is overloaded, for using the information to determine a second computer that can accept extra load and transferring at least one task to the second computer.

Claim 19

A computer as claimed in claim 12 further comprising means, operable when a second computer higher up the tree, to which the first computer is logically linked, fails or is otherwise inoperative, for generating a new logical link to another computer in the network which has capacity for accepting new downward links.

Claim 20

A computer as claimed in claim 12, wherein the means for storing includes: (i) means for using the periodic distribution of load information to determine whether or not the other computers to which the first computer is linked in the tree are operational, and (ii) means for marking the first computer, if one of the other computers lower in the tree to which the first computer is linked is not operational, as having capacity to accept new downward links.

Claim 21

A computer as claimed in claim 12 further comprising means for randomly permuting entries in the information, the entries relating to computers which have the same load and number of links separation from the computer.

Claim 22

A computer as claimed in claim 12, further comprising means, operable when an entry corresponding to the computer appears first in its own sorted information, for: attaching a counter to the entry; initializing the counter to negative value of a spare load capacity of the computer; incrementing the counter, if that entry is still first, whenever the information is distributed; and removing that entry from the information, if the counter becomes positive; whereby a probability that the same entry will appear first in the information stored in different computers is reduced.

Claim 23

A computer as claimed in claim 12, wherein: the means for causing periodically to distribute is operable according to a first period which includes a second period of periodic distribution of the information to the one computer higher up the tree; and the second period depends on a rate at which new tasks are created in the computer.

Claim 24

A computer as claimed in claim 21, wherein, in the means for causing, the first period depends on a rate at which new tasks are created in the other computers to which the first computer is logically linked in the tree structure.

Claim 25

A computer as claimed in claim 12, wherein the means for causing periodically to distribute includes means for distributing the information to one of the other computers which is lower in the tree in response to receipt by the first computer of the similar information from the other computer lower in the tree.

Claim 26

A network of computers, comprising a plurality of computers as claimed in claim 12.

Claim 27

A network as claimed in claim 24, wherein, for each computer, the means for generating logical links includes means for assigning a rank to each computer, no two computers being assigned the same rank, each computer being linked to one computer of lower rank and a number of computers of higher rank to form the tree structure.

Claim 28

A computer program product, for use with a computer, comprising: a recording medium; means, recorded on the recording medium, for directing the computer to operate in a network of similar such computers, means, recorded on the recording medium, for directing the computer to logically link the computer to similar such computers in a tree structure network, and for identifying the similar such computers; means, recorded on the recording medium, for directing the computer to store information regarding a load on the computer and loads on at least some of the similar such computers in the network; means, recorded on the recording medium, for directing the computer to send said information to the similar such computers to which the computer is logically linked; means, recorded on the recording medium, for directing the computer to receive similar information from said similar such computers to which the computer is logically linked, and for directing the computer to update the stored information in accordance therewith; and means, recorded on the recording medium, for directing the computer to select one of the similar such computers in the network having spare load capacity from said information, and for transferring tasks to the selected computer; wherein the means for directing to store includes means, recorded on the recording medium, for directing the computer to maintain information stored in the first computer, including a number of entries, each entry containing information regarding: (i) a load on one of the other computers in the network, (ii) a number of links in the tree separating that other computer from the first computer, and (iii) the one of the other computers, which are linked to the first computer, from which the entry was last received; and wherein, the computer further comprises means, recorded on the recording medium, operable when the first computer receives the similar information from one of the other computers to which it is linked, for directing the computer: (a) to increment a number of links value in each entry of the received similar information by one; (b) to delete entries in the received information which originated from the other computer; (c) to delete entries in the information already stored in the first computer which were received from the other computer; (d) to merge the received similar information with the information already stored in the first computer; and (e) to sort the merged information in ascending order of load, entries with equal load being sorted in ascending order of number of links separation.

Claim 29

A computer program product, for use with a computer, comprising: a recording medium; means, recorded on the recording medium, for directing the computer to operate in a network of similar such computers, means, recorded on the recording medium, for directing the computer to logically link the computer to similar such computers in a tree structure network, and for identifying the similar such computers; means, recorded on the recording medium, for directing the computer to store information regarding a load on the computer and loads on at least some of the similar such computers in the network; means, recorded on the recording medium, for directing the computer to send said information to the similar such computers to which the computer is logically linked; means, recorded on the recording medium, for directing the computer to receive similar information from said similar such computers to which the computer is logically linked, and for directing the computer to update the stored information in accordance therewith; and means, recorded on the recording medium, for directing the computer to select one of the similar such computers in the network having spare load capacity from said information, and for transferring tasks to the selected computer; wherein the means for directing to store includes means, recorded on the recording medium, for directing the computer to maintain information stored in the first computer, including a number of entries, each entry containing information regarding: (i) a load on one of the other computers in the network, (ii) a number of links in the tree separating that other computer from the first computer, and (iii) the one of the other computers, which are linked to the first computer, from which the entry was last received; and wherein, the computer further comprises means, recorded on the recording medium, operable when the first computer receives the similar information from one of the other computers to which it is linked, for directing the computer: (a) to increment a number of links value in each entry of the received similar information by one; (b) to delete entries in the received information which originated from the other computer; (c) to delete entries in the information already stored in the first computer which were received from the other computer; (d) to merge the received similar information with the information already stored in the first computer; and (e) to sort the merged information in ascending order of load, entries with equal load being sorted in ascending order of number of links separation.

Claim 30

A computer program product as claimed in claim 26, further comprising: means, recorded on the recording medium, for directing the computer to access a stored list of all the computers in the network; means, recorded on the recording medium, for directing the computer to select a computer from the list as a candidate neighboring computer for linking in the tree structure; means, recorded on the recording medium, for directing the computer to send a message to the selected computer indicating a link request; means, recorded on the recording medium, for directing the computer to establish a logical link with the selected computer by updating the means for directing to identify if a positive response from the selected computer is received; means, recorded on the recording medium, for directing the computer to receive a message from one of the similar such computers indicating that a link is requested; and means, recorded on the recording medium, for directing the computer to determine, on receipt of such a link request message, whether or not there is capacity for establishing a downward link, for directing the computer to send a positive response to the one similar such computer which sent the link request message if there is such capacity, and for directing the computer to update the identifying means accordingly.

Claim 31

A computer program product as claimed in claim 26, further comprising means, recorded on the recording medium, operable when the first computer is overloaded, for directing the computer to use the information to determine a second computer that can accept extra load and for directing the computer to transfer at least one task to the second computer.

Claim 32

A computer program product as claimed in claim 26 further comprising means, recored on the recording medium, operable when a second computer higher up the tree, to which the first computer is logically linked, fails or is otherwise inoperative, for directing the computer to generate a new logical link to another computer in the network which has capacity for accepting new downward links.

Claim 33

A computer program product as claimed in claim 26, wherein the means for directing to store includes: (i) means, recorded on the recording medium, for directing the computer to use the periodic distribution of load information to determine whether or not the other computers to which the first computer is linked in the tree are operational, and (ii) means, recorded on the recording medium, for directing the computer to mark the first computer, if one of the other computers lower in the tree to which the first computer is linked is not operational, as having capacity to accept new downward links.

Claim 34

A computer program product as claimed in claim 26 further comprising means, recorded on the recording medium, for directing the computer to randomly permute entries in the information, the entries relating to computers which have the same load and number of links separation from the computer.

Claim 35

A computer program product as claimed in claim 26, further comprising means, recorded on the recording medium, operable when an entry corresponding to the computer appears first in its own sorted information, for directing the computer: to attach a counter to the entry; to initialize the counter to negative value of a spare load capacity of the computer; to increment the counter, if that entry is still first, whenever the information is distributed; and to remove that entry from the information, if the counter becomes positive; whereby a probability that the same entry will appear first in the information stored in different computers is reduced.

Claim 36

A computer program product as claimed in claim 26, wherein: the means for directing to cause periodically to distribute is operable according to a first period which includes a second period of periodic distribution of the information to the one computer higher up the tree; and the second period depends on a rate at which new tasks are created in the computer.

Claim 37

A computer program product as claimed in claim 33, wherein, in the means for directing to cause, the first period depends on a rate at which new tasks are created in the other computers to which the first computer is logically linked in the tree structure.

Claim 38

A computer program product as claimed in claim 26, wherein the means for directing to cause periodically to distribute, includes means, recorded on the recording medium, for directing the computer to distribute the information to one of the other computers which is lower in the tree in response to receipt by the first computer of the similar information from the other computer lower in the tree.