Assignment of a POP to a DNS resolver based on volume of communications over a link between client devices and the POP

• US 10,447,648 B2
• Filed: 06/19/2017
• Issued: 10/15/2019
• Est. Priority Date: 06/19/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Bliss, Kevin, Jones, Harvo Reyzell, Mo, Fan, Radlein, Anton Stephen, Uppal, Hardeep Singh, Vasquez, Jorge, Velazquez, Axel David
• Primary Examiner(s): Murray, Daniel C.
• Application Number:
  US15/627,132
• Publication Number:
  US 20180367498A1
• Time in Patent Office: 848 Days
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/101 based on network conditions

Abstract

Systems and methods are described to enable routing of network communications in a content delivery system in a manner expected not to exceed the capacity of individual communication links of points of presence (POPs) within the content delivery system. Specifically, a route mapping service is disclosed that can determine the effect of potential DNS records on volumes of traffic expected to reach a POP through individual communication links, and that can alter DNS records such that the expected traffic does not exceed a capacity of those individual communication links. Illustratively, the DNS records may be altered at a level of individual DNS resolvers interacting with the content delivery system, and the volumes of traffic expected to reach a POP through individual communication links can be determined based on a volume of traffic of client computing devices associated with an individual DNS resolver.

Claims

1. A system comprising:

a plurality of points of presence (“

POPs”

), each POP comprising one or more computing devices configured to retrieve and transmit content, and each POP including at least two communication links with an external network;

a domain name system (“

DNS”

) server configured to receive, from a DNS resolver, requests to resolve a hostname of a content delivery system into a network address of a POP of the plurality of POPs; and

one or more processors implementing a demand analysis service, the one or more processors configured with specific computer-executable instructions to;

determine an association between the DNS resolver and a client computing device;

determine a volume of communications between the client computing device and the plurality of POPs;

select a first POP, from the plurality of POPs, for potential assignment to the DNS resolver based at least partly on a latency of communications between the client computing device and the first POP;

identify, based at least in part on routing information available at the first POP, a first communication link of the first POP over which communications between the first POP and the client computing device are routed;

determine that the volume of communications does not exceed a network capacity of the first communication link; and

transmit to the DNS server an indication that the first POP has been assigned to the DNS resolver, wherein assignment of the first POP to the DNS resolver causes the DNS server to respond to resolution requests from the DNS resolver with a network address of the first POP.

2. The content delivery system of claim 1, wherein the volume of communications represents at least one of a number of requests per second transmitted from the client computing device or a number of bits per second transmitted from the client computing device.

3. The content delivery system of claim 1, wherein the client computing device is associated with a subnetwork including a plurality of client computing devices, and wherein the volume of communications between the client computing device and the plurality of POPs corresponds to a volume of communications between the subnetwork and the plurality of POPs.

4. The content delivery system of claim 3, wherein the subnetwork corresponds to a block of network addresses of a predetermined size.

5. The content delivery system of claim 1, wherein the one or more processors are further configured with the specific computer-executable instructions to:

determine a volume of communications of a specific data type between the client computing device and the plurality of POPs; and

determine that the volume of communications of the specific data type does not exceed a capacity of the first POP to service data of the specific data type.

6. A computer-implemented method comprising:

determining an association between a domain name system (“

DNS”

) resolver and a client computing device;

determining a volume of communications between the client computing device and a point of presence (“

POP”

);

identifying, based at least in part on routing information available at the POP, a communication link of the POP over which communications between the POP and the client computing device are routed;

determining that the volume of communications does not exceed a network capacity of first communication link; and

transmitting to a DNS server an indication that the POP has been assigned to the DNS resolver.

7. The computer-implemented method of claim 6, wherein determining an association between the DNS resolver and a client computing device comprises:

transmitting a predetermined hostname to the client computing device;

receiving a request from the DNS resolver to resolve the predetermined hostname into a network address; and

associating the client computing device with the DNS resolver.

8. The computer-implemented method of claim 7, wherein the predetermined hostname is included within a universal resource locator (“

URL”

), and wherein the URL corresponds to a web beacon.

9. The computer-implemented method of claim 6, wherein the POP is included within a plurality of POPs, wherein the computer-implemented method further comprises selecting the POP, from the plurality of POPs, for potential assignment to the DNS resolver based at least partly on a network metric between the client computing device and the POP, and wherein the network metric includes at least one of latency, hop count, bandwidth, packet loss, or path reliability.

10. The computer-implemented method of claim 9 further comprising, prior to selecting the POP for potential assignment to the DNS resolver:

selecting a second POP from the plurality of POPs for potential assignment to the DNS resolver;

identifying, based at least in part on routing information available at the second POP, a communication link of the second POP over which communications between the second POP and the client computing device are routed; and

determining that the volume of communications exceeds a network capacity of the communication link of the second POP.

11. The computer-implemented method of claim 6, wherein the computer-implemented method further comprises:

identifying, based at least in part on routing information available at a second POP, a communication link of the second POP over which communications between the second POP and the client computing device are routed;

determining that a remaining percentage of the total volume of communications does not exceed a network capacity of the communication link of the second POP; and

transmitting to the DNS server an indication that the second POP has been assigned to the DNS resolver.

12. The computer-implemented method of claim 11, wherein assignment of the second POP to the DNS resolver causes the DNS server to respond resolution portion of requests from the DNS resolver by providing an address of the second POP.

13. The computer-implemented method of claim 12, wherein the portion is equal to the remaining percentage of the total volume of communications.

14. The computer-implemented method of claim 6, wherein the client computing device is associated with a subnetwork including a plurality of client computing devices, and wherein the volume of communications between the client computing device and the POP corresponds to a volume of communications between the subnetwork and the POP.

15. Non-transitory computer-readable media comprising computer-executable instructions, wherein the computer-executable instructions, when executed by a computing system, cause the computing system to:

determine an association between a domain name system (“

DNS”

) resolver and a client computing device;

determine a volume of communications between the client computing device and a point of presence (“

POP”

);

identify, based at least in part on routing information available at the POP, a communication link of the POP over which communications between the POP and the client computing device are routed;

determine that the volume of communications does not exceed a network capacity of the communication link; and

transmit to the DNS server an indication that the POP has been assigned to the DNS resolver.

16. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions cause the computing system to determine the association between the DNS resolver and the client computing device at least partly by:

receiving from the client computing device a request for content, wherein the request is addressed to an encoded network address;

decoding, from the encoded network address, identifying information of the DNS resolver; and

associating the client computing device with the DNS resolver.

17. The non-transitory computer-readable media of claim 15, wherein the routing information corresponds to a border gateway protocol (BGP) table.

18. The non-transitory computer-readable media of claim 15, wherein the POP is included within a plurality of POPs, wherein the computer-executable instructions cause the computing system to select the POP, from the plurality of POPs, for potential assignment to the DNS resolver based at least partly on a network metric between the client computing device and the POP.

19. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to:

determine an association between a second DNS resolver and a second client computing device;

determine a volume of communications between the second client computing device and the POP;

identify, based at least in part on routing information available at the POP, that communications between the POP and the second client computing device are routed over the communication link;

determine that a combination of the volume of communications associated with the first client computing device and the volume of communications associated with the second client computing device does not exceed a network capacity of the communication link; and

transmit to the DNS server an indication that the POP has been assigned to the second DNS resolver.

20. The non-transitory computer-readable media of claim 15, wherein the association between the DNS resolver and the client computing device indicates a percentage of DNS requests transmitted by the client computing device that are expected to be routed to the DNS resolver, and wherein the volume of communications between the client computing device and the POP is a percentage of a total volume of communications between the client computing device and the POP equal to the percentage of DNS requests.

21. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to, prior to transmitting to the DNS server the indication that the POP has been assigned to the DNS resolver:

select a second POP as a candidate for assignment to the DNS resolver;

identify, based at least in part on routing information available at the second POP, a communication link of the second POP over which communications between the second POP and the client computing device are routed;

determine that the volume of communications exceeds a network capacity of the communication link of the second POP; and

select the first POP as a candidate for assignment to the DNS resolver.