Loading balancing across servers in a computer network

• US 6,351,775 B1
• Filed: 05/30/1997
• Issued: 02/26/2002
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: SAP SE
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip Shi-Lung
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/866,461
• Time in Patent Office: 1,733 Days
• Field of Search: 709/242, 709/239, 709/240, 709/241, 709/238, 370/237, 370/400
• US Class Current: 709/238
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1025 Dynamic adaptation of the criteria on which the server selection is based
• CPC Class Codes: H04L 67/1038 Load balancing arrangements to avoid a single path through a load balancer

Abstract

A dynamic routing of object requests among a collection or cluster of servers factors the caching efficiency of the servers and the load balance or just the load balance. The routing information on server location can be dynamically updated by piggybacking meta information with the request response. To improve the cache hit at the server, the server selection factors the identifier (e.g. URL) of the object requested. A partitioning method can map object identifiers into classes; and requester nodes maintain a server assignment table to map each class into a server selection. The class-to-server assignment table can change dynamically as the workload varies and also factors the server capacity. The requester node need only be informed on an “on-demand” basis on the dynamic change of the class-to-server assignment (and thus reduce communication traffic). In the Internet, the collection of servers can be either a proxy or Web server cluster and can include a DNS and/or TCP-router. The PICS protocol can be used by the server to provide the meta information on the “new” class-to-server mapping when a request is directed to a server based on an invalid or obsolete class-to-server mapping. DNS based routing for load balancing of a server cluster can also benefit. By piggybacking meta data with the returned object to reassign the requester to another server for future requests, adverse effects of the TTL on the load balance are overcome without increasing traffic.

Claims

1. A method for communicating routing information between requester and server nodes, said server nodes serving requests for objects, the method comprising the steps of:

piggybacking meta information with a requested object; and

dynamically updating the routing information for a server assignment according to the meta information.

2. The method of claim 1, further comprising the steps of:

balancing a load among the server nodes, wherein said step of balancing the load comprises optimizing cache hits for the requested object.

3. The method of claim 2, further comprising the steps of:

mapping an object identifier to a class; and

assigning a server based on the class and a class-to-server assignment table.

4. The method of claim 3, said mapping step further comprising the step of mapping the object identifier into classes or hash classes via a hash table.

5. The method of claim 2, wherein a server selection method at the requester is provided to reduce assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requestor node for the server selection, including the steps of;

mapping an object identifier for each object request to a class, wherein if no valid server assignment is available in the class-server assignment table, then issuing a mapping request to an arbitrator; and

in response to said mapping step, updating the class-server assignment table.

6. The method of claim 2, wherein a server selection method at the requester is provided for reducing assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping an object identifier for each object request to a class, wherein if no valid server assignment is available in the class-server assignment table, then selecting a server; and

updating the class-server assignment table with a selected server, in response to said selecting step.

7. The method of claim 2, wherein said step of balancing the load, further comprises the step of assigning classes to server nodes as a function of the load associated with each class.

8. The method of claim 2, wherein said step of balancing the load, further comprises the step of incrementally reassigning classes to servers.

9. The method of claim 1, further comprising the step of balancing a load among the server nodes.

10. The method of claim 9, further comprising the step of assigning a server according to a hierarchical mapping of an object identifier or IP address.

11. The method of claim 9, further comprising the step of mapping a requester identifier to a class;

and assigning a server based on class.

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

the server communicating updated meta information to the requester; and

the requester updating the assignment.

13. The method of claim 1, wherein the collection of server nodes is a cluster of proxy servers or a cluster of Web servers in an Internet environment.

14. The method of claim 1, further comprising the step of assigning a server according to a hierarchical mapping of an object identifier.

15. The method of claim 14, wherein the object identifier is a URL.

16. The method of claim 14, wherein the step of assigning a server according to a hierarchical mapping of an object identifier, further comprises the steps of:

assigning each cluster to a virtual server node; and

dynamically mapping the virtual server node to a real server node.

17. The method of claim 16, wherein the collection of server nodes include a domain name-server (DNS) wherein said dynamically mapping step includes a name-to-address mapping and a time-to-live period (TTL) associated with the name-to-address mapping, further comprising the steps of:

the DNS dynamically mapping the virtual server node to the real server node at an interval less than the TTL;

communicating an updated server mapping to all servers;

wherein said meta information includes the updated server mapping; and

wherein said step of dynamically updating routing requests includes the step of routing subsequent object requests according to the updated server mapping.

18. The method of claim 16, wherein the collection of server nodes include a TCP router, further comprising the step of, the router dynamically mapping the virtual server node to a real proxy node.

19. The method of claim 1, wherein said piggybacking step comprises using a PICS protocol to update the routing information.

20. The method of claim 1, further comprising the step of each requesting node communicating a request for a current server assignment for an object.

21. The method of claim 20, wherein said step of communicating a request uses a PICS protocol to determine the current server assignment based on a class of the requested object.

22. The method of claim 1, further comprising a heterogeneous requester environment wherein not all requesters are adapted to perform said dynamically updating step.

23. A dynamic routing method among a plurality of proxy server nodes serving requests for objects, comprising the steps of:

assigning a server according to an object identifier of a requested object;

communicating an updated server assignment to an object requester, in response to said assigning step.

24. The method of claim 23, wherein said step of assigning a server comprises the step of assigning the server according to a hierarchical mapping of the object identifier.

25. The method of claim 23, further comprising the steps of:

mapping an object identifier to a class; and

assigning a server based on the class and a class-to-server assignment table.

26. The method of claim 23, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of

maintaining a class-server assignment table at a requester node for the server selection, including the steps of:

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then issuing a mapping request to an arbitrator;

in response to said mapping step, updating the class-server assignment table.

27. The method of claim 23, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then selecting a server; and

updating the class-server assignment table with a selected server, in response to said selecting step.

28. The method of claim 23, wherein object requests directed to a same host name or address are assigned to different servers in the proxy server nodes according to the object identifier of the requested object.

29. A dynamic routing method among a plurality of Web server nodes serving requests for objects, comprising the steps of:

assigning object requests directed to a same host name or address, to different servers in the plurality of Web server nodes according to an identifier of a requested object;

communicating an updated server assignment to an object requester; and

the object requestor dynamically maintaining the updated server assignment for the requested object for subsequent object requests.

30. The method of claim 29, wherein said step of assigning object requests comprises the step of assigning the object requests according to a hierarchical mapping of the object identifier.

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

mapping an object identifier to a class; and

assigning a server based on the class and a class-to-server assignment table.

32. The method of claim 29, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then issuing a mapping request to an arbitrator; and

in response to said mapping step, updating the class-server assignment table.

33. The method of claim 29, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then selecting a server; and

updating the class-server assignment table with a selected server, in response to said selecting step.

34. The program storage device of claim 29, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then selecting a server; and

updating the class-server assignment table with a selected server, in response to said selecting step.

35. A dynamic routing method for a collection of server nodes, wherein requests to the collection of server nodes can be assigned to different servers in the cluster, said method comprising the steps of:

a requester periodically communicating mapping requests, including one of a requester identifier or IP address, to a server;

mapping said one of a requester identifier or IP address to a server in the collection of server nodes based on one of a requester load and a server capacity;

communicating a server mapping to all servers, in response to said mapping step; and

if one of the servers receives a request from a requester no longer assigned to that server, the server informing the requester of a change of requester-to-server assignment.

36. The method of claim 35, wherein said step of informing the requester, further comprises the step of:

the server serving the request.

37. The method of claim 35, further comprising the steps of:

partitioning the requester identifier or IP address into classes; and

maintaining a class-to-server assignment table at an arbitrator server and in the collection of servers.

38. The method of claim 37, wherein the arbitrator server comprises a DNS in an Internet environment.

39. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for communicating routing information between requester and server nodes, said server nodes serving requests for objects, said method steps comprising:

piggybacking meta information with a requested object; and

dynamically updating the routing information for a server assignment according to the meta information.

40. The program storage device of claim 39, further comprising the steps of:

balancing a load among the server nodes, wherein said step of balancing the load optimizes cache hits for the requested object.

41. The program storage device of claim 40, further comprising the steps of:

mapping an object identifier to a class; and

assigning a server based on the class and a class-to-server assignment table.

42. The program storage device of claim 41, said mapping step further comprising the step of mapping the object identifier into classes or hash classes via a hash table.

43. The program storage device of claim 40, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of

maintaining a class-server assignment table at a requester node for the server selection, including the steps of:

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then issuing a mapping request to an arbitrator; and

in response to said mapping step, updating the class-server assignment table.

44. The program storage device of claim 40, wherein a server selection method at the requester for reducing assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then selecting a server; and

updating the class-server assignment table with a selected server, in response to said selecting step.

45. The program storage device of claim 40, wherein said step of balancing the load, further comprises the step of assigning classes to server nodes as a function of the load associated with each class.

46. The program storage device of claim 40, wherein said step of balancing the load, further comprises the step of incrementally reassigning classes to servers.

47. The program storage device of claim 39, further comprising the step of balancing a load among the server nodes.

48. The program storage device of claim 47, further comprising the step of assigning a server according to a hierarchical mapping of an object identifier or IP address.

49. The program storage device of claim 47, further comprising the step of mapping a requester identifier to a class;

and assigning a server based on class.

50. The program storage device of claim 47, further comprising the steps of:

the server communicating updated meta information to the requester; and

the requester updating the assignment.

51. The program storage device of claim 39, further comprising the step of assigning a server according to a hierarchical mapping of an object identifier.

52. The program storage device of claim 51, wherein the object identifier is a URL.

53. The program storage device of claim 51, wherein the step of assigning a server according to a hierarchical mapping of an object identifier, further comprises the steps of:

assigning each cluster to a virtual server node; and

dynamically mapping the virtual server node to a real server node.

54. A program storage device of claim 53, wherein the collection of server nodes include a domain name-server (DNS) wherein said dynamically mapping step includes a name-to-address mapping and a time-to-live period (TTL) associated with the name-to-address mapping, further comprising the steps of:

the DNS dynamically mapping the virtual server node to the real server node at an interval less than the TTL;

communicating an updated server mapping to all servers;

wherein said meta information includes the updated server mapping; and

wherein said step of dynamically updating routing requests includes the step of routing subsequent object requests according to the updated server mapping.

55. A program storage device of claim 53, wherein the collection of server nodes include a TCP router, further comprising the step of, the router dynamically mapping the virtual server node to a real proxy node.

56. The program storage device of claim 39, wherein the collection of server nodes is a cluster of proxy servers or a cluster of Web servers in an Internet environment.

57. The program storage device of claim 39, wherein said piggybacking step comprises using a PICS protocol to update the routing information.

58. The program storage device of claim 39, further comprising the step of each requesting node communicating a request for a current server assignment for an object.

59. The program storage device of claim 58, wherein said step of communicating a request uses a PICS protocol to determine the current server assignment based on a class of the requested object.

60. The program storage device of claim 39, further comprising a heterogeneous requester environment wherein not all requesters are adapted to perform said dynamically updating step.

61. The program storage device of claim 39, wherein the server is assigned according to an object identifier of the requested object.

62. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for dynamically routing object requests among a collection of server nodes serving requests for objects, said method steps comprising:

assigning a server according to an object identifier of a requested object;

communicating an updated server assignment to an object requester, in response to said assigning step.

63. A program storage device of claim 62, wherein said step of assigning a server comprises the step of assigning the server according to a hierarchical mapping of the object identifier.

64. A program storage device of claim 62, further comprising the steps of:

mapping an object identifier to a class; and

assigning a server based on the class and a class-to-server assignment table.

65. A program storage device of claim 62, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of

maintaining a class-server assignment table at a requester node for the server selection, including the steps of:

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then issuing a mapping request to an arbitrator;

in response to said mapping step, updating the class-server assignment table.

66. The program storage device of claim 62, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then selecting a server; and

updating the class-server assignment table with a selected server, in response to said selecting step.

67. The program storage device of claim 62, wherein object requests directed to a same host name or address are assigned to different servers in the server nodes according to the object identifier of the requested object.

68. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for dynamically routing object requests among a plurality of Web server nodes serving requests for objects, said method steps comprising:

assigning object requests directed to a same host name or address, to different servers in the cluster according to an identifier of a requested object;

communicating an updated server assignment to an object requester; and

the object requester dynamically maintaining the updated server assignment for the requested object for subsequent object requests.

69. The program storage device of claim 68, wherein said step of assigning object requests comprises the step of assigning the object requests according to a hierarchical mapping of the object identifier.

70. The program storage device of claim 68, further comprising the steps of:

mapping an object identifier to a class; and

assigning a server based on the class and a class-to-server assignment table.

71. The program storage device of claim 68, wherein a server selection method at the requester is provided to reduce the assignment request traffic, comprising the steps of:

maintaining a class-server assignment table at a requester node for the server selection, including the steps of;

mapping the object identifier for each object request to a class;

if no valid server assignment is available in the class-server assignment table, then issuing a mapping request to an arbitrator; and

in response to said mapping step, updating the class-server assignment table.

72. A program storage device readable by a machine, tangibly embodying a program of instructions executable on the machine to perform method steps for dynamically routing object requests among a collection of server nodes serving requests for objects, said method steps comprising:

a requester periodically communicating mapping requests, including one of a requester identifier or IP address, to a server;

mapping said one of a requester identifier or IP address to a server in the collection of server nodes based on one of a requester load and a server capacity;

communicating a server mapping to all servers, in response to said mapping step; and

if one of the servers receives a request from a requester no longer assigned to that server, the server informing the requester of a change of requester-to-server assignment.

73. The program storage device of claim 72, wherein said step of informing the requester, further comprises the step of:

the server serving the request.

74. The program storage device of claim 72, further comprising the steps of:

partitioning the requester identifier or IP address into classes; and

maintaining a class-to-server assignment table at an arbitrator server and in the collection of servers.

75. The program storage device of claim 74, wherein the arbitrator server comprises a DNS in an Internet environment.