# US 2010/0169490 A1 · Load-balancing and technology sharing using lempel-ziv complexity to select optimal client-sets

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169490 A1
- Document ID: US20100169490A1
- Status: Published application
- Kind: A1
- Application number: 12/649,957
- Filed: 2009-12-30
- Published: 2010-07-01
- Earliest claimed: 2008-12-31
- Assignees: Cerner Innovation, Inc.
- Inventors: Douglas S. McNair
- Web page: https://patentgrep.com/patent/US20100169490A1

## CPC

- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Optimal assignment of clients to client-sets, resources to resource-sets, and client-sets to resource-sets in a server farm allows for periodic re-balancing of the load as client usership and concurrent-user activity fluctuate. Unique combinations of clients are generated as candidate client-sets, and historical load measurements for clients in each candidate client-set are summed. Summed loads for the candidate client-sets are compared against available resources of resource-sets. An objective function is employed to identify optimal assignment of clients to client-sets, resources to resource-sets, and client-sets to resource-sets.

## Claims

### Claim 1

A method for periodic or aperiodic software application resource allocation under one or more load-dependent resource constraints by dynamically reconfiguring assignment of one or more client organizations and their associated applications and userships as distinct combinations or client-sets, to servers in a manner whereby merits of each such combination are mathematically evaluated and ranked in advance of undertaking selection of optimal assignments or allocations, the method comprising:
describing a plurality of servers and a plurality of userships and applications as abstract sets of elements corresponding to the plurality of servers and a plurality of clients, users, and applications, respectively;
defining a set of possible distinct client-sets and their resource loads and a set of possible distinct configurations of resources as resource-sets having known capacities;
determining a feasibility for a given assignment of client-sets to resource-sets;
determining a feasibility for distributing the users and resource load between servers in each resource-set; and
dynamically reconfiguring allocations of clients to client-sets, resources to resource-sets, and client-sets to resource-sets based on an objective function to optimize the cost-efficiency of the allocations simultaneously with insuring SLA compliance of the allocations.

### Claim 2 (depends on 1)

The method of claim 1, wherein the objective function evaluates assignments of clients and resources from a previous time interval to a future time interval.

### Claim 3 (depends on 1)

The method of claim 1, wherein the method comprises, for each client-set, generating a bitstring or array in which nonzero elements denote time periods within which summed historical timestamped resource consumption rates and logged dutycycle values for the clients in the client-set exceeded a desirable maximum target dutycycle calculated for resources of a given resource-set.

### Claim 4 (depends on 3)

The method of claim 3, wherein the resources for a given resource-set evaluated for a given client-set have a different capacity and configuration than the actual resources on which logged historical values accrued for the client-set.

### Claim 5 (depends on 3)

The method of claim 3, wherein Lempel-Ziv complexity is calculated for the bitstring or array for each client-set.

### Claim 6 (depends on 5)

The method of claim 5, wherein the method comprises:
generating a plurality of distinct combinations of clients as client-sets;
generating a plurality of distinct combinations of resources as resource-sets;
for each client assigned to a client-set and resource-set, determining if the client's application mix and business rules can feasibly coexist with the application mix and business rules of other clients assigned to the client-set;
if it is determined that the application mix and business rules of clients within a given client-set can feasibly coexist, updating a table of candidate allocations to mark that client-set as feasible and include in subsequent calculations of resource assignment; and
if a client's application mix and business rules are not compatible with one or more other clients in the client-set, deleting that client from that client-set.

### Claim 7 (depends on 1)

The method of claim 1, wherein dynamically reconfiguring allocations of client-sets on resource-sets comprises:
defining a sum of resources consumed by the clients in each client-set;
defining a sum of resource capacities represented by the resources in each resource-set;
calculating Lempel-Ziv complexity for candidate allocations of client-sets to resource-sets; and
rank-ordering the candidate allocations of client-sets to resource-sets according to the Lempel-Ziv complexity.

### Claim 8

A computer storage medium storing computer-useable instructions that, when used by a computing device, cause the computing device to perform a method for allocating clients to client-sets, server resources to resource-sets, and client-sets to resource-sets, the method comprising:
generating a plurality of candidate client-sets from a plurality of clients, each candidate client-set comprising a unique combination of clients;
accessing historical resource utilization metrics for each client over a given time interval;
determining resource utilization loads for each candidate client-set over the given time interval based on the historical resource utilization metrics;
comparing the resource utilization loads for each candidate client-set against available resources to identify any time periods in which a resource utilization load would have exceeded a threshold for the available resources;
calculating a Lempel-Ziv complexity for each candidate client-set;
selecting client-sets and allocating the selected client-sets to resource-sets based at least in part on the Lempel-Ziv complexity determined for each candidate client-set.

### Claim 9 (depends on 8)

The computer storage medium of claim 8, wherein generating the plurality of candidate client-sets comprises employing a random-selection algorithm to generate a large number of random unique combinations of clients.

### Claim 10 (depends on 9)

The computer storage medium of claim 9, wherein generating the plurality of candidate client-sets further comprises using a Monte Carlo algorithm to select the candidate client-sets from the large number of random unique combinations of clients.

### Claim 11 (depends on 8)

The computer storage medium of claim 8, wherein comparing the resource utilization loads for each candidate client-set against available resources comprises generating a plurality of resource-sets from a plurality of resources, each resource-set comprising a unique combination of resources.

### Claim 12 (depends on 11)

The computer storage medium of claim 11, wherein the method further comprises generating a plurality of candidate client-set allocations to resource-sets.

### Claim 13 (depends on 12)

The computer storage medium of claim 12, wherein calculating the Lempel-Ziv complexity for each candidate client-set comprises calculating a Lempel-Ziv complexity for each of the plurality of candidate client-set allocations to resource-sets.

### Claim 14 (depends on 8)

The computer storage medium of claim 8, wherein the method further comprises generating, for each candidate client-set, a bitstring or array in which nonzero elements denote time periods in which a resource utilization load would have exceeded a threshold for the available resources.

### Claim 15 (depends on 14)

The computer-storage medium of claim 14, wherein the Lempel-Ziv complexity is calculated for each candidate client-set based on the bitstring or array for each candidate client-set.

### Claim 16 (depends on 8)

The computer storage medium of claim 8, wherein the method further comprises:
accessing information regarding existing client-sets including assignment of clients to each existing client-set;
determining resource utilization loads for each existing client-set over the given time interval based on the historical resource utilization metrics and the assignment of clients to each existing client-set;
comparing the resource utilization loads for each existing client-set against available resources to identify any time periods in which a resource utilization load would have exceeded a threshold for the available resources; and
calculating a Lempel-Ziv complexity for each existing client-set.

### Claim 17 (depends on 16)

The computer storage medium of claim 16, wherein the method further comprises:
determining whether to rebalance assignments of clients to client-sets and client-sets to resource-sets based at least in part on the Lempel-Ziv complexity calculated for each candidate client-set and each existing client-set;
if it is determined to not rebalance assignments, reauthorizing existing client-sets; and
if it is determined to rebalance assignment, selecting candidate client sets based at least in part on the Lempel-Ziv complexity determined for each candidate client-set.

### Claim 18 (depends on 8)

The computer-storage medium of claim 8, wherein the method is periodically repeated.