3 ms·

A slightly off-topic comment, but being an early-stage PhD in theoretical CS with my thesis topic on approximation algorithms for scheduling, I would like to kn

A slightly off-topic comment, but being an early-stage PhD in theoretical CS with my thesis topic on approximation algorithms for scheduling, I would like to know whether there are some theoretical problems related to these VM schedulers used in practice. If there is somebody knowledgeable about what is theoretically open (unknown tight approximation ratio, for instance) AND very useful to people building Kubernetes et al, I would be really happy to learn more. (The natural advice is to "hit the books", actually read the papers related to Kubernetes and find out what is both theoretical and useful to this area. I intend to do that soon, but sifting through "practical papers" and looking for something interesting in theory is a lot of work, and I just hoped there might be somebody who could provide a shortcut.)

philip1209 11y ago
It was more of an amusement, but I used integer programming at a company hackathon to build a better image scheduler: https://engineering.opendns.com/2015/05/06/docker-container-scheduling-as-a-bin-packing-problem/ https://engineering.opendns.com/2015/05/06/docker-container-... With a large, fairly homogenous environment it didn't outperform random assignment that well, though. It worked best with small, inhomogeneous loads.
- NotOscarWilde 11y ago
  Right, ILP is a great tool for solving NP-complete problems relatively fast (depending on the solver, but there are some very good ones out there). However, as a theoretical tool it probably is not that exciting unless you're ready to tackle P vs. NP this way. (Unless you move to semidefinite programming and the SDP hierarchies, where the progress is very exciting but not yet that applicable to scheduling, to the best of my knowledge.) > With a large, fairly homogenous environment it didn't outperform random assignment that well, though. It worked best with small, inhomogeneous loads. Yes, that's probably a piece of the puzzle that I don't have yet -- to know a theoretical model that is both useful in practice and at the same time greedy/randomized assignment is not "good enough" for practical uses.
- seanp2k2 11y ago
  Interesting, I didn't know "inhomogeneous" was a word: http://english.stackexchange.com/questions/194906/heterogeneous-vs-inhomogeneous http://english.stackexchange.com/questions/194906/heterogene...
sciurus 11y ago
This may not be the level of specificity that you're looking for, but http://research.google.com/pubs/pub43438.html http://research.google.com/pubs/pub43438.html and http://research.google.com/pubs/pub41684.html http://research.google.com/pubs/pub41684.html are what I know google has published about their cluster management systems.
jacques_chester 11y ago
Lattice[1] "cheats" by turning the bin packing problem into an auction. Execution agents perform a simple local calculation and send in their bids. Then jobs are placed according to those bids. This is because while you can try to produce an optimal distribution, it's a fool's errand in a distributed system. A perfect solver, given imperfect data, produces nonsense. GIGO, as they used to say. Amit Gupta wrote some notes last year about it[2]. Disclaimer: I work for Pivotal. [1] http://lattice.cf/ http://lattice.cf/ [2] http://blog.pivotal.io/pivotal-cloud-foundry/products/app-placement-in-cloud-foundry-diego-a-classical-optimization-problem http://blog.pivotal.io/pivotal-cloud-foundry/products/app-pl...

philip1209 11y ago

It was more of an amusement, but I used integer programming at a company hackathon to build a better image scheduler: https://engineering.opendns.com/2015/05/06/docker-container-scheduling-as-a-bin-packing-problem/ https://engineering.opendns.com/2015/05/06/docker-container-... With a large, fairly homogenous environment it didn't outperform random assignment that well, though. It worked best with small, inhomogeneous loads.

NotOscarWilde 11y ago
Right, ILP is a great tool for solving NP-complete problems relatively fast (depending on the solver, but there are some very good ones out there). However, as a theoretical tool it probably is not that exciting unless you're ready to tackle P vs. NP this way. (Unless you move to semidefinite programming and the SDP hierarchies, where the progress is very exciting but not yet that applicable to scheduling, to the best of my knowledge.) > With a large, fairly homogenous environment it didn't outperform random assignment that well, though. It worked best with small, inhomogeneous loads. Yes, that's probably a piece of the puzzle that I don't have yet -- to know a theoretical model that is both useful in practice and at the same time greedy/randomized assignment is not "good enough" for practical uses.
seanp2k2 11y ago
Interesting, I didn't know "inhomogeneous" was a word: http://english.stackexchange.com/questions/194906/heterogeneous-vs-inhomogeneous http://english.stackexchange.com/questions/194906/heterogene...

sciurus 11y ago

This may not be the level of specificity that you're looking for, but http://research.google.com/pubs/pub43438.html http://research.google.com/pubs/pub43438.html and http://research.google.com/pubs/pub41684.html http://research.google.com/pubs/pub41684.html are what I know google has published about their cluster management systems.

jacques_chester 11y ago

Lattice[1] "cheats" by turning the bin packing problem into an auction. Execution agents perform a simple local calculation and send in their bids. Then jobs are placed according to those bids. This is because while you can try to produce an optimal distribution, it's a fool's errand in a distributed system. A perfect solver, given imperfect data, produces nonsense. GIGO, as they used to say. Amit Gupta wrote some notes last year about it[2]. Disclaimer: I work for Pivotal. [1] http://lattice.cf/ http://lattice.cf/ [2] http://blog.pivotal.io/pivotal-cloud-foundry/products/app-placement-in-cloud-foundry-diego-a-classical-optimization-problem http://blog.pivotal.io/pivotal-cloud-foundry/products/app-pl...