An Analytic Approach to Solving Load Balancing Problem in the Cloud

From Gravitant's blog.

http://blog.gravitant.com/2011/09/26/an-analytic-approach-to-solving-load-balancing-problem-in-the-cloud/

IT management moves into a new dimension by the Cloud. In traditional IT, most of the cost generation occurs in procurement of resources, provisioning and maintenance. By nature, the cost generation is fairly static in traditional IT. Fixed cost of hardware and data centers and stable variable maintenance and provisioning costs contribute to this static cost structure. Cloud’s dynamic nature affects cost management of enterprises in the Cloud, too. Pricing strategies of cloud providers go along with principle of cloud as a utility. Although many pricing options have a fixed portion for a reserved capacity, the usage based cost is always a significant and varying part of enterprise cloud costs. This dynamic cost structure increases the importance of intelligent provisioning and management.

My previous article, “Cloud Sourcing Optimization: A Conceptual Model Discussion”, in Gravitant’s blog, introduces Gravitant’s efforts in optimization in Cloud analytics. The next of the series is investigating analytic solution approaches to solving load balancing problems.

The underlying problem is simply to determine when to turn off a virtual machine (VM) due to low utilization without allowing utilization of any VM to exceed a certain threshold level by turning on a new VM. The aim is to keep VM utilization within a reasonable band to minimize provisioning cost while satisfying workload demand. The question is what the “optimal” high-mark and low-mark utilization values to turn on and off VMs are.

The obvious decision variables in a corresponding optimization problem are high-mark utilization value, low-mark utilization value, whether an existing VM is turned off due to low utilization, and whether a new VM is created due to high utilization of any VM. Each turned of VM creates an extra load of work on the rest of the VMs. Each new VM shares the load of a high-utilized VM. Objective is to minimize total cost of provisioning. Set of constraints can be summarized in three groups.

1- High-mark utilization: New utilization of the remaining VMs after adding the used capacity of low-utilization VMs should be lower than high-mark utilization value.

2- Low-mark utilization: Any VM should have a utilization more than low-mark utilization value.

3- New VM creation: If a VM has a higher-than-high-mark utilization, then a new VM is created.

Because there are both binary and continuous variables, the optimization model tends to be a mixed integer programming model. However, since the first set of constrains is quadratic, the exact definition of the model is quadratically constrained mixed integer programming model. Some straightforward enumeration over the set of VMs will help linearize the constraint. Therefore, we will have a mixed integer linear programming model.

Although this static model may seem restrictive in a setting with a varying amount of demand for virtual machines to meet under budget limitations, it has ability to roll over time and transform into a dynamic model which would fit very well to the span of provisioning and the nature of the Cloud. The utilization band in which VMs are allowed to operate changes dynamically and provides a flexible space for decision makers.

This article reveals the tip of the iceberg of the analytic solutions which Gravitant offers as a cloud brokerage and management company for the enterprises. Our set of analytic solutions that help enterprises move into and operate in the Cloud will continue to grow and evolve.