Global traffic management system using IP anycast routing and dynamic load-balancing

• US 7,574,499 B1
• Filed: 01/19/2005
• Issued: 08/11/2009
• Est. Priority Date: 07/19/2000
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Day, Richard David, Liu, Zaide, Swildens, Eric Sven-Johan
• Primary Examiner(s): WANG, LIANG CHE A
• Application Number:
  US11/040,167
• Time in Patent Office: 1,665 Days
• Field of Search: 709/225, 709/226, 709/202, 709/217, 709/223, 709/229, 709/230, 709/238, 709/224
• US Class Current: 709/223
• CPC Class Codes: G06F 2209/5016 Session
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 41/5029 Service quality level-based billing, e.g. dependent on measured service level customer is charged more or less
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 43/55 Testing of service level quality, e.g. simulating service usage
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1036 Load balancing of requests to servers for services different from user content provisioning, e.g. load balancing across domain name servers
• CPC Class Codes: H04L 67/142 Managing session states for stateless protocols; Signalling session states; State transitions; Keeping-state mechanisms

Abstract

A method and apparatus for serving content requests using global and local load balancing techniques is provided. Web site content is cached using two or more point of presences (POPs), wherein each POP has at least one DNS server. Each DNS server is associated with the same anycast IP address. A domain name resolution request is transmitted to the POP in closest network proximity for resolution based on the anycast IP address. Once the domain name resolution request is received at a particular POP, local load balancing techniques are performed to dynamically select the appropriate Web server at the POP for use in resolving the domain name resolution request. Approaches are described for handling bursts of traffic at a particular POP, security, and recovering from the failure of various components of the system.

Claims

1. A computer-implemented method for resolving a domain name resolution request, comprising:

assigning a first IP address to each of a plurality of domain name servers distributed across a plurality of point of presences;

assigning a second IP address to a first subset of said plurality of domain name servers, wherein said second IP address is different than said first IP address;

assigning a third IP address to a second subset of said plurality of domain name servers, wherein said third IP address is different than said first and second IP addresses;

wherein said first subset is different than said second subset;

receiving said domain name resolution request on a domain name server in said first subset of said plurality of domain name servers using said second IP address when said domain name resolution request sent to said first IP address times out;

receiving said domain name resolution request on a domain name server in said second subset of said plurality of domain name servers using said third IP address when said domain name resolution request sent to said second IP address times out.

2. The method of claim 1, wherein each of said plurality of domain name servers is in only one of said first subset of said plurality of domain name servers or said second subset of said plurality of domain name servers.

3. The method of claim 1, wherein:

said plurality of domain name servers comprises one or more subsets of domain name servers;

each of said one or more subsets of domain name servers is associated with a point of presence (POP) in a plurality of point of presences (POPs); and

each POP contains an optimal number of Web servers to serve Web content requests.

4. The method of claim 3, further comprising:

storing, at each of said plurality of domain name servers, data that identifies one or more of said plurality of POPs as being a neighboring POP.

5. The method of claim 4, further comprising:

grouping neighboring POPs into regions,

wherein each region is a logical grouping of POPs not having geographical boundaries.

6. The method of claim 5, wherein each POP in a region directs traffic only to POPs in its region.

7. The method of claim 4, further comprising:

redirecting subsequent domain name resolution requests from a particular POP to a neighboring POP after determining that a configurable capacity threshold has been exceeded for all Web servers in said particular POP.

8. The method of claim 7, further comprising:

dynamically resolving a redirected domain name resolution request at a receiving domain name server in a neighboring POP by returning an IP address of a Web server in the receiving domain name server'"'"'s POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in said receiving domain name server'"'"'s POP.

9. The method of claim 7, further comprising:

terminating the redirection of subsequent domain name resolution requests from said particular POP to a neighboring POP after determining that the configurable capacity threshold of a Web server in said particular POP is no longer being exceeded.

10. The method of claim 4, further comprising:

containing domain name resolution requests within a particular POP when a denial of service attack on said particular POP is detected.

11. The method of claim 10, further comprising:

returning POP operations back to normal at said particular POP after determining that the denial of service attack no longer exists.

12. The method of claim 3, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a Web server in a neighboring POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in neighboring POPs.

13. The method of claim 3, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a Web server in the domain name server'"'"'s POP; and

wherein said Web server is selected by dynamically load balancing requests among Web servers in said domain name server'"'"'s POP.

14. The method of claim 13, wherein if a Web server in said domain name server'"'"'s POP fails, the failed Web server is excluded in the dynamic load balancing until the failed Web server recovers.

15. The method of claim 3, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a load balancer in the domain name server'"'"'s POP;

wherein said load balancer returns an IP address of a Web server in the domain name server'"'"'s POP; and

wherein said load balancer selects a Web server IP address by dynamically load balancing requests among Web servers in said domain name server'"'"'s POP.

16. The method of claim 3, further comprising:

periodically sending a probe to all Web servers within a POP to gather Web server status information used for dynamically load balancing requests among Web servers in said POP.

17. A computer-readable storage medium storing one or more sequences of instructions for resolving a domain name resolution request, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps:

assigning a first IP address to each of a plurality of domain name servers distributed across a plurality of point of presences;

assigning a second IP address to a first subset of said plurality of domain name servers, wherein said second IP address is different than said first IP address;

assigning a third IP address to a second subset of said plurality of domain name servers, wherein said third IP address is different than said first and second IP addresses;

wherein said first subset is different than said second subset;

receiving said domain name resolution request on a domain name server in said first subset of said plurality of domain name servers using said second IP address when said domain name resolution request sent to said first IP address times out; and

receiving said domain name resolution request on a domain name server in said second subset of said plurality of domain name servers using said third IP address when said domain name resolution request sent to said second IP address times out.

18. The computer-readable storage medium of claim 17, wherein each of said plurality of domain name servers is in only one of said first subset of said plurality of domain name servers or said second subset of said plurality of domain name servers.

19. The computer-readable storage medium of claim 17, wherein:

said plurality of domain name servers comprises one or more subsets of domain name servers;

each of said one or more subsets of domain name servers is associated with a point of presence (POP) in a plurality of point of presences (POPs); and

each POP contains an optimal number of Web servers to serve Web content requests.

20. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

storing, at each of said plurality of domain name servers, data that identifies one or more of said plurality of POPs as being a neighboring POP.

21. The computer-readable storage medium of claim 20, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

grouping neighboring POPs into regions, wherein each region is a logical grouping of POPs not having geographical boundaries.

22. The computer-readable storage medium of claim 21, wherein each POP in a region directs traffic only to POPs in its region.

23. The computer-readable storage medium of claim 20, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

redirecting subsequent domain name resolution requests from a particular POP to a neighboring POP after determining that a configurable capacity threshold has been exceeded for all Web servers in said particular POP.

24. The computer-readable storage medium of claim 23, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

dynamically resolving a redirected domain name resolution request at a receiving domain name server in a neighboring POP by returning an IP address of a Web server in the receiving domain name server'"'"'s POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in said receiving domain name server'"'"'s POP.

25. The computer-readable storage medium of claim 23, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

terminating the redirection of subsequent domain name resolution requests from said particular POP to a neighboring POP after determining that the configurable capacity threshold of a Web server in said particular POP is no longer being exceeded.

26. The computer-readable storage medium of claim 20, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

containing domain name resolution requests within a particular POP when a denial of service attack on said particular POP is detected.

27. The computer-readable storage medium of claim 26, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

returning POP operations back to normal at said particular POP after determining that the denial of service attack no longer exists.

28. The computer-readable storage medium of claim 19, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a Web server in a neighboring POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in neighboring POPs.

29. The computer-readable storage medium of claim 19, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a Web server in the domain name server'"'"'s POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in said domain name server'"'"'s POP.

30. The computer-readable storage medium of claim 29, wherein if a Web server in said domain name server'"'"'s POP fails, the failed Web server is excluded in the dynamic load balancing until the failed Web server recovers.

31. The computer-readable storage medium of claim 19, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a load balancer in the domain name server'"'"'s POP,

wherein said load balancer returns an IP address of a Web server in the domain name server'"'"'s POP,

wherein said load balancer selects a Web server IP address by dynamically load balancing requests among Web servers in said domain name server'"'"'s POP.

32. The computer-readable storage medium of claim 19, wherein execution of the one or more sequences of instructions by the one or more processors causes the one or more processors to perform the step of:

periodically sending a probe to all Web servers within a POP to gather Web server status information used for dynamically load balancing requests among Web servers in said POP.

33. An apparatus for resolving a domain name resolution request, comprising:

one or more processors;

a machine-readable medium storing instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of;

assigning a first IP address to each of a plurality of domain name servers distributed across a plurality of point of presences;

assigning a second IP address to a first subset of said plurality of domain name servers, wherein said first IP address is different than said first IP address;

assigning a third IP address to a second subset of said plurality of domain name servers, wherein said third IP address is different than said first and second IP addresses;

wherein said first subset is different than said second subset;

receiving said domain name resolution request on a domain name server in said first subset of said plurality of domain name servers using said second IP address when said domain name resolution request sent to said first IP address times out; and

receiving said domain name resolution request on a domain name server in said second subset of said plurality of domain name servers using said third IP address when said domain name resolution request sent to said second IP address times out.

34. The apparatus of claim 33, wherein each of said plurality of domain name servers is in only one of said first subset of said plurality of domain name servers or said second subset of said plurality of domain name servers.

35. The apparatus of claim 33, wherein:

said plurality of domain name servers comprises one or more subsets of domain name servers;

each of said one or more subsets of domain name servers is associated with a point of presence (POP) in a plurality of point of presences (POPs); and

each POP contains an optimal number of Web servers to serve Web content requests.

36. The apparatus of claim 35, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

storing, at each of said plurality of domain name servers, data that identifies one or more of said plurality of POPs as being a neighboring POP.

37. The apparatus of claim 36, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

grouping neighboring POPs into regions,

wherein each region is a logical grouping of POPs not having geographical boundaries.

38. The apparatus of claim 37, wherein each POP in a region directs traffic only to POPs in its region.

39. The apparatus of claim 36, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

redirecting subsequent domain name resolution requests from a particular POP to a neighboring POP after determining that a configurable capacity threshold has been exceeded for all Web servers in said particular POP.

40. The apparatus of claim 39, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

dynamically resolving a redirected domain name resolution request at a receiving domain name server in a neighboring POP by returning an IP address of a Web server in the receiving domain name server'"'"'s POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in said receiving domain name server'"'"'s POP.

41. The apparatus of claim 39, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

terminating the redirection of subsequent domain name resolution requests from said particular POP to a neighboring POP after determining that the configurable capacity threshold of a Web server in said particular POP is no longer being exceeded.

42. The apparatus of claim 36, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

containing domain name resolution requests within a particular POP when a denial of service attack on said particular POP is detected.

43. The apparatus of claim 42, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

returning POP operations back to normal at said particular POP after determining that the denial of service attack no longer exists.

44. The apparatus of claim 35, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a Web server in a neighboring POP,

wherein said Web server is selected by dynamically load balancing requests among Web servers in neighboring POPs.

45. The apparatus of claim 35, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a Web server in the domain name server'"'"'s POP; and

wherein said Web server is selected by dynamically load balancing requests among Web servers in said domain name server'"'"'s POP.

46. The apparatus of claim 35, wherein if a Web server in said domain name server'"'"'s POP fails, the failed Web server is excluded in the dynamic load balancing until the failed Web server recovers.

47. The apparatus of claim 35, wherein receiving said domain name resolution request on a domain name server comprises:

dynamically resolving said domain name resolution request at said domain name server by returning an IP address of a load balancer in the domain name server'"'"'s POP;

wherein said load balancer returns an IP address of a Web server in the domain name server'"'"'s POP; and

wherein said load balancer selects a Web server IP address by dynamically load balancing requests among Web servers in said domain name server'"'"'s POP.

48. The apparatus of claim 35, wherein the instructions include additional instructions which, when executed by the one or more processors, further cause the one or more processors to perform the step of:

periodically sending a probe to all Web servers within a POP to gather Web server status information used for dynamically load balancing requests among Web servers in said POP.