Offline resource allocation algorithms

• US 9,009,318 B2
• Filed: 01/11/2012
• Issued: 04/14/2015
• Est. Priority Date: 11/03/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rangarajan, Nikhil Devanur, Jain, Kamal, Wilkens, Christopher A., Sivan, Balasubramanian
• Primary Examiner(s): NGUYEN, THU HA T
• Application Number:
  US13/348,465
• Publication Number:
  US 20130117454A1
• Time in Patent Office: 1,189 Days
• Field of Search: 709/226, 370/254, 705/7.25, 705/14
• US Class Current: 709/226
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Various embodiments provide offline algorithms for resource allocation. A known set of “offline” requests may be matched to available resources using an online resource allocation algorithm that models the offline resource allocation problem as though the requests were received stochastically. Requests may be scaled and then sampled to provide random, stochastic input for the online resource allocation algorithm. For each request, resources are allocated to the request by evaluating multiple options based upon shadow costs assigned to resources associated with the different options. After each request is processed, an adjustment is made to the shadow costs for remaining resources to reflect differences in rates for allocation and/or consumption of the resources and the updated shadow costs are used for a subsequent request. A scaled resource allocation determined using sampled requests in this manner may be scaled back up to obtain a solution for the offline resource allocation problem.

Claims

1. A computer-implemented method comprising:

collecting data regarding a plurality of requests for resources available from a service provider;

sampling, from the plurality of requests, a number of requests less than all of the plurality of requests to simulate random input of requests;

applying an online resource allocation algorithm with the sampled requests as stochastic input, the online resource allocation algorithm configured to, for each request, match said request to resources by evaluating a difference between a profit value and cost computed for different allocation options using an objective function that accounts for shadow costs assigned to the resources corresponding to each of the different allocation options, the shadow costs including computed or estimated costs that are assigned on an individual basis to the resources; and

determining whether a feasible solution exists to match the sampled requests to the resources based at least in part on the online resource allocation algorithm.

2. The computer-implemented method of claim 1 further comprising:

retuning an indication of the feasible solution as a result when the feasible solution exits; and

returning an indication that there is no feasible solution as the result when the feasible solution does not exist.

3. The computer-implemented method of claim 1 further comprising:

storing data describing an allocation of the resources to the plurality of requests determined by applying the online resource allocation algorithm to the sampled requests; and

returning an indication of the allocation as a result when the feasible solution exists.

4. The computer-implemented method of claim 1, wherein the plurality of requests are collected in advance and stored in a request database.

5. The computer-implemented method of claim 1, wherein the applying comprises:

assigning the shadow costs to the resources available from the service provider;

updating the shadow costs associated with the resources after evaluating each request to reflect differences in rates of consumption for the resources; and

allocating resources to each request using the updated shadow costs determined based on evaluating previous requests.

6. The computer-implemented method of claim 1, wherein the applying comprises selecting an option for each request that maximizes a profit margin computed for the different allocation options using the shadow costs.

7. The computer-implemented method of claim 1, further comprising scaling the plurality of requests according to a scaling factor.

8. The computer-implemented method of claim 1, wherein the online resource allocation algorithm is configured to select an option k for a request j at time t+1 as:

9. One or more computer-readable storage media storing instructions that, when executed by one or more server devices of a service provider, cause the one or more server devices to implement an allocation manager configured to:

randomly sample, from a database of requests collected by the service provider in advance, a number of requests for resources from the service provider less than all of the requests in the database to simulate receipt of the requests one by one from resource consumers; and

process the sampled requests one by one to match the resources to the requests, including for each request;

identifying one or more options of available resources to satisfy the request;

evaluating a difference between profit and cost computed for each of the options using an objective function that accounts for shadow costs assigned to the resources corresponding to each of the options;

selecting an option to fulfill the request that maximizes profit margin based on the evaluation of the differences between profits and costs; and

allocating resources corresponding to the selected option to the request.

10. One or more computer-readable storage media of claim 9, wherein the allocation manager is further configured to update shadow costs associated with each resource after each sampled request is processed to reflect changes in rates of consumption for the resources.

11. One or more computer-readable storage media of claim 10, wherein updating the shadow costs associated with each resource based on the allocation comprises increasing the shadow cost corresponding to a resource as consumption of the resource increases.

12. One or more computer-readable storage media of claim 9, further comprising applying a scaling factor to select a reduced number of the requests to process.

13. One or more computer-readable storage media of claim 9, wherein the objective function identifies a particular option of the one or more options for which the cost subtracted from the profit is maximized.

14. One or more computer-readable storage media of claim 9, wherein the requests for resources comprise orders from advertisers for advertising impressions available from the service provider via webpages served to clients by the service provider.

15. One or more computer-readable storage media of claim 9, wherein identifying one or more options of available resources comprises matching one or more request constraints specified by the request with the resources having associated resource constraints such that the request constraints and resource constraints are satisfied.

16. A computing system comprising:

one or more processors; and

computer readable storage media having one or more modules stored thereon, that, when executed via the one or more processors, cause the computing system to perform operations including;

applying a scaling factor to scale down a number of requests for resources available from a service provider associated with an offline resource allocation problem to produce a representative sample of the requests for resources;

sampling the scaled requests to provide random input of the requests one by one to an online resource allocation algorithm;

processing the sampled requests one by one to compute a scaled resource allocation that matches resources to the scaled requests, including for each particular request;

allocating resources to the particular request by evaluating multiple allocation options based in part upon shadow costs associated with corresponding resources;

updating the shadow costs to reflect changes in rates of consumption for corresponding resources based on the allocation to the particular request; and

using the updated shadow costs to evaluate options for allocation of resources to a next request.

17. The computing system of claim 16, wherein the one or more modules, when executed, cause the computing system to perform further operations including:

outputting a solution for the offline resource allocation problem by scaling up the scaled resource allocation that is computed.

18. The computing system of claim 16, wherein allocating resources to the particular request comprises applying the online resource allocation algorithm to compute a profit margin associated with using each of the multiple allocation options to serve the particular request and select an option of the multiple allocation options that maximizes the profit margin for the particular request.

19. The computing system of claim 16, wherein the requests comprise orders from an advertiser for impressions to enable the advertiser to place advertisements for presentation to clients in conjunction with resources provided by the service provider to clients in webpages.

20. The computer system of claim 16, wherein the one or more modules, when executed, cause the computing system to perform further operations including:

collecting from resource consumers the requests for the resources available from the service provider such that a complete set of requests for the offline resource allocation problem is received in advance of processing.