Load balancing of client connections across a network using server based algorithms

• US 6,178,160 B1
• Filed: 12/23/1997
• Issued: 01/23/2001
• Est. Priority Date: 12/23/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bolton, Derek W., Agrawal, Rajesh
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): KWOH, JASPER C
• Application Number:
  US08/996,683
• Time in Patent Office: 1,127 Days
• Field of Search: 709/105, 709/219, 709/233, 709/226, 710/60, 370/355, 370/352
• US Class Current: 370/255
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/58 Caching of addresses or names
• 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/101 based on network conditions
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/1038 Load balancing arrangements to avoid a single path through a load balancer
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A plurality of web servers (16, 18, and 20) have a common host name, and their authoritative domain server (24 or 26) responds to requests from a local domain-name server (22) for the network address corresponding to their common host name by making an estimate of the performance costs of adding a further client to each of the web servers and then sending the local domain-name server (22) the network address of the server to which the addition of a further client will result in the least performance cost. The performance cost is defined as the difference in the average number of waiting clients, and it takes into account both the additional response time for existing clients and the projected response time for the prospective new client.

Claims

1. In a communications network, a system comprising:

A) a plurality of application servers having different network addresses but sharing a common host name, each said application server including circuitry for communicating over the network with a plurality of clients in transactions consisting of clients'"'"' requests and the application server'"'"'s responses thereto, for measuring delays between requests and respective responses, for determining, as a function of the measured delays, performance-cost estimates representing the estimated increase that adding a further client will cause in the average number of said plurality of clients that are waiting for responses, and for transmitting the network performance-cost estimates over the network; and

B) a domain-name server that includes circuitry for receiving the performance-cost estimates from the application servers, for receiving over the network DNS queries specifying the common host name, for making a choice among the application servers as a function of the performance-cost estimates respectively received therefrom, and for responding to such DNS queries by sending as the DNS response thereto the chosen application server'"'"'s network address.

2. A system as defined in claim 1 wherein:

A) the performance-cost estimates made by the application servers represent the performance costs to existing clients only; and

B) the domain-name server'"'"'s circuitry for making a choice among the application servers additionally computes for each application server a projected new-client latency to be experienced by an added client and makes its choice as a function of the sums of the projected new-client latencies and the performance-cost estimates received from the respective application servers.

3. A system as defined in claim 2 wherein:

A) each application server includes circuitry for determining and transmitting to the domain-name server its transaction rate and average number of clients; and

B) the domain-name server'"'"'s circuitry for making a choice among the application servers computes a total transaction rate by adding together the transaction rates received from all the application servers, computes an average total number of clients by adding together the average numbers of clients received from all the application servers, projects a new-client transaction rate by dividing the total transaction rate by the average total number of clients, and computes each application server'"'"'s projected new-client latency by multiplying the new-client transaction rate by the respective application server'"'"'s average response time.

4. A system as defined in claim 1 wherein each application server determines its performance-cost estimate as a function additionally of the application server'"'"'s number of transactions.

5. A system as defined in claim 1 wherein each application server determines its performance-cost estimate as a function additionally of the application server'"'"'s transaction-data volume.

6. A system as defined in claim 1 wherein each application server'"'"'s circuitry for making performance-cost estimates includes circuitry for:

A) computing from the measured delays the total latency for each of a plurality of sample periods;

B) measuring a plurality of operating variables for each of the sample periods;

C) for each of at least one parameterized model of the relationship between total latency and certain of the operational variables, determining the model parameters that result, when the first model using those model parameters is applied to the measured operational variables, in the best fit of the first model'"'"'s output to the computed total latencies; and

D) generating as its performance-cost estimate the increased latency per unit of elapsed time that is predicted, by the model whose output resulting from the model parameters thus determined is the best fit to the total latencies computed for the sample periods, to result from increasing the number of transactions by the average number of transactions per client.

7. A system as defined in claim 6 wherein:

A) the circuitry for measuring a plurality of operating variables for each of the sample periods comprises circuitry for measuring the number of transactions and the transaction-data volume for each of the sample periods; and

B) one said model models the relationship that the total latency has to the number of transactions and transaction-data volume.

8. A system as defined in claim 7 wherein:

A) the circuitry for measuring a plurality of operating variables for each of the sample periods comprises circuitry for measuring the client-connect time; and

B) another said model models the relationship that the total latency has to the number of transactions, client-connect time, and the transaction-data volume.

9. A system as defined in claim 6 wherein:

A) the circuitry for measuring a plurality of operating variables for each of the sample periods comprises circuitry for measuring the number of transactions, the client-connect time, and the transaction-data volume for each of the sample periods; and

B) one said model models the relationship that the total latency has to the number of transactions, the client-connect time, and the transaction-data volume.

10. For responding to a DNS query requesting the network address associated with a host name shared by a plurality of application servers that have different network addresses and communicate over a communications network with pluralities of clients in transactions consisting of clients'"'"' requests and the application servers'"'"' responses thereto, a method comprising:

A) measuring the delays between requests and respective responses for each of the application servers;

B) determining, as a function of the measured delays, performance-cost estimates for each of the application servers representing the estimated increase that adding a further client thereto will cause in the average number of said plurality of clients waiting for responses therefrom;

C) making a choice among the application servers as a function of the performance-cost estimates.