REQUEST ROUTING UTILIZING CLIENT LOCATION INFORMATION

• US 20100125673A1
• Filed: 11/17/2008
• Published: 05/20/2010
• Est. Priority Date: 11/17/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sheehan, Richard, Richardson, David R., Patel, Imran S., Redman, Benjamin W. S., Cormie, John
• Granted Patent: US 8,028,090 B2
• Time in Patent Office: Days
• US Class Current: 709/239
• CPC Class Codes: H04L 2101/69 using geographic information, e.g. room number
• CPC Class Codes: H04L 45/741 Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6
• 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/1021 based on client or server locations
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A system, method, and computer-readable medium for request routing based on client location information are provided. A content delivery network service provider receives a DNS query from a client computing device. The DNS query corresponds to a resource identifier for requested content from the client computing device. The content delivery network service provider transmits an alternative resource identifier in response to the client computing device DNS query. The alternative resource identifier is selected as a function of client location information. The client location information is obtained from information corresponding to a mapping of at least partial IP addresses to known locations. The client computing device then issues a second DNS query to the same content delivery network service provider. The content delivery network service provider can then either resolve the second DNS query with an IP address of a cache component or transmit another alternative resource identifier that will resolve to the content delivery network service provider. The process can repeat with the content delivery network service provider'"'"'s network until a DNS server resolves a DNS query from the client computing device.

Claims

1. A method comprising:

obtaining a DNS query from a client computing device at a first DNS server, wherein the DNS query corresponds to a requested resource associated with an original resource identifier provided by a content provider and wherein the first DNS server corresponds to a content delivery network service;

obtaining a query IP address associated with the DNS query at the first DNS server;

obtaining a location-based identifier associated with the query IP address and a confidence factor, the confidence factor corresponding to a degree of confidence associated with the accuracy of the location-based identifier to query IP address association;

determining whether the confidence factor exceeds a threshold value;

if the confidence factor exceeds the threshold value;

determining a destination identifier associated with the DNS query, wherein the destination identifier is determined based on the location-based identifier;

selecting a network point of presence associated with the content delivery network service provider based on the destination identifier;

determining whether the first DNS server is authoritative to the DNS query based on the selected network point of presence; and

if the first DNS server is not authoritative;

obtaining an alternative resource identifier based on the selected network point of presence, wherein the alternative resource identifier includes information for causing a DNS query to resolve to a domain corresponding to the selected network point of presence;

transmitting the alternative resource identifier to the client computing device;

obtaining a subsequent DNS query from the client computing device at a second DNS server, wherein the subsequent DNS query corresponds to the alternative resource identifier provided by the content delivery network service provider;

determining whether the second DNS server is authoritative to the subsequent DNS query;

selecting a cache component for providing content associated with the original resource request if the second DNS server is authoritative to the second DNS query; and

transmitting information identifying the selected cache component if the second DNS server is determined to be authoritative.

2. The method as recited in claim 1 further comprising assigning a location-based identifier associated with the first DNS server if the confidence factor does not exceed the threshold value.

3. The method as recited in claim 1, wherein the destination identifier corresponds to a geographic region encompassing a location associated with the location-based identifier.

4. The method as recited in claim 1 further comprising overriding the determined destination identifier based on the original resource identifier, wherein the original resource identifier provides information associated with an alternative destination identifier.

5. The method as recited in claim 1, wherein selecting a network point of presence comprises selecting a network point of presence from a set of network points of presence capable of servicing resource requests associated with the determined destination identifier.

6. The method as recited in claim 5, wherein the network point of presence is selected from the set of network points of presence based on a distribution allocation.

7. The method as recited in claim 1 further comprising:

determining whether the selected network point of presence is available prior to determining whether the first DNS server is authoritative to the DNS query based on the selected network point of presence;

if the selected network point of presence is available, maintaining the selected network point of presence; and

if the selected network point of presence is not available, selecting an alternative network point of presence.

8. The method as recited in claim 7, wherein the availability of the selected network point of presence is based on health information indicative of the availability of the selected network point of presence to process incoming resource requests.

9. The method as recited in claim 7, wherein selecting an alternative network point of presence comprises selecting an alternative network point of presence from a failover list of alternative network points of presence.

10. The method as recited in claim 9, wherein the alternative network point of presence is selected from the failover list based on a distribution allocation.

11. The method as recited in claim 1 further comprising:

if the first DNS server is determined to be authoritative;

selecting a cache component for providing content associated with the original resource request; and

transmitting information identifying the selected cache component.

12. The method as recited in claim 1 further comprising overriding the determined destination identifier based on an identity of the content provider.

13. The method as recited in claim 12, wherein the determined destination identifier is overridden if the content provider'"'"'s subscription with the content delivery network service provider does not provide for content to be provided from a destination corresponding to the destination identifier.

14. The method as recited in claim 12, wherein the determined destination identifier is overridden if the content provider'"'"'s subscription with the content delivery network service provider provides for use of an alternative destination identifier.

15. The method as recited in claim 1, wherein the query IP address is associated with the client computing device.

16. The method as recited in claim 15, wherein the query IP address is associated with a DNS resolver component associated with the client computing device.

17. The method as recited in claim 1, wherein the location-based identifier corresponds to a physical location associated with the client computing device.

18. The method as recited in claim 1, wherein the location-based identifier corresponds to a logical location associated with the client computing device.

19. The method as recited in claim 1, wherein the location-based identifier corresponds to a relative location.

20. The method as recited in claim 19, wherein the relative location is inferred based on an association of the relative location to a known location.

21. The method as recited in claim 20, wherein the relative location is inferred based on latency information

22. A method comprising:

obtaining a DNS query from a client computing device at a first DNS server, wherein the DNS query corresponds to a requested resource associated with an original resource identifier provided by a content provider and wherein the first DNS server corresponds to a content delivery network service;

obtaining a query IP address associated with the DNS query at the first DNS server;

obtaining a location-based identifier associated with the query IP address;

selecting a network point of presence associated with the content delivery network service provider based on the location-based identifier;

determining whether the first DNS server is authoritative to the DNS query based on the selected network point of presence; and

if the first DNS server is not authoritative;

obtaining an alternative resource identifier based on the selected network point of presence, wherein the alternative resource identifier includes information for causing a DNS query to resolve to a domain corresponding to the selected network point of presence; and

transmitting the alternative resource identifier to the client computing device.

23. The method as recited in claim 22 further comprising determining a destination identifier associated with the DNS query, wherein selecting a network point of presence is further based on the destination identifier.

24. The method as recited in claim 23, wherein the destination identifier is determined as a function of the location-based identifier.

25. The method as recited in claim 24, wherein the destination identifier corresponds to a geographic region encompassing a location associated with the location-based identifier.

26. The method as recited in claim 23 further comprising overriding the determined destination identifier based on an identity of the content provider.

27. The method as recited in claim 26, wherein the identity of the content provider is obtained based on the original resource identifier.

28. The method as recited in claim 26, wherein the determined destination identifier is overridden if the content provider'"'"'s subscription with the content delivery network service provider does not provide for content to be provided from a destination corresponding to the destination identifier.

29. The method as recited in claim 26, wherein the determined destination identifier is overridden if the content provider'"'"'s subscription with the content delivery network service provider provides for use of an alternative destination identifier.

30. The method as recited in claim 23 further comprising overriding the determined destination identifier based on the original resource identifier, wherein the original resource identifier provides information associated with an alternative destination identifier.

31. The method as recited in claim 23, wherein the destination identifier is determined based on an identity of the content provider.

32. The method as recited in claim 31, wherein the destination identifier is further determined based on the obtained location-based identifier.

33. The method as recited in claim 23, wherein selecting a network point of presence comprises selecting a network point of presence from a set of network points of presence capable of servicing resource requests associated with the determined destination identifier.

34. The method as recited in claim 33, wherein the network point of presence is selected from the set of network points of presence based on a distribution allocation.

35. The method as recited in claim 22 further comprising:

determining whether the selected network point of presence is available prior to determining whether the first DNS server is authoritative to the DNS query based on the selected network point of presence;

if the selected network point of presence is available, maintaining the selected network point of presence; and

if the selected network point of presence is not available, selecting an alternative network point of presence.

36. The method as recited in claim 35, wherein the availability of the selected network point of presence is based on health information indicative of the availability of the selected network point of presence to process incoming resource requests.

37. The method as recited in claim 35, wherein selecting an alternative network point of presence comprises selecting an alternative network point of presence from a failover list of alternative network points of presence.

38. The method as recited in claim 37, wherein the alternative network point of presence is selected from the failover list based on a distribution allocation.

39. The method as recited in claim 22 further comprising:

if the first DNS server is determined to be authoritative;

selecting a cache component for providing content associated with the original resource request; and

transmitting information identifying the selected cache component.

40. The method as recited in claim 22 further comprising obtaining a confidence factor corresponding to a degree of confidence associated with the accuracy of the location-based identifier to query IP address association.

41. The method as recited in claim 40, wherein a network point of presence is selected based on the location-based identifier if the confidence factor exceeds a threshold value.

42. The method as recited in claim 22, wherein the location-based identifier is obtained from a data store containing query IP address to location-based identifier mapping entries.

43. The method as recited in claim 42, wherein the data store contains query IP address to location-based identifier mappings only for entries exceeding a minimum threshold confidence factor, the confidence factor corresponding to a degree of confidence associated with the accuracy of the location-based identifier to query IP address association.

44. The method as recited in claim 22, wherein the query IP address is associated with the client computing device.

45. The method as recited in claim 44, wherein the query IP address is associated with a DNS resolver component associated with the client computing device.

46. The method as recited in claim 22, wherein the location-based identifier corresponds to a physical location associated with the client computing device.

47. The method as recited in claim 22, wherein the location-based identifier corresponds to a logical location associated with the client computing device.

48. The method as recited in claim 22, wherein the location-based identifier corresponds to a relative location.

49. The method as recited in claim 48, wherein the relative location is inferred based on an association of the relative location to a known location.

50. The method as recited in claim 49, wherein the relative location is inferred based on latency information

51. A system for request routing comprising:

a first network point of presence associated with a content delivery network service provider, wherein the first network point of presence includes a DNS server component that receives a DNS query from a client computing device, wherein the DNS query corresponds to a requested resource associated with a first resource identifier, and wherein the DNS server in the first network point of presence is operable to;

obtain a query IP address associated with the DNS query at the first DNS server;

obtain a location-based identifier associated with the query IP address;

select a network point of presence associated with the content delivery network service provider based on the location-based identifier;

determine whether the first DNS server is authoritative to the DNS query based on the selected network point of presence; and

if the first DNS server is not authoritative;

obtain an alternative resource identifier based on the selected network point of presence, wherein the alternative resource identifier includes information for causing a DNS query to resolve to a domain corresponding to the selected network point of presence; and

transmit the alternative resource identifier to the client computing device.

52. The system as recited in claim 51, wherein the DNS server in the first network point of presence is further operable to determine a destination identifier associated with the DNS query, wherein selecting a network point of presence is further based on the destination identifier.

53. The system as recited in claim 52, wherein the destination identifier is determined as a function of the location-based identifier.

54. The system as recited in claim 52, wherein the DNS server in the first network point of presence is further operable to override the determined destination identifier based on an identity of the content provider.

55. The system as recited in claim 54, wherein the identity of the content provider is obtained based on the original resource identifier.

56. The system as recited in claim 51, wherein selecting a network point of presence comprises selecting a network point of presence from a set of network points of presence capable of servicing resource requests associated with the determined destination identifier.

57. The system as recited in claim 56, wherein the network point of presence is selected from the set of network points of presence based on a distribution allocation.

58. The system as recited in claim 51, wherein the DNS server in the first network point of presence is further operable to:

determine whether the selected network point of presence is available prior to determining whether the first DNS server is authoritative to the DNS query based on the selected network point of presence;

maintain the selected network point of presence if the selected network point of presence is available; and

select an alternative network point of presence if the selected network point of presence is not available.

59. The system as recited in claim 58, wherein the availability of the selected network point of presence is based on health information indicative of the availability of the selected network point of presence to process incoming resource requests.

60. The system as recited in claim 58, wherein selecting an alternative network point of presence comprises selecting an alternative network point of presence from a failover list of alternative network points of presence.

61. The system as recited in claim 60, wherein the alternative network point of presence is selected from the failover list based on a distribution allocation.

62. The system as recited in claim 51 further comprising:

a second network point of presence associated with a content delivery network service provider, wherein the second network point of presence includes a DNS server component that receives a subsequent DNS query from a client computing device, wherein the subsequent DNS query corresponds to a requested resource associated with the alternative resource identifier, and wherein the DNS server in the second network point of presence is operable to;

resolve the subsequent DNS query to identify a cache component for providing content associated with the original resource request; and

transmit information identifying the identified cache component to the client computing device.

63. A method comprising:

obtaining a DNS query from a client computing device at a first DNS server, wherein the DNS query corresponds to a requested resource associated with an original resource identifier provided by a content provider and wherein the first DNS server corresponds to a content delivery network service;

obtaining a query IP address associated with the DNS query at the first DNS server;

obtaining a location-based identifier associated with the query IP address;

obtaining a destination identifier based on the obtained location-based identifier;

determining whether the first DNS server is authoritative to the DNS query based on the destination identifier; and

if the first DNS server is not authoritative;

obtaining an alternative resource identifier based on the selected network point of presence, wherein the alternative resource identifier includes information for causing a DNS query to resolve to a domain corresponding to the selected network point of presence; and

transmitting the alternative resource identifier to the client computing device.

64. A method for request routing comprising:

obtaining a DNS query from a client computing device at a first DNS server, wherein the DNS query corresponds to a requested resource associated with a resource identifier and wherein the first DNS server corresponds to a content delivery network service provider;

determining that the first resource identifier is associated with an alternative resource identifier based on location information associated with the client computing device, wherein the location information is obtained from information corresponding to a mapping of at least partial IP addresses to known locations;

transmitting the alternative resource identifier to the client computing device, wherein the alternative resource identifier includes information for causing a DNS query to resolve to a domain corresponding to the content delivery service provider and supplemental request routing information not included in the first resource identifier;

obtaining a subsequent DNS query from the client computing device at a second DNS server, wherein the subsequent DNS query corresponds to the alternative resource identifier provided by the content delivery network service provider and wherein the second DNS server corresponds to the content delivery network service provider;

resolving the subsequent DNS query, at the second DNS server, to identify a cache component for providing content associated with the original resource request; and

transmitting information identifying the identified cache component to the client computing device.