System for on-line service in which gateway computer uses service map which includes loading condition of servers broadcasted by application servers for load balancing

• US 5,774,668 A
• Filed: 06/07/1995
• Issued: 06/30/1998
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Griffin, William J., Choquier, Philippe, Peyroux, Jean-Francios
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Kim, Ki S.
• Application Number:
  US08/472,807
• Time in Patent Office: 1,119 Days
• Field of Search: 395/187, 395/200, 395/650, 395/307, 395/200.53, 395/200.33, 395/200.37, 395/200.57, 395/200.48, 395/200.79, 395/675, 370/85, 370/480, 364/238, 364/281
• US Class Current: 709/223
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: H04L 51/226 Delivery according to priorities
• CPC Class Codes: H04L 67/01 Protocols
• 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/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

An on-line services network includes application servers and Gateway microcomputers that are interconnected by a LAN. The Gateway microcomputers receive service requests which are transmitted over a WAN from client microcomputers operated by end users. Upon receiving a request to open a service, the Gateway microcomputers access a periodically-updated service map to locate the replicated application servers that are currently running the corresponding service application, and then apply a load balancing method (using server load data contained within the service map) to select an application server that has a relatively low processing load. A communications protocol between the client and Gateway microcomputers enables users to access multiple services simultaneously. A hot redirection technique allows a user service session to be transferred from one application server to another (replicated) application server without termination of the service session. Various mechanisms are provided for efficiently reallocating application servers to different on-line services, and for allowing additional servers to be efficiently added to the network.

Claims

1. A data center for providing on-line service to end users who connect to the data center from client computers that run client applications, comprising:

a plurality of application servers interconnected by a local area network, each application server running at least one service application that implements an on-line service, different groups of said application servers running different service applications to provide different on-line services, application servers which run like service applications forming service groups; and

a plurality of gateway computers connected to said application servers by said local area network and connected to the client computers by a wide area network, each gateway computer locally storing a respective copy of a service map that includes a mapping of application servers to service groups, said service map automatically updated by said plurality of application servers, each gateway computer programmed to receive service requests from client computers and to route said service requests to application servers running corresponding service applications, the gateway computers further programmed to establish and maintain bi-directional data connections between the client computers and said application servers over the local area network based on entries within the service map, the data connections corresponding to user service sessions.

2. The data center according to claim 1, each gateway computer further programmed to, upon receiving a service request from a client computer to open a user-specified service, doing each of:

(a) identifying all application servers that fall within a service group which corresponds to said user-specified service,

(b) determining respective processing loads for each application server identified in step (a), and

(c) based on processing loads determined in step (b), selecting an application server from said service group to process said request to open said user-specified service.

3. The data center according to claim 2, wherein step (b) comprises accessing said service map, said service map indicating processing loads for substantially all of said application servers, including application servers of multiple different service groups, said service map automatically updated by said application servers to reflect changes in processing loads.

4. The data center according to claim 2, wherein step (c) comprises selecting an application server with a greatest available CPU processing power.

5. The data center according to claim 2, wherein step (c) comprises selecting an application server such that a probability of selection is proportional to an available CPU processing power.

6. The data center according to claim 1, each gateway computer further programmed to, upon receiving a service request from a client computer to open a user-specified service, doing each of:

(a) calling a service-specific locator to identify a unique one of said application servers that corresponds to said service request, and

(b) routing said service request to the application server identified in step (a).

7. The data center according to claim 6, wherein step (a) comprises using a user identifier to identify one of a plurality of MAIL servers.

8. The data center according to claim 6, wherein step (a) comprises using a user identifier and a service identifier to identify said unique application server.

9. The data center according to claim 6, wherein step (a) comprises using a conference locator to identify one of a plurality of CHAT servers.

10. The data center according to claim 9, wherein step (a) comprises identifying a CHAT server which is assigned to a user-specified CHAT conference.

11. The data center according to claim 1, further comprising a service map dispatcher connected to said local area network, said service map dispatcher programmed to receive information from said application servers and to generate said service map therefrom, said service map dispatcher further programmed to periodically broadcast an updated version of said service map to said gateway computers.

12. The data center according to claim 11, wherein said service map contains a mapping of application servers to service applications, said service map thereby enabling said gateway computers to identify application servers to handle specific service requests.

13. The data center according to claim 11, wherein said service map contains, for each of said application servers, a client count value that indicates a current number of service sessions.

14. The data center according to claim 11, wherein said service map contains, for each of said application servers, a processing load value which indicates a current application server processing load.

15. The data center according to claim 14, wherein said service map additionally contains, for each of said application servers, a CPU index value which indicates an overall application server processing power.

16. The data center according to claim 1, each gateway computer further programmed to receive a multiplexed data stream from a client computer, said multiplexed data stream containing alternating portions of different messages, at least two of said different messages addressed to different services, each gateway computer further programmed to demultiplex said multiplexed data stream to reconstruct said messages, and to route reconstructed messages to corresponding application servers, said gateway computers thereby permitting a client computer to concurrently communicate with multiple application servers so that an end user can simultaneously access multiple on-line services via a single gateway computer.

17. The data center according to claim 16, wherein said portions of different messages are varied in size so as to allocate different amounts of wide area network bandwidth to different services.

18. The data center according to claim 1, each gateway computer further programmed to receive multiple data streams from said application servers and to multiplex said data streams for transmission to a client computer, each of said data streams generated by a different application server and corresponding to a different on-line service, said gateways thereby allowing an end user to concurrently receive data from multiple on-line services.

19. The data center according to claim 18, wherein each gateway multiplexes said data streams by combining variable-length portions of said data streams, lengths of said variable-length portions being varied from on-line service to on-line service to allocate different amounts of bandwidth to different services.

20. The data center according to claim 1, further comprising a load monitoring computer programmed to monitor loads of said service groups, and to add an application server to a service group when a load on said service group exceeds a predetermined threshold.

21. The data center according to claim 1, wherein at least one of said application servers comprises a hard drive having stored thereon a plurality of dynamically loadable service modules, each dynamically loadable service module comprising executable code of a respective service application, said dynamically loadable service modules enabling an application server to be automatically allocated from one service to another, the at least one application server further including code for transferring a user service session to another application server when the application server is reallocated.

22. The data center according to claim 21, wherein the at least one application server runs a process that dynamically loads and unloads different executable service modules to activate and deactivate different service applications.

23. The data center according to claim 22, wherein said process is a multi-threaded process.

24. The data center according to claim 1, wherein each application server of at least one service group locally stores a replicated copy of on-line service data, said on-line service data provided to end users of an on-line service that corresponds to said service group.

25. The data center according to claim 1, further comprising a client microcomputer configured to access said on-line services, the client microcomputer comprising:

a plurality of client applications, each client application configured to communicate with a corresponding server application of the data center to thereby implement an on-line service, each client application generating an outgoing data stream to a corresponding server application and receiving an incoming data stream from said corresponding server applications; and

a communications program configured to multiplex multiple of said outgoing data streams for transmission to the data center, and configured to separate multiplexed incoming data streams and route said incoming data streams to corresponding of said client applications, said communications program thereby enabling a user of the data center to concurrently access multiple on-line services.

26. The client microcomputer according to claim 25, said communications program further configured to multiplex said outgoing data streams by combining variable-length data segments from alternating of said outgoing data streams, lengths of said variable-length segments assigned by said communications program according to throughput priorities of corresponding on-line services.

27. The client microcomputer according to claim 25, said communications program further configured to combine said outgoing data streams within packets, each packet containing segments from alternating of said outgoing data streams.

28. The client microcomputer according to claim 27, wherein said segments are variable-length segments, and wherein lengths of said segments are assigned on a per-client application basis.

29. The client microcomputer according to claim 27, said communications program further configured to implement a sliding window flow control protocol.

30. The client microcomputer according to claim 27, said communications program further configured to implement CCITT CRC-32 error correction.

31. In a computer network which comprises a gateway computer that connects a wide area network to a local area network, a method of processing service requests from users so as to balance a processing load among application servers of the network, the application servers interconnected by the local area network, the method comprising the steps of:

receiving a service request at a host data center, said service request transmitted from client computer to said host data center over said wide area network, said service request corresponding to a service;

identifying a group of application servers that are assigned to said service, said step of identifying comprising accessing a service map stored by said gateway computer, said service map automatically updated by said application servers;

determining processing loads of each application server in said group;

based on said processing loads, selecting an application server from said group to process said service request; and

routing said service request to a selected application server.

32. The method according to claim 31, wherein said step of selecting comprises calculating an available CPU processing power for each application server in said group.

33. The method according to claim 32, wherein said step of selecting further comprises selecting an application server having the greatest available CPU processing power.

34. The method according to claim 32, wherein a probability of selection of an application server is proportional to the available CPU processing power for said application server.

35. The method according to claim 32, wherein said available CPU processing power is calculated as a function of a CPU load value and a CPU index value for each respective application server of said group, said CPU load values indicating loads on respective application servers caused by service requests, said CPU index values indicating overall processing powers of respective application servers.

36. The method according to claim 31, wherein said step of determining comprises accessing said service map, said service map indicating processing loads for said application servers.

37. The method according to claim 36, wherein said service map is automatically updated on a substantially periodic basis to reflect changes in application server loads.

38. The method according to claim 36, wherein said service map is automatically updated on an average of at least once per minute to reflect changes in application server loads.

39. The method according to claim 37, wherein said service map is broadcasted to a plurality of service request routers of said host data center on a substantially periodic basis.

40. The method according to claim 31, wherein said service map includes a mapping of application servers to services for substantially every application server of said host data center.

41. The method according to claim 31, wherein said step of receiving, identifying, determining and selecting are performed by said gateway computer.

42. The method according to claim 31, wherein said service request comprises a request to open service.

43. The method of claim 31, further comprising the steps of:

generating a plurality of data streams between said client computer and said gateway computer, each data stream corresponding to a respective service session, each service session handled by a different application server; and

multiplexing said data stream for concurrent transmission over said wide area network;

the method thereby enabling concurrent use of multiple services by a single user.

44. The method according to claim 43, further comprising, at said gateway computer, doing each of:

demultiplexing multiplexed data streams generated by said client computer, and

forwarding demultiplexed data streams to corresponding application servers.

45. The method according to claim 43, wherein said step of multiplexing comprises allocating different quantities of wide area network bandwidth to different data streams of said plurality of data streams to thereby accommodate for differing throughput priorities of different services.

46. The method according to claim 43, wherein said step of multiplexing comprises generating a packet for transmission over said wide area network, said packet containing segments of each data stream of said plurality of data streams.

47. The method according to claim 46, wherein said segments are variable length segments, and wherein lengths of said segments are varied from data stream to data stream in order to allocate differing quantities of available wide area network bandwidth to different services.

48. The method according to claim 47, wherein said lengths are varied in proportion to predetermined throughput priorities of corresponding services.

49. The method according to claim 47, wherein said lengths are varied in proportion to user-specified throughput priorities of corresponding services.

50. A gateway computer, comprising:

a first network interface for communicating with client computers;

second network interface for communicating with a plurality of servers;

a memory, said memory containing load data for said plurality of servers, said load data updated periodically such that said load data indicates current loads for said plurality of servers, said load data indicating, for each server of said plurality of servers, an available processing power for processing requests from client computers; and

a CPU, said CPU programmed to each of;

(a) receive a request from a client computer,

(b) in response to said request, access said load data to identify a server of said plurality of servers that is lightly load, and

(c) route said request to said server identified in step (b).

51. The gateway computer according to claim 50, wherein said first network interface is configured for communications over a wide area network, and wherein said second network interface is configured for communications over a local area network.

52. The gateway computer according to claim 50, wherein said memory further comprises application mapping data, said application mapping data identifying server applications running on different servers of said plurality of servers.

53. The gateway computer according to claim 52, said CPU further programmed to, upon receiving a request which identifies an application, accessing said application mapping data to identify a group of servers of said plurality of servers that is running said application.

54. The gateway computer according to claim 50, said CPU further programmed to:

(d) receive respective data streams from at least two servers of said plurality of servers, and

(e) multiplex said data streams for transmission to said client computer.

55. A method of disseminating load data of a plurality of servers to a plurality of routing computers that route client requests to the servers based on the load data received from a dispatcher entity, the servers, the routing computers and the dispatcher entity interconnected by a local area network, the method comprising the steps of:

(a) at each server of the plurality of servers, automatically determining a current load on the respective server, and automatically transmitting load data that reflects the current load to the dispatcher entity of the local area network; and

(b) at the dispatcher entity, automatically compiling the load data received from each of the plurality of servers into a map, and broadcasting the map on the local area network to allow the routing computers to obtain the load data of the plurality of servers.

56. The method of claim 55, wherein step (a) comprises determining an available processing power of each server for handling client requests.

57. The method of claim 55, wherein step (a) comprises, at each server of the plurality of servers, sending service allocation data to the dispatcher entity, the service allocation data indicating at least one service to which the respective server is currently allocated, and wherein step (b) comprises broadcasting the allocation data of the plurality of servers from the dispatcher entity on the local area network.

59. The method of claim 55, wherein steps (a) and (b) are performed periodically.

58. A data center for providing on-line services to end users who connect to the data center from client computers that run client applications, comprising:

a plurality of application servers interconnected by a local area network, each application server running at least one service application that implements an on-line service, different groups of said application servers running different service applications to provide different on-line services, application servers which run like service applications forming service groups; and

a plurality of gateway computers connected to said application servers by said local area network and connected to the client computers by a wide area network, each gateway computer programmed to receive service requests from client computers and to route said service requests to application servers running corresponding service applications, the gateway computers further programmed to establish and maintain bi-directional data connections between the client computers and said application servers over the local area network based on entries within the service map, the data connections corresponding to user service sessions, each gateway computer further programmed to, upon a service request from a client computer to open a user-specified service, doing each of;

(a) identifying all application servers that fall within a service group which correspond to said user-specified service,

(b) determining respective processing loads for each application server identified in step (a), the step of determining comprising accessing a service map, said service map indicating processing loads for substantially all of said application servers, including application servers of multiple different service groups, said service map automatically updated by said application servers to reflect changes in processing loads, and

(c) based on processing loads determined in step (b), selecting an application server from said service group to process said request to open said user-specified service.