Optimal route selection in a content delivery network

• US 7,274,658 B2
• Filed: 03/01/2002
• Issued: 09/25/2007
• Est. Priority Date: 03/01/2001
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Miller, Gary L., Rao, Satish B., Sundaram, Ravi, Canfield, Timothy K., Bornstein, Claudson F.
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Boakye; Alexander O.
• Application Number:
  US10/087,033
• Publication Number:
  US 20020163882A1
• Time in Patent Office: 2,034 Days
• Field of Search: 370/227, 370/351, 370/235, 370/237, 370/238, 370/400, 370/401, 370/228, 455/556.2, 455/414.1, 709/217, 709/122, 709/219, 705/400, 705/51, 705/40
• US Class Current: 370/227
• 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 45/22 Alternate routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/289 Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A routing mechanism, service or system operable in a distributed networking environment. One preferred environment is a content delivery network (CDN) wherein the present invention provides improved connectivity back to an origin server, especially for HTTP traffic. In a CDN, edge servers are typically organized into regions, with each region comprising a set of content servers that preferably operate in a peer-to-peer manner and share data across a common backbone such as a local area network (LAN). The inventive routing technique enables an edge server operating within a given CDN region to retrieve content (cacheable, non-cacheable and the like) from an origin server more efficiently by selectively routing through the CDN'"'"'s own nodes, thereby avoiding network congestion and hot spots. The invention enables an edge server to fetch content from an origin server through an intermediate CDN server or, more generally, enables an edge server within a given first region to fetch content from the origin server through an intermediate CDN region. As used herein, this routing through an intermediate server, node or region is sometimes referred to as “tunneling.”

Claims

1. A method operative in a content delivery network having a set of edge servers organized into regions, wherein the edge servers provide delivery of content on behalf of participating content providers, comprising:

for a given content provider, periodically generating a map identifying a set of alternate routes that may be used for edge server to content provider origin server communications;

in response to a request for a given file received at a given edge server, using the map to identify a direct route and a set of one or more alternate routes between the edge server and the content provider origin server;

executing a race by initiating a concurrent download of the file over each of the direct route and the set of one or more alternate routes; and

as a result of the race, determining an optimal route between the edge server and the content provider origin server.

2. The method as described in claim 1 further including the step of using the optimal route for transferring additional data between the edge server and the content provider origin server for a given time period.

3. The method as described in claim 1 wherein the map is generated by determining distances between a given set of regions and the content provider origin server.

4. The method as described in claim 3 wherein the given set of regions are well-connected regions in the CDN.

5. The method as described in claim 4 further including the step of collecting ping data between each well-connected region and the content provider origin server to facilitate generation of the map.

6. The method as described in claim 1 further including the step of having the edge server fetch the map from a given location using a given name query.

7. The method as described in claim 1 wherein the step of executing the race further includes the steps of:

determining whether a given number of bytes has been received;

if the given number of bytes has been received over a given one of the routes, terminating download of the file over other of the given routes.

8. The method as described in claim 1 wherein the given file comprises content that is not cacheable on the edge server.

9. The method as described in claim 1 wherein the given file comprises content that is not then available on the edge server.

10. The method as described in claim 1 wherein the given file comprises dynamic content.

11. A method operative in a content delivery network having a set of edge servers organized into regions, wherein the edge servers provide delivery of content on behalf of participating content providers, and wherein a given content provider origin server may be reached over a set of routes, comprising:

identifying one or more routes between the edge server and the content provider origin server;

in response to a request for a given file received at a given edge server, initiating a concurrent download of the given file over each of the routes; and

determining an optimal route between the edge server and the content provider origin server as a function of the concurrent downloads.

12. A server for use in a content delivery network, comprising:

a processor, and

a computer-readable medium having processor-executable instructions for performing the following steps;

initiating a performance metric test on a set of potential routes between the server and a given second server, wherein at least one of the potential routes passes through a server intermediate the server and the given second server, and wherein the performance metric test is a download of a file, and wherein the file is an object being requested by an end user or a test object;

determining when a given number of bytes of the file have been received over a given one of the potential routes and for terminating the performance metric test with respect to other of the potential routes when the given number of bytes of the file have been received; and

collecting and analyzing data generated as a result of the performance metric test and determining an optimal path between the server and the given second server.

13. The server as described in claim 12 wherein the server is an edge server and the given second server is a content provider origin server.

14. The server as described in claim 12 wherein the server is an edge server and the given server is a reverse proxy server.

15. The server as described in claim 12 wherein the performance metric test is initiated in response to a given client request.

16. The server as described in claim 12 further including fetching a map defining the set of potential routes, wherein the map is generated on a per-content provider basis.

17. A server for use in a content delivery network, comprising:

a processor; and

a computer-readable medium having processor-executable instructions for performing the following steps;

initiating a performance metric test on a set of potential routes between the server and a given second server, wherein at least one of the potential routes passes through a server intermediate the server and the given second server, wherein the performance metric test is initiated if no such test has occurred in a given first time period, if a given second time period has elapsed since a last test, or if a given number of requests for a file have been received at the server machine without a test being run; and

collecting and analyzing data generated as a result of the performance metric test and determining an optimal path between the server and the given second server.