Scheduling Coflows for Minimizing the Makespan in Identical Parallel Networks

This paper addresses the coflow scheduling problem in identical parallel networks with the objective of minimizing the makespan. In the flow-level scheduling problem, we propose a $(3-\frac{2}{m})$-approximation algorithm as well as a $(\frac{8}{3}-\frac{2}{3m})$-approximation algorithm, where $m$ represents the number of network cores. Additionally, for the coflow-level scheduling problem, we present a $(2m)$-approximation algorithm.

We structure the remaining sections as follows. Section 2 provides an overview of several related works. In Section 3, we present the fundamental notations and preliminaries used in this paper. Our main results are presented in Section 4 and Section 5, where we provide two approximation algorithms for flow-level scheduling in Section 4, and one approximation algorithm for coflow-level scheduling in Section 5. Subsequently, in Section 6, we conduct experiments to evaluate and compare the performance of our proposed algorithms with Weaver’s [16]. Finally, in Section 7, we present our conclusions.

In this subsection, we introduce two algorithms for the flow-level scheduling problem. One is flow-list-scheduling (FLS) described in Algorithm 1, and the other is flow-longest-processing-time-first-scheduling (FLPT) described in Algorithm 2. The algorithm referred to as FLS (Algorithm 1) is outlined below. Let $\mathcal{F}$ represent the set of flows obtained from all coflows within the coflow set $\mathcal{K}$. For each flow $(i,j,k)\in\mathcal{F}$, our algorithm examines all flows that share congestion with $(i,j,k)$ and are scheduled prior to $(i,j,k)$. Subsequently, flow $(i,j,k)$ is assigned to the core $h\in\mathcal{M}$ with the least workload, thereby minimizing the completion time of flow $(i,j,k)$. Lines 6-11 determine the core with the minimum load and assign the flow to it. In terms of time complexity, Algorithm 1 (FLS) involves scanning each flow in $\mathcal{F}$ (line 6 in Algorithm 1), which amounts to $|\mathcal{F}|$ iterations. For each flow, a comparison is made among $m$ cores to identify the least loaded core (line 7 in Algorithm 1). Consequently, the time complexity of FLS is $O(m|\mathcal{F}|)$.

The algorithm known as FLPT (Algorithm 2) is presented below. It should be noted that Algorithm 2 is nearly identical to Algorithm 1. The key difference lies in line 6 of the algorithm. Specifically, lines 6-11 involve sorting the flows $(i,j,k)\in\mathcal{F}$ in non-increasing order based on the value of $d_{i,j,k}$. Subsequently, the algorithm identifies the core with the least workload and assigns the flow to it. In terms of time complexity, Algorithm 2 (FLPT) begins by spending a runtime complexity of $O(|\mathcal{F}|\log|\mathcal{F}|)$ to sort the flows (line 6 in Algorithm 2). Afterwards, FLPT follows the same procedure as FLS. Consequently, the time complexity of FLPT can be expressed as $O(m|\mathcal{F}|+|\mathcal{F}|\log|\mathcal{F}|)$.

This subsection shows that Algorithm 1 achieves $(3-\tfrac{2}{m})$-approximation ratio and Algorithm 2 achieves $(\tfrac{8}{3}-\tfrac{2}{3m})$-approximation ratio, where $m$ is the number of network cores. An intuitive lower bound on the optimal solution cost is

where $L_{i,k}=\sum_{j=1}^{N}d_{i,j,k}$, and $L_{j,k}=\sum_{i=1}^{N}d_{i,j,k}$. First, the following lemma for Algorithm 1 is obtained:

Therefore, theorem 1 is derived from lemma 1.

Next, this paper shows that Algorithm 2 has a better approximation ratio than Algorithm 1. We consider the worst case that one flow will affect other flows at input port $i\in\mathcal{I}$ and output port $j\in\mathcal{J}$ on the same core, then other affected flows will keep affecting others. This causes all flows on the same core can not be sent from input port to output port in parallel. In other words, the load of combining input port $i\in\mathcal{I}$ and output port $j\in\mathcal{J}$ of each core $h\in\mathcal{M}$ is the sum of all flows on core $h$. Therefore, the following lemma for Algorithm 2 is obtained:

Therefore, theorem 2 is derived from lemma 2.

This subsection introduces an algorithm for solving the coflow-level scheduling problem. The algorithm, called coflow-list-scheduling (CLS) and described in Algorithm 3, aims to assign each coflow $k\in\mathcal{K}$ to a core $h\in\mathcal{M}$ in order to minimize the completion time of coflow $k$. Lines 6-11 of the algorithm identify the core with the minimum maximum completion time and assign the coflow to it.

In terms of time complexity, Algorithm 3 scans each coflow in $\mathcal{K}$ (line 6), resulting in $|\mathcal{K}|$ iterations. For each coflow, the algorithm compares $m$ cores to find the least loaded core (line 7). Additionally, for each core, $N^{2}$ pairs of input and output ports are compared to determine the maximum completion time (line 7). Consequently, the time complexity of CLS is $O(m{N^{2}}|\mathcal{K}|)$.

This section paper shows that Algorithm 3 achieves $(2m)$-approximation ratio, where $m$ is the number of network cores. First, the following lemma for Algorithm 3 is obtained:

Therefore, theorem 3 is derived from lemma 3.

We have implemented a flow-level simulator to track the assignment of each flow to various cores in both identical parallel networks and heterogeneous parallel networks. Our simulator is based on Mosharaf’s implementation [8], which originally simulates coflows on a single core. To track coflows assigned to $m$ cores, we have modified the code so that our simulator traces flows $m$ times for all cores. Additionally, we have incorporated Shafiee and Ghaderi’s algorithm [21] to ensure that all flows are transferred in a preemptible manner within each core. Moreover, each link in our simulator has a capacity of 128 MBps. We have chosen the time unit to be $\tfrac{1}{128}$ second (approximately 8 milliseconds) so that each link has a capacity of 1 MB per time unit.

In our study, all algorithms are simulated using both synthetic and real traffic traces. In synthetic traces, coflows are generated based on the number of coflows, denoted as $K$, and the number of ports, denoted as $N$. Each coflow is described by $(W_{min},W_{max},L_{min},L_{max})$, where $1\leq W_{min}\leq W_{max}$ and $1\leq L_{min}\leq L_{max}$, for all $W_{min},W_{max},L_{min},L_{max}\in\mathbb{Z}$. Let $M$ represent the number of non-zero flows within each coflow. Then, $M=w_{1}\cdot w_{2}$, where $w_{1}$ and $w_{2}$ are randomly chosen from the set $\{W_{min},W_{min}+1,\ldots,W_{max}\}$. Additionally, $w_{1}$ is randomly assigned to input links, and $w_{2}$ is randomly assigned to output links. The size of flow $d_{i,j,k}$ is randomly selected from $\{L_{min},L_{min}+1,\ldots,L_{max}\}$. If the construction of a coflow is not explicitly specified in the synthetic traces, the default construction for all coflows follows a certain distribution of coflow descriptions: $(1,5,1,10)$, $(1,5,10,1000)$, $(5,N,1,10)$, and $(5,N,10,1000)$ with percentages of $41\%$, $29\%$, $9\%$, and $21\%$ respectively.

In real traces, coflows are generated from a realistic workload based on a Hive/MapReduce trace [7] obtained from Facebook, which was collected from a 3000-machine setup with 150 racks. These real traces have been widely used as benchmarks in various works, such as [11, 16, 18, 21]. The purpose of this benchmark is to provide realistic workloads synthesized from real-world data-intensive applications for the evaluation of coflow-based solutions. Since this paper does not consider release times, the release time for all coflows is set to 0.

In order to assess the performance of the algorithms, we calculate the approximation ratio. For identical parallel networks, the ratio is obtained by dividing the makespan achieved by the algorithms by the lower bound of the optimal value:

where $m$ represents the number of network cores. This lower bound value provides an estimate of the optimal makespan.

For heterogeneous parallel networks, the ratio of algorithms is calculated by dividing the makespan obtained from the algorithms by another lower bound of the optimal value:

In this case, $s_{l}$ represents the speed factor of core $l$. In a heterogeneous parallel network with $m$ network cores, $s_{l}$ is randomly selected from the range $\left[1,\frac{m}{h}\right]$, where $h$ is a heterogeneity factor. Higher values of $h$ indicate lower variance in network core speeds. This lower bound estimation takes into account the varying speeds of the cores.

By comparing the achieved makespan with these lower bound estimates, we can evaluate the performance of the algorithms in both identical and heterogeneous parallel networks.

Figure 2 illustrates the algorithm ratios of FLS, FLPT, Weaver, and CLS for different thresholds of the number of flows in identical parallel networks. The real traces consist of 526 coflows distributed across $m=5$ network cores with $N=150$ input/output links. Among all the coflows, the maximum number of flows is 21170, while the minimum number is 1. Additionally, the maximum flow size is 2472 MB, and the minimum size is 1 MB. Similar to the approach described in [21], we set a threshold to filter coflows based on the number of non-zero flows. Coflows with a number of flows below the threshold are filtered out. We consider five collections filtered using the following thresholds: 200, 400, 600, 800, and 1000.

Subsequent experiments reveal that when there is a large number of coflows or sparse demand matrices, FLPT and Weaver demonstrate very similar performance. Consequently, in Figure 2(a), FLPT exhibits the same ratio as Weaver. Additionally, CLS matches the ratio of $2m$ as depicted in Figure 2(b).

Figure 3 illustrates the algorithm ratios of FLS, FLPT, Weaver, and CLS for different numbers of network cores in identical parallel networks. In this synthetic trace, we consider $25$ coflows across 5 scenarios with varying numbers of network cores and $N=10$ input/output links. Each scenario represents a distinct number of cores, namely $m=5,10,15,20,25$. For each scenario, we generate 100 sample traces and report the average performance of the algorithms.

The results demonstrate that FLPT consistently outperforms Weaver in terms of the ratio, as depicted in Figure 3(a). Furthermore, as the number of cores increases, the improvement provided by FLPT becomes more significant. Additionally, the ratio of CLS exhibits an increasing trend with the growing number of cores, as illustrated in Figure 3(b). This result aligns with the theoretical analysis.

Figure 4 illustrates the algorithm ratios of FLS, FLPT, Weaver, and CLS for different numbers of network coflows in an identical parallel network. In this synthetic trace, we consider $m=5$ cores with $N=10$ input/output links across 5 scenarios with varying numbers of coflows. Each scenario represents a distinct number of coflows: $5,10,15,20,25$. For each scenario, we generate 100 sample traces and report the average performance of the algorithms.

The results demonstrate that FLPT outperforms Weaver in terms of the approximation ratio, as depicted in Figure 4(a). Furthermore, as the number of coflows increases, Weaver’s performance approaches that of FLPT. Moreover, the ratio of CLS decreases as the number of coflows increases, as shown in Figure 4(b). This indicates that the algorithm performs better with a larger number of coflows.

Figure 5 illustrates the approximation ratio of FLS, FLPT, Weaver, and CLS for dense and combined instances, as described in [21]. These instances are deployed in an identical parallel network. The synthetic trace consists of two sets of 25 coflows, each utilizing $m=5$ network cores and $N=10$ input/output links. One set represents a dense instance, while the other represents a combined instance. To create dense and combined instances, we define dense and sparse coflows. In a dense coflow, the coflow description $(W_{min},W_{max},L_{min},L_{max})$ is set to $(\sqrt{N},N,1,100)$. On the other hand, a sparse coflow has the description $(1,\sqrt{N},1,100)$. Therefore, in a dense instance, each coflow is dense, whereas in a combined instance, each coflow has an equal probability of being dense or sparse.

We generate 100 sample traces for each instance and present the average performance of the algorithms. The results show that FLPT outperforms Weaver in both dense and combined instances, as depicted in Figure 5(a). The improvement is more significant in the case of dense instances. Moreover, the ratio of dense instances is superior to that of combined instances, as shown in Figure 5(a) and Figure 5(b).

Figure 6 presents a box plot showing the performance of FLS, FLPT, Weaver, and CLS in an identical parallel network. The synthetic trace used for this analysis consists of $25$ coflows deployed in a network with $m=25$ cores and $N=10$ input/output links. We conducted 100 sample traces for each algorithm and represented the results using a box plot. The plot includes quartiles, maximum and minimum values for each algorithm. The findings demonstrate that FLPT not only achieves a superior ratio compared to Weaver but also exhibits a narrower interquartile range. This is evident in Figure 6 and summarized in Table 2. In Figure 6(b), it can be observed that the approximation ratio of CLS, as well as its interquartile range, increase as the number of cores grows.

Figure 7 displays the cumulative distribution function (CDF) of core completion time for FLS, FLPT, Weaver, and CLS in an identical parallel network. The synthetic trace used in this analysis involves 15 coflows operating in a network with $m=5$ cores and $N=10$ input/output links. The results indicate that FLPT achieves core completion before 29.320 seconds for all cores, while both FLS and Weaver achieve completion before 30.872 seconds, as illustrated in Figure 7(a). Additionally, CLS completes the core processing before 64.592 seconds for all cores, as depicted in Figure 7(b).

The algorithm proposed in this paper can be adapted for scheduling in heterogeneous parallel networks. The pseudocode of the algorithms is provided in the APPENDIX. The following are the simulation results of the algorithms in heterogeneous parallel networks.

Figure 8 illustrates the approximation ratio of FLPT and Weaver for different numbers of cores in heterogeneous parallel networks. The analysis is based on a synthetic trace comprising 25 coflows in five scenarios with varying numbers of network cores, while maintaining $N=10$ input/output links. In Figure 8(a), we set $h$ to 5, while in Figure 8(b), we set $h$ to 1. For each scenario, we generate 100 sample traces and report the average performance of the algorithms.

The findings demonstrate that as the number of cores increases, the approximation ratio also increases. Furthermore, as the number of cores increases, the performance gap between FLPT and Weaver widens. These observations align with the results observed in identical parallel networks. In Figure 8(b), the approximation ratio of CLS increases with the number of cores and decreases with the number of coflows. This result is also consistent with the findings observed in identical parallel networks.

Figure 9 illustrates a box plot displaying the performance of FLS, FLPT, Weaver, and CLS in heterogeneous parallel networks. The synthetic trace used in this analysis involves $25$ coflows operating in a network with $m=50$ cores and $N=10$ input/output links. For this scenario, we set $h$ as 5 and generated 100 sample traces for each algorithm. The box plot includes quartiles, maximum and minimum values for each algorithm. The results reveal that FLPT not only achieves a superior ratio compared to Weaver but also exhibits a narrower interquartile range. This is demonstrated in Figure 9(a) and summarized in Table 3. In Figure 9(b), it can be observed that the approximation ratio of CLS, as well as its interquartile range, increase as the number of cores grows. These results are consistent with those observed in identical parallel networks.

Figure 10 displays the approximation ratio of FLPT, Weaver, and CLS for different heterogeneity factors in heterogeneous parallel networks. The analysis is based on a synthetic trace comprising 25 coflows and $m=20$ cores with $N=10$ input/output links in five scenarios with varying heterogeneity factors.

For each scenario, we generated 100 sample traces and reported the average performance of the algorithms. When the heterogeneity increases (with $h=1$), FLPT and Weaver exhibit similar performance. However, when the heterogeneity decreases (with $h=5$), the performance gap between FLPT and Weaver widens. Overall, FLPT outperforms Weaver in terms of performance. Regarding CLS, there is no significant difference in performance based on heterogeneity factors. However, the number of cores has a greater impact on the performance of CLS.