EP0540151A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method of operating a computer in a network
Assignee: International Business Machines Corp
•
Filing: 1992-09-08
•
Granted: —
•
Expires: 2012-09-08
Abstract
Abstract A method is described of operating a computer in a network of computers using an improved load balancing technique, the method comprising: generating logical links 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; maintaining in the computer stored information 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, to receive from said 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.
Inventors
- 👤 David Allon
- 👤 Moshe Bach
- 👤 Yosef Moatti
- 👤 Abraham Teperman
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-31 16:44
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5083; G06F9/5088
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
135 words
A method of operating a computer in a network of computers, the method comprising: generating logical links 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; and maintaining in the computer stored information 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, to receive from said computers similar such information and to update its own information in accordance therewith, so that the information can be used to determine computers in the network that can accept extra load.
Claim 2
Dependent Claim
37 words
A method as claimed in claim 1 comprising the 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.
Claim 3
Dependent Claim
49 words
A method as claimed in claim 1 or claim 2 comprising, if the computer higher up the tree, to which the computer is logically linked fails or is otherwise inoperative, generating a new logical link to another computer in the network which has capacity for accepting new downward links.
Claim 4
Independent Claim
66 words
A method as claimed in any preceding claim wherein the periodic distribution of load information is used by the computer to determine whether or not the computers to which it is linked in the tree, are operational, the computer being marked, if one of the computers lower in the tree to which it is linked is not operational, as having capacity to accept new downward links.
Claim 5
Independent Claim
184 words
A method as claimed in any preceding claim wherein the information stored in the computer contains a number of entries, each entry containing information regarding (i) the load on one of the computers in the network, (ii) the number of links in the tree separating that other computer from the computer, and (iii) the one of the computers, which are linked to the computer, from which the entry was last received: and wherein when the computer receives the similar information from a computer to which it is linked the following steps are performed: (a) the number of links value in each entry of the received information is incremented by one; (b) entries in the received information which originated from the computer are deleted; (c) entries in the information already stored in the computer which were received from the sending computer are deleted; (d) the received information is merged with the information already stored in the computer; (e) the merged information is sorted in ascending order of load, entries with equal load being sorted in ascending order of number of links separation from the computer.
Claim 6
Dependent Claim
36 words
A method as claimed in claim 5 wherein before each distribution of information entries in the information relating to computers which have the same load and number of links separation from the computer are randomly permuted.
Claim 7
Dependent Claim
92 words
A method as claimed in claim 5 or claim 6 wherein if an entry corresponding to the computer appears first in its own sorted information a counter is attached to the entry and initialised to negative value of the spare load capacity of the computer, the counter being incremented, if that entry is still first, whenever the information is distributed, and if the counter becomes positive that entry is removed from the information, whereby the probability that the same entry will appear first in the information stored in different computers is reduced.
Claim 8
Independent Claim
38 words
A method as claimed in any preceding claim wherein the period of the periodic distribution of the information to a computer higher up the tree depends on the rate at which new tasks are created in the computer
Claim 9
Dependent Claim
38 words
A method as claimed in claim 8 wherein the period of the periodic distribution depends on the rate at which new tasks are created in the computers to which the computer is logically linked in the tree structure.
Claim 10
Independent Claim
41 words
A method as claimed in any preceding claim wherein the distribution of the information to a computer lower in the tree takes place in response to receipt by the computer of the similar information from the computer lower in the tree.
Claim 11
Independent Claim
21 words
A method of operating a network of computers, comprising operating each computer using a method as claimed in any preceding claim.
Claim 12
Dependent Claim
54 words
A method as claimed in claim 11 wherein the generation of the logical links is achieved by 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
Dependent Claim
116 words
A computer capable of operating in a network of similar such computers, the computer comprising: means identifying computers in the network to which the computer is logically linked in a tree structure; means for storing information regarding the load on the computer and at least some of the other computers in the network; means for sending said information to the computers to which the computer is logically linked; means for receiving similar information from said computers to which the computer is logically linked and updating the stored information in accordance therewith; means for selecting one of the other computers in the network having spare load capacity from said information and transferring tasks to the selected computer.
Claim 14
Dependent Claim
137 words
A computer as claimed in claim 13 including: means for accessing a stored list of all the computers in the network; means for selecting a computer from this list as a candidate neighbouring 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 identifying means if a positive response from the selected computer is received; means from receiving messages from other computers indicating that a link is requested; means for determining, on receipt of such a link request message, whether or not there is capacity for establishing a downward link and sending a positive response to the sender of the link request message if there is such capacity and updating the identifying means accordingly.
Claim 15
Dependent Claim
17 words
A network of computers comprising a plurality of computers as claimed in claim 13 or claim 14.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.