5.4 VM assignment problems

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

$$\begin{eqnarray*} ComputeRate(vm_i) & & \end{eqnarray*}$$

Each pair of VMs have some actual bandwidth and latency:

$$\begin{eqnarray*} \lefteqn{PathBW(vm_i,vm_j) = PathBW(ve_{i,j}) =} \\ & & \min_{vde \in route(vmap(vm_i),vmap(vm_j))} mbw(vde) \end{eqnarray*}$$

$$\begin{eqnarray*} \lefteqn{PathLatency(vm_i,vm_j) = PathLatency(ve_{i,j}) = } \\ & & \sum_{vde \in route(vmap(vm_i),vmap(vm_j))} mlat(vde) \end{eqnarray*}$$

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

$$\begin{eqnarray*} \lefteqn{AllocatedComputeRate(vd_i) = } \\ & & \sum_{vm \in VM : vmap(vm)=vd_i} comp(vm) \end{eqnarray*}$$

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

$$\begin{eqnarray*} \lefteqn{AllocatedBandwidth(vde_{i,j}) = } \\ & & \sum_{ve \in VE : vde_{i,j} \in route(ve)} bw(ve) \end{eqnarray*}$$

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

$\bullet$

Complete: $\forall vm \in VM : vmap(vm)$ exists.

$\bullet$

Compliant: $fixed(vm_i,vd_j) \Rightarrow vmap(vm_i) = vd_j$

$\bullet$

Computationally feasible: $\forall vm \in VM : ComputeRate(vm) \geq comp(vm)$ and $\forall vd \in VD : AllocatedComputeRate(vd) \leq mcomp(vd)$

$\bullet$

Communication feasible: $\forall ve \in VE : PathLatency(ve) \leq lat(ve) \wedge PathBW(ve) \geq bw(ve)$ and $\forall vde \in VDE : AllocatedBW(vde) \leq mbw(vde)$

$\bullet$

Routable: $\forall ve \in VE : route(ve)$ 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 $G_{vm}$ and its associated functions $fixed$, $comp$, $size$, $bw$, and $lat$, and $G_{vmd}$ and its associated functions $route$, $mcomp$, $mbw$, and $mlat$, choose a $vmap$ that meets the $vmap$ 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 $fixed$. 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 $fixed$ whenever a new set of VMs enters or leaves the system, or periodically.

Complex offline VM assignment problem: Given $G_{vm}$ and its associated functions, determine $vmap$, $VDE$, and $route$ such that $vmap$ meets the $vmap$ requirements. Here, the VMDs are fixed, but their overlay topology and its routing rules can be chosen to help find a suitable $vmap$. 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 $G_{vm}$, $G_{vmd}$, and their associated functions, an existing $vmap$, and a new $G'_{vm}$, determine $vmap' = f(vmap, G_{vm}, G'_{vm})$ such that it meets the $vmap$ requirements.

Complex online VM assignment problem: Given an existing $G_{vm}$, $G_{vmd}$, and their associated functions, an existing $vmap$, $route$, and a new $G'_{vm}$, determine a new $(vmap', VDE', route') = f(vmap, G_{vm}, G'_{vm})$ such that $vmap$ meets the requirements.