Linear programming applied to virtualization

Jean Baptiste FAVRE

2011 march

La version Française est disponible ici: Programmation linéraire appliquée à la virtualisation

Introduction

Operational research is a mathematical discipline providing tools for decision support. Among the problem that can be solved using these techniques are combinatorial problems. An example of this type of problem: sizing a virtualization infrastructure.

This time we won't use GLPK but LibreOffice. With the linear solver integrated into LibreOffice suite, it becomes very simple and almost easy to solve this problem. This is obviously just one example among many other of what we can do with LibreOffice.

Example

A company wants to deploy a web platform as virtual machines. These virtual machines will have of course different functions: Front server, Cache server, Proxy server, Master Database and Slave Database.

Company's technical teams have conducted tests of the future web platform and identified needs in terms of disk I/O, CPU and memory. In addition, the company does not want to acquire new types of hardware. Therefore we have to host the web platform on existing servers. We have 3 types of servers with different abilities in terms of disk I/O, CPU and memory, all known from technical teams again after tests. In addition, technical teams have found threshold effects, which degrade server's performances. These threshold effects are also shown.

<Warning>The values presented here have no real concrete base. They are only given to illustrate my point. The key here is to maintain a consistency per criteria. For exmple, the disk I/O could be specified in IOPS, or I/O operations per second. Same for CPU whose value may represent a relative index of performance.</Warning>

Virtual machines needs
 I/OCPURAMVM number
Front10075840
Cache1501501620
Proxy502503220
Slave Database2002006410
Master Database2502506410

Since we know the need for each virtual machine and their number, it's very easy to calculate the global need.

Physical servers capacity
 I/OCPURAMHosting costAcquisition costDepreciation
SRV190090012855550036 month
SRV26007506440300036 month
SRV33006004830200036 month
Threshold60%60%95%  

Here again, global capacity calculation is very easy.

The goal is to determine the number of each type server we have to buy while minimizing costs.

Some mathematics

Let x1, x2 and x3 the number of servers from SRV1, SRV2 and SRV3 sort to acquire.

For each criterion (disk I/O, CPU and memory), it is understood that total need for virtual machines have to be covered by the contribution of physical servers. We apply threshold for each capacity item, ie only 60% capacity I/O disque, 60% capacity CPU and 95% of the memory are actually "available".

This give us 3 constraints:

Right values represent the virtual machines global need.

The total cost for this platform will depend on how many of each type to buy. The cost calculation is actually quite simple:

Using LibreOffice

Once the basics of the problem, we can solve it. In this case, we will use OpenLibreOffice, specifically Calc. You can retrieve the Calc workbook used for this exercise.

Calc sheet overview

Cells in light green can, and should, be modified by you. This will allow you to play several scenarios.

Cells containing the information need of virtual machines and server capacity can also be modified. Obviously, it will enroll representative values of your hardware and / or virtual machines.

However, do not change anything outside of step 1, except if you exactly know what you do: Step 2 consolidates the needs and capabilities, Step 3 gives you the information Number of physical servers. As in step 4, you guessed it gives you the final result with the cost of your infrastructure. All uses formulas, beware if you want to change any of them.

LibreOffice Solver usage

Let's enter Tools > Solver menu, as showed on capture below:

Menu LibreOffice Outils - Solveur

In opened frame, cellule cible indicates our target, ie final cost. It's F24 cell. As we have to minize cost, you can choose Minimum. The cells that can be modified are physical servers number, ie cells C24 to E24. Finally, our constraints are:

LibreOffice Solver frame - Parameters

We're almost there. One last detail to be: make sure that the number of server to be positive on the one hand, and especially an integer. I doubt that 2.3215 server will be of any use, nor to you, nor to the CFO:). To do this, click Options and tick the two boxes as shown below:

LibreOffice Solver frame - Options

Once done, you can ask for a solution clicking Solve. If everything goes well, you got the result:

LibreOffice Solver result frame

You noticed that the sheet has been updated. Click Keep the result to close the frame:

Calc sheet overview after optimization

You are then able to announce the investment necessary for the production launch of the platform:

Total cost is 4833,33 € per month, ie 174 000 € for 36 month.

Conclusion

You can also test different scenarios, forfor example to test the impact of adding RAM to a server type . To do this, edit the cell in step 1 and repeat the optimization. Each time, the optimizer will give you the combination which will be the lowest cost ... Magic math!

Another example, how to "neutralize" a type of physical server? Simply by setting its capacity to 0! :)

Of course, asking manually for optimisation can be tedious. One solution: Macros. The optimizer is a component of LibreOffice among others, and it is possible to control it from a macro. You can then update the sheet with a simple click of a button. But that's another story.

This example is obviously and deliberately, simplified. Many other parameters come into play. But now that you know how, feel free to adapt the worksheet. As an exercise, you can search for the ideal distribution of virtual machines on different servers.

About Jean Baptiste FAVRE

I spend most of my free time on the Internet working on GNU/Linux with Debian or CentOS, virtualization with Xen and KVM, as well as cluster stacks with Corosync and OpenAIS. Particularly interested in Linux, Netfilter, virtualization, monitoring and clusters, most of my personal works are published on this website and others should not delay.

By way professional, I manage servers running RedHat or CentOS and a VMware ESXi farm.

From time to time, I manage to drop my keyboard and read a book while listening to music, but it never lasts long.

License

Creative Commons License This document is available under Creative Common by-nc-sa License

Valid XHTML 1.0 Strict | Valid CSS | Creative Common by-nc-sa License

Index

  1. Introduction
  2. Example
  3. Some mathematics
  4. Using LibreOffice
  5. LibreOffice Solver usage
  6. Conclusion
  7. About ...
  8. License