Multi-autonomous system anycast content delivery network

• US 8,607,014 B2
• Filed: 12/22/2009
• Issued: 12/10/2013
• Est. Priority Date: 12/22/2009
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Spatscheck, Oliver, Al-Qudah, Zakaria, Rabinovich, Michael, Van der Merwe, Jacobus, Lee, Seunjoon
• Primary Examiner(s): Alsip, Michael
• Application Number:
  US12/645,000
• Publication Number:
  US 20110153941A1
• Time in Patent Office: 1,449 Days
• Field of Search: 711/154, 711/165, 709/224, 709/226, 709/229, 709/238
• US Class Current: 711/165
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• 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/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests

Abstract

A content delivery network includes first and second sets of cache servers, a domain name server, and an anycast island controller. The first set of cache servers is hosted by a first autonomous system and the second set of cache servers is hosted by a second autonomous system. The cache servers are configured to respond to an anycast address for the content delivery network, to receive a request for content from a client system, and provide the content to the client system. The first and second autonomous systems are configured to balance the load across the first and second sets of cache servers, respectively. The domain name server is configured to receive a request from a requestor for a cache server address, and provide the anycast address to the requestor in response to the request. The anycast island controller is configured to receive load information from each of the cache servers, determine an amount of requests to transfer from the first autonomous system to the second autonomous system; send an instruction to the first autonomous system to transfer the amount of requests to the second autonomous system.

Claims

1. A content delivery network comprising:

a first set of cache servers hosted by a first autonomous system and a second set of cache servers hosted by a second autonomous system, wherein the first autonomous system balances a first load among the first set of cache servers by controlling routing within the first autonomous system and the second autonomous system balances a second load among the second set of cache servers by controlling routing within the second autonomous system, wherein each of the cache servers performs operations comprising;

responding to an anycast address for the content delivery network; and

receiving a request for content from a client system and providing the content to the client system;

a domain name server that performs operations comprising;

receiving a request for a cache server address; and

providing the anycast address in response to the request for the cache server address; and

an anycast island controller separate from the first autonomous system, which performs operations comprising;

receiving load information from the first set and the second set of cache servers;

generating an island topology for an anycast island serviced by the anycast island controller, wherein the island topology includes weights for each node in the first autonomous system, wherein the weights are based on a difference between a present demand for the first autonomous system and a first aggregate capacity of the first set of cache servers;

identifying, based on the island topology, when a first aggregate load for the first autonomous system exceeds the first aggregate capacity of the first set of cache servers and a second aggregate load for the second autonomous system is below a second aggregate capacity of the second set of cache servers;

determining an amount of requests for content to transfer from the first autonomous system to the second autonomous system in response to the identifying;

preventing a transient loop from forming in the first autonomous system and the second autonomous system prior to sending an instruction to the first autonomous system to control the routing of the anycast address to transfer the amount of requests for content to the second autonomous system, wherein the transient loop is prevented, at least in part, by waiting for devices shifting traffic associated with the amount of requests to stop shifting the traffic; and

sending the instruction to the first autonomous system to control the routing of the anycast address to transfer the amount of requests for content to the second autonomous system after the transient loop is prevented.

2. The content delivery network of claim 1, further comprising a third set of cache servers hosted by a third autonomous system, wherein the third autonomous system performs operations comprising balancing a third load among the third set of cache servers, wherein the anycast island further performs operations comprising determining a second amount of requests for content to transfer from the first autonomous system to the third autonomous system and sending an instruction to the first autonomous system to transfer the second amount of requests for content to the third autonomous system.

3. The content delivery network of claim 1, wherein the domain name server further performs operations comprising:

receiving a second request for a cache server address; and

providing a unicast address in response to a second request for a cache server address, the unicast address corresponding to an available cache server.

4. The content delivery network of claim 1, wherein the anycast island controller further performs operations comprising determining if a critically overloaded cache server and a cache server with a significant excess capacity are within the first autonomous system.

5. The content delivery network of claim 4, wherein the anycast island controller further performs operations comprising notifying the first autonomous system when a critically overloaded cache server and a cache server with a significant excess capacity are within the first autonomous system.

6. The content delivery network of claim 1, wherein the anycast island controller further performs operations comprising verifying the amount of requests shifted from the first autonomous system to the second autonomous system.

7. The content delivery network of claim 6, wherein the anycast island controller further performs operations comprising notifying the first autonomous system of a failure to shift the amount of requests to the second autonomous system.

8. The content delivery network of claim 1, wherein the load information includes one of network bandwidth, central processing unit utilization, memory utilization, and number of requests being served.

9. The content delivery network of claim 1, wherein the first autonomous system balances the load across the first set of cache servers by controlling the routing of the anycast address within the first autonomous system.

20. The content delivery network of claim 1, wherein

the first and second autonomous systems are within the anycast island;

the anycast island controller determines if an aggregate load of the anycast island exceeds an aggregate capacity of cache servers within the anycast island; and

the domain name server provides a unicast address to a portion of the client systems within the anycast island to direct requests to cache servers located outside of the anycast island when the aggregate load exceeds the aggregate capacity.

10. An anycast island controller comprising:

a memory that stores instructions;

a processor that executes the instructions to performing operations comprising;

receiving load information from a first set of cache servers hosted by a first autonomous system and a second set of cache servers hosted by a second autonomous system, the first autonomous system configured to balance a first load among the first set of cache servers and the second autonomous systems configured to balance a second load among the second set of cache servers;

generating an island topology for an anycast island serviced by the anycast island controller, wherein the island topology includes weights for each node in the first autonomous system, wherein the weights are based on a difference between a present demand for the first autonomous system and a first aggregate capacity of the first set of cache servers;

identifying, based on the island topology, when a first aggregate load for the first autonomous system exceeds the first aggregate capacity of the first set of cache servers and a second aggregate load for the second autonomous system is below a second aggregate capacity of the second set of cache servers;

determining an amount of requests to transfer from the first autonomous system to the second autonomous system in response to the identifying;

preventing a transient loop from forming in the first autonomous system and the second autonomous system prior to sending an instruction to the first autonomous system to control the routing of the anycast address to transfer the amount of requests for content to the second autonomous system, wherein the transient loop is prevented, at least in part, by waiting for devices shifting traffic associated with the amount of requests to stop shifting the traffic; and

sending the instruction to the first autonomous system to control the routing of the anycast address to transfer the amount of requests to the second autonomous system after the transient loop is prevented.

11. The anycast island controller of claim 10, wherein the operations further comprise determining if a critically overloaded cache server and a cache server with a significant excess capacity are within the first autonomous system.

12. The anycast island controller of claim 11, wherein the operations further comprise notifying the first autonomous system when a critically overloaded cache server and a cache server with a significant excess capacity are within the first autonomous system.

13. The anycast island controller of claim 10, wherein the operations further comprise verifying the amount of requests shifted from the first autonomous system to the second autonomous system.

14. The anycast island controller of claim 13, wherein the operations further comprise notifying the first autonomous system of a failure to shift the amount of requests to the second autonomous system.

15. A computer readable device comprising a plurality of instructions to manipulate a processor to cause the processor to perform operations comprising:

receiving load information from a first set of cache servers hosted by a first autonomous system and a second set of cache servers hosted by a second autonomous system, the first autonomous system configured to balance a first load among the first set of cache servers and the second autonomous systems configured to balance a second load among the second set of cache servers;

generating an island topology for an anycast island associated with the first and second autonomous systems, wherein the island topology includes weights for each node in the first autonomous system, wherein the weights are based on a difference between a present demand for the first autonomous system and a first aggregate capacity of the first set of cache servers;

identifying, based on the island topology, when a first aggregate load for the first autonomous system exceeds the first aggregate capacity of the first set of cache servers and a second aggregate load for the second autonomous system is below a second aggregate capacity of the second set of cache servers;

determining an amount of requests to transfer from the first autonomous system to the second autonomous system when the first aggregate load exceeds the first aggregate capacity and the second aggregate load is below the second aggregate capacity;

preventing a transient loop from forming in the first autonomous system and the second autonomous system prior to sending an instruction to the first autonomous system to control the routing of the anycast address to transfer the amount of requests for content to the second autonomous system, wherein the transient loop is prevented, at least in part, by waiting for devices shifting traffic associated with the amount of requests to stop shifting the traffic; and

sending the instruction to the first autonomous system to controlling the routing of the anycast address to transfer the amount of requests to the second autonomous system after the transient loop is prevented.

16. The computer readable device of claim 15, wherein the operations further comprise determining if a critically overloaded cache server and a cache server with a significant excess capacity are within the first autonomous system.

17. The computer readable device of claim 16, wherein the operations further comprise notifying the first autonomous system when a critically overloaded cache server and a cache server with a significant excess capacity are within the first autonomous system.

18. The computer readable device of claim 15, wherein the operations further comprise verifying the amount of requests shifted from the first autonomous system to the second autonomous system.

19. The computer readable device of claim 15, wherein the operations further comprise notifying the first autonomous system of a failure to shift the amount of requests to the second autonomous system.