US 11,381,639 B1 · Load balancing technique selection based on estimated load

Abstract

Request routing in a network of computing devices. Back-end nodes associated with a request router send load reports to request routers. To select a back-end node for processing a request, a request router determines, based on the reports, estimated loads and corresponding errors of the estimated loads for respective nodes. A load balancing technique may be selected, based on the estimated loads and corresponding errors (e.g., round robin may be selected if the significance of an average error outweighs the difference between estimated load values for the nodes, or least estimated load may be selected of the difference between load values is greater than the average error). The selected technique is applied to choose one of the nodes to process the request. Load probability distribution may also be used for request routing, in combination with or separate from the selection based on the estimated loads.

Claims20

Dependent claims

A system, comprising:

a plurality of computers configured to host a plurality of back-end nodes to process requests from a plurality of clients;
and
a plurality of computers configured to host a plurality of request routers, wherein individual ones of the plurality of request routers are configured to:
receive an indication of a request to be routed for a client of the plurality of clients;
determine, for individual back-end nodes of a group of the plurality of back-end nodes, an estimated current load and a corresponding error of the estimated current load;
determine, based on the determined estimated current load and corresponding error for individual back-end nodes of the group, whether to apply a least load technique or a round robin technique to select one of the back-end nodes from the group to receive the request;
apply the determined technique to choose one of the back-end nodes from the group;
and
indicate the back-end node chosen to receive the request.

6 more elements

A method, comprising:

performing, by a request router:
receiving an indication of a request to be routed for a client;
determining, for individual back-end node of a group of back-end nodes, an estimated current load and a corresponding error of the estimated current load;
selecting, based on the determined estimated current load and corresponding error for individual back-end nodes of the group, a technique from among multiple load balancing techniques to apply to choose one of the back-end nodes from the group to receive the request;
applying the selected technique to choose one of the back-end nodes from the group;
and
indicating the back-end node chosen to receive the request.

4 more elements

One or more non-transitory computer readable storage media storing program instructions that are executable on or across one or more processors to implement a request router configured to perform:

determining for a group of back-end nodes, in response to receipt of an indication of a request to be routed for a client, an estimated current load for individual ones of the back-end nodes in the group and a corresponding error of the estimated current load;
selecting, based on a respective estimated current load and respective error for individual back-end nodes of the group, a technique from among multiple load balancing techniques to apply to choose one of the back-end nodes from the group;
applying the selected technique to choose one of the back-end nodes from the group;
and
indicating the back-end node chosen to receive the request.

2 more elements

Dependencies are inferred from the claim text.

Load balancing technique selection based on estimated load

Life of this patent

Load balancing technique selection based on estimated load

Life of this patent

Abstract

Claims20