Hybrid content request routing system

Patent metadata

Field	Value
Publication number	US-11290418-B2
Application number	US-202016987806-A
Country	US
Kind code	B2
Filing date	Aug 7, 2020
Priority date	Sep 25, 2017
Publication date	Mar 29, 2022
Grant date	Mar 29, 2022

Abstract

A hybrid content request routing system is described herein. The hybrid content request routing system may use aspects of the anycast routing technique and aspects of the domain name server (DNS) resolver-based routing technique to identify the appropriate network address to provide to a user device in response to receiving a DNS query. For example, the hybrid content request routing system may include one or more points of presence (POPs), with some or all of the POPs forming one or more virtual POPs. Individual POPs may be assigned unique network addresses and POPs that form a virtual POP may be assigned the same anycast network address. The hybrid content request routing system can measure latencies from user devices to the individual POP network addresses and to the anycast network addresses and use the measured latencies to identify the network address that may result in the lowest latency.

First claim

What is claimed is:

1. A computer-implemented method comprising:
obtaining a first source network address and a second source network address that use a network device to submit queries;
obtaining an indication of a first latency between a first user device corresponding to the first source network address and a first point of presence (POP) that has a unique network address, an indication of a second latency between the first user device and a second POP that has a non-unique network address, an indication of a third latency between a second user device corresponding to the second source network address and the first POP, and an indication of a fourth latency between the second user device and the second POP;
determining that a combination of the first latency and the third latency is less than a combination of the second latency and the fourth latency; and
resolving a query from the network device based at least in part on the determination.

2. The computer-implemented method of claim 1 , further comprising:
obtaining a second query from the network device, wherein the second query comprises a unique client identifier;
determining that the unique client identifier comprises the first source network address; and
mapping the first source network address to the network device.

3. The computer-implemented method of claim 1 , wherein the first user device with the first source network address is configured to generate and transmit the query to the network device, wherein the first user device is further configured to obtain the unique network address from the network device, and wherein the first user device is further configured to transmit a content request to the unique network address.

4. The computer-implemented method of claim 1 , wherein resolving a query from the network device further comprises:
determining that the first POP is available; and
transmitting the unique network address to the network equipment in response to the determination that the first POP is available.

5. A system comprising:
a data store that stores latency information; and
a selection system comprising a processor configured with specific computer-executable instructions that, when executed, cause the selection system to at least:
identify that a first source network address and a second source network address are mapped to a network device;
obtain an indication of a first latency between a first user device corresponding to the first source network address and a first network location that has a unique network address, an indication of a second between the first user device and a second network location that has a non-unique network address, an indication of a third latency between a second user device corresponding to the second source network address and the first network location, and an indication of a fourth latency between the second user device and the second network location;
determine that a combination of the first latency and the third latency is lower than a combination of the second latency and the fourth latency; and
resolve a query from the network device based at least in part on the determination.

6. The system of claim 5 , wherein the processor is further configured with specific computer-executable instructions that, when executed, cause the selection system to at least:
determine that the first network location is available; and
transmit the unique network address to the network equipment in response to the determination that the first network location is available.

7. The system of claim 5 , wherein the processor is further configured with specific computer-executable instructions that, when executed, cause the selection system to at least:
determine that the network location is unavailable; and
transmit the non-unique network address instead of the unique network address to the network equipment to resolve the query.

8. The system of claim 7 , wherein the processor is further configured with specific computer-executable instructions that, when executed, cause the selection system to at least determine that the first network location is one of malfunctioning, offline, or currently at request processing capacity.

9. The system of claim 5 , wherein the combination of the first latency and the third latency is one of an average of the first latency and the third latency, a median of the first latency and the third latency, a mode of the first latency and the third latency, a minimum of the first latency and the third latency, or a maximum of the first latency and the third latency.

10. The system of claim 5 , wherein the processor is further configured with specific computer-executable instructions that, when executed, cause the selection system to at least:
obtain a second query from the network equipment, wherein the second query comprises a unique client identifier;
determine that the unique client identifier comprises the first source network address;
map the first source network address to the network equipment; and
store the mapping of the first source network address to the network equipment in a client ID mapping data store.

11. The system of claim 5 , further comprising a third network location, wherein the second network location and the third network location are both assigned the non-unique network address.

12. The system of claim 11 , wherein the second network location is configured to at least:
obtain a content request from the first user device with the first source network address;
measure a fifth latency of a transmission of the content request from the first user device to the second network location; and
store the measured fifth latency in the data store in an entry associated with the first source network address and the non-unique network address.

13. The system of claim 12 , wherein the third network location is configured to at least:
obtain a second content request from the second user device with the second source network address;
measure a sixth latency of a transmission of the second content request from the second user device to the third network location; and
store the measured sixth latency in the data store in an entry associated with the second source network address and the non-unique network address.

14. The system of claim 12 , wherein the content request is routed from the first user device to the second network location according to a border gateway protocol (BGP) routing protocol.

15. The system of claim 5 , wherein the selection system comprises a domain name server (DNS).

16. Non-transitory, computer-readable storage media comprising computer-executable instructions for resolving a query, wherein the computer-executable instructions, when executed by a computer system, cause the computer system to at least:
determine that a first source network address and a second source network address are mapped to a network device;
obtain an indication of a first latency between a first user device corresponding to the first source network address and a first network location that has a first type of network address, an indication of a second latency between the first user device and a second network location that has a second type of network address, an indication of a third latency between a second user device corresponding to the second source network address and the first network location, and an indication of a fourth latency between the second user device and the second network location;
compare a combination of the first latency and the third latency with a combination of the second latency and the fourth latency; and
resol

Assignees

• Amazon Tech Inc

Inventors

• Vasquez Jorge
• Narayan Mohanish
• Jones Harvo Reyzell

Classifications

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• H04L61/4511

  using domain name system [DNS] · CPC title

• H04L67/10 Primary

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L61/5069

  for group communication, multicast communication or broadcast communication · CPC title

• H04L61/5007

  Internet protocol [IP] addresses · CPC title