Global load balancing across mirrored data centers

• US 20080071925A1
• Filed: 09/18/2006
• Published: 03/20/2008
• Est. Priority Date: 09/18/2006
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Thirumalai, Srikanth, Sundaram, Ravi, Kleinberg, Robert, Leighton, F. Thomson, Lewin, Daniel M., Yerushalmi, Yoav O., Soviani, Adrian M., Rahul, Hariharan Shankar, Maggs, Bruce, Levine, Matthew, Dhanidina, Rizwan S., Parikh, Jay Gunvantrai, Lewin, Anne E.
• Granted Patent: US 7,734,815 B2
• Time in Patent Office: Days
• US Class Current: 709/241
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• 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

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 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;

identifying a set of proxy points, wherein each proxy point is identified by directing a trace route from each of a set of mirror sites toward a given 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 latency and packet loss data;

generating a score for each mirror site based on the latency and packet loss data generated by probing the proxy points, wherein the score is a function of a time-weighted average of latency modified by a penalty factor that is a function of a time-weighted average of packet loss;

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, receiving a 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 an IP address identifying a preferred mirror site at which the request may be serviced.

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

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

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

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

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

5. A method of directing a request to a domain that is replicated at a set of mirror sites, comprising:

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 latency and packet loss data;

generating a score for each mirror site based on at least the latency data generated by probing the proxy points, wherein the score is a function of a time-weighted average of latency modified by a penalty factor, wherein the penalty factor is a function of the packet loss data; and

identifying a mirror site as being a preferred mirror site based on the scores;

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

receiving the request to the domain;

using the network map to return an IP address identifying the preferred mirror site at which the request may be serviced.

6. A method of directing a request to a domain that is replicated at a set of mirror sites, comprising:

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;

collecting latency and packet loss data generated by probing the proxy points;

using the latency and packet loss data to compute exponentially time-weighted average of latency and a time-weighted average of loss;

for each mirror site, generating a score that is a function of the time-weighted average of latency modified by a penalty factor that is a function of the time-weighted average of loss;

using the scores to identify a mirror site as being a preferred mirror site;

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

receiving the request to the domain;

using the network map to return an IP address identifying the preferred mirror site at which the request may be serviced.