System and method for routing service requests

• US 10,567,303 B2
• Filed: 06/22/2017
• Issued: 02/18/2020
• Est. Priority Date: 03/14/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Dumitriu, Dan Mihai, Sivasubramanian, Swaminathan
• Primary Examiner(s): Walsh, John B
• Application Number:
  US15/630,717
• Publication Number:
  US 20180013693A1
• Time in Patent Office: 971 Days
• CPC Class Codes: H04L 1/0018 based on latency requirement
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/563 Data redirection of data network streams
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A computer-implemented method routes service requests to services in a service framework provided by a plurality of hosts. The method comprises receiving a service request for a service in the service framework and discovering a plurality of candidate hosts that host the service. The plurality of candidate hosts are a subset of the plurality of hosts. The method further comprises selecting a candidate host from the plurality of candidate hosts based on measured latencies for the plurality of candidate hosts and routing the service request to the selected candidate host.

Claims

1. A computer-implemented method comprising:

receiving a service request;

determining which of a plurality of candidate host computing devices to use for servicing the service request by at least;

for particular candidate host computing devices of the plurality of candidate host computing devices, assigning a weighting to the particular candidate host computing device based in part on latency information representing a service latency reflecting a queuing latency and a time required to process the service request by the particular candidate host computing device; and

selecting a candidate host computing device from the particular candidate host computing devices for servicing the service request based, at least in part, on the respective weighting assigned to each of the particular candidate host computing devices; and

routing the service request to the selected candidate host computing device.

2. The method of claim 1, wherein determining which of the plurality of candidate host computing devices to use for servicing the service request comprises accessing information about a hierarchy, the plurality of candidate host computing devices being logically defined as having locations within the hierarchy.

3. The method of claim 2, wherein the hierarchy further comprises a first level including a plurality of leaf nodes, wherein individual leaf nodes correspond to particular ones of the plurality of candidate host computing devices;

and a second level defining a first plurality of zones, wherein individual zones comprise a subset of the plurality of leaf nodes.

4. The method of claim 3, wherein the hierarchy further comprises a third level including a second plurality of zones which each comprise a subset of the first plurality of zones, and a fourth level including a root node associated with the plurality of leaf nodes, the first plurality of zones, and the second plurality of zones.

5. The method of claim 1, wherein the assigned weighting for each of the particular candidate host computing devices is based in part on a network latency for each of the particular candidate host computing devices, and wherein the network latency is reflected in the latency information for each of the particular candidate host computing devices.

6. The method of claim 1, wherein selecting a candidate host computing device for servicing the service request further comprises pseudo-randomly selecting a candidate host computing device from the particular candidate host computing devices based in part on measured latencies for the particular candidate host computing devices in accordance with the weighting assigned to the particular candidate host computing devices.

7. A system comprising:

a plurality of candidate host computing devices;

wherein the system is configured to;

receive a service request;

determine which of a plurality of candidate host computing devices to use for servicing the service request by at least;

for particular candidate host computing devices of the plurality of candidate host computing devices, assigning a weighting to the particular candidate host computing device based in part on latency information representing a service latency reflecting a queuing latency and a time required to process the service request by the particular candidate host computing device; and

selecting a candidate host computing device from the particular candidate host computing devices for servicing the service request based, at least in part, on the respective weighting assigned to each of the particular candidate host computing devices; and

route the service request to the selected candidate host computing device.

8. The system of claim 7, wherein the plurality of host computing devices are heterogeneous and have different processing capacities, and wherein the system is further configured to select the candidate host computing device based at least in part on the processing capacities of the candidate host computing devices when making routing decisions.

9. The system of claim 7, wherein the assigned weighting for each of the particular candidate host computing devices is based in part on a network latency for each of the particular candidate host computing devices, and wherein the network latency is reflected in the latency information for each of the particular candidate host computing devices.

10. The system of claim 7, wherein the plurality of host computing devices are logically defined as having locations within a hierarchy of a service framework, wherein the hierarchy further comprises:

a first level including a plurality of leaf nodes, wherein individual leaf nodes correspond to individual host computing devices of the plurality of host computing devices;

a second level defining a first plurality of zones, wherein individual zones comprise a subset of the plurality of leaf nodes;

a third level including a second plurality of zones, each of the second plurality of zones comprises a subset of the first plurality of zones; and

a fourth level including a root node associated with the leaf nodes, the first plurality of zones, and the second plurality of zones.

11. The system of claim 7, wherein the system is further configured to route the service request to the selected candidate host via at least one proxy host.

12. A non-transitory computer-readable medium bearing computer-executable instructions which, when executed on a computing device, direct the computing device to:

receive a service request;

determine which of a plurality of candidate host computing devices to use for servicing the service request by at least;

for particular candidate host computing devices of the plurality of candidate host computing devices, assigning a weighting to the particular candidate host computing device based in part on latency information representing a service latency reflecting a queuing latency and a time required to process the service request by the particular candidate host computing device; and

selecting a candidate host computing device from the particular candidate host computing devices for servicing the service request based, at least in part, on the respective weighting assigned to each of the particular candidate host computing devices; and

route the service request to the selected candidate host computing device.

13. The non-transitory computer-readable medium of claim 12, wherein the plurality of candidate host computing devices are heterogeneous and have different processing capacities, and wherein the computer-executable instructions further configure the computing device to account for the processing capacities of the plurality of candidate host computing devices when selecting a candidate host computing device.

14. The non-transitory computer-readable medium of claim 12, wherein the computer-executable instructions further configure the computing device to pseudo-randomly select a candidate host computing device from the plurality of candidate computing devices based on measured latencies for the particular candidate host computing devices in accordance with the assigned to the particular candidate host computing devices.