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.

Wednesday, January 5, 2011

Logitech MX5500 via Bluetooth on Windows 7

So, after my work laptop crashed and I had to reinstall Windows 7, I had some odd issues with my Logitech MX5500 keyboard. It work, but would periodically drop characters, particularly when I first started typing after a pause. I remembered having this issue the first time I built this laptop, and went off in search of drivers for the Bluetooth card (I assume the BIOS was handling the keyboard thus far).

After installing the driver provided by Dell, I attempted to re-pair the keyboard using the standard 'Add a device' function, which could see the keyboard after I pressed its pairing button, but would spin indefinitely trying to connect to it. Search, Search, Search, finally found this post - deja vu sets in.


For some odd reason, Windows doesn't seem to want to automatically enable drivers for the keyboard. Right clicking the icon in the add devices wizard and selecting properties, then ticking the drivers box under services makes everything better.

Update: For some reason, after ticking this box once, Windows will automatically do its thing when you re-add keyboard after it has been removed for whatever reason. Re-adds will present an 8 or so digit PIN that you enter on the keyboard to confirm the pairing, which was was not asked for during the original pairing... I don't know if that is good/bad/indifferent, but it works.