5.5 Connected components

The simple online VM assignment problem can be formulated in terms of connected components. The connected components of a graph are a partitioning of the graph into subgraphs. A connected component of a directed graph $G = (V,E)$ is a maximal set of vertices $U \subseteq V$ such that for every pair of vertices $u$ and $v$ in $U$, there is a path connecting them. Hence two vertices are in the same connected component if and only if there exists a path between the vertices. If a graph contains only one connected component then it is said to be a connected graph.

The directed graph $G_{vm}$ is a connected graph while the directed graph $G_{vmd}$ may or may not be connected. It will be connected if and only if $\forall$ $vd_{i}$ $\in$ $VD$ there $\exists$ at least one $vm_{i} \in$ $VM$ such that $vmap(vm_{i}) = vd_{i}$. Note that since $G_{vm}$ is connected, the graph of $vd$ $\in VD$ where $\forall$ $vd$ there $\exists$ $vmap$ such that $vd = vmap(vm_{i})$ such that $vm_{i} \in VM$, will also be connected.

Given an existing $G_{vm}$, $G_{vmd}$, and their associated functions, we calculate $cost(vde_{i,j})$ where

$$\begin{eqnarray*} cost(vde_{i,j}) = f(mbw(vde_{i,j}), mlat(vde_{i,j})) \forall vde_{i,j} \in VDE \end{eqnarray*}$$

$cost(vde_{i,j})$ is a measure of the network cost value associated with each edge in the VM daemon graph $G_{vmd}$. The cost value would be an integrated metric, a function of the measured available bandwidth, $mbw(vde_{i,j})$, and latency, $lat(vde_{i,j})$, on the edges in the VM daemon graph $G_{vmd}$.

The VM assignment problem may now be described as: