System and method for routing service requests

• US 9,692,708 B2
• Filed: 08/07/2014
• Issued: 06/27/2017
• 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: Sivasubramanian, Swaminathan, Dumitriu, Dan Mihai
• Primary Examiner(s): Maung, Zarni
• Application Number:
  US14/454,629
• Publication Number:
  US 20150032896A1
• Time in Patent Office: 1,055 Days
• Field of Search: 709223-229, 709232, 709250
• 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 of routing requests to hosts, the method comprising:

storing a model of a service framework organized in a hierarchy comprising;

a first level including a plurality of leaf nodes, individual leaf nodes corresponding to one of a plurality of hosts, and

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

for individual service requests to be processed by a host of the plurality of hosts;

receiving a service request;

discovering a plurality of candidate hosts from the plurality of the leaf nodes for processing the request;

assigning a selection probability to individual candidate hosts of the plurality of candidate hosts based, at least in part, on a probabilistic distribution of measured latency data for the plurality of candidate hosts;

selecting a candidate host for servicing the service request based, at least in part, on the assigned selection probability; and

routing the service request to the selected candidate host.

2. The method as recited in claim 1, 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 leaf nodes, the first plurality of zones, and the second plurality of zones.

3. The method as recited in claim 1, wherein routing the service request to the selected candidate host includes routing the service request directly to the selected candidate host.

4. The method as recited in claim 1, wherein routing the service request to the selected candidate host includes routing the service request to the selected candidate host via at least one proxy host.

5. The method as recited in claim 1, wherein the latency data corresponds to at least one of a network latency, a redirection latency or a service latency.

6. The method as recited in claim 1, wherein the selection probability of individual candidate hosts is an assigned weighting based on the measured latency data.

7. The method as recited in claim 6, wherein the assigned weightings correspond to measured latencies for each of the plurality of candidate hosts.

8. A system comprising:

a plurality of host computing devices for responding to requests, wherein the plurality of host computing devices are organized in a hierarchy comprising;

a first level including a plurality of leaf nodes, wherein individual leaf nodes correspond to one of the plurality of 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;

wherein the system is configured to;

for individual service requests to be processed by a host computing device of the plurality of host computing devices,

discover a plurality of candidate host computing devices from the leaf nodes for processing the request;

select a candidate host computing device based, at least in part, on a probabilistic distribution of measured latency data for the plurality of candidate hosts; and

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

9. The system as recited in claim 8, 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 which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

10. The system as defined in claim 8, wherein the plurality of host computing devices are heterogeneous and have different processing capacities, and wherein the system is configured to account for the processing capacities of the plurality of host computing devices when making routing decisions.

11. The system as recited in claim 10, wherein the system is further configured to assign weightings for the plurality of candidate hosts based on the measured latency data.

12. The system as recited in claim 11, wherein the assigned weightings correspond to measured latencies for each of the plurality of candidate hosts.

13. The system as recited in claim 10, wherein the system is configured to acquire the measured latency data for individual host computing devices of the plurality of host computing devices.

14. The system as recited in claim 13, wherein the measured latency data is distributed according to a peer-to-peer distribution model.

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

responsive to a service request, discover a set of candidate host computing devices, the set of candidate host computing devices being a subset of a plurality of host computing devices, the plurality of host computing devices organized in a hierarchy comprising;

a first level including a plurality of leaf nodes, individual leaf nodes corresponding to one of the plurality of host computing devices; and

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

select a candidate host computing device of the plurality of host computing devices based, at least in part, on a probabilistic distribution of measured latency data for the set of candidate host computing devices; and

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

16. The non-transitory computer-readable medium as recited in claim 15, 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 which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

17. The non-transitory computer-readable medium as recited in claim 15, wherein the plurality of host computing devices are heterogeneous and have different processing capacities, and wherein the configured computer-executable instructions further configure the computing device to account for the processing capacities of the plurality of computing devices when making routing decisions.

18. The non-transitory computer-readable medium as recited in claim 15, wherein the computer-executable instructions further configure the computing to acquire measured latency data for individual host computing devices of the plurality of host computing devices.

19. The non-transitory computer-readable medium as recited in claim 18, wherein the measured latency data is distributed according to a peer-to-peer distribution model.

20. The non-transitory computer-readable medium as recited in claim 18, wherein the computer-executable instructions further configure the computing device to assign weightings for the plurality of host computing devices based on the measured latency data.