Let us define some additional terminology. Each VM computes at some actual rate:

Each pair of VMs have some actual bandwidth and latency:

A VMD has an allocated compute rate, which is the sum of all the rates of VMs mapped to it:

Similarly, an edge between two VMDs has an allocated bandwidth:

The VM assignment problem is to find a function that meets the following requirements:

- Complete: exists.
- Compliant:
- Computationally feasible: and
- Communication feasible: and
- Routable: exists.

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.