5.1 Terminology

Figure 7: Terminology.

Figure 7 serves as a point of reference for the terminology we use in describing our design and the problems it induces. On the left hand side, we can see the three layers: the virtual machines themselves (VM layer), the virtual machine daemons that host them (VMD layer), and the physical network resources on which the VMDs run (Physical layer). The graph of VM Daemons is the overlay itself. A VM daemon or VMD is a generalization of a VNET server that is able to manage VMs and measure their traffic and the characteristics of the underlying network. The nodes and edges at the VM layer are mapped to nodes and routes at the VMD layer. The physical layer is the underlying IP network itself. The nodes of the VMD layer are mapped to the end-systems of this network. The right hand side of Figure 7 shows the symbols we use at each layer and the mapping between layers. The boldfaced symbols represent where adaptation and the use of underlying resource mechanisms can take place.

The VM layer consists of the individual VMs ($vm_i \in VM$) and the communication edges among them ( $ve_{i,j} \in VE$), represented as a graph ($G_{vm}(VM,VE)$). If $vm_i$ sends to $vm_j$, then there is an edge $ve_{i,j}$ in $VE$. The VM layer is essentially a representation of the demands that the user's VMs are placing on the system. $bw(ve_{i,j})$ and $lat(ve_{i,j})$ are the bandwidth and latency requirements of communication between $vm_i$ and $vm_j$. $comp(vm_i)$ is the computational demand of $vm_i$, while $size(vm_i)$ is the total size of its machine image.

The VMD layer consists of VM daemons ($vd_i \in VD$), and the communication edges among them ( $vde_{i,j} \in VDE$), represented as a graph ( $G_{vmd}(VD,VDE)$). If $vd_i$ sends to $vd_j$, there must be a route ( $route(vd_i,vd_j)$) between them. A virtual machine $vm_i$ is assigned to a single VMD ($vmap(vm_i)$). Hence, an edge $ve_{i,j}$ in the VM layer corresponds to a route $route(ve_{i,j})=route(vmap(vm_i),vmap(vm_j))$ in the VMD layer. Multiple VMs may be assigned to a single VMD. At the VMD layer, we also maintain the measured bandwidth and latency of edges in the $G_{vmd}$, $mbw(vde_{i,j})$, $mlat(vde_{i,j})$, and the computational rate at each node ($mcomp(vd_i)$).

The physical layer consists of the underlying topology, $G_{net}(V,E)$, where the nodes $v_i \in V$ are the routers and hosts at the IP layer and $e_{i,j} \in E$ are the links. $route(v_i,v_j)$ are the routes chosen by the network, and $host(v_i)$ is true if $v_i$ is a host. In addition, we may be able to measure the bandwidth and latency of the elements of a link ($mbw(e_{i,j})$, $mlat(e_{i,j})$), the backplane bandwidth of a router ($mbw(v_i)$), and the raw computational power of a host ($mcomp(v_i)$). Each VMD is assigned to a single host in the physical layer, and each host has at most a single VMD. This mapping is via $vdmap(vd_i)$. Each edge in the $G_{vmd}$ turns into a route $route(vde_{i,j})$ at the physical layer.