Method for generating a network map

• US 7,251,688 B2
• Filed: 05/29/2001
• Issued: 07/31/2007
• Est. Priority Date: 05/26/2000
• Status: Expired due to Term

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akamai Technologies, Inc.
• Inventors: Sundaram, Ravi, Leighton, F. Thomson, Levine, Matthew, Soviani, Adrian
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): GOLD, AVI M
• Application Number:
  US09/866,884
• Publication Number:
  US 20020078237A1
• Time in Patent Office: 2,254 Days
• Field of Search: 709/223, 709/224, 709/238, 709/244
• US Class Current: 709/224
• CPC Class Codes: H04L 43/50 Testing arrangements
• 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/563 Data redirection of data network streams
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

An intelligent traffic redirection system performs global load balancing for Web sites located at mirrored data centers. The system relies on a network map that is generated continuously, preferably for the user-base of the entire Internet. Instead of probing each local name server (or other host) that is connectable to the mirrored data centers, the network map identifies connectivity with respect to a much smaller set of proxy points, called “core” (or “common”) points. A core point is representative of a set of local name servers (or other hosts) that, from a data center'"'"'s perspective, share the point. To discover a core point, an incremental trace route is executed from each of the set of mirrored data centers to a local name server that may be used by client to resolve a request for a replica stored at the data centers. An intersection of the trace routes at a common routing point is then identified. Thus, for example, the common routing point may be the first common point for the trace routes when viewed from the perspective of the data centers (or the last common point for the trace routes when viewed from the perspective of the local name server). The common routing point is then identified as the core point for the local name server.

Claims

1. A method of mapping the Internet to generate an optimized set of proxy points in a local name server address space, comprising:

for a given pair of data centers each accessible over the Internet, physically executing a trace route over the Internet from each data center to a given local name server, wherein the given local name server is one of a plurality of local name servers that end user clients use to access resources on the Internet;

locating an intersection of the trace routes at a common routing point; and

assigning an Internet Protocal (IP) address of the common routing point as a proxy point in the local name server address space.

2. The method as described in claim 1 wherein the data centers are mirror sites that host content from at least one content provider.

3. The method as described in claim 1 wherein the common routing point is a first common point when viewed from a perspective of the data centers.

4. The method as described in claim 1 wherein the common routing point is a last common point when viewed from a perspective of the given local name server.

5. A method of generating a network map to be used in routing end user local name server requests to a set of content provider mirror sites, wherein the content provider mirror sites are each accessible over a public Internet, and wherein the end user local name server is one of a plurality of end user local name servers that clients use to access resources on the public Internet, comprising:

for each local name server, physically directing a trace route over the public Internet from each content provider mirror site to the local name server;

determining a point in the public Internet adjacent an intersection of the trace routes; and

associating an IP address of the point to a given one of the content provider mirror sites in the map.

6. The method as described in claim 5 wherein the point is the intersection of the routes.

7. A method of generating a network map useful for determining which of a set of mirror sites should receive a client name server request, wherein the mirror sites are each accessible over a public Internet, and wherein the client name server is one of a plurality of client name servers that clients use to access resources on the public Internet, comprising:

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

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

using the given data to generate the network map.