# US 10,320,680 B1 · Load balancer that avoids short circuits > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,320,680 B1 - Document ID: US10320680B1 - Status: Granted - Kind: B1 - Application number: 14/932,580 - Filed: 2015-11-04 - Granted: 2019-06-11 - Earliest claimed: 2015-11-04 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Nima Sharifi Mehr - Web page: https://patentgrep.com/patent/US10320680B1 ## CPC - H04L 47/125: by balancing the load, e.g. traffic engineering - H04L 43/106: using time related information in packets, e.g. by adding timestamps - H04L 47/283: in response to processing delays, e.g. caused by jitter or round trip time [RTT] - H04L 67/1001: for accessing one among a plurality of replicated servers - H04L 67/1008: based on parameters of servers, e.g. available memory or workload (monitoring of computer activity G06F11/30) - H04L 67/1034: Reaction to server failures by a load balancer - H04L 67/30: Profiles - H04L 69/16: Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP] - H04L 43/0852: Delays - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Network devices, such as load balancers may be configured to route requests to hosts that are responding in a shorter period of time than other hosts. Sometimes hosts respond in shorter periods of time due to errors (they short-circuit). Such behavior may cause a spike in failed requests and increase the impact of a host malfunction. Disclosed is an enhanced load balancing algorithm that reduces request loads to hosts that are responding to request more quickly than expected or historically observed. A load balancer tracks the hosts' performance. Upon detecting response times shorter than expected from a host, the load balancer will reduce the load on the host. The request routing will go back to normal distribution after the host behaving according to its known performance profile. ## Claims ### Claim 1 A system, comprising: a fleet of back-end nodes implemented by a back-end system; and one or more load balancers configured to: determine a historical response time profile for individual back-end nodes of the fleet of back-end nodes; track recent response times for individual back-end nodes of the fleet of back-end nodes; determine a pool of eligible back-end nodes from the fleet of back-end nodes based at least in part on: a comparison of the respective recent response times for each back-end node compared to a short response time threshold for the back-end node, wherein the short response time threshold is based on the respective historical response time profile for the back-end node; and wherein back-end nodes having recent response times faster than the respective short response time thresholds are excluded from the pool of eligible back-end nodes; for a request received by the one or more load balancers from a client: select, from the pool of eligible back-end nodes and in accordance with a load balancing mechanism, a back-end node to handle the request, wherein the pool of eligible back-end nodes from which the back-end node is selected excludes back-end nodes having recent response times faster than the respective short response time thresholds; send the request to the selected back-end node; receive a response to the request; and forward the response to the client. ### Claim 2 (depends on 1) The system of claim 1, wherein to determine the historical response time profile for individual back-end nodes of the fleet of back-end nodes, the one or more load balancers are further configured to: for a plurality of requests received by the one or more load balancers: select respective back-end nodes to handle the requests according to a load balancing mechanism; assign respective timestamps to the respective requests; send the requests to the selected back-end nodes; receive respective responses from the selected back-end nodes; determine response times for the respective responses, and forward the respective responses to respective clients; and update a running average of recent response times for respective back-end nodes. ### Claim 3 (depends on 2) The system of claim 2, wherein the one or more load balancers are further configured to update the respective historical response time profile for respective back-end nodes based at least in part on the respective updated running average. ### Claim 4 (depends on 1) The system of claim 1, wherein the one or more load balancers are further configured to: continue to track response times for back-end nodes that are excluded from the pool of eligible back-end nodes; and include an excluded back-end node in the pool of eligible back-end nodes when the excluded back-end node exhibits response times above the respective short response time threshold. ### Claim 5 A process, comprising: performing by one or more load balancers: determining a pool of eligible back-end nodes from a fleet of back-end nodes based at least in part on: comparing respective recent response times for each back-end node of the fleet of back-end nodes compared to a short response time threshold for the respective back-end node, wherein the short response time threshold is based at least in part on one or more characteristics of the back-end node; and excluding back-end nodes having recent response times faster than the respective short response time thresholds from the pool of eligible back-end nodes; for requests received by the one or more load balancers from one or more clients: selecting, from the pool of eligible back-end nodes and in accordance with a load balancing mechanism, respective back-end nodes to handle the requests, wherein the pool of eligible back-end nodes from which the back-end node is selected excludes back-end nodes having recent response times faster than the respective short response time thresholds; and sending the requests to the respective selected back-end nodes. ### Claim 6 (depends on 5) The process recited in claim 5, further comprising: assigning a timestamp to a request and sending the request to a given back-end node of the fleet of back-end nodes; receiving a response from the given back-end node; determining a response time for the request based at least in part on the timestamp; and storing the determined response time to a data store. ### Claim 7 (depends on 6) The process recited in claim 6, further comprising updating a running average of recent response times for the given back-end node based at least in part on the determined response time. ### Claim 8 (depends on 7) The process recited in claim 7, wherein the short response time threshold is based at least in part on a historical response time profile for the given back-end node, the process further comprising updating the historical response time profile for the given back-end node based at least in part on the running average of recent response times. ### Claim 9 (depends on 8) The process recited in claim 8, wherein the updated historical response time profile for the given back-end node is used to determine eligibility of the given back-end node for the pool of eligible back-end nodes. ### Claim 10 (depends on 5) The process recited in claim 5, the process further comprising: receiving respective responses to the requests; and forwarding the respective responses to the respective clients. ### Claim 11 (depends on 5) The process recited in claim 5, wherein the short response time threshold is based at least in part on a historical response time profile for the given back-end node, and wherein the historical response time profiles for individual back-end nodes of the fleet of back-end nodes are set to known response times for a particular type of back-end node. ### Claim 12 (depends on 5) The process recited in claim 5, wherein subsequent to said determining the pool of eligible back-end nodes from the fleet of back-end nodes based on said comparing, said selecting respective back-end nodes in accordance with the load balancing mechanism includes routing more requests to back-end nodes of the pool with shorter recent response times than to back-end nodes of the pool with longer recent response times. ### Claim 13 A non-transitory computer-readable medium storing program instructions that are executed by one or more processors to implement a load balancer configured to: in response to a request, select a back-end node from a fleet of back-end nodes to service the request based at least in part on: a historical response time profile; and a current response time; wherein a load balancer mechanism for selecting the back-end node specifies that a back-end node with a current response time faster than a short response time threshold has a lower probability of selection than a back-end node with a current response time greater than the short response time threshold. ### Claim 14 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein the load balancer is further configured to: determine the respective historical response time profiles for the back-end nodes, wherein determine includes: assign a timestamp to a request and send the request to a given back-end node of the fleet of back-end nodes; receive a response from the given back-end node; determine a response time for the received request based at least in part on the timestamp; and update a running average of recent response times for the given back-end node. ### Claim 15 (depends on 14) The non-transitory computer-readable medium of claim 14, wherein the load balancer is further configured to update the respective historical response time profile for the given back-end node based at least in part on the updated running average. ### Claim 16 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein to specify that the back-end node with the current response time faster than the short response time threshold is assigned the lower probability of selection than the back-end node with the current response time greater than the short response time threshold, the load balancer is configured to weight back-end nodes according to response times, and wherein nodes with shorter times are weighted so as to be more likely to be selected. ### Claim 17 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein the load balancer is further configured to: continue to track response times for back-end nodes with current response times faster than a short response time threshold; and increase the probability of selection for a particular back-end node of the back-end nodes with current response times faster than a short response time threshold when the particular back-end node exhibits improved health. ### Claim 18 (depends on 13) The non-transitory computer-readable medium of claim 13, wherein the load balancer is further configured to route more requests to back-end nodes with relatively shorter recent response times than to back-end nodes with relatively longer recent response times. ### Claim 19 (depends on 13) The non-transitory computer readable medium of claim 13, wherein to perform said select respective back-end nodes to handle the requests, the load balancer is further configured use responses to TCP or HTTP pings to identify back-end nodes that are unable to process requests. ### Claim 20 (depends on 13) The non-transitory computer readable medium of claim 13, wherein the respective historical response time profile for the back-end node includes a number of open connections for the back-end node, a time of day, a type of request, a requestor id, or an origin of a request; and wherein the short response time threshold is based at least in part on the number of open connections for the back-end node, the time of day, the type of request, a requestor id, or the origin of the request.