Let us define some additional terminology. Each VM computes at some actual rate:
The VM assignment problem is to find a function that meets the
We define four variants of the VM assignment problem. The first two are offline versions while the second two are online problems.
Simple offline VM assignment problem: Given and its associated functions , , , , and , and and its associated functions , , , and , choose a that meets the requirements. The VMDs are fixed, as are their overlay topology and routing rules. We envision three situations in which this problem arises. The first is if the user has a private VMD network and runs a multi-VM application on it. The problem needs to be solved at program startup, and thereafter whenever the communication patterns have changed dramatically. The second case is when multiple users can map their own virtual machines to a shared VMD infrastructure. In this situation, the VMs of other users can be treated as . The problem also occurs if it is the VMD infrastructure that determines the mapping. In that situation, the problem can be solved with no VMs whenever a new set of VMs enters or leaves the system, or periodically.
Complex offline VM assignment problem: Given and its associated functions, determine , , and such that meets the requirements. Here, the VMDs are fixed, but their overlay topology and its routing rules can be chosen to help find a suitable . We see this problem occurring in two contexts. The first is if the user has a private VMD network that supports topology and routing changes. The second is for a shared VMD overlay where the VMDs solve the problem collectively over all running VMs.
Simple online VM assignment problem: Given an existing , , and their associated functions, an existing , and a new , determine such that it meets the requirements.
Complex online VM assignment problem: Given an existing , , and their associated functions, an existing , , and a new , determine a new such that meets the requirements.