VirtCO: Joint Coflow Scheduling and Virtual Machine Placement in Cloud Data Centers

We begin by modeling the joint coflow scheduling and VM placement problem to optimize the average CCT for all coflows. For the virtualization environment, we define $H$ and $h_m$ as the set of physical hosts and the $m$ -th physical host within the data center, respectively. Applications request resources in the form of VMs. For each application, $V$ and $v_j$ denote the set of VMs and the $j$ -th VM for the application, respectively. The VM placement is represented by an $H\times V$ matrix denoted by $X$ . $x_j^m$ denotes whether $v_j$ is hosted by $h_m$ . Specifically, $x_j^m=1$ if $v_j$ is hosted by $h_m$ ; otherwise, $x_j^m=0$ .

The coflow information $C_i$ associated with an application is characterized by traffic matrix $P_i$ , where $p_{i,j,k}$ denotes the size of flow $C_i$ to be transferred from $v_j$ to $v_k$ . In the example depicted in Fig. 1 , coflow $C_1$ has the traffic matrix $⟨p_{1,1,2}=5$ , $p_{1,2,3}=1$ , $p_{1,3,1}=2⟩$ and coflow $C_2$ has the traffic matrix $⟨p_{2,2,3}=1$ , $p_{2,3,2}=2⟩$ . All incomplete coflows are included in the collection $𝒞$ . To illustrate the network resource constraints, we define $ℬ$ as the residual bandwidth on PMs. $ℬ$ consists of the egress and ingress bandwidth, denoted by $B_e^m$ and $B_{in}^m$ , respectively. $B_i$ denotes the rate allocated to $C_i$ , which is composed of the egress and ingress rates allocated to $C_i$ on $h_m$ , denoted as $e_i^m$ and $i{n}_i^m$ . VM size, denoted as $siz{e}_j$ , is represented by several slots, and the number of available slots in $h_m$ is $slo{t}_m$ . Under any placement, $t_i$ denotes the CCT of $C_i$ .

To optimize the average CCT, VirtCO leverages the minimum remaining time-first heuristic to schedule the coflow in $𝒞$ having minimum remaining CCT with the highest priority. We describe the main framework of VirtCO in Algorithm 1. The algorithm is invoked whenever a new application enters the data center. Specifically, when a new application associated with a coflow arrives, the algorithm is triggered to determine its VM placement, scheduling priority, and bandwidth allocation (allowing preemption). Line 4 of Algorithm 1 invokes another algorithm to compute the minimum CCT for the arriving coflow. In Section 4.2, we illustrate the details of minimizing the single CCT through VM placement and network scheduling. Among all incomplete coflows, the algorithm sets the priorities according to their remaining completion time in ascending order (lines 7-10). To avoid starvation, the algorithm checks the waiting time of coflows in $𝒞$ and sets a threshold to ensure that no coflow starves for an arbitrary period $\theta$ (lines 11-14). $\theta$ is usually in minutes and determined empirically by cloud providers.

The problem of minimizing the CCT for a single coflow in the cloud environment is formally stated as follows: given the estimated traffic matrix of a coflow $C_i$ , we try to find a feasible placement $X_i$ of all its VMs onto PMs, allocating feasible bandwidth $e_i^m$ and $i{n}_i^m$ for $C_i$ on each $h_m$ , to minimize its completion time $t_i$ . Although single-flow optimization heuristics would allocate the entire bandwidth of the link to the scheduled flow, a desirable property of coflow is that completing any flow faster than the bottleneck in a coflow does not affect the CCT. Therefore, the minimum completion time of a coflow can be attained as long as all flows finish at the same time with the bottleneck flow. That is, all flows in $C_i$ should finish at the CCT $t_i$ .

Note that we enforce scheduling in the hypervisor layer with coflow granularity. Under placement $X_i$ , the amount of data coflow that $C_i$ sends from $h_m$ is $s_i^m$ , and the coflow $C_i$ received from $h_m$ is $r_i^m$ . $s_i^m$ and $r_i^m$ are computed by

(1) $$\{\begin{array}{c}{s}_i^m=\underset{j}{\sum }\underset{k}{\sum }{x}_j^m(1-x_k^m)p_{i,j,k},\hfill \\ r_i^m=\underset{j}{\sum }\underset{k}{\sum }{x}_k^m(1-x_j^m)p_{i,j,k}\hfill \end{array}$$

Corollary 1 Having allocated the bandwidth $e_i^m$ and $i{n}_i^m$ to $C_i$ on one PM $h_m$ , we can determine the minimum CCT through weighted fair sharing among individual flows of $C_i$ on $h_m$ , with the weight

(2) $$w_{i,j,k}=\frac{p_{i,j,k}}{s_i^m}$$

Proof For notational simplicity, we define $h_m$ as the sender host and $h_n$ as the receiver host. As all flows in a coflow are completed at the same time, we assume that $t_i=1$ . Then, the egress and ingress bandwidth allocated to each PM are equal to $s_i^m$ and $r_i^n$ , respectively. As the data sent must be equal to the data received, ${\sum }_m{s}_i^m={\sum }_n{r}_i^n$ . Let $p_{m,n}={\sum }_{j\in m}{\sum }_{k\in n}{p}_{i,j,k}$ denote the aggregate flow sent from $h_m$ to $h_n$ . Thus, we have ${\sum }_m{\sum }_n{p}_{m,n}={\sum }_n{r}_i^n$ . Let $p_{m,n}$ be the bandwidth shared for flow $m\to n$ , and then reduce ${\sum }_n$ from both sides. We then have ${\sum }_m{p}_{m,n}=r_n$ . Thus, with $p_{m,n}$ as the bandwidth shared for all flows sent from $m$ , the data transfer finishes exactly at $t_i=1$ . Therefore, to achieve the optimal time $t_i$ , each $p_{m,n}$ shares the bandwidth with $w_{m,n}=p_{m,n}/s_i^m$ . Furthermore, as $p_{m,n}$ is the aggregate flow of all $p_{i,j,k}$ , each flow shares the bandwidth with the proportion $w_{i,j,k}=p_{i,j,k}/s_i^m$ .

Corollary 1 indicates the theoretical feasibility of enforcing scheduling at the granularity of coflows and hypervisors. This control granularity is able to attain the same performance as the finer granularity of flows and VMs. This design allows fewer rate limiters than other implementations and reduces the computation intensiveness of core algorithms.

Given the above definitions, we formulate the problem of minimizing $t_i$ as follows:

(3) $$P=\min t_i$$

subject to the following:

(3a) $$\{\begin{array}{c}\frac{s_i^m}{e_i^m}=t_i,\hfill \\ \frac{r_i^m}{i{n}_i^m}=t_i,\hfill \end{array}\forall m$$

(3b) $$\{\begin{array}{c}{e}_i^m⩽B_e^m,\hfill \\ i{n}_i^m⩽B_{in}^m,\hfill \end{array}\forall m$$

(3c) $$\underset{m}{\sum }{x}_j^m=1,\forall j$$

(3d) $$\underset{j}{\sum }{x}_j^m⩽slo{t}_m,\forall m$$

Constraint Eq. ( 3a ) enforces that the completion time of all flows is equal to the CCT. With the minimum bandwidth allocated, the residual bandwidth is released to admit other coflows. Equations ( 3C ) and ( 3d ) represent the placement constraints. However, the original problem (3) is difficult to solve directly because it is a nonlinear programming problem with binary integer variables. To facilitate the solution, we define ${\alpha }_i=1/t_i$ , then, Eq. ( 3 ) can be modified to

(4) $$P^{\prime }=\max {\alpha }_i$$

The boundary conditions of Eq. ( 4 ) are given by

(4a) $${\alpha }_i\underset{j}{\sum }\underset{k}{\sum }{x}_j^m(1-x_k^m)p_{i,j,k}⩽B_e^m,\forall m$$

(4b) $${\alpha }_i\underset{j}{\sum }\underset{k}{\sum }{x}_k^m(1-x_j^m)p_{i,j,k}⩽B_{in}^m,\forall m$$

$$\underset{m}{\sum }{x}_j^m=1,\forall j,$$

$$\underset{j}{\sum }{x}_j^m⩽slo{t}_m,\forall m.$$

Then, we introduce two variables: $W_{i,j,k}^m$ and $V_{i,j,k}^m$ . Let $V_{i,j,k}^m={\alpha }_i{x}_j^m(1-x_k^m)$ and $W_{i,j,k}^m={\alpha }_i{x}_k^m(1-x_j^m)$ .

Substituting $V_{i,j,k}^m$ and $W_{i,j,k}^m$ into problem (4), and we can transform this problem into the following:

(5) $$P^{\prime }=\max {\alpha }_i$$

The boundary conditions of Eq. ( 5 ) are given by

(5a) $$\underset{j}{\sum }\underset{k}{\sum }{V}_{i,j,k}^m{p}_{i,j,k}⩽B_e^m,\forall m$$

(5b) $$\underset{j}{\sum }\underset{k}{\sum }{W}_{i,j,k}^m{p}_{i,j,k}⩽B_i^m,\forall m$$

(5c) $$\underset{m}{\sum }{V}_{i,j,k}^m⩽{\alpha }_i,\forall j,k$$

(5d) $$\underset{m}{\sum }{W}_{i,j,k}^m⩽{\alpha }_i,\forall j,k$$

Equation ( 5 ) represents an LP problem with the limited scale of variables and constraints that can be solved in a timely manner. We analyze the computation complexity of the algorithm from two perspectives: bandwidth allocation and VM placement. For the aspect of bandwidth allocation, as we only conduct rate limiting on each hypervisor, the variable scale is limited to the number of physical hosts $|H|$ . For VM placement, each iteration of computation generates the VM placement for an application, and the variables’ scale is bounded by $|V|$ . The computation overhead to run the LP is bounded by $|H|$ and $|V|$ . In practice, the available $|H|$ for hosting an application is usually limited to several adjacent racks, which are approximately dozens of hosts. The $|V|$ requested by an application is also extremely limited. Therefore, the small scale optimization can be computed efficiently, and with a small computation overhead.

After $V_{i,j,k}^m$ and $W_{i,j,k}^m$ are derived, $x_j^m$ and $x_k^m$ can be computed by

(6) $$\{\begin{array}{c}{x}_j^m(1-x_k^m)=\frac{V_{i,j,k}^m}{{\alpha }_i},\hfill \\ x_k^m(1-x_j^m)=\frac{W_{i,j,k}^m}{{\alpha }_i}\hfill \end{array}$$

In the previous computation, as we relax the binary integral variables to fractional ones, the solution may contain some $x_j^m$ that are decimal fractions. A fractional $x_j^m$ means that we need to divide the VM to place it separately on different PMs, which is not practicable. Thus, we resort to rounding $x_j^m$ by placing $V{M}_j$ on PM $m^{\prime }$ where $m^{\prime }={\max }_m{x}_j^m$ and set $x_j^{m^{\prime }}=1$ . In summary, the rationale for our algorithm is to integrate coflow scheduling and VM placement to achieve optimal scheduling, and then let VM placement cooperate to approximate this goal. The heuristic for pursuing a minimal CCT is summarized in Algorithm 2.

Finally, we analyze the performance of Algorithm 2 using the standard notion of approximation ratio. The approximation ratio of Algorithm 2 is defined as the supremum of $t_{\min }/t_i$ , where $t_{\min }$ is the minimum CCT of $C_i$ and $t_i$ is CCT obtained by our algorithm.

Theorem 1 Algorithm 2 has the approximation ratio of 2, that is,

$$t_i⩽2t_{\min }.$$

Proof To prove this theorem, the equivalent proposition is ${\alpha }_i⩾{\alpha }_{\max }/2$ , where ${\alpha }_i$ and ${\alpha }_{\max }$ are the inverse of $t_i$ and $t_{\min }$ , respectively. We assume that the objective of problem (5) is ${\alpha }_{\text{upper}}$ . Problem (5) is the binary relaxation of problem (4) and the feasible solution of the linear formulation sets an upper bound ${\alpha }_{\text{upper}}⩾{\alpha }_{\max }$ .

Multiplier $x_j^m(1-x_k^m)$ is mathematically equal to a graph cut where $j$ and $k$ are vertices and edge $⟨j,k⟩$ cuts vertex $m$ from $M-m$ . The physical meaning of this cut is that we place VM $j$ in host $h_m$ with the proportion $x_j^m$ . In our heuristic, we only pick the $x_j^m$ with the largest value and discard the rest. Let $C_{(j,k)}^m$ be the weight of cut $⟨j,k⟩$ , and let the value of $x_j^m$ be the value of $C_{(j,k)}^m$ . Accordingly, let $a_j^m$ be the value of cut $A_{(j,k)}^m$ in the optimal solution. Finally, we have a set of cuts $C$ that separates every $m$ from $M$ , which is the final placement.

Note that each cut $C_{(j,k)}^m$ is an incident at two of these components. Each edge will be in two of the cuts, hence, $\sum w(C_{(j,k)}^m)=2w(C)$ . Therefore, we have

$$\underset{m}{\sum }{x}_j^m(1-x_k^m)⩽\underset{m}{\sum }w(C_{(j,k)}^m)⩽\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}$$ $$\underset{m}{\sum }w(A_{(j,k)}^m)=2w(A),$$ $${\alpha }_i=$$ $${\displaystyle \frac{\underset{m}{\sum }{V}_{i,j,k}^m}{\underset{m}{\sum }(x_j^m(1-x_k^m))}}⩾{\displaystyle \frac{\underset{m}{\sum }{V}_{i,j,k}^m}{2\underset{m}{\sum }(a_j^m(1-a_k^m))}}=$$ $${\displaystyle \frac{{\alpha }_i^{\text{upper}}}{2}}⩾{\displaystyle \frac{{\alpha }_i^{\max }}{2}}.$$

The analytical result provides the worst-case guarantee of this algorithm. Theoretically, a loose bound is derived, but in practice this algorithm works effetively in improving the CCT for real applications in the cloud environment.