# US 2012/0254444 A1 · Dynamic capacity management of multiple parallel-connected computing resources

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

- Number: US 2012/0254444 A1
- Document ID: US20120254444A1
- Status: Published application
- Kind: A1
- Application number: 13/436,271
- Filed: 2012-03-30
- Published: 2012-10-04
- Earliest claimed: 2011-04-01
- Assignees: Carnegie Mellon University
- Inventors: Mor Harchol-Balter; Anshul Gandhi; Varun Gupta; Michael Kozuch
- Web page: https://patentgrep.com/patent/US20120254444A1

## CPC

- G06F 9/06: using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F 2209/5019: Workload prediction
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A dynamic capacity management policy for multi-paralleled computing resources (e.g., application servers, virtual application servers, etc.) that includes one or more of a state-change component, a load-balancing component, and a robustness-control component. The state-change component delays the release (e.g., powering down of a physical server, removal from a virtual-server lease, etc.) of each computing resource for a set amount of time. The load-balancing component can work in conjunction with the state-change component to reduce the number of idle computing resources by distributing incoming requests in a manner that keeps the already-processing computing resources as full of requests as possible. The robustness-control component scales capacity as a function of the current number of requests within the system of computing resources to account for variations other than request rate, such as request size, reduced processor frequency, network slowdowns, etc., that affect processing capacity.

## Claims

### Claim 1

A method of controlling a plurality of computing resources each having a lower-setup-cost state and a higher-setup-cost state, comprising:
arranging the plurality of computing resources so that each is capable of processing at least a share of an incoming request stream; and
controlling each of the plurality of computing resources so that each switches from the lower-setup-cost state to the higher-setup-cost state as a function of a timing-out of a state-change delay timer that is initiated when that computing resource is idled.

### Claim 2 (depends on 1)

A method according to claim 1, further comprising distributing new arrivals in the incoming request stream to individual computing resources as a function of a packing factor.

### Claim 3 (depends on 2)

A method according to claim 2, wherein said distributing new arrivals includes distributing new arrivals so as to optimize packing of the ones of the plurality of computing resources that are in the lower-setup-cost state.

### Claim 4 (depends on 3)

A method according to claim 3, further comprising indexing the ones of the plurality of computing resources in the lower-setup-cost state, said distributing new arrivals as a function of the indexing and the packing factor.

### Claim 5 (depends on 4)

A method according to claim 4, wherein said distributing new arrivals as a function of said indexing and the packing factor includes distributing new arrivals to the lowest index-numbered one of the computing resources in the lower-setup-cost state having fewer requests than the packing factor.

### Claim 6 (depends on 1)

A method according to claim 1, further comprising determining a minimum number, kreqd, of the plurality of computing resources to be in the lower-setup-cost state and overriding ones of the state-change delay timers as needed to keep the minimum number of the plurality of computing resources in the lower-setup-cost state.

### Claim 7 (depends on 6)

A method according to claim 6, wherein said determining includes determining kreqd as a function of a total number of requests currently distributed among the plurality of computing resources.

### Claim 8 (depends on 7)

A method according to claim 7, wherein said determining includes determining kreqd further as a function of a packing factor and a number, k, of the plurality of computing resources currently in the lower-setup-cost state.

### Claim 9 (depends on 8)

A method according to claim 8, wherein:
kreqd=k·(psrv/pref)
where:
psrv=an average request size multiplied by a request rate into one of the plurality of computing resources, as based on k and the total number of requests currently distributed among the plurality of computing resources, and
pref=the packing factor multiplied by the average request size.

### Claim 10 (depends on 1)

A method according to claim 1, further comprising setting each state-change delay timer as a function of an arrival rate of the incoming request stream.

### Claim 11

A processing system for processing an incoming request stream, comprising:
a plurality of computing resources each capable of processing at least a share of the incoming request stream and having a lower-setup-cost state and a higher-setup-cost state;
a load balancer designed and configured to distribute new arrivals within the incoming request stream among said plurality of computing resources; and
a state-change delay timer for each of said plurality of computing resources;
wherein:
said state-change delay timer is designed and configured to start running as a function of the corresponding one of said plurality of computing resources becoming idle; and
the corresponding one of said plurality of computing resources is switched from said lower-setup-cost state to said higher-setup-cost state as a function of a timing-out of said state-change delay timer.

### Claim 12 (depends on 11)

A system according to claim 11, wherein each of said plurality of computing resources has a packing factor and said load balancer is designed and configured to distribute new arrivals within the incoming request as a function of said packing factor.

### Claim 13 (depends on 12)

A system according to claim 12, wherein said load balancer is designed and configured to distribute new arrivals so as to optimize packing of the ones of the plurality of computing resources that are in the lower-setup-cost state.

### Claim 14 (depends on 13)

A system according to claim 13, wherein said load balancer is designed and configured to, when the system is operating, create an index of the ones of said plurality of computing resources in the lower-setup-cost state and distribute new arrivals as a function of said index and said packing factor.

### Claim 15 (depends on 14)

A system according to claim 14, wherein said load balancer is designed and configured to, when the system is operating, distribute new arrivals to a lowest index-numbered one of said computing resources in said lower-setup-cost state having fewer requests than the packing factor.

### Claim 16 (depends on 11)

A system according to claim 11, further comprising a robustness controller designed and configured to determine a minimum number, kreqd, of said plurality of computing resources to be in said lower-setup-cost state and override ones of said state-change delay timers as needed to keep the minimum number of said plurality of computing resources in said lower-setup-cost state.

### Claim 17 (depends on 16)

A system according to claim 16, wherein said robustness controller is designed and configured to determine kreqd as a function of a total number of requests currently distributed among said plurality of computing resources.

### Claim 18 (depends on 17)

A system according to claim 17, wherein said robustness controller is designed and configured to determine kreqd further as a function of a packing factor and a number, k, of said plurality of computing resources currently in said lower-setup-cost state.

### Claim 19 (depends on 18)

A system according to claim 18, wherein:
kreqd=k·(psrv/pref)
where:
psrv=an average request size multiplied by a request rate into one of said plurality of computing resources, as based on k and the total number of requests currently distributed among said plurality of computing resources, and
pref=the packing factor multiplied by the average request size.

### Claim 20 (depends on 11)

A system according to claim 11, further comprising a timer controller in operative communication with each of said plurality of computing resources and designed and configured to set each state-change delay timer as a function of an arrival rate of the incoming request stream.

### Claim 21

A machine readable storage medium containing machine-executable instructions for controlling a plurality of computing resources in processing an incoming request stream, wherein each of the plurality of computing resources has a lower-setup-cost state and a higher-setup-cost state, said machine-executable instructions comprising:
a first set of machine-executable instructions for distributing new arrivals in the incoming request stream as a function of a packing factor.

### Claim 22 (depends on 21)

A machine-readable storage medium according to claim 21, wherein said machine-executable instructions further includes machine-executable instructions for optimizing packing of the ones of the plurality of computing resources that are in the lower-setup-cost state.

### Claim 23 (depends on 22)

A machine-readable storage medium according to claim 22, wherein said machine-executable instructions further includes machine-executable instructions for indexing the ones of the plurality of computing resources in the lower-setup-cost state and distributing new arrivals as a function of the indexing and the packing factor.

### Claim 24 (depends on 23)

A machine-readable storage medium according to claim 23, wherein said machine-executable instructions further includes machine-executable instructions for distributing new arrivals to the lowest index-numbered one of the computing resources in the lower-setup-cost state having fewer requests than the packing factor.

### Claim 25 (depends on 21)

A machine-readable storage medium according to claim 21, wherein each of the plurality of computing resources has a state-change delay timer and said machine-executable instructions further includes machine-executable instructions for determining a minimum number, kreqd, of the plurality of computing resources to be in the lower-setup-cost state and overriding ones of the state-change delay timers as needed to keep the minimum number of the plurality of computing resources in the lower-setup-cost state.

### Claim 26 (depends on 25)

A machine-readable storage medium according to claim 25, wherein said machine-executable instructions further includes machine-executable instructions for determining kreqd as a function of a total number of requests currently distributed among the plurality of computing resources.

### Claim 27 (depends on 26)

A machine-readable storage medium according to claim 26, wherein said machine-executable instructions further includes machine-executable instructions for determining kreqd further as a function of a packing factor and a number, k, of the plurality of computing resources currently in the lower-setup-cost state.

### Claim 28 (depends on 27)

A machine-readable storage medium according to claim 27, wherein said machine-executable instructions further includes machine-executable instructions for executing the equation
kreqd=k·(psrv/pref)
where:
psrv=an average request size multiplied by a request rate into one of the plurality of computing resources, as based on k and the total number of requests currently distributed among the plurality of computing resources, and
pref=the packing factor multiplied by the average request size.

### Claim 29 (depends on 21)

A machine-readable storage medium according to claim 21, wherein each of the plurality of computing resources has a state-change delay timer and said machine-executable instructions further include machine-executable instructions for setting each state-change delay timer as a function of an arrival rate of the incoming request stream.
