US 10,855,808 B1Granted

Intelligent load balancer

AssigneeServiceNow, Inc.

InventorsAmitav Mohanty, Sreenivas Durvasula

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques for routing requests on a network are described. In accordance with certain aspects, a temporal window is incremented or moved over time to facilitate dynamic routing decisions. The temporal window may be used to project or estimate incoming request traffic based on a suitable probabilistic distribution model, such as a Poisson or Gaussian probability distribution, applied to the window so as to estimate or predict traffic at different times as the window is incremented. Estimated execution times for incoming requests may also be computed so that arrival and completion times of each request or traffic event can be modeled. Processor-implemented routines may be employed to solve the sub-problems defined by the temporal window incoming traffic estimation and the estimated execution times efficiently, allowing the parent or overall routing decision problem to be solved efficiently using dynamic processes, including in real-time contexts.

Claims20

Dependent claims

A cloud platform, comprising:

a data center comprising a plurality of application servers;
a client network comprising a plurality of client devices, wherein the plurality of client devices generate requests to be processed by the application servers;
a network over which the requests travel between the client network and the data center;
and
one or more load balancers configured to route the requests among the application servers using a priority tree based on predicted network events, wherein the one or more load balancers generate and use the priority tree by performing acts comprising:
generating a temporal window having a width corresponding to a time interval;
sliding the temporal window in increments through a series of future times;
for each future time in the series, applying a probabilistic model to the temporal window to determine a probable number of expected requests of a respective request type at the respective future time within the time interval encompassed by the temporal window;
based upon the probable number of expected requests of the respective request type for each future time in the series, executing a bin packing routine to generate the priority tree comprising nodes corresponding to expected requests and expected request types;
assigning requests received over time at the one or more load balancers to a respective node of the priority tree, wherein the expected request and expected request type that correspond to the respective node are matched to the request and a type of the request;
based on the assignment of a respective request to the respective node, routing the respective request to a respective application server;
and
updating the probabilistic model based on a number of nodes corresponding to expected requests and expected request types that were not assigned requests.

10 more elements

A load balancer, comprising:

a processing component configured to execute stored routines;
and
a memory component configured to store executable routines, wherein the executable routines, when executed by the processing component, cause the processing component to perform acts comprising:
sliding a temporal window forward in time in specified time increments, wherein the temporal window has a width corresponding to a time interval;
as the temporal window slides forward in time, determining an expected number of requests for each of one or more request types at each time corresponding to a respective time increment to which the temporal window slides;
executing a bin packing routine to generate a priority tree comprising nodes based on the expected number of requests for each of one or more request types at different future times, wherein each node corresponds to an expected request of a respective request type at a future time;
as requests are received over time, assigning each request to a respective node of the priority tree, wherein an expected request and expected request type that correspond to the respective node are matched to the request and a type of the request, and wherein assignment of a respective request corresponds to the respective request being routed to a network resource associated with the respective node;
and
updating the determination of the expected number of requests based on a number of nodes not being assigned requests.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/504,044Filed 5 Jul 2019
Granted: 1 Dec 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06F 9/505
The resource being a machine, e.g. CPUs, Servers, Terminals: considering the load
H04L 67/63
Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and…: routing…
H04L 41/145
Network analysis or design: involving simulating, designing, planning or modelling of a network
H04L 47/125
Avoiding congestion; Recovering from congestion: by balancing the load, e.g. traffic engineering