Constrained placement in hierarchical randomized schedulers

Abstract

A distributed scheduler for a virtualized computer system has a hierarchical structure and includes a root scheduler as the root node, one or more branch schedulers as intermediate nodes, and a plurality of hosts as leaf nodes. A request to place a virtual computing instance is propagated down the hierarchical structure to the hosts that satisfy placement constraints of the request. Each host that receives the request responds with a score indicating resource availability on that host, and the scores are propagated back up the hierarchical structure. Branch schedulers that receive such scores compare the received scores and further propagate a 'winning' score, such as the highest or lowest score, up the hierarchical structure, until the root scheduler is reached. The root scheduler makes a similar comparison of received scores to select the best candidate among the hosts to place the virtual computing instance.