Check out the new USENIX Web site. next up previous
Next: 5.5.0.0.1 Input: Up: 5 Towards an adaptive Previous: 5.4 VM assignment problems

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:


Subsections
next up previous
Next: 5.5.0.0.1 Input: Up: 5 Towards an adaptive Previous: 5.4 VM assignment problems
Ananth Sundararaj 2004-02-17