Distributed load balancing for single entry-point systems

• US 7,395,335 B2
• Filed: 04/07/2005
• Issued: 07/01/2008
• Est. Priority Date: 02/06/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, John W., Link, Craig A., Barry, Charles H., Im, Hoon, Brown, Justin D.
• Primary Examiner(s): Cardone; Jason
• Assistant Examiner(s): HOSSAIN, TANIM M
• Application Number:
  US11/101,777
• Publication Number:
  US 20050198335A1
• Time in Patent Office: 1,181 Days
• Field of Search: 709/226, 709/227, 709/203
• US Class Current: 709/226
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1014 based on the content of a request

Abstract

A method and system for distributing work load in a cluster of at least two service resources. Depending upon the configuration, a service resource may be an individual process, such as a single instance of a computer game, or a node on which multiple processes are executing, such as a Server. Initial connection requests from new clients are directed to a single entry-point service resource in the cluster, called an intake. A separate intake is designated for each type of service provided by the cluster. The clients are processed in a group at the service resource currently designated as the intake to which clients initially connected, for the duration of the session. Based upon its loading, the current intake service resource determines that another service resource in the cluster should become a new intake for subsequent connection requests received from new clients. Selection of another service resource to become the new intake is based on the current work load of each resource in the cluster. All resources in the cluster are periodically informed of the resource for each service being provided that was last designated as the intake, and of the current load on each resource in the cluster. Subsequently, new clients requesting a service are directed to the newly designated intake for that service and processed on that resource for the duration of the session by those clients.

Claims

1. A method for determining which of a plurality of game services included in a cluster of nodes is to be an intake for a type of game by responding to a plurality of different types of incoming messages for load-balancing at each node included in the cluster of nodes, wherein the plurality of different types of incoming messages are received from a plurality of sources in the cluster, including from other nodes, comprising the steps of:

(a) at each node, determining a type of the incoming message that has been received;

(b) determining an appropriate response to be performed by a load-balancer running on the node, for each incoming message, based on one of a frequency, a content, and the type of the incoming message; and

(c) determining one of the incoming messages is an intake message which designates that one of the game services on the node is to be the intake, and thereafter designating the game service as the intake for the corresponding type of game, wherein as the intake, the game service receives all requests from any client wishing to participate in that type of game.

2. The method of claim 1, further comprising the step of employing information comprising each of the incoming messages to balance a load on a local node relative to loads on other nodes of the cluster.

3. The method of claim 1, wherein the plurality of different types of the incoming messages comprises a service message that is received from a game service on a local node, the service message including:

(a) an identification of the game service and its port on the local node;

(b) a number of clients being served by the game service on the local node; and

(c) an indication of whether additional clients will be served by the game service of the local node.

4. The method of claim 3, wherein the step of determining the appropriate response for the service message includes the step of updating information maintained by the local node for all games services on the local node to reflect information included in the service message.

5. The method of claim 1, wherein the plurality of different types of the incoming message comprises a data message that is received from a different node, the data message including:

(a) an identification of the different node;

(b) the total load on the different node;

(c) a list of game services served by the different node; and

(d) an indication of whether additional clients will be served by the different node.

6. The method of claim 5, wherein the step of determining the appropriate response for the data message includes the steps of:

(a) updating information maintained by a local node for all different node states on the cluster to reflect information included in the data message; and

(b) assuming that the different node has failed if the data message has not been received within a predefined interval by the local node.

7. The method of claim 1, wherein the intake message includes:

(a) an identification of the different node; and

(b) an identification of an intake for a game type that the different node has determined should be assigned to a node in the cluster other than the different node.

8. The method of claim 7, wherein the step of determining the appropriate response for the intake message further includes the steps of:

(a) updating information maintained by the local node for all intake locations on the cluster to reflect information included in the intake message;

(b) determining whether the local node has been assigned by the different node to take over the intake for the game type, and if so;

(c) determining whether the local node can provide the game service for the game type, and if so, enabling the game service on the local node to assume control as the intake for the game type and sending a status message indicative thereof to other nodes of the cluster;

else

(d) selecting a different game service on yet another node in the cluster to be the intake for the game type.

9. The method of claim 8, wherein the step of selecting the different game service includes the step of sending an intake message to other nodes of the cluster indicating that the game type is being assigned to the different game service on the node that was selected.

10. The method of claim 1, wherein the plurality of different types of the incoming message comprises a status message that is received from an intake node for a game type, the status message including:

(a) an identification of the intake node; and

(b) an identification of the game type.

11. The method of claim 10, wherein the step of determining the appropriate response for the status message includes the steps of:

(a) updating information maintained by a local node for all intake locations on the cluster to reflect information included in the status message;

(b) assuming that a reassignment of the intake has failed for the game type and assuming control of the intake for the game type if a status message for the game type has not been received within a predefined interval;

else

(c) if the status message has been received within the predefined interval, determining that reassignment of the intake for the game type was successful.

12. The method of claim 11, further comprising the steps of:

(a) determining if both the local node and another node are asserting control of the intake for the game type; and

if so, (b) applying an arbitrary rule to resolve which of the local node and the other node shall be a controller for the intake for the game type.

13. A system for determining which of a plurality of game services included in a cluster of nodes is to be an intake for a type of game by responding to a plurality of different types of incoming messages for load-balancing at each node included in the cluster of nodes, comprising:

(a) a memory in which a plurality of machine instructions are stored;

(b) at least one processor for implementing the cluster of nodes, each said at least one processor being coupled to the memory, said at least one processor executing the plurality of machine instructions, causing a plurality of functions to be implemented, said plurality of functions including;

(i) enabling the plurality of different types of incoming messages to be received from a plurality of sources in the cluster, including from other nodes;

(ii) determining a type of the incoming message that has been received at each node;

(iii) determining an appropriate response to be performed by a load-balancer running on the node, for each incoming message, based on one of a frequency, a content, and the type of the incoming message; and

(iv) upon determining one of the incoming messages is an intake message which designates that one of the game services on the node is to be the intake, designating the game service as the intake for the corresponding type of game, wherein as the intake, the game service receives all requests from any client wishing to participate in that type of game.

14. The system of claim 13, wherein execution of the plurality of machine instructions further causes information comprising each of the incoming messages to be employed to balance a load on a local node relative to loads on other nodes of the cluster.

15. The system of claim 13, wherein the plurality of different types of the incoming messages comprises:

(a) a service message that is received from a game service on a local node, said service message including an identification of the game service and its port on the local node, a number of clients being served by the game service on the local node, and an indication of whether additional clients will be served by the game service on the local node;

(b) a data message that is received from a different node, said data message including an identification of the different node, the total load on the different node, a list of game services served by the different node, and an indication of whether additional clients will be served by the different node;

(c) an intake message that is received from a different node, said intake message including an identification of the different node and an identification of an intake for a game type that the different node has determined should be assigned to a node in the cluster other than the different node; and

(d) a status message that is received from an intake node for a game type, said status message including an identification of the intake node and an identification of the game type.

16. The system of claim 15, wherein execution of the machine instructions further causes information maintained by the local node for all games services on the local node cluster to be updated to reflect information included in the service message.

17. The system of claim 15, wherein execution of the machine instructions further causes information maintained by the local node for all different node states on the cluster to be updated to reflect information included in the data message, wherein the machine instructions cause the local node to determine that the different node has failed if the data message has not been received from the different node by the local node within a predefined interval.

18. The system of claim 15, wherein execution of the machine instructions further causes:

(a) information maintained by the local node for all intake locations on the cluster to be updated to reflect information included in the intake message;

(b) a determination of whether the local node has been assigned by the different node to take over the intake for the game type; and

if so,

(c) a determination of whether the local node can provide the game service for the game type; and

if so,

(d) enabling the game service on the local node so that it assumes control as the intake for the game type and sends the status message indicative thereof to other nodes of the cluster;

otherwise,

(e) selecting a different game service on yet another node in the cluster to be the intake for the game type, and sending the intake message to other nodes of the cluster indicating that the game type is being assigned to the different game service on the node that was selected.

19. The system of claim 15, wherein execution of the machine instructions further causes:

(a) information maintained by a local node for all intake locations on the cluster to be updated to reflect information included in the status message;

(b) a determination that a reassignment of the intake has failed for the game type resulting in the local node assuming control of the intake for the game type, if the status message for the game type has not been received within a predefined interval; and

otherwise,

(c) a determination that reassignment of the intake for the game type was successful if the status message has been received within the predefined interval.

20. The system of claim 19, wherein execution of the machine instructions further causes an arbitrary rule to be applied, to resolve which of the local node and another node shall be a controller for the intake for the game type, if it is determined that both the local node and the other node are both asserting control of the intake for the game type.