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
First Claim
1. A method of operating a first computer in a network of computers, the method comprising the steps of:
- generating logical links between the first computer and other computers in the network so that a tree structure is formed, the logical links including a link to one of the other computers higher up the tree and links to a number of computers lower down the tree; and
maintaining in the first computer stored information regarding a current load on the first computer and a load on at least some of the other computers in the network, the step of maintaining including causing the first computer;
(i) periodically to distribute the information to the computers to which it is logically linked,(ii) to receive from said other computers similar such information, and(iii) to update its own information in accordance therewith, so that the information can be used to determine ones of the other computers in the network that can accept extra load;
wherein the step of maintaining includes 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 method further comprises the steps, when the first computer receives the similar information from on one of the other computers to which it is linked, of;
(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.
0 Assignments
0 Petitions
Accused Products
Abstract
A method is described of operating a computer in a network of computers using an improved load balancing technique. Logical links are generated between the computer and other computers in the network so that a tree structure is formed, the computer being logically linked to one computer higher up the tree and a number of computers lower down the tree. Stored information is maintained in the computer regarding the current load on the computer and the load on at least some of the other computers in the network by causing the computer periodically to distribute the information to the computers to which it is logically linked, and to receive from the computers similar such information and to update its own information in accordance therewith, so that the information can be used to determine a computer in the network that can accept extra load. A sender-initiated embodiment of the invention includes the further step of, when the computer is overloaded, using the information to determine a computer that can accept extra load and transferring at least one task to that computer. The load balancing technique is scalable, fault tolerant, flexible and supports clustering, thus making it suitable for use in networks having very large numbers of computers.
-
Citations
35 Claims
-
1. A method of operating a first computer in a network of computers, the method comprising the steps of:
-
generating logical links between the first computer and other computers in the network so that a tree structure is formed, the logical links including a link to one of the other computers higher up the tree and links to a number of computers lower down the tree; and maintaining in the first computer stored information regarding a current load on the first computer and a load on at least some of the other computers in the network, the step of maintaining including causing the first computer; (i) periodically to distribute the information to the computers to which it is logically linked, (ii) to receive from said other computers similar such information, and (iii) to update its own information in accordance therewith, so that the information can be used to determine ones of the other computers in the network that can accept extra load; wherein the step of maintaining includes 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 method further comprises the steps, when the first computer receives the similar information from on one of the other computers to which it is linked, of; (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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. 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. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35)
-
Specification