5

PROBLEM:
We have N physical machines(PMs) each with ram Ri, cpu Ci and a set of currently scheduled VMs each with ram requirement ri and ci respectively
Moving(Migrating) any VM from one PM to other has a cost associated which depends on its ram ri. A PM with no VMs is shut down to save power.
Our target is to minimize the weighted sum of (N,migration cost) by migrating some VMs i.e. minimize the number of working PMs as well as not to degrade the service level due to excessive migrations.

My Approach:
Brute Force approach is choosing the minimum loaded PM and try to fit its VMs to other PMs by First Fit Decreasing algorithm or we can select the victim PMs and target PMs based on their loading level and shut down victims if possible by moving their VMs to targets.
I tried this Greedy approach on the Data of Baadal(IIT-D cloud) but It isn't giving promising results.

I have also tried to study the Ant colony optimization for dynamic VM consolidating but was unable to understand very much. I used the links.
http://dumas.ccsd.cnrs.fr/docs/00/72/52/15/PDF/Esnault.pdf http://hal.archives-ouvertes.fr/docs/00/72/38/56/PDF/RR-8032.pdf

Would anyone please clarify the solution or suggest any new approach/resources for better performance.
I am basically searching for the algorithms not the physical optimizations and I also know that many commercial organizations have provided these solution but I just wanted to know more the underlying algorithms.

Thanks in advance.

Improve this question
3
  • 1
    This problem seems quite related to the Machine Reassignment Problem and the Multi-Capacity Bin Packing Problem. For such problems, the appropriate methods are quite dependent of the size of the problem. I'll try to elaborate later today, but you might want to give a look to this research paper:researchgate.net/profile/Thibaut_Vidal/publication/… (full disclamer: I am one of the author) that proposes an approach for such a problem
    – Renaud M.
    Feb 25, 2015 at 12:39
  • How about: when the number of under-utilized physical machines (defined by utilization threshold) reach a certain number (defined by a threshold on the number of such machines), migrate the lowest-utilized ones, otherwise don't do anything?
    – rwong
    Mar 27, 2015 at 23:28
  • Cross-posted: programmers.stackexchange.com/q/241536/34181, stackoverflow.com/q/23961204/781723. Please don't cross-post -- it violates SE rules.
    – D.W.
    Sep 16, 2016 at 3:46

1 Answer 1

Reset to default
1

I wouldn't try to optimize the load across the PM's, since that will probably result in constant moving of VM's. The result of a single move will likely change the balance, requiring yet another move.

Instead, i would try to determine the acceptable load factor per PM (over-allocation), and only take actions when:

a. the action will not disturb operations

b. the result will improve the situation (a significantly better location is available on another PM)

And there are other factors in play as well. Do you know which machines have 'affinity' to other machines? A pair of a web-server and a related database-server will probably perform better when placed nearer to each other..

In other words: i would aim for stability (minimal number of moves, and smallest moves) instead of maximum resource optimization.

I would guess that you can optimize placement by using certain standard sizes of VM's, that are easily divideable for your hardware (like LEGO blocks are different sizes, but you can always find a piece that 'fits'), That would minimize the unusable 'rest' hardware for a PM that is to small to place a VM in.

But I would guess the mayor suppliers of virtualization software already have this worked out much better than you or i can in 5 minutes.

Improve this answer
4
  • thanks for your reply, Standard sizes(2x,4x,8x) are really helpful, we have currently implemented this strategy but in our cloud we have static resource allotment and no over-allocation is done. Could you please explain your step a. and b. above more clearly.
    – v78
    May 31, 2014 at 9:07
  • @devanshdalal if you don't over-allocate, and all VM's are standard sizes, why would you want to move then across PM at all?
    – oɔɯǝɹ
    May 31, 2014 at 14:37
  • okay I know it will not optimize much with that but if some VMs from a PM leaves we would better be aiming for a possibility of suting it down by periodically checking with with our algorithm. We can also give assume that VMs are not standard sizes for that
    – v78
    Jun 1, 2014 at 5:37
  • @devanshdalal perhaps you can show us what you have, and we can try to improve/optimize it from there?
    – oɔɯǝɹ
    Jun 1, 2014 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.