System and method for routing service requests

• US 8,037,186 B2
• Filed: 03/06/2009
• Issued: 10/11/2011
• 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): Maung; Zarni
• Application Number:
  US12/399,881
• Publication Number:
  US 20090172191A1
• Time in Patent Office: 949 Days
• Field of Search: 709223-229, 709/250, 709/232, 719/105
• US Class Current: 709/226
• 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 service requests, comprising:

receiving, by a first candidate host, a service request, wherein the first candidate host is operable to service the service request;

discovering a plurality of candidate hosts operable to respond to the service request;

obtaining latency data corresponding to one or more of the plurality of candidate hosts, wherein the latency data corresponds to at least one of a network latency, a redirection latency and a service latency;

obtaining latency data associated with the first candidate host;

determining whether the service request should be serviced by the first candidate host or routed to one or more of the plurality of candidate hosts, wherein the determination is based on a probabilistic distribution of the first candidate host and each of one or more of the plurality of candidate hosts corresponding to the latency data associated with the first candidate host and the latency data corresponding to one or more of the plurality of candidate hosts; and

in response to the determination of whether the service request should be serviced by the first candidate host or routed to one or more of the plurality of candidate hosts, servicing the service request by the first candidate host.

2. The method as recited in claim 1, wherein discovering the plurality of candidate hosts includes accessing information about a hierarchy of hosts, the plurality of candidate hosts being logically defined as having locations within the hierarchy of hosts.

3. The method as recited in claim 1, wherein determining whether the service request should be serviced by the first candidate host or routed to one or more of the plurality of candidate hosts includes assigning weightings to the first candidate host and each of the one or more of the plurality of candidate hosts.

4. The method as recited in claim 3, wherein the assigned weightings correspond to measured latencies for the first candidate host and each of the plurality of candidate hosts.

5. The method as recited in claim 1, wherein determining whether the service request should be serviced by the first candidate host or routed to one or more of the plurality of candidate hosts includes:

obtaining load information from the first candidate host and each of the one or more of the plurality of candidate hosts; and

determining a latency based on the load information obtained from the first candidate host and each of the one or more of the plurality of candidate hosts.

6. The method as recited in claim 5 further comprising processing the load information based on at least one predictor.

7. The method as recited in claim 6, wherein the predictor is a linear fit predictor.

8. The method as recited in claim 6, wherein the predictor is an exponential smoothing predictor.

9. The method as recited in claim 1 further comprising determining whether the service request should be serviced by the first candidate host or routed to one or more of the plurality of candidate hosts according to a physical topology of the candidate hosts.

10. The method as recited in claim 1 further comprising determining whether the service request should be serviced by the first candidate host or routed to one or more of the plurality of candidate hosts according to heterogeneity information associated with the candidate hosts.

11. The method as recited in claim 1, wherein the plurality of candidate hosts are hierarchically organized into a hierarchy comprising (i) a first level including a plurality of leaf nodes, each of the leaf nodes corresponding to one of hosts, and (ii) a second level including a first plurality of zones which each comprise a subset of the plurality of leaf nodes.

12. The method as recited in claim 11, wherein the hierarchy further comprises (iii) a third level including a second plurality of zones which each comprise a subset of the first plurality of zones, and (iv) a fourth level including a root node which comprises the leaf nodes, the first plurality of zones, and the second plurality of zones.

13. The method as recited in claim 1, wherein the latency data associated with the first candidate host includes a service latency for servicing the request at the first candidate host.

14. The method as recited in claim 13, wherein the latency data associated with each of one or more of the plurality of candidate hosts includes at least one of a network latency and a service latency associated with servicing the request at the respective candidate host.

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

responsive to a service request at a first candidate host, discover a set of candidate host computers, the set of candidate host computers being a subset of the plurality of available computers;

determine whether the service request should be serviced by the first candidate host or routed to one or more candidate host computers of the set of candidate host computers, the determination based on a probabilistic distribution, the probabilistic distribution corresponding to latencies associated with the first candidate host and each of the one or more candidate host computers of the set of candidate host computers; and

responsive to the determination of whether the service request should be serviced by the first candidate host or routed to one or more candidate host computers of the set of candidate host computers, service route the service request at the determined first candidate host or one or more candidate host computers of the set of candidate host computers.

16. The non-transitory computer accessible medium as recited in claim 15, wherein the plurality of available computers are organized in a hierarchy which comprises a first level including a plurality of leaf nodes, each of the leaf nodes corresponding to one of the plurality of host computers, and a second level including a first plurality of zones which each comprise a subset of the plurality of leaf nodes.

17. The non-transitory computer accessible medium as recited in claim 15, wherein the latencies associated with each of the one or more candidate computers of the set of candidate computers include a latency associated with a direct server response.

18. The non-transitory computer accessible medium as recited in claim 15, wherein the determination of whether the service request should be serviced by the first candidate host or routed to one or more candidate host computers of the set of candidate host computers is based on a comparison of vector latencies associated with the first candidate host and each candidate host computer of the set of candidate host computers.

19. The non-transitory computer accessible medium as recited in claim 15, wherein the latencies associated with the first candidate host include a service latency associated with servicing the request at the candidate host.

20. The non-transitory computer accessible medium as recited in claim 19, wherein the latencies associated with each of the one or more host candidate computers of the set of host candidate computers include at least one of a network latency and a service latency associated with servicing the request at the respective host candidate computer.