Constrained placement in hierarchical randomized schedulers

A non-transitory computer readable medium comprising instructions to be executed in a computer system to carry out a method of placing a virtual computing instance on a host using a hierarchy of nodes, each node executing a distributed scheduler software component, said method comprising:

• propagating a constrained placement request for placing the virtual computing instance down the hierarchy of nodes to one or more of the distributed scheduler software components in one or more leaf nodes of the hierarchy of nodes that satisfy placement constraints of the request, wherein the propagating includes:
• issuing, by a root node, the constrained placement request to a randomly chosen subset of intermediate nodes associated with leaf node children that satisfy the placement constraints of the request, and
• forwarding, by each intermediate node that receives the constrained placement request, the constrained placement request to a randomly chosen subset of child nodes that are associated with the intermediate node and either satisfy the placement constraints of the request or are associated with leaf node children satisfying the placement constraints of the request;
• receiving one or more responses to the constrained placement request, wherein each of the leaf nodes that receives the constrained placement request propagates a respective response up the hierarchy of nodes, and wherein each of the intermediate nodes that receives responses from child nodes further propagates up the hierarchy of nodes one of the responses received from the child nodes based on a comparison of the received responses;
• selecting one of the leaf nodes as a node by which the constrained placement request is to be satisfied, based on the received one or more responses to the constrained placement request;
• and
• causing the virtual computing instance to be executed on the selected leaf node.

A method of placing a virtual computing instance on a host using a hierarchy of nodes, each node executing a distributed scheduler software component, said method comprising:

• propagating a constrained placement request for placing the virtual computing instance down the hierarchy of nodes to one or more of the distributed scheduler software components in one or more leaf nodes of the hierarchy of nodes that satisfy placement constraints of the request, wherein the propagating includes:
• issuing, by a root node, the constrained placement request to a randomly chosen subset of intermediate nodes associated with leaf node children that satisfy the placement constraints of the request, and
• forwarding, by each intermediate node that receives the constrained placement request, the constrained placement request to a randomly chosen subset of child nodes that are associated with the intermediate node and either satisfy the placement constraints of the request or are associated with leaf node children satisfying the placement constraints of the request;
• receiving one or more responses to the constrained placement request, wherein each of the leaf nodes that receives the constrained placement request propagates a respective response up the hierarchy of nodes, and wherein each of the intermediate nodes that receives responses from child nodes further propagates up the hierarchy of nodes one of the responses received from the child nodes based on a comparison of the received responses;
• selecting one of the leaf nodes as a node by which the constrained placement request is to be satisfied, based on the received one or more responses to the constrained placement request;
• and
• causing the virtual computing instance to be executed on the selected leaf node.