Methods and apparatus for dynamic allocation of servers to a plurality of customers to maximize the revenue of a server farm
First Claim
Patent Images
1. A method for optimizing server farm resource usage among a plurality of contract customers comprising steps performed by a processor of:
- providing a long term forecast of server resource workload for each contract customer having a contract for on-going usage of server resources at a server farm based on previously monitored workload conditions;
building a resource allocation plan for allocation of server resources to customers for a plurality of time slots based on the long term forecast and customer contract information;
controlling the allocation of server resources in accordance with the resource allocation plan;
monitoring the current workload conditions of server resources during operation of the server farm;
providing a short term forecast based on currently monitored workload conditions at said server resources;
evaluating refinement of the resource allocation plan should said short term forecast differ from said long term forecast;
refining the resource allocation plan to generate a current resource allocation plan when the short term forecast differs from said long term forecast by more than a predetermined threshold; and
adjusting the allocation of server resources in accordance with the current resource allocation plan, wherein said providing a long term forecast comprises the steps of;
constructing an expected revenue function (ERF) for every customer; and
constructing a time slot allocation of resources for each of a plurality of time slots using the ERF for every customer andwherein said constructing an ERF, whereby ERFi,t[j] is a weight that corresponds to an expected revenue from allocating a jth server to customer i at time slot t, comprises the steps of;
providing input of MLISLAi comprising the contract of customer i, a FORECASTi,t comprising a forecasted probability distribution of load Mti for customer i at time slot t whereby FORECASTi,t(x) is a probability that a load Mt will be at least x, REVENUE[j] comprises a charge or rate for a jth server if needed, PENALTY[j] comprises a penalty for a jth server if required and not allocated, Pr[j needed] is a probability that a jth server is needed for the customer at time t, and Pr[j required] comprises a probability that a jth server is required for the customer at time slot t; and
determining the following;
for j =1, . . . , n;
Let Mneeded min be the minimum load Mt s.t. MAP(Mt)=(x,y) and y≧
jPr[j needed]=Pr[M≧
Mneededmin]=FORECASTi,t(Mneededmin)Let be the minimum load Mt s.t. MAP(Mt)=(x,y) and xjPr[j required]=Pr[Mt≧
Mneededmin]=FORECASTi,t(Mneededmin)ERFi,t[j]=Pr[j needed*REVENUE[j]+Pr[j required]*GUARANTEE[j]*PENALTY[j].
1 Assignment
0 Petitions
Accused Products
Abstract
A method and structure for dynamic allocation of servers to customers in a server farm which supports a flexible contract structure such that the total revenue of the farm is maximized. The invention creates a resource allocation plan based on a long term forecast for the server farm, taking into account traffic, number of servers, customers'"'"' contracts and revenue optimization algorithms. The plan is then modified as indicated by short term forecasting using currently monitored load metrics to reallocate to maximize revenue for particular time periods.
-
Citations
4 Claims
-
1. A method for optimizing server farm resource usage among a plurality of contract customers comprising steps performed by a processor of:
-
providing a long term forecast of server resource workload for each contract customer having a contract for on-going usage of server resources at a server farm based on previously monitored workload conditions; building a resource allocation plan for allocation of server resources to customers for a plurality of time slots based on the long term forecast and customer contract information; controlling the allocation of server resources in accordance with the resource allocation plan; monitoring the current workload conditions of server resources during operation of the server farm; providing a short term forecast based on currently monitored workload conditions at said server resources; evaluating refinement of the resource allocation plan should said short term forecast differ from said long term forecast; refining the resource allocation plan to generate a current resource allocation plan when the short term forecast differs from said long term forecast by more than a predetermined threshold; and adjusting the allocation of server resources in accordance with the current resource allocation plan, wherein said providing a long term forecast comprises the steps of; constructing an expected revenue function (ERF) for every customer; and constructing a time slot allocation of resources for each of a plurality of time slots using the ERF for every customer and wherein said constructing an ERF, whereby ERFi,t[j] is a weight that corresponds to an expected revenue from allocating a jth server to customer i at time slot t, comprises the steps of; providing input of MLISLAi comprising the contract of customer i, a FORECASTi,t comprising a forecasted probability distribution of load Mti for customer i at time slot t whereby FORECASTi,t(x) is a probability that a load Mt will be at least x, REVENUE[j] comprises a charge or rate for a jth server if needed, PENALTY[j] comprises a penalty for a jth server if required and not allocated, Pr[j needed] is a probability that a jth server is needed for the customer at time t, and Pr[j required] comprises a probability that a jth server is required for the customer at time slot t; and determining the following; for j =1, . . . , n; Let Mneeded min be the minimum load Mt s.t. MAP(Mt)=(x,y) and y≧
jPr[j needed]=Pr[M≧
Mneededmin]=FORECASTi,t(Mneededmin)Let be the minimum load Mt s.t. MAP(Mt)=(x,y) and xj Pr[j required]=Pr[Mt≧
Mneededmin]=FORECASTi,t(Mneededmin)ERFi,t[j]=Pr[j needed*REVENUE[j]+Pr[j required]*GUARANTEE[j]*PENALTY[j].
-
-
2. A method for optimizing server farm resource usage among a plurality of contract customers comprising steps performed by a processor of:
-
providing a long term forecast of server resource workload for each contract customer having a contract for on-going usage of server resources at a server farm based on previously monitored workload conditions; building a resource allocation plan for allocation of server resources to customers for a plurality of time slots based on the long term forecast and customer contract information; controlling the allocation of server resources in accordance with the resource allocation plan; monitoring the current workload conditions of server resources during operation of the server farm; providing a short term forecast based on currently monitored workload conditions at said server resources; evaluating refinement of the resource allocation plan should said short term forecast differ from said long term forecast; refining the resource allocation plan to generate a current resource allocation plan when the short term forecast differs from said long term forecast by more than a predetermined threshold; and adjusting the allocation of server resources in accordance with the current resource allocation plan, wherein said providing a long term forecast comprises the steps of; constructing an expected revenue function (ERF) for every customer; and constructing a time slot allocation of resources for each of a plurality of time slots using the ERF for every customer and wherein said constructing a time slot allocation of resources for each of a plurality of time slots comprises the steps for each time slot of; inputting ERFi,t for every customer i, N comprising the number of servers, M comprising a set of all customers, U comprising an auxiliary table wherein an entry U[i,j] is a vector describing the optimal allocation of i servers to the first j customers and U[N,M] is the optimal allocation of servers to the set of all customers; determining the RAPi,t for all customers by the steps of; defining U[0,*]=U[*,0]=0 for i=1, . . . , N and j=1, . . . , M such that U[i,j]=allocation corresponding to maxii x=0(U [i−
x,j −
1]+Σ
xy=1ERFj,t[y]); andoutputting U[N,M].
-
-
3. A system for optimizing server farm resource usage among a plurality of contract customers comprising:
-
a processing device for executing components; a long term forecasting component for generating a long term forecast of server resource workload for each contract customer having a contract for on-going usage of server resources at a server farm based on previously monitored workload conditions; a resource allocation planning component for constructing a resource allocation plan for allocation of server resources to customers for a plurality of time slots based on the long term forecast and customer contract information; a short term forecasting component for obtaining current workload conditions of server resources during operation of the server farm and for generating a short term forecast of server resource workload based on currently monitored workload conditions; and a resource manager for controlling the allocation of server resources in accordance with the resource allocation plan, for evaluating refinement of said resource allocation plan when the short term forecast differs from the long term forecast evaluating refinement of the resource allocation plan should said short term forecast differ from said long term, for refining the resource allocation plan to generate a current resource allocation plan when the short term forecast differs from said long term forecast by more than a predetermined threshold and for adjusting the allocation of server resources in accordance with the current resource allocation plan wherein said long term forecast component comprises; an expected revenue function (ERF) component for determining an ERF for every customer; and a time slot allocation component for determining an allocation of resources for each of a plurality of time slots using the ERF for every customer and wherein said ERF component construct an ERF, whereby ERFi,t[j] is a weight that corresponds to an expected revenue from allocating a jth server to customer i at time slot t, comprises the steps of; providing input of MLISLAi comprising the contract of customer i, a FORECASTi,t comprising a forecasted probability distribution of load Mti for customer i at time slot t whereby FORECASTi,t(x) is a probability that a load Mt will be at least x, REVENUE[j] comprises a charge or rate for a jth server if needed, PENALTY[j] comprises a penalty for a jth server if required and not allocated, Pr[j needed] is a probability that a jth server is needed for the customer at time t, and Pr[j required] comprises a probability that a jth server is required for the customer at time slot t; and determining the following; for j=1, . . . , n; Let Mneededmin be the minimum load Mt s.t. MAP(Mt)=(x,y) and y≧
jPr[j needed]=Pr[M≧
Mneededmin]=FORECASTi,t(Mneededmin)Let be the minimum load Mt s.t. MAP(Mt)=(x,y) and xj Pr[j required]=Pr[Mt≧
Mneededmin]=FORECASTi,t(Mneededmin)ERFi,t[j]=Pr[j needed*REVENUE[j]+Pr[j required]*GUARANTEE[j]*PENALTY[j].
-
-
4. A system for optimizing server farm resource usage among a plurality of contract customers comprising:
-
a processing device for executing components; a long term forecasting component for generating a long term forecast of server resource workload for each contract customer having a contract for on-going usage of server resources at a server farm based on previously monitored workload conditions; a resource allocation planning component for constructing a resource allocation plan for allocation of server resources to customers for a plurality of time slots based on the long term forecast and customer contract information; a short term forecasting component for obtaining current workload conditions of server resources during operation of the server farm and for generating a short term forecast of server resource workload based on currently monitored workload conditions; and a resource manager for controlling the allocation of server resources in accordance with the resource allocation plan, for evaluating refinement of said resource allocation plan when the short term forecast differs from the long term forecast evaluating refinement of the resource allocation plan should said short term forecast differ from said long term, for refining the resource allocation plan to generate a current resource allocation plan when the short term forecast differs from said long term forecast by more than a predetermined threshold and for adjusting the allocation of server resources in accordance with the current resource allocation plan wherein said long term forecast component comprises; an expected revenue function (ERF) component for determining an ERF for every customer; and a time slot allocation component for determining an allocation of resources for each of a plurality of time slots using the ERF for every customer and wherein the time slot allocation component constructs a time slot allocation of resources for each of a plurality of time slots by the steps for each time slot of; inputting ERFi,t for every customer i, N comprising the number of servers, M comprising a set of all customers, U comprising an auxiliary table wherein an entry U[i,j] is a vector describing the optimal allocation of i servers to the first j customers and U[N,M] is the optimal allocation of servers to the set of all customers; determining the RAPi,t for all customers by the steps of; defining U[0,*]=U[*,0]=0 for i=1, . . . , N and j=1, . . . , M such that U[i,j]=allocation corresponding to maxix=0(U[i−
x,j−
1]+Σ
xy=1ERFj,t[y]); andoutputting U[N,M].
-
Specification