Dynamic resource allocation using known future benefits

• US 7,765,301 B1
• Filed: 02/13/2006
• Issued: 07/27/2010
• Est. Priority Date: 12/04/2001
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Thathachar, Jayram S., Krauthgamer, Robert, Minkoff, Maria, Schieber, Baruch M., Sviridenko, Maxim I., Kimbrel, Tracy J.
• Primary Examiner(s): BOUTAH, ALINA A
• Application Number:
  US11/352,328
• Time in Patent Office: 1,625 Days
• Field of Search: 709/226, 709/225, 705 7- 10
• 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 computer implemented method of resource allocation to yield benefit comprising the steps of:

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

producing from the input matrix an output matrix of allocations of resources to customers to realize a benefit, wherein said output matrix is indexed by customers and time periods;

during a time interval, reallocating a resource from a first customer to a second customer and making the resource unavailable to any customer during the time interval that the resource is being allocated to the second customer, wherein the step of making the resource unavailable comprises including a step of making the resource which is a server unavailable to any customer during the time interval that the resource is being allocated to the second customer, wherein the time interval is set to equal a non-negligible amount of time required for the server to prepare to serve a new customer.

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. The method of claim 1, including generating an input matrix of customer demands for telephone operator resources.

9. The method of claim 1, including generating an input matrix of customer demands for resources which are servers.

10. The method of claim 1, wherein the step of making the resource unavailable to any customer comprises making the resource unavailable to any customer for a time on an order of 5 or 10 minutes.