Patent Description:
Virtual machines (VMs) are virtualised computing components that execute with physical hardware to provide virtual computer systems. VMs are dynamically deployable such that a VM can be instantiated for execution of tasks such as software operations at runtime. Further, VMs can be terminated on completion of tasks to free-up infrastructure resources for redeployment to other VMs. The efficient use of physical computing infrastructure across potentially multiple dynamically created and completing VMs is important to avoid excessive resource consumption. To balance this, it is necessary that sufficient infrastructure resource is available for all deployed VMs such that a failure of an operation executing in a VM does not arise as a result of, for example, insufficient physical resource, excessive resource sharing, insufficient performance and/or an inability to complete a task execution in a required timeframe. Thus, there is a challenge in scheduling VMs to physical computing infrastructure to provide efficient and effective completion of tasks executed by VMs.

A scheduling method for managing risk in resource over committed systems is described in <CIT> that discloses the immediate provision of VMs in a system in response to a specific request considering the resource load of the system and the likelihood of spikes in the resource requirements.

According to a first embodiment of the present invention, a computer implemented method of scheduling a plurality of virtual machines for execution by a physical computing infrastructure is provided, each virtual machine being deployable to a subset of the infrastructure to execute a computing task, the method comprising: determining, for each virtual machine, a subset of the infrastructure and a time period for deployment of the virtual machine, so as to schedule the virtual machines to execute to completion over an aggregate of all time periods; and deploying each virtual machine by provisioning of physical resources in accordance with the determining step, wherein the determination is based on a mathematical optimisation of a risk function for each of the virtual machines corresponding to a relative risk that a virtual machine will fail to fully execute its task to completion; wherein the risk function is a function of a likelihood of failure of a task for a virtual machine and a relative impact of such failure, wherein the likelihood of failure is determined based on a probability that execution of the task will commence in accordance with the schedule, and based on a probability that execution of the task will complete in accordance with the schedule, wherein the impact of the failure is a function of a criticality of a job request, wherein the likelihood of failure is defined along a time dimension due to a processing and/or duration variability, and due to network delay variability, the likelihood of failure is additionally defined along a magnitude dimension, wherein the processing and/or duration variability is a probability of the task not starting on a server within its virtual machine time period and a probability of the task not being completed before a target time, wherein the network delay variability is a probability of having a network delay variability above or up to an acceptable criteria, wherein the magnitude dimension is a probability of the task failing the instantiation to a virtual machine time period by its target due to requirements concerning an amount of physical resources consumed, and wherein the mathematical optimisation is further arranged to minimise a quantity of physical resources in the physical computing infrastructure consumed to execute the virtual machines to completion over the aggregate time period.

According to a second embodiment of the present invention, a computer system is provided including a processor and memory storing computer program code for performing the steps of the method set out above.

According to a third embodiment of the present invention, a computer system including a processor and memory storing computer program code is provided for performing the steps of the method set out above.

Examples of the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which:.

<FIG> is a block diagram of a computer system suitable for the operation of embodiments of the present invention. A central processor unit (CPU) <NUM> is communicatively connected to a storage <NUM> and an input/output (I/O) interface <NUM> via a data bus <NUM>. The storage <NUM> can be any read/write storage device such as a random-access memory (RAM) or a non-volatile storage device. An example of a non-volatile storage device includes a disk or tape storage device. The I/O interface <NUM> is an interface to devices for the input or output of data, or for both input and output of data. Examples of I/O devices connectable to I/O interface <NUM> include a keyboard, a mouse, a display (such as a monitor) and a network connection. examples of the present invention provide risk-aware heuristics methods to support real-time dynamic allocation of tasks to virtual machine (VM) slots of physical computing infrastructure resources. The mechanism introduces a risk-dependent element to a scheduler's core optimiser. This element calculates, in one example, an aggregated risk from weighted risk estimates of scheduled tasks alongside other potentially other scheduling costs. A risk assessment function can automatically update and propagate risk into the future when a task's expectation and/or physical resources change and if necessary trigger re-optimisation.

A data center (DC) or server farm is a cluster of potentially many computer systems such as servers forming, for example, an organisation's internal IT infrastructure and/or external IT-based services such as cloud services. They are typically host to a multiple commodity hardware and software as physical computing infrastructure including, inter alia, servers, top-of-rack and aggregation switches, routers, load balancers and middleware. Cloud computing services require a combination of multiple resources such as link bandwidth and IT (CPU, I/O bandwidth etc.).

<FIG> is a component diagram of an arrangement for scheduling virtual machines for use with physical computing infrastructure according to an example of the present invention. A set of computing tasks <NUM> such as execution of software application(s), software batch processes, real-time software processes or the like, are undertaken by way of deployment of VMs <NUM> using physical computing infrastructure. The physical computing infrastructure can be provided by, for example, DCs and constitutes a physical platform which provides resources for cloud computing services for the execution of applications. Each application is performed through jobs constituted as one or more tasks that are executed by means of VMs which are deployed using DC physical resources (e.g. CPU, I/O, network links). Sun an arrangement is depicted, for example, in <FIG>. Due to the intrinsically variable and multi-tenant nature of cloud services, it is challenging for a cloud computing provider to estimate, at a given time, physical resource availability and an expected performance for a particular application, job and/or task. Where volatility increases the risks of unmanaged peak-demand and service performance degradation also increases.

A distinguishing feature of DC workload is that a fraction of DC workload is flexible, that is it can be re-scheduled. Hence a cloud provider can derive benefits from optimising workload time scheduling to VMs throughout a period of time managing peak-demand and minimising risks of service degradation. Examples of the present invention provide a risk-aware meta-heuristics methodology which reduces a risk of service degradation and balances other objectives, complementing the function of a main optimiser performing real-time dynamic scheduling of Tasks to DC's physical resources VM time slots. Such an optimiser for conventional VM scheduling is known in the art.

Thus, examples of the present invention provide a risk-aware element which operates within a scheduler's optimiser for calculating a cumulative risk from weighted risk estimates for each of a plurality of scheduled (or to be scheduled) Tasks. Other parameters in a scheduling objective function can also be taken into account, such as minimising a number of unallocated tasks, optimising a utilisation of physical resources according to energy saving objectives, and/or minimising a lead time for tasks across a scheduling time period.

An iterative risk assessment function automatically updates and propagates risk for tasks for execution by VMs in time slots into the future. In the event of a change to a task duration - deviating from an expectation - or a change to physical resource utilization, a rescheduling (by re-allocation) of tasks to VMs and physical infrastructure can be performed.

A VM can be characterised by two main characteristics:.

Heuristics employed in examples of the present invention operate on a time dimension for VMs, assuming that execution of certain tasks can be delayed. A further dimension for VMs is a magnitude of physical resources utilised and can be modelled through a risk of task failure due to lack of resources.

A DC's resources and workload planning functions need to cater for task requests in real-time by assigning tasks to VMs on available physical resources. Additionally, it is necessary to make provision for future demand and this can be achieved by monitoring DC utilisation and workload forecasts (which predict expected tasks over time) and ensuring adequate future resource provisioning.

DC workload is subject to variability arising from, for example:.

In order to restrict the impact of such uncertainty on service quality, embodiments of the present invention introduce real-time risk-aware optimisation of task scheduling to VM slots deployable to available physical resources.

Examples of the present invention thus provide:.

In a preferred example, de-risking employs a novel heuristics-search method which combines swap and insertion of tasks to a VM slot schedule and computes a neighbourhood according to a risk of already scheduled tasks and remaining feasible slots for unallocated Tasks (see <FIG>).

Some examples of the present invention provide benefits such as:.

Some examples of the present invention provide output including:.

Examples of the present invention undertake risk calculation using constraints propagation as a risk assessment method at a task level, where each task has an expected start time. This can be modelled through three main features of the system for tasks:.

Thus, some examples of the present invention assess each task allocation risk at the following <NUM> levels:.

In examples of the present invention, the model is based on a set of constraint objects, where each task is modelled with an invariants function of previous tasks in the schedule, task precedence and parallel relations, and task splitting over multiple time slots. An invariant is a type of functional constraint that is composed of a set of inputs, an output and a function that calculates the output when the inputs are valued. The root input of the network is a first task variable. The scheduler estimates, through such a function, the task start/end times and a risk function for all tasks resulting from a task allocation when associating (scheduling) a task and its associated VM to a time slot and physical resource. Objectives of the scheduler include reducing (preferably minimising) a sum of risk for every task in the schedule. Task variables include an earliest start time, latest start time, earliest end time, and latest end time of the task (see <FIG> and <FIG>). These variables are influenced by previous tasks in the schedule, the resource and a time slot the task is scheduled to.

A resource can be represented as a tuple [PhysicalServer, TimeSlot]. When a new task arrives, likelihood and impact for each pair (Ri, TSj) are assessed, where Rj is resource j and TSj is time-slot j. Given a schedule S composed of a set of resources {Resources} and a set of tasks {Tasks}, an objective is to minimise an objective function with <NUM> components with priority being driven by weights. These three components are:.

When building a schedule S, an overall objective can be to minimise the following weighted function <MAT>.

Thus, given schedule S and resource ri, task tj:.

and a likelihood of not having sufficient resource meeting the asked performance features: <MAT> where:.

A risk of given VM slots, reserved for Task ti, going un-allocated is the probability of the task arrival time being later than the time window (refer to the shaded part of the normal distributions in <FIG>). The stochasticity of a task arrival time is due to its random nature and uncertainty about task duration and network delay.

A task's VM time slot duration is modelled as a distribution learned over time (e.g. normal distribution) and may be described by means of: <MAT> <MAT>.

Task allocation can be seen as a sequence of independent such distributions. A task scheduling engine computes in real-time earliest/latest start/end times (as depicted in Figure <FIG>) of all expected Tasks based on their respective duration distributions, then sums up all the risk to obtain the overall risk Risk(t,r,S) which it then aims to minimise through re-allocation of tasks to [resource, timeslots] through equation (<NUM>).

For example, in the example of <FIG>, an end time of T1 is represented by a distribution starting from <NUM>:<NUM>, with a mean value at <NUM>:<NUM> (the mean point in a normal is equal to the end time that would be obtained without a risk model) and with a latest value at <NUM>:<NUM>. The end time of T2 is represented by a distribution starting from <NUM>:<NUM>, with a mean value at <NUM>:<NUM> and with a latest value at <NUM>:<NUM>. It can be seen that the T1 duration distribution is influencing the distribution of start times for T2 and the end times for T2; thus T2 duration distribution and the T2 start times distribution are added (the start times distribution being, itself, a function of the T1 distribution).

Task variability in start and end time as modelled through such distributions are iteratively accumulated taking into account previously scheduled tasks. Task start time and end time are influenced by a task processing time and an end time of previous tasks in the schedule. <FIG> and <FIG> illustrate how a probability of task start/end time is propagated over the schedule. The model defines function fstan and fend which are the distributions of task start and end time. <MAT> where j>=<NUM> and fstart(ri, t0,S) = aConstant <MAT> where j>=<NUM> and fend (ri, t0,S) = aConstant
where Fa is the function which recursively aggregates the probability on tj time, where task tj is inserted in schedule S, from twofold inputs: <NUM>) a probability of previous task tj-<NUM> end time; and <NUM>) the probability of tj processing time.

Probability of failure for task ti is then a function -called Pc here - returning a portion of a distribution of tj start or end time or tj's network transfer duration or tj's magnitude requirement match, that overlaps the failure criteria (beyond target, out of VM slot, exceeding available resources): <MAT> where j>=<NUM> <MAT> where j>=<NUM>.

In case of Network delay and Magnitude probability, there is a likelihood components are summing up the probability of excessive network delay, or magnitude requirement failure over the tasks in {Tasks}. The model defines function fnetwork which is a distribution of network transfer times over the network path between a job request machine and a physical resource, and fmagnitude which is an amount of resource likely to be available after task consumption (i.e. VM instantiation). <MAT> where j>=1and fnetwork(ri, t0,TSi, S) = aConstant <MAT> where j>=<NUM> <MAT> and fmagnitude(ri, t0,TSi, S)=aConstant <MAT> where j>=<NUM>.

<FIG> provides an example of theses variables for a sequence of <NUM> scheduled tasks to the same resource, T1 and T2. Earliest start and latest start times are themselves functions of the task processing time.

In <FIG>: T2. earliestStartTime = Fstart(T1. earliestEndTime, T2. startTimeDistribution, T2. timeslot, R) , where Fstart is the function calculating recursively the start time distribution of each scheduled task, from the distribution of previous task in schedule.

Similarly, T2. latestStartTime = Fstart(T1. latestEndTime, T2. startTimeDistribution, T2. timeslot, R) <MAT> <MAT>.

In <FIG>, an example of a task duration distribution is depicted as a normal distribution. Here the end time of T1 is represented by a distribution starting from <NUM>:<NUM> (T1 is estimated to end at the earliest at <NUM>:<NUM>), with a mean value at <NUM>:<NUM> (the mean point in a normal law is equal to the end time that we would get without the risk model) and with a latest value at <NUM>:<NUM>. The end time of T2 is represented by a distribution starting from <NUM>:<NUM>, with a mean value at <NUM>:<NUM> and with a latest value at <NUM>:<NUM>. It can be seen that the T1 duration distribution is influencing the distribution of start times for T2; with T2's own variability being driven by and the end times for T2 is influenced by both the T2 duration distribution and the T2 start times distribution (which itself is a function of T1 distribution). We call this impacting mechanism from one task to the other scheduled task the risk propagation.

In <FIG>, an example of an approximate mathematical method of propagation is illustrated. Assuming a task start-time and duration distributions can be described by N independent random variables Xi, where each Xi follows a Gamma law Γ(ki, θ) for i = <NUM>, <NUM>,. , N, then the end-time distribution can be obtained through a propagation of such distributions and is given by of the sum of Xis which can be approximated as the Gamma function as follows: <MAT>.

<FIG> provide an example that illustrates the technical effect of risk assessment while scheduling VMs within an optimiser for a cloud computing environment. At the start of the scheduling horizon <FIG>, we have four tasks/VMs already planned to be processed and instantiated on given time slot. Exemplary risk estimates that the scheduler may have calculated for an entire day at a start of the scheduling horizon for <FIG> is given in table <NUM>:.

The optimiser has scheduled the tasks to two physical resources R1 and R2 over the entire scheduling horizon. R1 is used over three time slots TS1, TS2 and TS3, where <NUM>% of the available features are planned to be consumed on TS1, <NUM>% planned to consume on TS2, and <NUM>% planned on TS3. R2 is used over one time slot TS4 using <NUM>% of resources. R3 has not had any VM allocated yet. Table <NUM> shows resource pair (Tasks, Time slot) and overall risks calculated by the scheduler with the aim of maintaining the risk for failing time or magnitude on T1 and T3 in TS1, and on T2 in TS2, and T5 on TS3 to lower than a threshold.

As considered earlier in (with respect to equation (<NUM>)), the overall cost is a trade-off between <NUM> items with a priority being balanced through weights: <NUM>) Overall risk in R1 for the <NUM> tasks; <NUM>) Overall workload completion time and <NUM>) resource consumption over R1, R2, R3. R3 is left spare, minimising the number of resources used while minimising the risk of failing the tasks (satisfying item <NUM>).

Assuming a first time in which the schedule needs to be rearranged is due to the arrival of a new task, T6, then the scheduler considers three possible options, depicted in <FIG>, <FIG> and <FIG>. These three possible options can be made depending on the importance weights of the above three cost items:.

Option <NUM>: Schedule to R2: as depicted in <FIG> and based on the risks calculated as set out in Table <NUM>.

Option <NUM>: Schedule to R3: as depicted in <FIG> and based on the risks calculated as set out in Table <NUM>.

Option <NUM>: Schedule to R1: as depicted in <FIG> and based on the risks calculated as set out in Table <NUM>.

Option <NUM> may be chosen if there is no risk trade-off and T6 can be performed on R2. Assuming T6 features and required (entire horizon) time slot fit into the capability and availability of R2, that is T6 will consume the <NUM>% left time space on R2. The consumption of R2 is likely to vary above <NUM>% and thus there is a significant likelihood for the completion of T6 to be delayed. The estimated risk of failure of T6 if instantiated on R2 reaches a high level of <NUM>%.

Options <NUM>: With Option <NUM>, the magnitude (bandwidth for instance) required by T6 is so that the estimated risk of failure of T6 if instantiated on R2 reaches <NUM>%, hence another option is explored i.e. R3. If R3 has enough bandwidth then T6 will be scheduled to R3, with a low risk of <NUM>% say. However if R3 does not have enough bandwidth while R2 does, then the core optimiser may capture this while assessing the risk of assignment T6-> R3, which will result to the assignment T6 -> R2 and may reschedule T4 -> R3. An alternative decision could be to reschedule T4 -> R1 but because T4 was previously planned the cost optimiser heuristics drive it to reschedule to a position where the risk is kept a low as possible (not higher than the risk of T4 when it was on R2).

Option <NUM> will be considered if there is risk of failing T6 on R2 and R3. However, since R1 is already busy with a plan of Jobs, there is risk of causing some failure on the already planned tasks. Here the schedule will focus on minimising risk over all tasks, possibly evaluating the re-arrangement of some of the earlier allocation. In this case the engine reschedules T4-> (R3, TS5) and T6-> (R2, TS4) which minimises the overall tasks' risks.

The schedule will thus decide on Option <NUM>.

<FIG> is a flowchart of a method of scheduling a plurality of virtual machines for execution by a physical computing infrastructure according to examples of the present invention. Each virtual machine is deployable to a subset of the infrastructure to execute a computing task. At step <NUM> the method determines a subset of the infrastructure and a time period for deployment of the virtual machine. In this way, the method schedules the virtual machines to execute to completion over an aggregate of all time periods. Notably, the determination is based on a mathematical optimisation of a risk function for each of the virtual machines corresponding to a relative risk that a virtual machine will fail to fully execute its task to completion.

In one example, the risk function is a function of a likelihood of failure of a task for a virtual machine and a relative impact of such failure. The likelihood of failure can be determined based on a probability that execution of the task will commence in accordance with the schedule, and based on a probability that execution of the task will complete in accordance with the schedule.

In one example, the mathematical optimisation is arranged to minimise a quantity of resources in the physical computing infrastructure consumed to execute the virtual machines to completion over the aggregate time period.

Claim 1:
A computer implemented method of scheduling a plurality of virtual machines (<NUM>) for execution by a physical computing infrastructure (<NUM>), each virtual machine (<NUM>) being deployable to a subset of the infrastructure (<NUM>) to execute a computing task (<NUM>), the method comprising:
determining, for each virtual machine (<NUM>), a subset of the infrastructure (<NUM>) and a time period for deployment of the virtual machine (<NUM>), so as to schedule the virtual machines (<NUM>) to execute to completion over an aggregate of all time periods; and
deploying each virtual machine by provisioning of physical resources in accordance with the determining step,
wherein the determination is based on a mathematical optimisation of a risk function for each of the virtual machines (<NUM>) corresponding to a relative risk that a virtual machine (<NUM>) will fail to fully execute its task to completion; wherein the risk function is a function of a likelihood of failure of a task for a virtual machine (<NUM>) and a relative impact of such failure, wherein the likelihood of failure is determined based on a probability that execution of the task (<NUM>) will commence in accordance with the schedule, and based on a probability that execution of the task (<NUM>) will complete in accordance with the schedule, wherein the impact of the failure is a function of a criticality of a job request, wherein the likelihood of failure is defined along a time dimension due to a processing and/or duration variability, and due to network delay variability, the likelihood of failure is additionally defined along a magnitude dimension, wherein the processing and/or duration variability is a probability of the task not starting on a server within its virtual machine time period and a probability of the task not being completed before a target time, wherein the network delay variability is a probability of having a network delay variability above or up to an acceptable criteria, wherein the magnitude dimension is a probability of the task failing the instantiation to a virtual machine time period by its target due to requirements concerning an amount of physical resources consumed, and
wherein the mathematical optimisation is further arranged to minimise a quantity of physical resources in the physical computing infrastructure (<NUM>) consumed to execute the virtual machines (<NUM>) to completion over the aggregate time period.