4 ms·

Thanks for your reply, eru! > Do you need an online solution or do you know all demands in advance? The online solution, as we don't know the type of load in

by kuvkir 17y ago

Thanks for your reply, eru! > Do you need an online solution or do you know all demands in advance? The online solution, as we don't know the type of load in advance. It resembles tetris in some way, meaning that we don't know which piece you'll get next. > Also what do you do when not enough slots are available for all VMs? If it's not theoretically possible to host all VMs like in examples you provided, nothing can be done. But it's not an algorithmic problem, in real world new servers should be bought in that case.

rjprins 17y ago
Wait, this is very simple: Always pick the server with the most slots open. Only when no server has enough space to accomodate the next machine, but together they have enough space, should you apply a packing algorithm.
- eru 17y ago
  If this is so simple, please prove the optimality of your solution. I can imagine that, when you have a perfect fit i.e. a machine that has l slots open and a VM that takes l slots, putting the VM on that machine might prove a good idea. At least when moving VMs is not too cheap compared to the advantages of a homogeneous load.
  - rjprins 17y ago
    Okay, you have two conflicting criteria: Spreading load and minimizing VM movements: Algorithm A: Always choose the server with the most slots free spreads the load most equally without moving VM's. (Assuming servers are equal in capacity. Minimizing load-balance is defined as minimizing the difference between highest loaded server and lowest loaded server.) Proof: Given a VM to be placed, v, and a set of servers S of which server s' is has most slots free. Say picking s' to place v does not give the most optimal load-balance. Then there must be server with with more slots free then s', contradiction. Algorithm B: Let S be a series of servers ordered by load (lowest number of free slots first). Put a new VM v on the first server s, on which v fits. This maximizes the initial number of VM's you can place without moving VM's, without prior knowledge. Proof: Because we always try to fit each VM in the first server possible, we maximize the amount of consecutive space on the last server. Thus, without prior knowledge, this maximizes the number of VM's we can place. I take it you like neither of these solutions. You want to compromise between the two solutions. Doing that right (there is not optimal in that sense) would depend on the scale difference between servers slots and space required by VM's. If VM's are small and servers big, you can safely go for load balance. If VM's are big and servers relatively small, you may go for B.
    - eru 17y ago
      If you want a simple solution, your Algorithm A is good for a first try. However if you have more information about the probability distribution of the number of slots in a VM, you could in theory do better than that.
- kuvkir 17y ago
  That's not that simple. Let us imagine the following configuration. We have 3 servers each of 4 slots, below is the state of each server (the state of a server is a set of VMs it's running) [3], [2, 1] and [2]. Say we need to place a new 3-slot VM to our system. We'll pick the third server as less-loaded and try to accomodate the second server. Together they have enough space, but we can't provision the VM withour using all 3 servers. The solution here is 1) migrate a 1-slot VM from server 2 to server 1 2) migrate a 2-slot VM from server 2 to server 3 3) place the new VM to server 2
  - rjprins 17y ago
    Don't get me wrong, a correct packing algorithm for this is far from trivial! What would you say is more important: minimizing the amount of slots to move or the number of VM's?
    - kuvkir 17y ago
      That's not a simple question. But I would guess having one 2-slot migration is better than two 1-slot migrations...
eru 17y ago
I guess one solution would be to put the request on hold and serve it as soon as enough slots are open. Or isn't this a problem?
- kuvkir 17y ago
  This isn't acceptable unfortunately. VMs are meant to run for quite a reasonable amount of time, so we'll be waiting very-very long until slots get available...
  - eru 17y ago
    OK, so we just reject those demands?
    - kuvkir 17y ago
      We can't reject as it'll be used in the commercial application with users paying money for using cloud resources. Basically what is needed is to find the list of VM migrations needed to be done to free enough space for a new VM (of course, if it's ever possible).
      - eru 17y ago
        Yes, my question was: What to do when it's not possible? Put it on hold or reject it or automatically buy new servers?
        kuvkir 17y ago
        Yes, completely reject if it's not possible at all.
eru 17y ago
If you know something about the probability distribution of VM requests, use that knowledge! Otherwise: When adding a new VM, just search for the maneuver that minimizes total cost (cost of moving VMs + cost of inequality). You can structure that search as a shortest-path-problem in a graph and solve it with the Dijkstra-Algorithm. See http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance for comparison.
- kuvkir 17y ago
  Given real conditions that the minimal slot for VM is a 256MB RAM instance, with a physical server having 64 such slots, the educated guess is that the distribution might be similar to the normal distribution with a centre of a 2-slot VM, as 512MB VM is the most popular choice on our target market. How can that particular fact be of help ?
  - eru 17y ago
    You can take this guess as a starting point. Later you can use the empirical distribution you encounter in the wild. First, the distribution is useful for running simulations of your placement algorithm(s). Also without a distribution your are limited to analysing worst-case-scenarios. With a distribution of inputs you can also take a look at the distribution of outputs that your method achieves. Suppose you measure the quality of your output with a single number, than you can look at certain quantiles - like the median outcome. Or the 95%-quantile, that will be closer to the worst case scenario, but not as pathological. Second, to give an extreme example: Say you'd know everything about the coming demands, then you no longer had to use an online algorithm. But even much more limited knowledge will help you prepare for the future.

by kuvkir 17y ago

rjprins 17y ago

Wait, this is very simple: Always pick the server with the most slots open. Only when no server has enough space to accomodate the next machine, but together they have enough space, should you apply a packing algorithm.

eru 17y ago
If this is so simple, please prove the optimality of your solution. I can imagine that, when you have a perfect fit i.e. a machine that has l slots open and a VM that takes l slots, putting the VM on that machine might prove a good idea. At least when moving VMs is not too cheap compared to the advantages of a homogeneous load.
- rjprins 17y ago
  Okay, you have two conflicting criteria: Spreading load and minimizing VM movements: Algorithm A: Always choose the server with the most slots free spreads the load most equally without moving VM's. (Assuming servers are equal in capacity. Minimizing load-balance is defined as minimizing the difference between highest loaded server and lowest loaded server.) Proof: Given a VM to be placed, v, and a set of servers S of which server s' is has most slots free. Say picking s' to place v does not give the most optimal load-balance. Then there must be server with with more slots free then s', contradiction. Algorithm B: Let S be a series of servers ordered by load (lowest number of free slots first). Put a new VM v on the first server s, on which v fits. This maximizes the initial number of VM's you can place without moving VM's, without prior knowledge. Proof: Because we always try to fit each VM in the first server possible, we maximize the amount of consecutive space on the last server. Thus, without prior knowledge, this maximizes the number of VM's we can place. I take it you like neither of these solutions. You want to compromise between the two solutions. Doing that right (there is not optimal in that sense) would depend on the scale difference between servers slots and space required by VM's. If VM's are small and servers big, you can safely go for load balance. If VM's are big and servers relatively small, you may go for B.
  - eru 17y ago
    If you want a simple solution, your Algorithm A is good for a first try. However if you have more information about the probability distribution of the number of slots in a VM, you could in theory do better than that.
kuvkir 17y ago
That's not that simple. Let us imagine the following configuration. We have 3 servers each of 4 slots, below is the state of each server (the state of a server is a set of VMs it's running) [3], [2, 1] and [2]. Say we need to place a new 3-slot VM to our system. We'll pick the third server as less-loaded and try to accomodate the second server. Together they have enough space, but we can't provision the VM withour using all 3 servers. The solution here is 1) migrate a 1-slot VM from server 2 to server 1 2) migrate a 2-slot VM from server 2 to server 3 3) place the new VM to server 2
- rjprins 17y ago
  Don't get me wrong, a correct packing algorithm for this is far from trivial! What would you say is more important: minimizing the amount of slots to move or the number of VM's?
  - kuvkir 17y ago
    That's not a simple question. But I would guess having one 2-slot migration is better than two 1-slot migrations...

eru 17y ago

I guess one solution would be to put the request on hold and serve it as soon as enough slots are open. Or isn't this a problem?

kuvkir 17y ago
This isn't acceptable unfortunately. VMs are meant to run for quite a reasonable amount of time, so we'll be waiting very-very long until slots get available...
- eru 17y ago
  OK, so we just reject those demands?
  - kuvkir 17y ago
    We can't reject as it'll be used in the commercial application with users paying money for using cloud resources. Basically what is needed is to find the list of VM migrations needed to be done to free enough space for a new VM (of course, if it's ever possible).
    - eru 17y ago
      Yes, my question was: What to do when it's not possible? Put it on hold or reject it or automatically buy new servers?
      - kuvkir 17y ago
        Yes, completely reject if it's not possible at all.

eru 17y ago

If you know something about the probability distribution of VM requests, use that knowledge! Otherwise: When adding a new VM, just search for the maneuver that minimizes total cost (cost of moving VMs + cost of inequality). You can structure that search as a shortest-path-problem in a graph and solve it with the Dijkstra-Algorithm. See http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance for comparison.

kuvkir 17y ago
Given real conditions that the minimal slot for VM is a 256MB RAM instance, with a physical server having 64 such slots, the educated guess is that the distribution might be similar to the normal distribution with a centre of a 2-slot VM, as 512MB VM is the most popular choice on our target market. How can that particular fact be of help ?
- eru 17y ago
  You can take this guess as a starting point. Later you can use the empirical distribution you encounter in the wild. First, the distribution is useful for running simulations of your placement algorithm(s). Also without a distribution your are limited to analysing worst-case-scenarios. With a distribution of inputs you can also take a look at the distribution of outputs that your method achieves. Suppose you measure the quality of your output with a single number, than you can look at certain quantiles - like the median outcome. Or the 95%-quantile, that will be closer to the worst case scenario, but not as pathological. Second, to give an extreme example: Say you'd know everything about the coming demands, then you no longer had to use an online algorithm. But even much more limited knowledge will help you prepare for the future.