Long-term resource provisioning with cascading allocations

<u>Related Art</u>

0001This disclosure is generally related to data center operations. More specifically, this disclosure is related to a system that provides long-term resource provisioning for a data center.

0002Modem virtualization technologies have made it is possible for data centers to run different jobs in a shared environment. In other words, the different jobs can share the same physical resources, such as memory, central processing unit (CPU), and bandwidth, all of which can be provided by a single machine or a cluster of machines. One important consideration for data center operations is to consolidate multiple jobs (or loads) on a single machine or a cluster of machines.

0003Effective provisioning of the resources involves finding groups of jobs that can consolidate well, i.e., groups that can more effectively utilize the physical resources on a machine or a cluster of machines. A better consolidation can result in increased data center capacity. Moreover, by powering-off unused machines, the data center can also increase its energy savings.

SUMMARY

0004One embodiment of the present invention provides a system for provisioning physical resources shared by a plurality of jobs. During operation, the system establishes resource-usage models for the jobs, ranks the jobs based on quality of service (QoS) requirements associated with the jobs, and provisions the jobs for a predetermined time interval in such a way that any unused reservations associated with a first subset of jobs having higher QoS rankings are distributed to other remaining jobs with preference given to a second subset of jobs having a highest QoS ranking among the other remaining jobs. Provisioning the jobs involves making reservations for the jobs based on the resource-usage model and corresponding QoS requirements associated with the jobs.

0005In a variation on this embodiment, provisioning the jobs further involves assigning different numbers of shares to the jobs based on corresponding QoS rankings associated with the jobs, and assigning reservations based on an assumption that unused reservations associated with the first subset of jobs will be proportionally distributed to the other remaining jobs according to the number of shares assigned to the other remaining jobs. The number of shares assigned to a respective job is correlated to the respective job's QoS ranking.

0006In a variation on this embodiment, provisioning the jobs further involves sorting the jobs in descending order based on QoS rankings; and iteratively, starting from a job having a highest QoS ranking, forming a subgroup by adding a next-in-line job to a previously formed subgroup, establishing a resource-usage model for the subgroup, and determining a required amount of resources needed by the subgroup based on the resource-usage model for the subgroup and QoS requirement associated with the next-in-line job.

0007In a further variation, the system makes a reservation for the next-in-line job based on a difference between the required amount of resources and reservations made for the previously formed subgroup.

0008In a further variation, in response to at least two jobs having a same QoS ranking, the system forms a tiered subgroup by adding the at least two jobs as a tier to the previously formed subgroup, determines a scale factor for each of the at least two jobs based on resources required by each of the at least two jobs, and makes reservations for each of the at least two jobs based on the scale factor.

0009In a variation on this embodiment, the system provisions the jobs for multiple predetermined time intervals, which involves determining a maximum amount of resources required by a group of one or more jobs over the multiple predetermined time intervals.

0010In a variation on this embodiment, the system receives an isolation parameter which defines a degree of isolation among jobs. Provisioning the jobs involves applying the isolation parameter while making reservations for the jobs, and a complete isolation results in making individual reservations for the jobs.

BRIEF DESCRIPTION OF THE FIGURES

0011<figref idref="f0001">FIG. 1</figref> presents a diagram illustrating an exemplary shortfall analysis for a job.

0012<figref idref="f0002">FIG. 2</figref> presents a diagram illustrating how resources cascade between two adjacent prefix groups, in accordance with an embodiment of the present invention.

0013<figref idref="f0003">FIG. 3</figref> presents a diagram illustrating a resource-provisioning controller, in accordance with an embodiment of the present invention.

0014<figref idref="f0004">FIG. 4</figref> presents a flowchart illustrating an exemplary process of resource provisioning, in accordance with an embodiment of the present invention.

0015<figref idref="f0005">FIG. 5</figref> illustrates an exemplary computer system for resource provisioning in a data center, in accordance with one embodiment of the present invention.

0016In the figures, like reference numerals refer to the same figure elements.

DETAILED DESCRIPTION

0017The following description is presented to enable any person skilled in the art to make and use the embodiments, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present disclosure. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

<u>Overview</u>

0018Embodiments of the present invention provide a system for providing long-term resource provisioning to a data center. More specifically, the system provisions resources for a group of jobs based on resource needs of the jobs in a set of future time intervals. To satisfy the resource needs for the jobs as well as meeting their quality-of-service (QoS) requirements, the system applies a total pool allocation algorithm that makes individual reservations for jobs based on descending QoS orders until the cumulative reservations made are large enough to meet resource needs of all jobs. A cascaded algorithm is also used to plan the redistribution of unused reservations to other jobs based on their QoS rankings.

0019In this disclosure, the term "physical resource" refers to various types of physical equipment needed for finishing a computing job. It can include processing capability, storage space, communication bandwidth, input/output, etc. Moreover, a particular "physical resource" can refer to a single machine, a cluster of machines, or all machines in a data center. Moreover, the terms "physical resource" and "physical machine" are interchangeable.

0020In this disclosure, the term "job" refers to a computational task in a shared environment. More specifically, a job can be a virtual machine instance or a collection of virtual machine instances.

<u>Single Interval Provisioning</u>

0021Although a preferred resource-provisioning system for data center operations should be able to automatically and frequently adjust provisioning, close supervision by a human operator to such a system is still desired. For example, it might be desired to have a monitoring tool that monitors the resource needs of the jobs and suggests resource provisioning. A human operator can then approve and implement the provisioning. An automatic system might adjust provisioning every 15 minutes, while a supervised system might adjust much less frequently (e.g., daily, weekly or even monthly).

0022Provisioning of resources in a single time interval is very similar to short-term provisioning. The only difference is that the short-term system uses models predicting resource-usage requirements of a group of jobs for an immediately following time interval (such as the next 15 minutes) to allocate resources to meet the resource-usage requirements according to QoS specifications of those jobs; single interval provisioning, on the other hand, involves the provision of resources for a particular time interval that may not be immediately following. Short-term provisioning is relatively easier because recent resource consumption is a strong predictor of near-term resource needs.

0023In this disclosure, the QoS specification (or the QoS level) for a job is denoted as <i>p</i>, which is the acceptable probability that the job will not be fully provisioned with its resource needs. In other words, a job with QoS level <i>p</i> will not receive all requested resources with a probability <i>p</i>, during a measured interval. Note that QoS level <i>p</i> should not be confused with a job failure probability. Most modem applications are written well enough that they can perform adequately well even when they do not have 100% of requested resources. For example, an application under heavy load might temporarily deliver lower resolution images, or an application running in batch mode might start early to ensure completion by a deadline. However, resilience to resource shortfall is an application-specific characteristic. To avoid confusion, the failure to fully provision is also referred to as a "shortfall" situation. Note that the appropriate setting of the QoS <i>p</i> (i.e., the allowed "probability of shortfall") will be greater than the allowed probability of failure for the job.

0024In this disclosure, we use a random variable <maths id="math0001"><math display="inline"><msubsup><mi>Z</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup></math><img file="EP2631798A2_D0001.tif" /></maths> to represent the resources required by job <i>i</i> in time interval τ. Note that <i>Z</i> can be a one-dimensional resource, such as CPU cycles, memory, hard disk, or I/O; or a multidimensional resource. When only a single time interval is considered, we can temporarily omit the τ index.

0025The resource needs for job <i>i</i> can be modeled by an observed probability distribution function φ^(<i>i</i>)(<i>z</i>) for the random variable <i>Z</i>^(<i>i</i>). The corresponding cumulative distribution can be expressed as: <maths id="math0002" num="(1)"><math display="block"><msup><mi mathvariant="normal">Φ</mi><mfenced><mi>i</mi></mfenced></msup><mfenced><mi>y</mi></mfenced><mo>=</mo><munderover><mo>∫</mo><mrow><mo>-</mo><mi>inf</mi></mrow><mi>y</mi></munderover><msup><mi>ϕ</mi><mfenced><mi>i</mi></mfenced></msup><mfenced><mi>z</mi></mfenced><mn>.</mn></math><img file="EP2631798A2_D0002.tif" /></maths> Note that the difference between observed distributions and true distributions can be ignored with enough samples. However, when the modeling and consolidation algorithms are newly applied to a set of jobs, some care must be taken to use prior assumptions and incorporate the risk of modeling errors.

0026The total pool algorithm (also sometimes called the statistical packing algorithm) processes the jobs in decreasing QoS order (or increasing <i>p</i>) by making individual reservations for jobs according to: <maths id="math0003" num="(2)"><math display="block"><msup><mi>r</mi><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mi>inverse</mi><mspace width="1em" /><msup><mi mathvariant="normal">Φ</mi><mfenced><mi>i</mi></mfenced></msup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup></mfenced><mo>,</mo></math><img file="EP2631798A2_D0003.tif" /></maths> until the cumulative reservations <maths id="math0004"><math display="inline"><msup><mover><mi>r</mi><mo>^</mo></mover><mfenced><mi>k</mi></mfenced></msup><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>k</mi></munderover></mstyle><msup><mi>r</mi><mfenced><mi>i</mi></mfenced></msup></math><img file="EP2631798A2_D0004.tif" /></maths> are large enough that the whole pool of jobs has enough resources. The remaining jobs (with indexes larger than <i>k</i>) require no reservation. In other words, once jobs with higher QoS levels are individually provisioned with enough resources to meet their QoS requirements, the frequent availability of unused resources will be adequate to meet the QoS requirements of jobs with lower QoS levels.

0027More formally speaking, the total pool allocation algorithm works by finding the smallest index <i>k</i> such that the partial sum of the individual reservations for the first <i>k</i> - 1 jobs<i>, r̂</i>^(<i>k</i>-1)<i>,</i> plus a partial reservation <i>s</i>^(<i>k</i>) ≤ <i>r</i>^(<i>k</i>) at job <i>k,</i> is large enough to meet the entire groups' resource needs at the <i>k_th</i> job's QoS level (i.e., <i>p</i>^(<i>k</i>)). That is, <maths id="math0005" num="(3)"><math display="block"><msup><mover><mi>r</mi><mo>^</mo></mover><mfenced><mi>k</mi><mo>-</mo><mn>1</mn></mfenced></msup><mo>+</mo><msup><mi>s</mi><mfenced><mi>k</mi></mfenced></msup><mo>=</mo><mi>inverse</mi><mspace width="1em" /><msup><mi mathvariant="normal">Ψ</mi><mfenced><mi>n</mi></mfenced></msup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>k</mi></mfenced></msup></mfenced><mn>.</mn></math><img file="EP2631798A2_D0005.tif" /></maths> Note the (<i>n</i>) superscript on Ψ, meaning the cumulative distribution is for the entire group. According to Eq. (3), jobs 1, 2, ..., <i>k</i> can obtain reservations <i>r</i>⁽¹⁾, <i>r</i>⁽²⁾, ..., <i>r</i>^(<i>k</i>-1), <i>s</i>^(<i>k</i>), and no reservation is given to the remaining jobs. Note that, because the jobs are in QoS order, QoS requirements of the remaining jobs can be met even without further reservations. The actual reservation given to a job <i>i</i> depends on where the job stands with respect to the transitional index <i>k</i>: <maths id="math0006" num="(4)"><math display="block"><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mrow><mo>{</mo></mrow><mtable><mtr><mtd><msup><mi>r</mi><mfenced><mi>i</mi></mfenced></msup><mo>,</mo></mtd><mtd><mi>i</mi><mo><</mo><mi>k</mi></mtd></mtr><mtr><mtd><msup><mi>s</mi><mfenced><mi>k</mi></mfenced></msup><mo>,</mo></mtd><mtd><mi>i</mi><mo>=</mo><mi>k</mi></mtd></mtr><mtr><mtd><mn>0</mn><mo>,</mo></mtd><mtd><mi>i</mi><mo>></mo><mi>k</mi></mtd></mtr></mtable><mn>.</mn></math><img file="EP2631798A2_D0006.tif" /></maths> It is more convenient to express Eq. (4) using its algorithmic version: <img file="EP2631798A2_D0007.tif" /> where the variable "accum" is the total reservation made. The correctness of Eq. (4) (and its algorithmic version) follows from the observation that meeting the group's resource needs according to Eq. (3) will meet all individual jobs' resource needs at a QoS level of <i>p</i>^(<i>k</i>), which is more than adequate for any subsequent job with index <i>j</i> > <i>k</i>, where <i>p</i>^(<i>j</i>) ≤ <i>p</i>^(<i>k</i>).

0028Application of the total pool algorithm requires modeling of resource needs for individual jobs (Eq. (2)), as well as modeling of the resource needs for the entire group (Eq. (3)). So far we have described a total pool allocation algorithm that proceeds sequentially through the jobs in QoS order and results in the reservations shown in Eq. (4), with large protective reservations for jobs with indices less than <i>k</i> and no reservations for jobs with indices greater than <i>k</i>. It is possible to improve this result slightly, reducing the total reservation by computing all the reservations at once using a so-called fixed-point calculation. In most cases, the result of the fixed-point calculation resembles the reservations of Eq. (4), but softens the transition at <i>k</i>, reserving less for jobs with indices less than <i>k</i> and making small reservations for jobs with indices greater than <i>k</i>.

0029Assuming that, for each job <i>i</i>, we can model the joint distribution of the resource needs of the job (random variable <i>Z</i>^(<i>i</i>)) and the total resource needs of all other jobs excluding job <i>i</i> (random variable <i>Y</i>^(-<i>i</i>)), which is denoted as the observed probability distribution function <i>ξ</i>^(<i>i</i>)(<i>y</i>,<i>z</i>), then the shortfall probability can be calculated as: <maths id="math0007" num="(5)"><math display="block"><msup><mi>q</mi><mfenced><mi>i</mi></mfenced></msup><mfenced><msup><mi>s</mi><mfenced><mi>i</mi></mfenced></msup><mo>⁢</mo><msup><mi>s</mi><mi>T</mi></msup></mfenced><mo>=</mo><mstyle displaystyle="false"><msub><mo>∫</mo><mrow><mfenced><mi>y</mi><mo>⁢</mo><mi>z</mi></mfenced><mo>∈</mo><mfenced open="{" close="}"><mfenced><mi>z</mi><mo>></mo><msup><mi>s</mi><mfenced><mi>i</mi></mfenced></msup></mfenced><mo>∧</mo><mfenced><mi>y</mi><mo>+</mo><mi>z</mi><mo>></mo><msup><mi>s</mi><mi>T</mi></msup></mfenced></mfenced></mrow></msub></mstyle><msup><mi>ξ</mi><mfenced><mi>i</mi></mfenced></msup><mfenced><mi>y</mi><mo>⁢</mo><mi>z</mi></mfenced><mo>ⅆ</mo><mi>z</mi><mo>,</mo></math><img file="EP2631798A2_D0008.tif" /></maths> where <i>s</i>^(<i>i</i>) is the individual reservation made for job <i>i,</i> and <i>s^T</i> = <i>s</i>⁽¹⁾ + <i>s</i>⁽²⁾ +...+ <i>s</i>^(<i>n</i>) is the reservation made for the entire group. A shortfall occurs when neither the individual reservation nor the group reservation is large enough: (<i>z > s</i>^(<i>i</i>))∧(<i>y</i> + <i>z</i> > <i>s^T</i>).

0030<figref idref="f0001">FIG. 1</figref> presents a diagram illustrating an exemplary shortfall analysis for a job. The x-axis is the resource needs of job <i>i</i> (variable <i>z</i>), and the y-axis is the resource needs of all other jobs (variable <i>y</i>). The dotted line stands for the individual reservation made for job <i>i</i>(<i>s</i>^(<i>i</i>)); the dashed line stands for the reservation made for the entire group (<i>s^T</i>). When the resource needs for job <i>i</i> are smaller than the individual reservation made for job <i>i</i> (i.e., on the left side of the dotted line), such needs can be satisfied by the individual reservation for job <i>i</i>. When the resource needs for job <i>i</i> are greater than its individual reservation (i.e., on the right side of the dotted line), but the resource needs for the group are less than the group reservation (i.e., below the dashed line), resource needs for job <i>i</i> can be satisfied by the unused reservations of other jobs. The shaded area (to the left of the dotted line and above the dashed line) is the so-called shortfall region. Shortfall occurs when resource needs fall within the shortfall region. Note that, if the group reservation is not large enough, then depending on how the virtual machine scheduler works, some jobs may still be fully provisioned. Here we assume that the "pain will be shared," all jobs within the group will be short of their full resource needs, and that even a slight shortfall will count as a failure event for purposes of QoS requirements. This is a conservative approach to meeting QoS requirements, that is, unless they are guaranteed by the individual or group reservations, we will not assume they are met.

0031Using the shortfall probability, one can determine the required individual reservation <i>s</i>^(<i>i</i>) as a simultaneous solution of: <maths id="math0008" num="(6)"><math display="block"><msup><mi>q</mi><mfenced><mi>i</mi></mfenced></msup><mfenced><msup><mi>s</mi><mfenced><mi>i</mi></mfenced></msup><mo>⁢</mo><msup><mi>s</mi><mi>T</mi></msup></mfenced><mo>=</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup><mo>,</mo></math><img file="EP2631798A2_D0009.tif" /></maths> and <maths id="math0009" num="(7)"><math display="block"><msup><mi>S</mi><mi>T</mi></msup><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><msup><mi>s</mi><mfenced><mi>i</mi></mfenced></msup><mn>.</mn></math><img file="EP2631798A2_D0010.tif" /></maths>

0032Eqs. (6) and (7) can be solved using a fixed-point computation: starting with a total reservation <i>s^T</i>, solve for the individual reservations <i>s</i>^(<i>i</i>) necessary to meet the QoS requirements according to Eq. (6); then use these individual reservations to define a new total reservation according to Eq. (7). If the observed probability distribution functions are provided as histograms, this fixed-point computation can proceed systematically: search for the correct <i>s^T</i> by starting with the largest possible value, and reducing <i>s^T</i> stepwise. This will result in <i>s</i>^(<i>i</i>) in the solution of Eq. (6) increasing monotonically. The search stops when the sum of the <i>s</i>^(<i>i</i>) exceeds <i>s^T</i>, thus identifying the fixed point to within the accuracy of the quantization of the histogram. To complete the algorithm, <i>s^T</i> is set to the sum of the <i>s</i>^(<i>i</i>) according to Eq. (7), thus ensuring that both the <i>s</i>^(<i>i</i>) and <i>s^T</i> are equal to or larger than necessary.

0033The correctness of this algorithm follows from Eq. (6). At the fixed point, the probability of a shortfall will be the probability <i>p</i>^(<i>i</i>) required by the QoS specification. Note that, when histograms and stepwise searches are used, there may be some overshoot. However, the fact that <i>q</i>^(<i>i</i>)(<i>s</i>^(<i>i</i>),<i>s^T</i>) monotonically decreases as <i>s</i>^(<i>i</i>) and <i>s^T</i> both increase can result in: <maths id="math0010" num="(8)"><math display="block"><msup><mi>q</mi><mfenced><mi>i</mi></mfenced></msup><mfenced><msup><mi>s</mi><mfenced><mi>i</mi></mfenced></msup><mo>⁢</mo><msup><mi>s</mi><mi>T</mi></msup></mfenced><mo>≤</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup><mo>,</mo></math><img file="EP2631798A2_D0011.tif" /></maths> which meets or exceeds the QoS requirement for job <i>i</i>.

0034Although this fixed-point variation of the total pool allocation algorithm can be viewed as the optimal solution to the provisioning problem, assuming that the only control of the provisioning is to make individual job reservations, other tools can also be used to control provisioning, including a solution that selectively redistributes unused reservations.

0035The aforementioned total pool allocation algorithm allows unused reservations to be redistributed evenly among all jobs in the pool. However, it is beneficial to selectively redistribute those unused reservations by favoring jobs with higher QoS ratings (i.e., jobs with lower <i>p</i>). In one embodiment, a "share" machinery is used when redistributing the unused reservations. More specifically, each job is assigned with a number of shares, and the unused reservations are distributed proportionally to the shares of the remaining jobs needing resources. Hence, by assigning higher QoS jobs with more shares, one can ensure that those jobs can obtain more unused reservations. For example, when jobs are indexed in decreasing QoS order, the system can assign shares based on the index: job <i>i</i> receives <i>M</i>^{<i>n</i>-<i>i</i>} shares, where <i>M</i> is a large positive constant and <i>n</i> is the number of jobs in the pool. The larger the <i>M</i>, the more the redistribution favors higher QoS jobs. In the limit <i>M</i> → ∞, all unused resources will "cascade" through the remaining jobs in QoS order, until all jobs' resource needs are met (or there aren't enough resources). In practice, <i>M</i> is set at a finite value, such as 5 or 10. At these finite values, some of the unused resources will "leak" to lower QoS jobs. With the total pool allocation algorithm, these resources are not wasted because giving unused resources to lower QoS jobs also helps with consolidation.

0036In an alternative embodiment, instead of assigning shares to jobs, or virtual machines, the system uses a grouping machinery to create a similar cascading of unused resources to jobs based on their QoS rankings. More specifically, the two jobs (or virtual machines) with the highest QoS rankings are grouped together, and then a hierarchy of groups is built by adding lower QoS jobs successively as the hierarchy is extended, as shown: <maths id="math0011" num="(9)"><math display="block"><mfenced open="{" close="}"><mfenced open="{" close="}"><mfenced open="{" close="}"><mfenced open="{" close="}"><msub><mi>vm</mi><mn>1</mn></msub><mo>⁢</mo><msub><mi>vm</mi><mn>2</mn></msub></mfenced><mo>⁢</mo><msub><mi>vm</mi><mn>3</mn></msub></mfenced><mo>⁢</mo><msub><mi>vm</mi><mn>4</mn></msub></mfenced><mo>…</mo><mo>,</mo><msub><mi>vm</mi><mi>n</mi></msub></mfenced><mn>.</mn></math><img file="EP2631798A2_D0012.tif" /></maths> The individual jobs (or virtual machines) are given reservation <i>r̃</i>^(<i>i</i>), and the total resource pool <i>r̃^T</i> is chosen to be larger than the sum of the individual reservations, given as: <maths id="math0012" num="(10)"><math display="block"><msup><mover><mi>r</mi><mo>˜</mo></mover><mi>T</mi></msup><mo>≥</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>i</mi></mfenced></msup><mn>.</mn></math><img file="EP2631798A2_D0013.tif" /></maths> Note that <i>r̃^T</i> is set with some extra padding to allow bin-packing across multiple physical machines and for rounding to an integral number of machines. Each group is given a large reservation equal to the total resources in the pool minus any reservations not in its subtree: <maths id="math0013" num="(11)"><math display="block"><msup><mover><mi>g</mi><mo>˜</mo></mover><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><msup><mover><mi>r</mi><mo>˜</mo></mover><mi>T</mi></msup><mo>-</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mi>n</mi></munderover></mstyle><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>j</mi></mfenced></msup><mo>,</mo></math><img file="EP2631798A2_D0014.tif" /></maths> where <i>g̃</i>^(<i>i</i>) is the reservation for the group formed in the hierarchy containing vm₁, vm₂, ..., vm_i in its subtree. These group reservations capture unused resources in their subtree until all needs are met. This way the unused resources will favor the left side of the group hierarchy, meeting the resource needs of higher QoS jobs before meeting the resource needs of the lower QoS jobs.

0037One practical consideration is that QoS specifications are likely to fall into a small number of fixed levels. Hence, not every job will have a distinct QoS level <i>p</i>^(<i>i</i>). Rather than cascading unused resources through the jobs sequentially, the unused resources can cascade simultaneously to all jobs with the same QoS level. This can be arranged by making the share assignment equal for equal QoS jobs, or if the grouping mechanism is used, adding equal QoS jobs together at the same level in the hierarchy.

0038For simplicity, we first consider a case of distinct QoS levels and strictly ordered cascading (i.e., <i>M</i> → ∞, or a hierarchy of groups with one new virtual machine added at each level). The cascading excess algorithm processes the jobs in descending QoS order (thus ascending <i>p</i>^(<i>i</i>)) with the highest QoS job first. At each step, an actual reservation <i>r̃</i>^(<i>i</i>) is chosen so that the cumulative reservation will meet the resource needs of job <i>i</i> grouped with all the preceding jobs. For each <i>i</i>, let <i>r̅</i>^(<i>i</i>) be the total reservation required for the prefix group {1, 2, ..., <i>i</i>} at the QoS level of the last job in the group: <maths id="math0014" num="(12)"><math display="block"><msup><mover><mi>r</mi><mo>‾</mo></mover><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mi>inverse</mi><mspace width="1em" /><msup><mi mathvariant="normal">Ψ</mi><mfenced><mi>i</mi></mfenced></msup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup></mfenced><mo>,</mo></math><img file="EP2631798A2_D0015.tif" /></maths> where Ψ^(<i>i</i>) is the cumulative distribution function (CDF) for the prefix group. The actual reservation <i>r̃</i>^(<i>i</i>) for job <i>i</i> is the additional reservation necessary for job <i>i</i> (beyond the sum of reservations already made for the higher QoS jobs, <i>r̃</i>⁽¹⁾ + <i>r̃</i>⁽²⁾ +...+ <i>r̃</i>^(<i>i</i>-1)) to meet the total requirement for the prefix group {1, 2, ..., <i>i</i>}. The algorithm for calculating <i>r̃</i>^(<i>i</i>) can be written as: <img file="EP2631798A2_D0016.tif" />

0039Notice that the benefit derived from using the share (or grouping) machinery to cascade unused resources through the remaining jobs in descending QoS order is that a lower QoS job needing more than its predicted resources (for example, beyond what is necessary to meet its QoS needs) will not receive unused resources until these resources have cascaded through higher QoS jobs. <figref idref="f0002">FIG. 2</figref> presents a diagram illustrating how resources cascade between two adjacent prefix groups, in accordance with an embodiment of the present invention. The top half of <figref idref="f0002">FIG. 2</figref> shows the probability density function (PDF) for the prefix group {1, 2, ..., <i>i</i>-1}; and the bottom half of <figref idref="f0002">FIG. 2</figref> shows the PDF for the next prefix group {1, 2, ..., <i>i</i>}. Note that for descending QoS order, shortfall probability <i>p</i>^(<i>i</i>) increases with <i>i</i>, thus leading to required reservation for the prefix group shift to the left relative to the distribution. One can see from <figref idref="f0002">FIG. 2</figref> that little additional reservation <i>r̃</i>^(<i>i</i>) is needed. The correctness of this cascading-excess algorithm is provided by knowing that <maths id="math0015"><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>i</mi></munderover></mstyle><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>j</mi></mfenced></msup><mo>≥</mo><msup><mover><mi>r</mi><mo>‾</mo></mover><mfenced><mi>i</mi></mfenced></msup></math><img file="EP2631798A2_D0017.tif" /></maths> and by Eq. (12). The cumulative reservations made based on the cascading-excess algorithm are large enough to meet the resource needs of group {1, 2, ..., <i>i</i>} at QoS level <i>p</i>^(<i>i</i>) and will necessarily meet the resource needs for job <i>i</i>, the last member of the group, at QoS level <i>p</i>^(<i>i</i>)<i>.</i>

0040In cases where multiple jobs have the same QoS requirement, a tier-based cascading-excess algorithm can be implemented. More specifically, the unused reservations cascade to all jobs in the same tier, or jobs with the same QoS level, at the same time. To do so, jobs in a given tier are given an equal number of shares. Hence, when these jobs are given their reservations, they will receive equal portions of the extra available resources.

0041The tier-based cascade algorithm defines <i>m</i> QoS tiers, such that each (QoS-ordered) job <i>i</i> is assigned to a tier, and such that each job in a given tier shares the same QoS level. <i>Tier k</i> of a job <i>i</i> can be defined by the grouping mechanism as <i>k</i> = <i>G</i>(<i>i</i>)<i>,</i> and the number of jobs in tier <i>k</i> is denoted as <i>m_k.</i> Assuming the tiers are indexed in descending QoS order, the reservation required for a prefix group that includes all jobs <i>i</i> such that <i>G</i>(<i>i</i>) ≤ <i>k</i> is: <maths id="math0016" num="(13)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup><mo>=</mo><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Ψ</mi><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msubsup><mi>p</mi><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup></mfenced><mo>,</mo></math><img file="EP2631798A2_D0018.tif" /></maths> where <maths id="math0017"><math display="inline"><msubsup><mi mathvariant="normal">Ψ</mi><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup></math><img file="EP2631798A2_D0019.tif" /></maths> is the CDF for the prefix group, and <maths id="math0018"><math display="inline"><msubsup><mi>p</mi><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup></math><img file="EP2631798A2_D0020.tif" /></maths> is the shortfall probability associated with QoS tier <i>k</i>.

0042Because the share mechanism allocates extra resources at each tier equally among the jobs in the tier, the remaining reservation required, <maths id="math0019"><math display="inline"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup><mo>,</mo></math><img file="EP2631798A2_D0021.tif" /></maths> can be heuristically allocated proportionally to each job's individual provisioning reservation <i>r</i>_*^(<i>i</i>). In one embodiment, the system makes actual reservations for each job based on the scaled individual reservation for the job. The scaled individual reservation for job <i>i</i> is defined as: <maths id="math0020" num="(14)"><math display="block"><msup><mi>γ</mi><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mfrac><msubsup><mi>r</mi><mo>*</mo><mfenced><mi>i</mi></mfenced></msubsup><mrow><msub><mi mathvariant="normal">Σ</mi><mrow><mi>G</mi><mfenced><mi>j</mi></mfenced><mo>=</mo><mi>G</mi><mfenced><mi>i</mi></mfenced></mrow></msub><mo>⁢</mo><msubsup><mi>r</mi><mo>*</mo><mfenced><mi>j</mi></mfenced></msubsup></mrow></mfrac><mn>.</mn></math><img file="EP2631798A2_D0022.tif" /></maths> Accordingly, the actual reservation for job <i>i</i> is given by: <img file="EP2631798A2_D0023.tif" />

0043Note that other than the scale individual reservation defined by Eq. (14), other definitions ofthis proportioning factor are also possible, as long as all the γ^(<i>i</i>) values for a given tier sum to 1. This particular heuristic, that apportions the tier reservations proportionally to the individual provisioning reservation, has the advantage of offering individual protection as well as guiding migration decisions sensibly. The correctness of this tier-based cascading-excess algorithm is provided by knowing that: for each <i>k,</i><maths id="math0021"><math display="inline"><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>G</mi><mfenced><mi>i</mi></mfenced><mo>=</mo><mi>k</mi></mrow></munder></mstyle><msup><mi>γ</mi><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mn>1</mn></mstyle></math><img file="EP2631798A2_D0024.tif" /></maths> and <maths id="math0022"><math display="inline"><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>G</mi><mfenced><mi>i</mi></mfenced><mo>=</mo><mi>k</mi></mrow></munder></mstyle><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>i</mi></mfenced></msup></mstyle><mo>=</mo><mi>max</mi><mo>⁢</mo><mfenced><mn>0</mn><mo>,</mo><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup><mo>-</mo><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>G</mi><mfenced><mi>i</mi></mfenced><mo>&lt;</mo><mi>k</mi></mrow></munder></mstyle><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>i</mi></mfenced></msup></mstyle></mfenced><mn>.</mn></math><img file="EP2631798A2_D0025.tif" /></maths> Therefore, <maths id="math0023"><math display="inline"><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>G</mi><mfenced><mi>i</mi></mfenced><mo>≤</mo><mi>k</mi></mrow></munder></mstyle><msup><mover><mi>r</mi><mo>˜</mo></mover><mfenced><mi>i</mi></mfenced></msup></mstyle><mo>≥</mo><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi>g</mi><mfenced><mi>k</mi></mfenced></msubsup><mn>.</mn></math><img file="EP2631798A2_D0026.tif" /></maths> Hence, according to Eq. (13), the cumulative reservation is large enough to meet the needs of the tier prefix group <maths id="math0024"><math display="inline"><msubsup><mi mathvariant="normal">Ψ</mi><mi>k</mi><mfenced><mi>g</mi></mfenced></msubsup></math><img file="EP2631798A2_D0027.tif" /></maths> at QoS level <i>p</i>^(<i>k</i>).

0044In general, there is a tradeoff between the modeling effort and the amount of consolidation achieved. The simple total pool allocation algorithm has the simplest modeling requirements, which models individual job resources and the total resources. The fixed-point variation of the total pool allocation algorithm obtains a better, more consolidated solution, but requires joint models for each job. The cascading-excess algorithm obtains a better, more consolidated solution by using more provisioning machinery in the underlying virtualization scheduler (i.e., either "shares" or grouping), but its modeling needs are slightly more complicated than the simple total pool allocation, requiring models of <i>n</i> "prefix groups," rather than <i>n</i> individual models. The tier-based cascading-excess algorithm, as an extension of the cascading-excess algorithm, also obtains an improved consolidated solution, but requires models of the <i>m</i> tier prefix groups, as well as the <i>n</i> individual models (for calculating γ).

0045If the jobs are independent, then the different modeling requirements are not significant, all the above models can be derived by various convolutions of the individual job models. However, in practice, the jobs' resource needs are usually correlated, and modeling that accounts for this correlation (i.e., modeling various group resource requirements) is essential to solving the consolidation problem well. The cascading-excess algorithm also provides the benefit of more isolation of the high QoS jobs from the low QoS jobs.

<u>Multiple Interval Provisioning</u>

0046Long-term provisioning of a data center involves provisioning for multiple time intervals. Rather than dynamically changing provisioning before each time interval, it is preferable to set one provisioning in advance that will work well for multiple time intervals (e.g., an entire day, or an entire week). The motivation for this more stable provisioning is that it allows data center operators to more carefully supervise operations of the data center, for example, by less frequently reviewing and/or manually applying a longer-term provisioning recommendation.

0047The challenge for multiple interval provisioning is computing a provisioning that works simultaneously for multiple intervals. A simple strategy might be to use any one of the above-described single interval provisioning algorithms to compute reservations <i>r</i>_τ^(<i>i</i>) for each time interval τ, and then use the maximum across all such reservations by setting: <maths id="math0025" num="(15)"><math display="block"><msubsup><mover><mi>r</mi><mo>˜</mo></mover><mo>*</mo><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><msubsup><mover><mi>r</mi><mo>˜</mo></mover><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mn>.</mn></math><img file="EP2631798A2_D0028.tif" /></maths>

0048While this might work well for some sets of jobs, it has the disadvantage that, if the resource needs of jobs are complementary, they likely will not all need their maximum in the same time interval. Hence, even though the single interval provisioning algorithms do a good job of sharing resources within a single time interval, the max operation in Eq. (15) does not do a good job of sharing resources among time intervals. A better approach is needed.

0049Among the various single interval provisioning algorithms, the cascading-excess approach provides the most control for reallocating resources among time intervals. Here, we can extend the cascading-excess algorithm to multiple time intervals. For each prefix group {1, 2, ..., <i>i</i>}, the required reservation <maths id="math0026"><math display="inline"><msup><mover><msub><mi>r</mi><mo>*</mo></msub><mo>‾</mo></mover><mfenced><mi>i</mi></mfenced></msup></math><img file="EP2631798A2_D0029.tif" /></maths> to meet the resource needs of the group at the QoS level of the last member of the group (i.e., <i>p</i>^(<i>i</i>)) for all time intervals can be computed using: <maths id="math0027" num="(16)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Ψ</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup></mfenced><mo>,</mo></math><img file="EP2631798A2_D0030.tif" /></maths><maths id="math0028" num="(17)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mo>*</mo><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mn>.</mn></math><img file="EP2631798A2_D0031.tif" /></maths>

0050Using the aforementioned share or grouping machineries, and assuming that the excess resources will cascade to the job in descending QoS order, the actual reservations can be computed using the following algorithm: <img file="EP2631798A2_D0032.tif" />

0051This algorithm differs from the simple max algorithm described by Eq. (15). Rather than applying the max to the actual single interval reservation <i>r̃</i>_τ^(<i>i</i>). this algorithm applies the max to the required reservation before making the actual reservation, as shown in Eq. (17). This way allows more sharing of resources within the prefix groups.

0052The correctness of this algorithm is provided by noticing that, for each prefix group {1, 2, ..., <i>i</i>}, there will be enough cumulative reservation as <maths id="math0029"><math display="inline"><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>i</mi></munderover></mstyle><msup><mover><msub><mi>r</mi><mo>*</mo></msub><mo>˜</mo></mover><mfenced><mi>j</mi></mfenced></msup><mo>≥</mo><msup><mover><msub><mi>r</mi><mo>*</mo></msub><mo>‾</mo></mover><mfenced><mi>i</mi></mfenced></msup><mn>.</mn></math><img file="EP2631798A2_D0033.tif" /></maths> According to Eq. (17), the cumulative reservation <i>r̅</i>_*^(<i>i</i>) is large enough to meet the resource needs of the prefix group at the QoS level of the last member of the group, job <i>i</i>, in every time interval. Hence, the provisioning for prefix group <i>i</i> ensures that job <i>i</i> will meet its QoS requirements.

0053For the tiered cases, Eqs. (16) and (17) can be rewritten as: <maths id="math0030" num="(18)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi mathvariant="italic">gτ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Ψ</mi><mi mathvariant="italic">gτ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msubsup><mi>p</mi><mi>g</mi><mfenced><mi>i</mi></mfenced></msubsup></mfenced><mo>,</mo></math><img file="EP2631798A2_D0034.tif" /></maths><maths id="math0031" num="(19)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mrow><mi>g</mi><mo>*</mo></mrow><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mi mathvariant="italic">gτ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>,</mo></math><img file="EP2631798A2_D0035.tif" /></maths> where <maths id="math0032"><math display="inline"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mrow><mi>g</mi><mo>*</mo></mrow><mfenced><mi>i</mi></mfenced></msubsup></math><img file="EP2631798A2_D0036.tif" /></maths> is the required reservation to meet the resource needs of the group at the QoS level of the last tier of the group (i.e., <maths id="math0033"><math display="inline"><msubsup><mi>p</mi><mi>g</mi><mfenced><mi>i</mi></mfenced></msubsup></math><img file="EP2631798A2_D0037.tif" /></maths>) for all time intervals.

0054The scaled individual reservation for job <i>i</i> can be calculated as an average of the fraction over all time intervals according to: <maths id="math0034" num="(20)"><math display="block"><msubsup><mi>γ</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><mfrac><msubsup><mi>r</mi><mrow><mo>*</mo><mi>τ</mi></mrow><mfenced><mi>i</mi></mfenced></msubsup><mrow><msub><mi mathvariant="normal">Σ</mi><mrow><mi>G</mi><mfenced><mi>j</mi></mfenced><mo>=</mo><mi>G</mi><mfenced><mi>i</mi></mfenced></mrow></msub><mo>⁢</mo><msubsup><mi>r</mi><mrow><mo>*</mo><mi>τ</mi></mrow><mfenced><mi>j</mi></mfenced></msubsup></mrow></mfrac><mo>,</mo></math><img file="EP2631798A2_D0038.tif" /></maths><maths id="math0035" num="(21)"><math display="block"><msup><mi>γ</mi><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mfrac><mn>1</mn><mi>T</mi></mfrac><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mi>τ</mi></munder></mstyle><msubsup><mi>γ</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup></mstyle><mo>,</mo></math><img file="EP2631798A2_D0039.tif" /></maths> there <i>T</i> is the number of time points.

0055The algorithm is similar to the single interval tier-based cascading-excess algorithm: <img file="EP2631798A2_D0040.tif" />

0056Because, for each <i>k</i>, <maths id="math0036"><math display="inline"><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><mi>G</mi><mfenced><mi>i</mi></mfenced><mo>=</mo><mi>k</mi></mrow></munder></mstyle><msup><mi>γ</mi><mfenced><mi>i</mi></mfenced></msup><mo>=</mo><mn>1</mn></mstyle><mo>,</mo></math><img file="EP2631798A2_D0041.tif" /></maths> logic that proves the correctness of the single interval scenario also holds for this multiple interval tier-based cascading-excess algorithm.

<u>Isolation between Job Models</u>

0057One of the benefits of virtualization is to allow virtual machines to share resources; yet another benefit, less often cited, is to isolate virtual machines from each other. It is challenging to achieve both these benefits because sharing resources often means that complete isolation is not possible or desirable. In practice, it is desirable to have enough isolation that rogue behavior of one job does not seriously impact the other jobs in the system.

0058A simple step to improve isolation is to use the "maximum" specifications presented in virtualization systems, such as VMware^® (registered trademark of VMware, Inc. of Palo Alto, California). For example, if an individual reservation for job <i>i</i> requires a reservation: <maths id="math0037" num="(22)"><math display="block"><msubsup><mi>r</mi><mo>*</mo><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Φ</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup></mfenced><mo>,</mo></math><img file="EP2631798A2_D0042.tif" /></maths> then a maximum could be set according to: <maths id="math0038" num="(23)"><math display="block"><msubsup><mi>m</mi><mo>*</mo><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Φ</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup><mo>/</mo><mn>2</mn></mfenced><mn>.</mn></math><img file="EP2631798A2_D0043.tif" /></maths> In other words, job <i>i</i> is not allowed to use more resources than necessary to outperform its QoS requirement by a certain constant factor, in this case 2. Another simple approach to specifying the maxima is to use a multiplicative factor greater than 1, such as 1.2, applied to <i>r</i>_*^(<i>i</i>), but the availability of Φ^(<i>i</i>) makes Eq. (23) a more principled approach to setting the maxima. Note that the maxima set in Eq. (23) can be set even when different group consolidation algorithms, described in the preceding section, are being used to set the minima (i.e., the reservations). While setting maxima is helpful, when group consolidation algorithms are used, additional technology is also needed to provide better control of job isolations.

0059When jobs are first virtualized, a conservative strategy is to reserve amounts of virtual resources equivalent to the previously employed physical resources. Although this does not completely isolate the jobs from each other (they still share and benefit from unused resources), they do at least as well as their previously non-virtualized physical implementations. Unfortunately, this conservative approach of simply reserving virtual resources equivalent to the previously employed physical resources does not realize the full benefits of virtualization. Once the resource needs of jobs are well modeled, and the QoS requirements are well specified, considerable additional savings in resources and improvement in QoS are possible through isolation reduction and resource sharing. This can be achieved through any of the aforementioned algorithms.

0060It is important to emphasize that jobs with highly variable resource needs are not a problem for the aforementioned resource consolidation algorithms, and do not need to be isolated, as long as their variability is adequately well modeled. When jobs are first virtualized, it is useful to manage the degree of isolation, starting with high isolation, and then as the jobs' resource needs are better modeled, reducing the isolation and achieving greater consolidation.

0061Here we introduce a parameter α that controls the isolation of jobs. α ranges between 0 and 1, with 0 meaning full isolation and 1 meaning full sharing of resources among jobs. For cases where jobs have distinct QoS levels, Eq. (22) defines an individual reservation, and the required reservation<i>r̅</i>_*^(<i>i</i>) for a prefix group {1, 2, ..., <i>i</i>} to meet the resource needs of the group at the QoS level of the last member of the group (i.e., <i>p</i>^(<i>i</i>)) is (according to Eqs. (16)-(17)): <maths id="math0039" num="(24)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mo>*</mo><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Φ</mi><mi>τ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msup><mi>p</mi><mfenced><mi>i</mi></mfenced></msup></mfenced><mn>.</mn></math><img file="EP2631798A2_D0044.tif" /></maths>

0062Assuming the jobs are sorted in descending QoS order and using Eqs. (22) and (24), we can set their allocation according to: <img file="EP2631798A2_D0045.tif" />

0063As one can see, at one extreme (α = 0), the above algorithm is reduced to the individual provisioning (<i>r̃</i>_*^(<i>i</i>) = <i>r</i>_*^(<i>i</i>)) defined by Eq. (22); at the other extreme (α = 1), the above algorithm is reduced to the multiple interval cascading-excess algorithm described in the previous section.

0064For cases where jobs may have the same QoS levels (the tier-based cases), the required reservation for a tier "prefix group" that can meet the QoS requirement of the last tier member is (according to Eqs. (18)-(19)): <maths id="math0040" num="(25)"><math display="block"><msubsup><mover><mi>r</mi><mo>‾</mo></mover><mrow><mi mathvariant="italic">g</mi><mo>*</mo></mrow><mfenced><mi>i</mi></mfenced></msubsup><mo>=</mo><munder><mi>max</mi><mi>τ</mi></munder><mspace width="1em" /><mi>inverse</mi><mspace width="1em" /><msubsup><mi mathvariant="normal">Ψ</mi><mi mathvariant="italic">gτ</mi><mfenced><mi>i</mi></mfenced></msubsup><mo>⁢</mo><mfenced><mn>1</mn><mo>-</mo><msubsup><mi>p</mi><mi>g</mi><mfenced><mi>i</mi></mfenced></msubsup></mfenced><mn>.</mn></math><img file="EP2631798A2_D0046.tif" /></maths>

0065Using the same α parameter, one can set the allocations according to: <img file="EP2631798A2_D0047.tif" />

0066Similarly to the previous algorithm, this tier-based algorithm is reduced to individual provisioning at α = 0, and to the multiple interval tier-based cascading-excess algorithm described in the previous section at α = 1.

0067Embodiments of the present invention provide a solution for long-term resource provisioning in data centers. More specifically, the system applies multiple interval algorithms (cascading-excess and tier-based cascading-excess) to models for future resource needs over multiple time intervals, such as multiple time periods over a day, or multiple days over a week, thus enabling less frequent changes in provisioning. Hence, the system provides human operators an opportunity to supervise resource provisioning. For example, a human operator can receive recommendations from a monitoring tool, which monitors the resource usage of the jobs, and can then manually apply the recommendations. Moreover, it is possible for the system to manage the degree of isolation among jobs. Particularly, the system can transition between a nearly complete isolation mode and a resource-sharing mode that enables highly efficient group consolidation. For example, when jobs are newly introduced and their resource needs are poorly understood, the system can operate in the complete isolation mode where jobs receive individual reservations that can meet their QoS needs. After the jobs are better modeled and the potential sharing of resources can be analyzed and implemented, the system can operate in the sharing mode where reservations are made to the group (based on the total pool allocation algorithm and its variations) to enable efficient group consolidation.

<u>System and Modules</u>

0068<figref idref="f0003">FIG. 3</figref> presents a diagram illustrating a resource-provisioning controller, in accordance with an embodiment of the present invention. In <figref idref="f0003">FIG. 3</figref>, resource-provisioning controller 300 includes a QoS identifier 302, a resource-usage monitor 304, a resource-usage model constructor 306, a reservation calculator 308, an excess-redistribution module 310, a scheduler 312, and a user interface 314.

0069Resource-provisioning controller 300 controls the resource provisioning of jobs located on a physical machine or a cluster of machines in order to achieve the best performance. QoS identifier 302 identifies the QoS requirements associated with each job. In one embodiment, the QoS requirement is expressed by a shortfall probability. Resource-usage monitor 304 monitors the resource needs for each job, which can be totally random or have a certain temporal pattern. Resource-usage model constructor 306 receives usage information from resource-usage monitor 304 and constructs a resource-usage model for each job accordingly. In some embodiments, resource-usage model constructor 306 computes models for prefix groups of jobs. In one embodiment, the resource-usage model includes a resource-needs distribution function, which indicates the probability of a job or group of jobs needing a certain amount of resources. In a further embodiment, the resource-usage model includes a temporal distribution of the resource needs of a job or group of jobs. For example, the probability for certain jobs to need a large amount of resources in the morning may be high.

0070Based on the constructed resource-usage model and the QoS requirement for each job, reservation calculator 308 computes the required reservation for each job. In one embodiment, a total pool allocation algorithm is used to compute the required reservation. More specifically, reservation calculator 308 first indexes the jobs in descending QoS order, and then finds the smallest index <i>k</i> such that the partial sum of the individual reservations for the first <i>k</i> - 1 jobs plus a partial reservation for job <i>k</i> is large enough to meet the entire group's resource needs at the <i>k_th</i> job's QoS level. In other words, reservation calculator 308 outputs reservations for the first <i>k</i> - 1 jobs as their individual reservations required to meet their QoS requirements, a reservation for the <i>k_th</i> job as a fraction of its individual reservation required to meet its QoS requirement, and zero reservations for the remaining lower QoS jobs. In one embodiment, reservation calculator 308 computes the reservations using a fixed-point variation of the total pool allocation algorithm. Note that in order to implement the fixed-point variation, resource-usage model constructor 306 needs to construct joint models for jobs that describe resource needs for a job and the remainder of the group.

0071Excess-redistribution module 310 controls how the unused reservations are redistributed among jobs. In one embodiment, excess-redistribution module 310 uses the "share" machinery that assigns shares to jobs based on their QoS requirement, and more shares are given to higher QoS jobs. In this way the operation of a system such as VMware, bydistributing unused reservations proportionally to the shares, will cause unused reservations cascade through the remaining jobs in QoS order. In one embodiment, excess-redistribution module 310 uses the "grouping" machinery that builds a hierarchy of groups, each of which is formed by adding a next-in-line lower-ordered QoS job to a previously formed group. The reservation made for the newly added job is the additional reservation necessary for the job (beyond the sum of reservations already made for the higher QoS jobs) that can meet the QoS requirement for the current group. Note that in cases where the unused reservations are distributed evenly among remaining jobs, excess-redistribution module 310 is not invoked.

0072In one embodiment, outputs of reservation calculator 308 and excess-redistribution module 310 are sent to scheduler 312, which makes the actual reservations for each job. In one embodiment, the outputs are sent to user interface 314, which presents the output to a human operator. The human operator can review the proposed resource provisioning and determine whether to implement such provisioning. User interface 314 also enables the operator to control isolation module 316. More specifically, the operator can set the isolation parameter. Using the isolation parameter, isolation module 316 can manage the degree of isolation among jobs. If the isolation parameter is set as 0, total isolation of jobs is required by isolation module 316. Consequently, reservation calculator 308 computes reservations for jobs based on their individual needs. If the isolation parameter is set as 1, isolation module 316 allows jobs to share resources completely. Consequently, reservation calculator 308 computes reservations for jobs based on their needs as a group. In a further embodiment, instead of a human operator, isolation module 316 determines the isolation parameter based on inputs from resource-usage monitor 304. As the system gradually accumulates knowledge about the resource-usage of the jobs, isolation module 316 increases the isolation parameter.

0073Resource-provisioning controller 300 can be used to provision resources for a single time interval or multiple time intervals. When used for multiple interval provisioning, resource-usage model constructor 306 needs to construct resource-usage models for the various time intervals, and reservation calculator 308 computes the reservations for jobs that can meet the QoS requirements for all time intervals. Similarly, excess-redistribution module 310 also needs to implement the multiple interval algorithm when redistributing the unused reservations. Provisioning strategy for the multiple intervals can be presented to the operator by user interface 314, and the operator can instruct scheduler 312 to implement the proposed provisioning for the multiple time intervals simultaneously.

0074<figref idref="f0004">FIG. 4</figref> presents a flowchart illustrating an exemplary process of resource provisioning, in accordance with an embodiment of the present invention. During operation, the system identifies QoS requirements for each job running on a machine or a cluster of machines (operation 402), and constructs a resource-usage model for each job based on the resource-usage history of the job (operation 404). In one embodiment, the resource-usage model includes a resource-usage probability distribution function, such as a probability density function (PDF). In a further embodiment, the resource-usage-distribution probability function varies with time.

0075Subsequently, the system computes resource reservations for jobs (operation 406). Depending on the desired level of consolidation, various algorithms can be used to compute the resource reservations, including but not limited to: a simple total pool allocation algorithm, a fixed-point variation of the total pool allocation algorithm, a cascading-excess algorithm, and a tier-based cascading-excess algorithm. In a further embodiment, the system uses an isolation parameter to control the degree of isolation among jobs. Note that the computed resource reservations can be applied to a single time interval or multiple time intervals. For multiple interval cases, the multiple interval variations of the various algorithms are implemented by the system when computing the resource reservations.

0076The system optionally presents the computed resource reservations to a human operator (operation 408) and receives feedback from the operator (operation 410). Based on the operator's feedback, the system implements the resource reservations for a single time interval or multiple time intervals (operation 412).

0077<figref idref="f0005">FIG. 5</figref> illustrates an exemplary computer system for resource provisioning in a data center, in accordance with one embodiment of the present invention. In one embodiment, a computer and communication system 500 includes a processor 502, a memory 504, and a storage device 506. Storage device 506 stores a resource-provisioning application 508, as well as other applications, such as applications 510 and 512. During operation, resource-provisioning application 508 is loaded from storage device 506 into memory 504 and then executed by processor 502. While executing the program, processor 502 performs the aforementioned functions. Computer and communication system 500 is coupled to an optional display 514, keyboard 516, and pointing device 518.

0078Note that the considerations of resource provisioning can be applied at multiple levels in the data centers, including a single machine, a cluster of machines, or a data center, where group consolidation can be used to improve the resource utilization while meeting QoS requirements.

0079The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. The computer-readable storage medium includes, but is not limited to, volatile memory, non-volatile memory, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs), DVDs (digital versatile discs or digital video discs), or other media capable of storing computer-readable media now known or later developed.

0080The methods and processes described in the detailed description section can be embodied as code and/or data, which can be stored in a computer-readable storage medium as described above. When a computer system reads and executes the code and/or data stored on the computer-readable storage medium, the computer system performs the methods and processes embodied as data structures and code and stored within the computer-readable storage medium.

0081Furthermore, methods and processes described herein can be included in hardware modules or apparatus. These modules or apparatus may include, but are not limited to, an application-specific integrated circuit (ASIC) chip, a field-programmable gate array (FPGA), a dedicated or shared processor that executes a particular software module or a piece of code at a particular time, and/or other programmable-logic devices now known or later developed. When the hardware modules or apparatus are activated, they perform the methods and processes included within them.