Hybrid virtual machine allocation optimization system and method

Patent metadata

Field	Value
Publication number	US-12578985-B2
Application number	US-202218070118-A
Country	US
Kind code	B2
Filing date	Nov 28, 2022
Priority date	Nov 28, 2022
Publication date	Mar 17, 2026
Grant date	Mar 17, 2026

Abstract

Systems and methods for determining an allocation plan for allocating virtual machines (VMs) to a hosted service utilizes a demand forecast that predicts future demand for VMs, a response curve that correlates user experience to VM utilization, and an estimated spot eviction rate to determine the allocation plan. The demand forecast, the response curve and the eviction rate are processed using mixed-integer optimization to determine the numbers of VMs of each allocation type that should be online at any given time to meet demand.

First claim

What is claimed is:

1 . A data processing system comprising:
a processor; and a machine-readable medium storing executable instructions that, when executed, cause the processor to perform operations comprising:
estimating a demand forecast for allocating virtual machines (VMs) to a service hosted by a cloud service provider over a predetermined allocation time period based on historical demand data;
using a causal inference model to determine a response curve that correlates user experience to VM utilization, the causal inference model receiving historical utilization data, historical customer satisfaction data, and historical cost data and producing the response curve as an output;
estimating an eviction rate for spot VMs based on historical eviction data; and
using an allocation optimizer model to process the demand forecast, the response curve, and the eviction rate along with current allocation data and current pricing data corresponding to a plurality of different VM allocation types using mixed-integer optimization to determine an allocation plan that identifies numbers of VMs of each of the VM allocation types to allocate during the allocation time period; and
performing a resource allocation for the service based on the determined allocation plan during the allocation time period.

2 . The data processing system of claim 1 , wherein the demand forecast is estimated using one or more forecasting algorithms.

3 . The data processing system of claim 1 , wherein the response curve indicates an optimal number of sessions per VM threshold that minimizes impact of utilization of VMs on user satisfaction.

4 . The data processing system of claim 3 , wherein the historical customer satisfaction data is based on a Customer Satisfaction (CSAT) metric based on user input to questions pertaining to use of services provided by the cloud service provider.

5 . The data processing system of claim 1 , wherein the eviction rate indicates a probability that a spot VM will be evicted within a predetermined time horizon.

6 . The data processing system of claim 1 , wherein a weighted average of the historical eviction data over a predetermined eviction time period is used to estimate the eviction rate.

7 . The data processing system of claim 1 , wherein the VM allocation types include a spot VM allocation type, and
wherein the estimated eviction rate is used to determine how many spot VMs to allocate as part of the allocation plan.

8 . The data processing system of claim 7 , wherein the VM allocation types include an on-demand type and a reserved type, and
wherein the allocation plan identifies a number of the on-demand type and a number of the reserved type to allocate as part of the allocation plan.

9 . The data processing system of claim 1 , wherein the allocation time period is at least a week.

10 . The data processing system of claim 1 , wherein the mixed-integer optimization involves minimizing a cost of allocation of VMs for the service,
wherein the numbers of each of the VM allocation types correspond to decision variables for the mixed-integer optimization that are used to minimize the cost of allocation, and wherein the demand forecast, the response curve, the eviction rate, the current allocation data, and the current pricing data correspond to constraints for the mixed-integer optimization.

11 . The data processing system of claim 1 , wherein the operations further comprise:
displaying a graphical representation of the allocation plan on a user interface; and receiving input from a user via the user interface that specifies at least one user selectable parameter, the at least one user selectable parameter being used in determining at least one of the demand forecast, the response curve, the eviction rate, and the allocation plan.

12 . A method for determining allocation plan for identifying numbers of VMs of each of a plurality of VM allocation types to allocate to a service hosted by a cloud service provider during an allocation time period, the method comprising:
estimating a demand forecast for allocating virtual machines (VMs) to a service hosted by a cloud service provider over a predetermined allocation time period based on historical demand data; using a causal inference model to determine a response curve that correlates user experience to VM utilization, the causal inference model receiving historical utilization data, historical customer satisfaction data, and historical cost data and producing the response curve as an output; estimating an eviction rate for spot VMs based on historical eviction data; and using an allocation optimizer model to process the demand forecast, the response curve, and the eviction rate along with current allocation data and current pricing data corresponding to a plurality of different VM allocation types to determine an allocation plan that identifies numbers of VMs of each of the VM allocation types to allocate during the allocation time period; and performing a resource allocation for the service based on the determined allocation plan during the allocation time period.

13 . The method of claim 12 , wherein the allocation optimizer model processes the demand forecast, the response curve, the eviction rate, the current allocation data, and the current pricing data using mixed-integer optimization to determine the allocation plan.

14 . The method of claim 13 , wherein the mixed-integer optimization involves minimizing a cost of allocation of VMs for the service,
wherein the numbers of each of the VM allocation types correspond to decision variables for the mixed-integer optimization that are used to minimize the cost of allocation, and wherein the demand forecast, the response curve, the eviction rate, the current allocation data, and the current pricing data correspond to constraints for the mixed-integer optimization.

15 . The method of claim 12 , wherein the response curve indicates an optimal number of sessions per VM threshold that minimizes impact of utilization of VMs on user satisfaction.

16 . The method of claim 15 , wherein the historical customer satisfaction data is based on a Customer Satisfaction (CSAT) metric based on user input to questions pertaining to use of services provided by the cloud service provider.

17 . The method of claim 12 , wherein a weighted average of the historical eviction data over a predetermined eviction time period is used to estimate the eviction rate.

18 . The method of claim 12 , wherein the VM allocation types include a spot VM allocation type, and
wherein the estimated eviction rate is used to determine how many spot VMs to allocate as part of the allocation plan.

19 . The method of claim 18 , wherein the VM allocation types include an on-demand type and a reserved type, and
wherein the allocation plan identifies a number of the on-demand type and a number of the reserved type to allocate as part of the allocation plan.

20 . A non-transitory computer readable medium on which are stored instructions that, when executed by a processor, cause a programmable device to perform functions of:
estimating a demand forecast for allocating virtual machines (VMs) to a service hosted by a cloud service provider over a predetermined allocation time period based on historical demand data; using a causal inference model to determine a response curve that correlates user experience to VM utilization, the causal inference model receiving historical utilization data, historical customer satisf

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Ahlvin Benjamin Eric
• Peng sida
• Atchison Abigail Sandra

Classifications

• G06Q10/04

  Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) · CPC title

• G06F2009/45595

  Network integration; Enabling network access in virtual machine instances · CPC title

• G06F2009/4557

  Distribution of virtual machine instances; Migration and load balancing · CPC title

• G06N5/04

  Inference or reasoning models · CPC title

• G06F2209/5019

  Workload prediction · CPC title