Method and apparatus for load balancing

• US 20020194335A1
• Filed: 05/28/2002
• Published: 12/19/2002
• Est. Priority Date: 06/19/2001
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Maynard, William Pat
• Granted Patent: US 8,180,921 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: G06F 2201/875 Monitoring of systems including the internet
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method and apparatus is provided in which a multi-site load balancing system directs a client to a site best able to respond to the client'"'"'s request based on a combination of balancing methods. Performance metric balancing is employed to select sites having the best performance metrics to participate in network latency balancing to determine the site best able to respond the request. The sites participating in the network latency balancing are selected based on having performance metrics within an allowable deviation of the best performance metric. Alternatively, network latency balancing is employed to select sites having the least network latency to participate in performance metric balancing to determine the site best able to respond to the request.

Claims

1. A method of load balancing multiple sites in a network comprising:

identifying a plurality of sites able to respond to a DNS request in accordance with a first criteria; and

selecting from the identified sites one site best able to respond to the request in accordance with a second criteria.

2. The method of claim 1, wherein the first criteria is a performance metric, the performance metric providing a measure of a site'"'"'s ability to respond to the request, and the identified sites have performance metrics within an allowable deviation of the best performance metric.

3. The method of claim 1, wherein the performance metric is a number of connections per second currently being processed in the site, and the best performance metric is the least number of connections.

4. The method of claim 1, wherein the performance metric is a measure of a response time between a site'"'"'s receipt of the request and the site'"'"'s response to the request, and the best performance metric is the shortest response time.

5. The method of claim 1, wherein the performance metric is a measure of the site'"'"'s utilization of a bandwidth provided to the site, and the best performance metric is the lowest utilization.

6. The method of claim 2, wherein the second criteria is a network latency, the network latency providing a measure of a receipt time between a site'"'"'s response to the request and a receipt of the site'"'"'s response at the client, the selected site having the least network latency wherein the least network latency is the shortest receipt time.

7. The method of claim 6, wherein the network latency provides a number of router hops between a site and the client and the least network latency is the least number of router hops.

8. The method of claim 6, wherein the network latency provides a ping response time between a site and the client and the least network latency is the shortest ping response time.

9. The method of claim 6, wherein the first criteria is the network latency, and the identified sites have network latencies within an allowable deviation of a least network latency.

10. The method of claim 9, wherein the second criteria is the performance metric, and the selected site has the best performance metric.

11. A method of balancing traffic loads on multiple sites in a network comprising:

receiving a domain name service (DNS) request from a client name server on behalf of a client;

selecting sites to participate in identifying the site best able to respond to the DNS request; and

directing the client to the identified site.

12. The method of claim 11, wherein selecting the participating sites is based on a performance metric of each site, wherein the participating sites have performance metrics that are within an allowable deviation of the best performance metric of all of the sites.

13. The method of claim 12, wherein the performance metric is a number of connections currently present in the site, and the best performance metric is the least number of connections.

14. The method of claim 12, wherein the performance metric is a measure of a load on a central processing unit (CPU) currently experienced in the site, and the best performance metric is the lowest CPU load.

15. The method of claim 11, wherein identifying the site best able to respond to the request is based on a network latency of the site relative to the client, and the identified site has the least network latency.

16. The method of claim 15, wherein determining the least network latency comprises:

sending a DNS response to the client simultaneously from each of the participating sites; and

determining which of the participating sites sent the fastest DNS response.

17. The method of claim 16, further comprising:

receiving by the client name server a DNS response sent simultaneously from each of the available sites, wherein the site having the lowest latency is the site that sent the fastest DNS response.

18. The method of claim 16, further comprising:

counting a number of router hops to traverse from each of the available sites to the client, wherein the site having the lowest latency is the site having the least number of router hops.

19. The method of claim 16, further comprising:

pinging the client from each of the available sites, wherein the site having the lowest latency is the site having the fastest pinging.

20. The method of claim 16, wherein directing the client to the identified site comprises sending a DNS response to the client name server that includes an identification of the identified site.

21. The method of claim 20, wherein the identification of the identified site is a virtual internet protocol address of the identified site.

22. A multi-site load balancing system comprising:

a client name server to receive a domain name service (DNS) request from a client;

a plurality of multi-site load balancers, each having a domain name server, to identify sites able to respond to the DNS request in order of a performance metric associated with each identified site, wherein the domain name server of at least one of the plurality of multi-site load balancers communicates to the client name server which one of the identified sites has a least network latency to the client.

23. The system of claim 22, wherein the identified sites include only sites whose performance metric is within an allowed deviation of the best performance metric.

24. The system of claim 23, wherein the performance metric is a number of connections currently present in the site, and the best performance metric is the least number of connections.

25. The system of claim 23, wherein the performance metric is a measure of a load on a central processing unit (CPU) currently experienced in the site, and the best performance metric is the lowest CPU load.

26. The system of claim 23, wherein the identified site that has the least network latency is the identified site having a shortest packet transit time between the identified site and the client.

27. The system of claim 26, wherein the plurality of multi-site load balancers determine which one of the identified sites has the shortest packet transit time by causing a DNS response to be sent to the client name server simultaneously from each of the identified sites and wherein the identified site having the shortest packet transit time is the identified site that sent the fastest DNS response.

28. The system of claim 23, wherein the identified site that has the least network latency is the identified site that has a least number of router hops between the identified site and the client.

29. The system of claim 23, wherein the identified site that has the least network latency is the identified site that has a shortest ping time between the identified site and the client.

30. An apparatus to direct a client to an optimal site in a network comprising:

at least two multi-site load balancers each having a domain name server;

a client name server to forward a domain name service DNS request from a client to a selected one of the domain name servers;

at least one site coupled with each of the multi-site load balancers, the sites having a suitable performance metric, wherein the selected one of the domain name servers is able to facilitate a determination of which of the sites is the optimal site to satisfy the DNS request based on which of the sites having the suitable performance metric also have a least network latency to the client.

31. The apparatus of claim 30, wherein the suitable performance metric is within an allowable deviation of the best performance metric of all of the sites.

32. The apparatus of claim 31, wherein the suitable performance metric includes the best performance metric of all of the sites.

33. The apparatus of claim 31, wherein the performance metric is a number of connections currently present in the site, and the best performance metric is the least number of connections.

34. The apparatus of claim 31, wherein the performance metric is a measure of a load on a central processing unit (CPU) currently experienced in the site, and the best performance metric is the lowest CPU load.

35. The apparatus of claim 30, wherein the one of the domain name servers is able to facilitate a determination of which of the sites have the least network latency to the client by causing each of the sites to simultaneously send a DNS response to the client name server, the fastest DNS response being sent from the site that has the least network latency.

37. The article of claim 36, wherein the selection of sites to participate in identifying the site best able to respond to the DNS request is based on a performance metric of each site, wherein the participating sites have performance metrics that are within an allowable deviation of the best performance metric of all of the sites.

38. The article of claim 37, wherein the performance metric is a number of connections currently present in the site, and the best performance metric is the least number of connections.

39. The article of claim 37, wherein the performance metric is a measure of a load on a central processing unit (CPU) currently experienced in the site, and the best performance metric is the lowest CPU load.

40. The article of claim 36, wherein the data causes the machine to identify the site best able to respond to the request based on a network latency of the site relative to the client, wherein the site identified as best able to respond is the site that has the least network latency.

41. The article of claim 40, wherein the data causes the machine to determine the site that has the least network latency by:

sending a DNS response to the client simultaneously from each of the participating sites; and

determining which of the participating sites sent the fastest DNS response.

42. The article of claim 40, wherein the data causes the machine to determine the site that has the least network latency by further:

receiving a DNS response sent simultaneously from each of the participating sites, wherein the site having the lowest latency is the site that sent the fastest DNS response.

43. The article of claim 40, wherein the data causes the machine to determine the site that has the least network latency by further:

counting a number of router hops to traverse from each of the available sites to the client, wherein the site having the lowest latency is the site having the least number of router hops.

44. The article of claim 40, wherein the data causes the machine to determine the site that has the least network latency by further:

pinging the client from each of the available sites, wherein the site having the lowest latency is the site having the fastest pinging.

45. The article of claim 36, wherein the data causes the machine to direct the client to the identified site by sending a DNS response to a client name server associated with the client, wherein the DNS response includes an identification of the identified site.

46. The article of claim 45, wherein the identification of the identified site is a virtual internet protocol address of the identified site.

36. An article of manufacture comprising a machine-accessible medium including data that when accessed by a machine cause the machine to:

receive a domain name service (DNS) request from a server on behalf of a client;

select sites to participate in identifying the site best able to respond to the DNS request; and

directing the client to the identified site.