Dynamic resource allocation using known future benefits

• US 20030105868A1
• Filed: 12/04/2001
• Published: 06/05/2003
• Est. Priority Date: 12/04/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thathachar, Jayram S., Krauthgamer, Robert, Schieber, Baruch M., Sviridenko, Maxim I., Kimbrel, Tracy J.
• Granted Patent: US 7,085,837 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A benefit task system implements a policy for allocating resources to yield some benefit. The method implemented may be applied to a variety of problems, and the benefit may be either tangible (e.g., profit) or intangible (e.g., customer satisfaction). In one example, the method is applied to server allocation in a Web site server “farm” given full information regarding future loads to maximize profits for the Web hosting service provider. In another example, the method is applied to the allocation of telephone help in a way to improve customer satisfaction. In yet another example, the method is applied to distributed computing problem where the resources to be allocated are general purpose computers connected in a network and used to solve computationally intensive problems. Solution of the Web server “farm” problem is based on information regarding future loads to achieve close to the greatest possible revenue based on the assumption that revenue is proportional to the utilization of servers and differentiated by customer class. The method of server allocation uses an approach which reduces the Web server farm problem to a minimum-cost network flow problem, which can be solved in polynomial time. Similar solutions are applicable to other resource allocation problems.

Claims

1. A method of resource allocation to yield a benefit comprising the steps of:

generating an input time-customer matrix of demands for resources where a benefit function is known in advance; and

producing from the input matrix an output time-customer matrix of allocations of resources to customers to realize a benefit.

2. The method of resource allocation as recited in claim 1, wherein resource allocation is done to maximize a benefit.

3. The method of resource allocation as recited in claim 1, wherein the benefit is a tangible benefit.

4. The method of resource allocation as recited in claim 3, wherein the tangible benefit is a profit and resource allocation is done to maximize the profit.

5. The method of resource allocation as recited in claim 1, wherein the benefit is an intangible benefit.

6. The method of resource allocation as recited in claim 5, wherein the intangible benefit is customer satisfaction and resource allocation is done to maximize customer satisfaction.

7. The method of resource allocation as recited in claim 1, wherein the resource is computer cycles and resource allocation is done to more efficiently solve computationally intensive problems.

8. A method of resource allocation to yield a benefit comprising the steps of:

choosing a state s_i, for each time t so as yield a benefit where all the state sets and the benefit function are known in advance;

reducing the problem to the analogous maximum-cost network flow problem by

constructing a directed network with s “

rails”

, one per site, each rail being a chain of edges each representing one time step, flow along a rail representing an allocation of resources to a corresponding site,

constructing a set of “

free pool”

nodes, one per time step, through which flow will pass when resources are reallocated from one site to another,

for a demand matrix d_{i, t}, 1≦

i≦

s, 1≦

t≦

T, constructing nodes n_{i, t}, 1≦

i≦

s, 0≦

t≦

T, along with nodes f_t, 1≦

t≦

T, and for each site s and each time step t, constructing three edges from n<sub>i, t−

1</sub> to n_{i, t}, wherein the first edge has capacity └

d_{i, t}┘ and

cost r_{i, t}, the second edge has capacity one and cost r_{i, t}·

(d_{i, t}−

└

d_{i, t}┘

), and the third edge has infinite capacity and cost zero, flow along the first edge representing a benefit of allocating resources s to site i during time step t, up to the integer part of d_{i, t}, flow along the second edge representing a remaining benefit, r_{i, t}, times a fractional part of d_{i, t} to be collected by one more resource, and flow along the third edge representing that extra resources can remain allocated to s but do not collect any benefit,

constructing edges of infinite capacity and cost zero from n<sub>i, t−

1</sub> to f_t and from f_i to n_{i, t}, for each 1≦

t≦

T and each 1≦

i≦

s which represent a movement of servers from one site to another,

constructing a source into which a flow k is injected, with infinite capacity zero cost edges to each n_{i, 0}, and a sink with infinite capacity zero cost edges from each n_{i, T}; and

solving the maximum-cost network flow problem and allocating resources.

9. The method of resource allocation as recited in claim 8, wherein resource allocation is done to maximize a benefit.

10. The method of resource allocation as recited in claim 8, wherein the benefit is a tangible benefit.

11. The method of resource allocation as recited in claim 10, wherein the tangible benefit is a profit and resource allocation is done to maximize the profit.

12. The method of resource allocation as recited in claim 8, wherein the benefit is an intangible benefit.

13. The method of resource allocation as recited in claim 12, wherein the intangible benefit is customer satisfaction and resource allocation is done to maximize customer satisfaction.

14. The method of resource allocation as recited in claim 8, wherein the resource is computer cycles and resource allocation is done to more efficiently solve computationally intensive problems.

15. A method for server allocation in a Web server “

farm”

based on information regarding future loads to achieve close to greatest possible revenue based on an assumption that revenue is proportional to the utilization of servers and differentiated by customer class comprising the steps of;

modeling the server allocation problem mathematically;

in the model, dividing time into intervals of fixed length based on the assumption that each site'"'"'s demand is uniformly spread throughout each such interval;

maintaining server allocations fixed for the duration of an interval, servers being reallocated only at the beginning of an interval, and a reallocated server being unavailable for the length of the interval during which it is reallocated providing time to “

scrub”

the old site (customer data) to which the server was allocated, to reboot the server and to load the new site to which the server has been allocated, each server having a rate of requests it can serve in a time interval and customers share servers only in the sense of using the same servers at different times, but do not use the same servers at the same time;

associating each customer'"'"'s demand with a benefit gained by the service provider in case a unit demand is satisfied and finding a time-varying server allocation that would maximized benefit gained by satisfying sites'"'"' demand; and

reducing to a minimum-cost network flow problem and solving in polynomial time.