Wednesday, March 16, 2011

Bin Packing Problem...

I have a collection of blade servers which host virtual machine guests. Each blade has a known RAM capacity that can safely be allocated to guests (80GB each in my current environment, but eventually some hosts will be larger than others). Each guest consumes a known quantity of RAM, which is variable across the environment. 

The goal is to optimize placement of the VMs to reduce unusable space and leave as many blades as possible unused (so they can be powered off).

I’ve found that for my current environment with uniformly sized hosts, I can calculate a theoretical best consumption like this:
hostCount = 34; // 9 chassis * 4 blades each, -2 utilized elsewhere
hostRAM = 80;
demandRAM = [sum of VM demands]
maxFreeHosts = (int)( hostCount – (demandRAM/hostRAM)) // Integer division should eliminate the need for a cast here, but I was originally working with an Excel formula.

Obviously this would only be true for a “liquid” with variable size occupying a host, not a “solid” with a fixed size.

I’m still working on an algorithm to arrange these optimally, but as best I can tell it is an example of the Bin Packing Problem, Which is either NP-Hard or NP-Complete depending on who you ask.
https://secure.wikimedia.org/wikipedia/en/wiki/Bin_packing_problem

As an additional complexity, Ideally I would like to take note of what host a given guest is on, and minimize migrations, which have a time penalty of a ~5 minutes and cause a <30 second ‘freeze’ of the VM during the move.

Go figure I would stumble on something that sound easy, and turns out to be NP-Hard. When it comes to packing actual bins, my mother has an unnatural ability to do this sort of optimizing in her head, but it turns out that computers aren't very good at it at all.

5 comments:

  1. Live casino no deposit bonus - Vntopbet
    Live クイーンカジノ casino no deposit bonus · Play slots with real money, casino 10bet games and casino games · Play Live Casino bk8 · Live Online Casino · Betway Casino · Casino

    ReplyDelete
  2. Bet on Golf - Betting & Gambling in Virtual Reality
    How to 10bet watch live golf matches with bk8 a virtual reality headset and how クイーンカジノ to watch and A virtual reality show takes place inside the game room at MGM National Harbor in Atlantic

    ReplyDelete
  3. Bet9ja Archives - vntopbet.com
    Bet9ja Archives. クイーンカジノ We are very pleased that we have started to update our bk8 website and 10bet Bet9ja is not as popular as Bet9ja.

    ReplyDelete
  4. Best casino bonus codes 2021 | Free spins no deposit
    Find a list of the casino bonus codes and promotions for United Kingdom 출장안마 players. worrione Discover bonus microtouch solo titanium codes for casinos with free spins no deposit wooricasinos.info on registration.‎How many free spins do you receive from the casino? · ‎What are the bonuses for United Kingdom players? · ‎What are 토토사이트 the free spins and promotions for United Kingdom players?

    ReplyDelete
  5. Because there are not any selections that players can use in the course of the course of the game one of the best technique is to attempt to scale back the house edge. The casino has around 14% edge on bets on a tie so one strong piece of advice can be to never guess on a Tie. Bets on the Banker do end in a commission but in common with betting on the Player the house edge is tremendously lowered to 온라인카지노 just over 1%.

    ReplyDelete