Method for extending a network map

• US 7,028,083 B2
• Filed: 05/29/2001
• Issued: 04/11/2006
• Est. Priority Date: 05/26/2000
• Status: Active Grant

• Current Assignee: Akamai Technologies, Inc.
• Original Assignee: Akomai Technologies Incorporated
• Inventors: Kleinberg, Robert, Levine, Matthew, Soviani, Adrian
• Primary Examiner(s): Huynh, Kim
• Assistant Examiner(s): SORRELL, ERON J
• Application Number:
  US09/866,896
• Publication Number:
  US 20020073199A1
• Time in Patent Office: 1,778 Days
• Field of Search: 709/220, 709/223, 709/225, 709/238
• US Class Current: 709/223
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/115 using a dedicated packet
• 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
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

An intelligent traffic redirection system performs global load balancing. The system uses a network map that is generated in part by extending a “sparse” IP address data map. In particular, a method of extending an IP address block map begins by defining a set of one or more upper bound block(s). These upper bound blocks are then used to partition a space of IP addresses into subsets or “territories”, wherein each territory represents a largest set of IP addresses to which a piece of mapping data may be extended. The “piece” of mapping data typically consists of a host (usually a “name server” identified by the core point discovery process) IP address and some data about that host, namely, a “nearest” data center or a flag indicating that either “no data” exists for that host or that the system is “indifferent” as to which of a set of mirrored data centers the host should be mapped. A unification algorithm partitions the territory of each upper bound block into the largest possible sub-blocks in which a given unanimity criterion is satisfied and extends the mapping data in each such sub-block to all of the territory of that sub-block.

Claims

1. A method executed with a computer of extending an arbitrary sparse set of IP blocks having associated mapping data into an IP address block map that is consistent with the arbitrary sparse set of IP blocks having associated mapping data, comprising:

defining a set of upper bound blocks;

defining a unanimity criterion that determines whether a set of mapping data are sufficiently in agreement to be reduced to a single piece of mapping data;

using the set of upper bound blocks to partition a space of IP addresses into territories, wherein each territory represents a largest set of IP addresses to which a piece of mapping data may be extended, and wherein a piece of mapping data may be extended to the territory only if (a) the territory includes an IP block from the arbitrary sparse set of IP blocks that has that piece of mapping data and (b) the unanimity criterion applies to all of the IP blocks from the arbitrary sparse set that are included in the territory;

generating the IP address block map by partitioning the territory of each upper bound block into a largest possible sub-block in which the unanimity criterion is satisfied and extending the mapping data in each such sub-block to all of the territory of that sub-block.

2. The method as described in claim 1 wherein the upper bound blocks comprise CIDR blocks contained in one or more BGP routing tables.

3. The method as described in claim 1 wherein the upper bound blocks comprise CIDR blocks contained in one or more BGP routing tables, with the CIDR blocks being further subdivided according to geographic location.

4. The method as described in claim 1 wherein the territory associated to an IP address block includes all of the IP addresses belonging to that block.

5. The method as described in claim 1 wherein the territory associated to an IP address block includes all of the IP addresses belonging to that block that do not belong to any more-specific upper bound block that is a sub-block of the given IP address block.

6. The method as described in claim 1 wherein the unanimity criterion is that a set of mapping data is unanimous if all data values in the set are equal.

7. The method as described in claim 1 wherein the unanimity criterion is that a set of mapping data is unanimous if all data values are in the set are equal, disregarding those values which belong to a set of one or more special values that are treated as indifferent.

8. The method as described in claim 1 wherein the mapping data comprises network mapping decisions based on network probes.

9. The method as described in claim 8 wherein the network probes comprise ICMP packets.

10. A method executed within a computer of extending an arbitrary sparse data set used for making request routing decisions, comprising:

determining whether routing decisions for a given set of name servers in a given IP address block of the arbitrary sparse data set are sufficiently in agreement;

if the routing decisions for the given set of name servers in the given IP address block of the arbitrary sparse data set are sufficiently in agreement, extending the routing decisions for at least one new name server; and

if the routing decisions for the given set of name servers in the given IP address block of the arbitrary sqarse data set are not sufficiently in agreement, breaking the block into a largest possible sub-block so that, in each sub-block, the routing decisions for a subset of name servers are sufficiently in agreement.

11. A method executed within a computer of extending an arbitrary sparse set of IP blocks having associated mapping data into an IP address block map that is consistent with the arbitrary sparse set of IP blocks having associated mapping data, comprising:

for each of a set of one or more blocks;

(a) determining whether given mapping data therein satisfies a given criterion for all of the IP blocks from the arbitrary sparse set that are included in the set;

(b) if the given mapping data satisfies the given criterion, extending a routing decision to all IP addresses in a given portion of the block while discarding mapping data in more specific areas of the given portion; and

(c) if the given mapping data does not satisfy the given criterion, dividing the block into at least two sub-blocks; and

(d) generating the IP address block map by repeating steps (a)–

(c) recursively for each of the sub-blocks.