Global load balancing across mirrored data centers

• US 7,111,061 B2
• Filed: 05/29/2001
• Issued: 09/19/2006
• Est. Priority Date: 05/26/2000
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Thirumalai, Srikanth, Sundaram, Ravi, Kleinberg, Robert, Leighton, F. Thomson, Yerushalmi, Yoav O., Soviani, Adrian M., Rahul, Hariharan Shankar, Maggs, Bruce, Levine, Matthew, Dhanidina, Rizwan S., Parikh, Jay Gunvantrai
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US09/866,897
• Publication Number:
  US 20020129134A1
• Time in Patent Office: 1,939 Days
• Field of Search: 709220-221, 709223-225, 709/227, 709/229, 709232-235, 709/203, 709238-242
• US Class Current: 709/224
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/45 Network directories; Name-to-address mapping
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• 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/1034 Reaction to server failures 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 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

The invention is an intelligent traffic redirection system that does global load balancing. It can be used in any situation where an end-user requires access to a replicated resource. The method directs end-users to the appropriate replica so that the route to the replica is good from a network standpoint and the replica is not overloaded. The technique preferably uses a Domain Name Service (DNS) to provide IP addresses for the appropriate replica. The most common use is to direct traffic to a mirrored web site.

Claims

1. A method of determining which of a set of content provider mirror sites should receive an end user'"'"'s initial request, comprising:

generating a network map during a map generation process according to the following sub-steps;

dynamically determining a set of proxy points, wherein each proxy point of the set of proxy points is determined by directing a trace route from each of a set of content provider mirror sites toward a given local name server and determining a given point in the Internet where the trace routes from each of the set of content provider mirror sites intersect;

probing each of the proxy points from each of the set of content provider mirror sites to generate given data;

generating a download predictor score for each content provider mirror site based on the given data generated by probing the proxy points;

identifying which mirror site provides a best download performance based on the download predictor score; and

associating a given name server IP address with the identified mirror site to generate the network map; and

upon completion of the map generation process, in response to an end user'"'"'s initial request to a given local name server, returning an IP address of the identified mirror site based on information in the network map.

2. A method, operated by a server provider, for managing global traffic redirection for a set of content providers operating mirrored sites, wherein the service provider is distinct from the set of content providers operating the mirrored sites, comprising:

for each content provider in the set of content providers, generating a network map during a map generation process according to the following sub-steps;

dynamically determining a set of proxy points, wherein each proxy paint of the set of proxy points is determined by directing a trace route from each of a set of data centers that host mirrored sites for the content provider toward a given local name server and determining a given point in the Internet where the trace routes from each or the set of data centers intersect;

from each of set of data centers that host mirrored sites for the content provider, executing a given network test against each of the set of proxy points;

generating a time-weighted average of a given network performance metric based on data generated by executing the given network test;

generating a score for each data center per proxy point;

generating a set of candidate data centers for each of a set of name servers;

associating a candidate data center to each of a set of IP address space blocks to generate the network map;

providing the network map to a name server; and

using the network maps generated for the set of content providers to direct end user requests to a mirrored site to a given data center.

3. The method as described in claim 2 wherein the given network test is a ping test.

4. The method as described in claim 2 wherein the given metric is latency or packet loss.

5. The method as described in claim 2 further including the step of discarding from the set of candidate data centers any data center that does not meet a given operating criteria.

6. The method as described in claim 5 wherein the given operating criteria is evaluated using a file download test.

7. A method of determining which of a set of mirror sites should receive a request to a domain that is replicated at the set of mirror sites, comprising:

generating a network map during a map generation process according to the following sub-steps;

dynamically determining a set of proxy points, wherein each proxy point of the set of proxy points is determined by directing a trace route from each of a set of mirror sites toward a given local name server and determining a given point in the Internet where the trace routes from each of the set of mirror sites intersect;

probing each of the proxy points from each of the set of mirror sites to generate given data;

generating a score for each mirror site based on the given data generated by probing the proxy points;

identifying which mirror site provides a best performance based on the score; and

associating a given name server IP address with the identified mirror site to generate the network map; and

upon completion of the map generation process, and responsive to a local name server making a request associated with the domain, receiving the request at a name server associated with the network map; and

having the name server associated with the network map use the network map to return to the local name server an IP address identifying a preferred mirror site at which the request may be serviced.

8. The method as described in claim 7 wherein the request originates at a client machine and the domain is associated with a content provider Web site.

9. The method as described in claim 7 wherein the request originates from a content delivery network edge server and the set of mirror sites comprise storage servers.

10. The method as described in claim 7 wherein the request originates at a streaming server and the set of mirror sites comprises a plurality of signal acquisition points.

11. The method as described in claim 7 wherein the request originates at a logging process and the set of mirror sites comprises a plurality of log archival servers.

12. The method as described in claim 7 wherein the request originates at a mail process and the set of mirror sites comprises a plurality of mail servers.