Experimental Analysis of Algorithms for
Coflow Scheduling?
Zhen Qiu, Cliff Stein and Yuan Zhong

arXiv:1603.07981v1 [cs.NI] 25 Mar 2016

Dept. of IEOR, Columbia University, New York NY 10027, USA

Abstract. Modern data centers face new scheduling challenges in optimizing job-level performance objectives, where a significant challenge
is the scheduling of highly parallel data flows with a common performance goal (e.g., the shuffle operations in MapReduce applications).
Chowdhury and Stoica [6] introduced the coflow abstraction to capture
these parallel communication patterns, and Chowdhury et al. [8] proposed effective heuristics to schedule coflows efficiently. In our previous
paper [17], we considered the strongly NP-hard problem of minimizing
the total weighted completion time of coflows with release dates, and
developed the first polynomial-time scheduling algorithms with O(1)approximation ratios.
In this paper, we carry out a comprehensive experimental analysis on a
Facebook trace and extensive simulated instances to evaluate the practical performance of several algorithms for coflow scheduling, including
our approximation algorithms developed in [17]. Our experiments suggest
that simple algorithms provide effective approximations of the optimal,
and that the performance of the approximation algorithm of [17] is relatively robust, near optimal, and always among the best compared with
the other algorithms, in both the offline and online settings.

1

Introduction

Data-parallel computation frameworks such as MapReduce [9], Hadoop [1,5,18],
Spark [20], Google Dataflow [2], etc., are gaining tremendous popularity as they
become ever more efficient in storing and processing large-scale data sets in
modern data centers. This efficiency is realized largely through massive parallelism. Typically, a datacenter job is broken down into smaller tasks, which
are processed in parallel in a computation stage. After being processed, these
tasks produce intermediate data, which may need to be processed further, and
which are transferred between groups of servers across the datacenter network,
in a communication stage. As a result, datacenter jobs often alternate between
computation and communication stages, with parallelism enabling the fast completion of these large-scale jobs. While this massive parallelism contributes to
efficient data processing, it presents many new challenges for network scheduling.
In particular, traditional networking techniques focus on optimizing flow-level
?

Research partially supported by NSF grant CCF-1421161

performance such as minimizing flow completion times1 , and ignore job-level
performance metrics. However, since a computation stage often can only start
after all parallel dataflows within a preceding communication stage have finished
[7,10], all these flows need to finish early to reduce the processing time of the
communication stage, and of the entire job.
To faithfully capture application-level communication requirements, Chowdhury and Stoica [6] introduced the coflow abstraction, defined to be a collection
of parallel flows with a common performance goal. Effective scheduling heuristics
were proposed in [8] to optimize coflow completion times. In our previous paper
[17], we developed scheduling algorithms with constant approximation ratios for
the strongly NP-hard problem of minimizing the total weighted completion time
of coflows with release dates, and conducted preliminary experiments to examine
the practical performance of our approximation algorithms. These are the first
O(1)-approximation algorithms for this problem. In this paper, we carry out
a systematic experimental study on the practical performance of several coflow
scheduling algorithms, including our approximation algorithms developed in [17].
Similar to [17], the performance metric that we focus on in this paper is the
total weighted coflow completion time. As argued in [17], it is a reasonable useroriented performance objective. It is also natural to consider other performance
objectives, such as the total weighted flow time2 , which we leave as future work.
Our experiments are conducted on real-world data gathered from Facebook and
extensive simulated data, where we compare our approximation algorithm and
its modifications to several other scheduling algorithms in an offline setting, and
evaluate their relative performances, and compare them to an LP-based lower
bound. The algorithms that we consider in this paper are characterized by several main components, such as the coflow order in which the algorithms follow,
the grouping of the coflows, and the backfilling rules. We study the impact of
each such component on the algorithm performance, and demonstrate the robust and near-optimal performance of our approximation algorithm [17] and its
modifications in the offline setting, under the case of zero release times as well
as general release times. We also consider online variants of the offline algorithms, and show that the online version of our approximation algorithm has
near-optimal performance on real-world data and simulated instances.
The rest of this section is organized as follows. In Section 1.1, we quickly recall
the problem formulation of coflow scheduling, the approximation algorithm of
[17] as well as its approximation ratio. Section 1.2 gives an overview of the
experimental setup and the main findings from our experiments. A brief review
of related works is presented in Section 1.3.

1

2

In this paper, the term “flow” refers to data flows in computer networking, and is
not to be confused with the notion of “flow time,” commonly used in the scheduling
literature.
Here “flow time” refers to the length of time from the release time of a coflow to its
completion time, as in scheduling theory.

1.1

Coflow Model and Approximation Algorithm

We consider a discrete-time system where n coflows need to be scheduled
in an m × m datacenter network with m inputs and m outputs. For each k ∈
{1, 2, · · · , n}, coflow
k is released at time rk , and can be represented by an m×m

m
(k)
(k)
(k)
matrix D
= dij
, where dij is the number of data units (a.k.a. flow
i,j=1

size) that need to be transferred from input i to output j. The network has the
so-called non-blocking switch architecture [3,4,12,16], so that a data unit that is
transferred out of an input is immediately available at the corresponding output.
We also assume that all inputs and outputs have unit capacity. Thus, in a time
slot, each input/output can process at most one data unit; similar to [17], these
restrictions are called matching constraints. Let Ck denote the completion time
of coflow k, which is the time when all data units from coflow k have finished
being transferred. We are interested
in developing efficient (offline) scheduling
Pn
algorithms that minimize
w
C
k
k , the total weighted completion time of
k=1
coflows, where wk is a weight parameter associated with coflow k.
A main result of [17] is the following theorem.
Theorem 1 [17] There exists a deterministic polynomial time 67/3-approximation
algorithm for the coflow scheduling problem, with the objective of minimizing the
total weighted completion time.
The approximation algorithm of [17] consists of two related stages. First, a coflow
order is computed by solving a polynomial-sized interval-indexed linear program
(LP) relaxation, similar to many other scheduling algorithms (see e.g., [11]).
Then, we use this order to derive an actual schedule. To do so, we define a
grouping rule, under which we partition coflows into a polynomial number of
groups, based on the minimum required completion times of the ordered coflows,
and schedule the coflows in the same group as a single coflow optimally, according to an integer version of the Birkhoff-von Neumann decomposition theorem.
The description of the algorithm is given in Algorithm 4 of the Appendix for
completeness. Also see [17] for more details. From now on, the approximation
algorithm of [17] will be referred to as the LP-based algorithm.
1.2

Overview of Experiments

Since our LP-based algorithm consists of an ordering and a scheduling stage,
we are interested in algorithmic variations for each stage and the performance
impact of these variations. More specifically, we examine the impact of different
ordering rules, coflow grouping and backfilling rules, in both the offline and online
settings. Compared with the very preliminary experiments we did in [17], in
this paper we conduct a substantially more comprehensive study by considering
many more ordering and backfilling rules, and examining the performance of
algorithms on general instances in addition to real-world data. We also consider
the offline setting with general release times, and online extensions of algorithms,
which are not discussed in [17].

Workload. Our evaluation uses real-world data, which is a Hive/MapReduce
trace collected from a large production cluster at Facebook [7,8,17], as well as
extensive simulated instances.
For real-world data, we use the same workload as described in [8,17]. The
workload is based on a Hive/MapReduce trace at Facebook that was collected
on a 3000-machine cluster with 150 racks, so the datacenter in the experiments
can be modeled as a 150 × 150 network switch (and coflows be represented by
150 × 150 matrices). We select the time unit to be 1/128 second (see [17] for
details) so that each port has the capacity of 1MB per time unit. We filter the
coflows based on the number of non-zero flows, which we denote by M 0 , and we
consider three collections of coflows, filtered by the conditions M 0 ≥ 25, M 0 ≥ 50
and M 0 ≥ 100, respectively.
We also consider synthetic instances in addition to the real-world data. For
problem size with k = 160 coflows and m = 16 inputs and outputs, we randomly
generate 30 instances with different numbers of non-zero flows involved in each
coflow. For instances 1-5, each coflow consists of m flows, which represent sparse
coflows. For instances 5-10, each coflow consists of m2 flows, which represent
dense coflows. For instances 11-30, each coflow consists of u flows, where u is
uniformly distributed on {m, · · · , m2 }. Given the number k of flows in each
coflow, k pairs of input and output ports are chosen randomly. For each pair of
(i, j) that is selected, an integer processing requirement di,j is randomly selected
from the uniform distribution on {1, 2, · · · , 100}.
Our main experimental findings are as follows:
– Algorithms with coflow grouping consistently outperform those without grouping. Similarly, algorithms that use backfilling consistently outperform those
that do not use backfilling. The benefit of backfilling can be further improved
by using a balanced backfilling rule (see §3.2 for details).
– The performance of the LP-based algorithm and its extensions is relatively
robust, and among the best compared with those that use other simpler
ordering rules, in the offline setting.
– In the offline setting with general release times, the magnitude of inter-arrival
times relative to the processing times can have complicated effects on the
performance of various algorithms. (see §4.1 for details).
– The LP-based algorithm can be extended to an online algorithm and has
near-optimal performance.
1.3

Related Work

There has been a great deal of success over the past 20 years on combinatorial
scheduling to minimize average completion time, see e.g., [11,14,15,19], typically
using a linear programming relaxation to obtain an ordering of jobs and then
using that ordering in some other polynomial-time algorithm. There has also
been success in shop scheduling. We do not survey that work here, but note that
traditional shop scheduling is not “concurrent”. In the language of our problem,
that would mean that two flows in the same coflow could not be processed

simultaneously. The recently studied concurrent open shop problem removes
this restriction and models flows that can be processed in parallel. There is a
close connection between concurrent open shop problem and coflow scheduling
problem. When all coflow matrices are diagonal, coflow scheduling is equivalent
to a concurrent open shop scheduling problem [8,17]. Leung et al. [13] presented
heuristics for the total completion time objective and conducted an empirical
analysis to compare the performance of different heuristics for concurrent open
shop problem. In this paper, we consider a number of heuristics that include
natural extensions of heuristics in [13] to coflow scheduling.

2

Preliminary Background

In [17], we formulated the following interval-indexed linear program (LP)
relaxation of the coflow scheduling problem, where τl ’s are the end points of
a set of geometrically increasing intervals, with τ0 = 0, and τl = 2l−1 for l ∈
{1, 2, . . . , L}. Here L is such that τL = 2L−1 is an upper bound on the time that
all coflows are finished processing under any optimal algorithm.
(LP )

Minimize

l X
n X
m
X
u=1 k=1

n
X
k=1

wk

L
X

(k)

τl−1 xl

subject to

l=1

(k)

(1)

(k)

(2)

dij 0 x(k)
u ≤ τl , for i = 1, . . . , m, l = 1, . . . , L;

j 0 =1

l X
n X
m
X

di0 j x(k)
u ≤ τl , for j = 1, . . . , m, l = 1, . . . , L;

u=1 k=1 i0 =1
(k)

xl

= 0 if rk +

m
X

(k)

dij 0 > τl or rk +

j 0 =1
L
X
l=1
(k)
xl

(k)

xl

m
X

(k)

di0 j > τ l ;

(3)

i0 =1

= 1, for k = 1, . . . , n;

≥ 0, for k = 1, . . . , n, l = 1, . . . , L.
(k)

For each k and l, xl can be interpreted as the LP-relaxation of the binary decision variable which indicates whether coflow k is scheduled to complete
within the interval (τl−1 , τl ]. Constraints (1) and (2) are the load constraints on
the inputs and outputs, respectively, which state that the total amount of work
completed on each input/output by time τl cannot exceed τl , due to matching
constraints. Constraint (3) takes into account of the release times.
(LP) provides a lower bound on the optimal total weighted completion time
of the coflow scheduling problem. If, instead of being end points of geometrically
increasing time intervals, τl are end points of the discrete time units, then (LP)
becomes exponentially sized (which we refer to as (LP-EXP)), and gives a tighter
lower bound, at the cost of longer running time. (LP) computes an approximated
PL
(k)
completion time C̄k = l=1 τl−1 x̄l , for each k, based on which we re-order and
index the coflows in a nondecreasing order of C¯k , i.e.,
C̄1 ≤ C̄2 ≤ . . . ≤ C̄n .

(4)

3

Offline Algorithms with Zero Release Time

In this section, we assume that all the coflows are released at time 0. We
compare our LP-based algorithm with others that are based on different ordering,
grouping, and backfilling rules.

3.1

Ordering Heuristics

An intelligent ordering of coflows in the ordering stage can substantially
reduce coflow completion times. We consider the following five greedy ordering
rules, in addition to the LP-based order (4), and study how they affect algorithm
performance.
Definition 1 The First in first (FIFO) heuristic orders the coflows arbitrarily
(since all coflows are released at time 0).
Definition 2 The Shortest Total Processing Time first (STPT) heuristic orders
the coflowsP
basedPon the total amount of processing requirements over all the
m
m
ports, i.e., i=1 j=1 dij .
Definition 3 The Shortest Maximum Processing Time first (SMPT) heuristic
orders the coflows based on the load ρ of the coflows, where ρ = max{ max ηi ,
Pm
Pmi=1,...,m
max θj }, ηi = { j 0 =1 dij 0 } is the load on input i, and θj = { i0 =1 di0 j } is

j=1,...,m

the load on output j.
Definition 4 To compute a coflow order, the Smallest Maximum Completion
Time first (SMCT) heuristic treats all inputs and outputs as 2m independent
machines. For each input i, it solves a single-machine scheduling problem where n
(k)
(k)
jobs are released at time 0, with processing times ηi , k = 1, 2, · · · , n, where ηi
is the ith input load of coflow k. The jobs are sequenced in the order of increasing
(k)
ηi , and the completion times C (i) (k) are computed. A similar problem is solved
(k)
for each output j, where jobs have processing times θj , and the completion
times C(j) (k) are computed. Finally, the SMCT heuristic computes a coflow
order according to non-decreasing values of C 0 (k) = max{C (i) (k), C(j) (k)}.
i,j

Definition 5 The Earliest Completion Time first (ECT) heuristic generates a
sequence of coflow one at a time; each time it selects as the next coflow the one
that would be completed the earliest3 .
3

These completion times depend on the scheduling rule used. Thus, ECT depends on
the underlying scheduling algorithm. In §3.2, the scheduling algorithms are described
in more detail.

3.2

Scheduling via Birkhoff-von Neumann Decomposition,
Backfilling and Grouping

The derivation of the actual sequence of schedules in the scheduling stage
of our LP-based algorithm relies on two key ideas: scheduling according to an
optimal (Birkhoff-von Neumann) decomposition, and a suitable grouping of the
coflows. It is reasonable to expect grouping to improve algorithm performance,
because it may consolidate skewed coflow matrices to form more balanced ones
that can be scheduled more efficiently. Thus, we compare algorithms with grouping and those without grouping to understand its effect. The particular grouping
procedure that we consider here is the same as that in [17] (also see Step 2 of
Algorithm 4 of the Appendix), and basically groups coflows into geometrically
increasing groups, based on aggregate demand. Coflows of the same group are
treated as a single, aggregated coflow, and this consolidated coflow is scheduled
according to the Birkhoff-von Neumann decomposition (see [17] or Algorithm 5
of the Appendix).
Backfilling is a common strategy used in scheduling for computer systems
to increase resource utilization (see, e.g. [8]). While it is difficult to analytically
characterize the performance gain from backfilling in general, we evaluate its
performance impact experimentally. We consider two backfilling rules, described
as follows. Suppose that we are currently scheduling coflow D. The schedules are
computed using the Birkhoff-von Neumann decomposition, which in turn makes
use of a related, augmented matrix D̃, that is component-wise no smaller than D.
The decomposition may introduce unforced idle time, whenever D 6= D̃. When
we use a schedule that matches input i to output j to serve the coflow with
Dij < D̃ij , and if there is no more service requirement on the pair of input i and
output j for the coflow, we backfill in order from the flows on the same pair of
ports in the subsequent coflows. When grouping is used, backfilling is applied to
the aggregated coflows. The two backfilling rules that we consider – which we call
backfilling and balanced backfilling – are only distinguished by the augmentation
procedures used, which are, respectively, the augmentation used in [17] (Step 1
of Algorithm 5) and the balanced augmentation described in Algorithm 1.
The balanced augmentation (Algorithm 1) results in less skewed matrices
than the augmentation step in [17], since it first “spreads out” the unevenness
among the components of a coflow. To illustrate, let






10 0 0
10 10 10
10 20 0
D =  10 0 0  , B =  10 10 10  , and C =  10 0 20  .
10 0 0
10 10 10
10 10 10
Under the balanced augmentation, D is augmented to B and under the augmentation of [17], D is augmented to C.
3.3

Scheduling Algorithms and Metrics

We consider 30 different scheduling algorithms, which are specified by the
ordering used in the ordering stage, and the actual sequence of schedules used

Algorithm 1: Balanced Coflow Augmentation
Data: A single coflow D = (dij )m
.
 m i,j=1
˜
with equal row and column sums, and D ≤ D̃.
Result: A matrix D̃ = dij
i,j=1

Let ρ be the
P load of D.
0
pi ← ρ − P m
j 0 =1 dij , for i = 1, 2, . . . , m.
m
0 j , for j = 1, 2, . . . , m.
d
qi ← ρ − P
0
i
i =1 P
m
∆ ← mρ − m
j=1 dij .
i=1
0
dij = bdij + pi qi /∆c.
Augment D0 = (d0ij ) to a matrix D̃ with equal row and column sums (see Step 1
of Algorithm 5 of the Appendix; also see [17]).

in the scheduling stage. We consider 6 different orderings described in §3.1, and
the following 5 cases in the scheduling stage:
–
–
–
–
–

(a) without grouping or backfilling, which we refer to as the base case;
(b) without grouping but with backfilling;
(c) without grouping but with balanced backfilling;
(d) with grouping and with backfilling;
(e) with grouping and with balanced backfilling.

We will refer to these cases often in the rest of the paper. Our LP-based algorithm
(Algorithm 4 in the Appendix) corresponds to the combination of LP-based
ordering and case (d).
For ordering, six different possibilities are considered. We use HA to denote
the ordering of coflows by heuristic A, where A is in the set {FIFO, STPT,
SMPT, SMCT, ECT}, and HLP to denote the LP-based coflow ordering. Note
that in [17], we only considered orderings HF IF O , HSM P T and HLP , and cases
(a), (b) and (d) for scheduling, and their performance on the Facebook trace.

(a) Comparison of total weighted completion times normalized using the base case
(e) for each order

(b) Comparison of 6 orderings with zero
release times on Facebook data.

Fig. 1: Facebook data are filtered by M 0 ≥ 50. Weights are equal.

3.4

Performance of Algorithms on Real-World Data

We compute the total weighted completion times for all 6 orders in the 5
different cases (a) – (e) described in §3.3, through a set of experiments on filtered
coflow data. We present representative comparisons of the algorithms here.
Figure 1a plots the total weighted completion times as percentages of the base
case (a), for the case of equal weights. Grouping and backfilling both improve the
total weighted completion time with respect to the base case for all 6 orders. In
addition to the reduction in the total weighted completion time from backfilling,
which is up to 7.69%, the further reduction from grouping is up to 24.27%, while
the improvement from adopting the balanced backfilling rule is up to 20.31%.
For 5 non-arbitrary orders (excluding FIFO), scheduling with both grouping and
balanced backfilling (i.e., case (e)) gives the smallest total weighted completion
time.
We then compare the performances of different coflow orderings. Figure 1b
shows the comparison of total weighted completion times evaluated on filtered
coflow data in case (e) where the scheduling stage uses both grouping and balanced backfilling. Compared with HF IF O , all other ordering heuristics reduce
the total weighted completion times of coflows by a ratio between 7.88 and 9.11,
with HLP performing consistently better than other heuristics.
3.5

Cost of Matching

The main difference between our coflow scheduling problem and the wellstudied concurrent open shop problem we discussed in §1.3 is the presence of
matching constraints on paired resources, i.e. inputs and outputs, which is the
most challenging part in the design of approximation algorithms [17]. Since our
approximation algorithm handles matching constraints, it is more complicated
than scheduling algorithms for concurrent open shop problem. We are interested
in how much we lose by imposing these matching constraints.
To do so, we generate two sets of coflow data from the Facebook trace. For
each coflow k, let the coflow matrix D(k) be a diagonal matrix, which indicates
that coflow k only has processing requirement from input i to output i, for
(k)
i = 1, . . . , m. The processing requirement Di,i is set to be equal to the sum
of all dataflows of coflow k in the Facebook trace that require processing from
input i. We then construct coflow matrix D̃(k) such that D̃(k) is not diagonal and
has the same row sum and column sum as D(k) . The details of the generation is
described as in Algorithm 2.
The diagonal structured coflow matrices can reduce the total completion time
of by a ratio up to 2.09, which indicates the extra processing time introduced
by the matching constraints.
3.6

Performance of Algorithms on General Instances

In previous sections, we present the experimental results of several algorithms
on the Facebook trace. In order to examine the consistency of the performance of

these algorithms, we consider more instances, including examples where certain
algorithms behave badly.
Bad Instances for Greedy Heuristics We consider the following examples
which illustrate instances on which the ordering heuristics do not perform well.


10 0
Example 1 Consider a 2 × 2 network and n coflows with D =
, n
0 0




0 0
90
coflows with D =
, and a · n coflows with D =
. The optimal
0 10
09
schedule in this case is to schedule the orders with the smallest total processing
time first, i.e.,
Pn the schedule is generated according to the STPT rule. The limit
C (ECT &SM CT &SM P T )
is increasing in n and when n → ∞ it
of the ratio k=1 kPn Ck (ST P T )
k=1
√
√
a2 +4a+2
becomes a2 +2a+2 . This ratio reaches its maximum of 2 when a = 2.
We can generalize this counterexample to an arbitrary number of inputs and
outputs m. To be more specific, in an m × m network, for j = 1, 2, · · · , m, we
have n coflows only including flows to be transferred to output j, i.e., dij = 10.
We also have a · n coflows with equal transfer requirement on all pairs of inputs
and outputs, i.e., dij = 9 for i, j = 1, 2, · · · , m. The ratio
Pn
(ECT &SM CT &SM P T )
a2 + 2ma + m
k=1 CkP
= 2
lim
n
n→∞
a + 2a + m
k=1 Ck (ST P T )
√
√
has a maximum value of m when a = m. Note that in the generalized
example, we need to consider the matching constraints when we actually schedule
the coflows.


1 0
Example 2 Consider a 2 × 2 network and n coflows with D =
, and
0 10


10 0
a · n coflows with D =
. The optimal schedule in this case is to schedule
0 0
the orders with the Smallest Maximum Completion Time
first, i.e., the schedule
Pn
C (ST P T )
is generated according to the SMCT rule. The ratio Pnk=1 Ckk(SM CT ) is increasing
k=1

in n and when n → ∞ it becomes
√

when a =

a2 +2a
a2 +1

This ratio reaches its maximum of

√

5+1
2

5+1
2 .

This counterexample can be generalized to an arbitrary number of inputs and
outputs m. In an m × m network, for each i = 2, 3, · · · , m, we have n coflows
with two nonzero entries, d11 = 1 and dii = 10. We also have a · n coflows with
only one zero entry d11 = 10. The limit of the ratio
Pn
Ck (ST P T )
a2 + 2(m − 1)a
lim Pnk=1
=
n→∞
a2 + m − 1
k=1 Ck (SM CT )
p
p
has a maximum value of 1/2 + m − 3/4 when a = 1/2 + m − 3/4.

General instances We present comparison of total weighted completion time
for 6 orderings and 5 cases on general simulated instances as described in §1.2,
in Appendix Tables 1 to 5, normalized with respect to the LP-based ordering in
case (c), which performs best on all of the instances. We have the similar observation from the general instances that both grouping and backfilling reduce
the completion time. However, under balanced backfilling, grouping does not
improve performance much. Both grouping and balanced backfilling form less
skewed matrices that can be scheduled more efficiently, so when balanced backfilling is used, the effect of grouping is less pronounced. It is not clear whether
case (c) with balanced backfilling only is in general better than case (e) with
both balanced backfilling and grouping, as we have seen Facebook data on which
case (e) gives the best result. As for the performance of the orderings, on the
one hand, we see in Table 3 very close time ratios among all the non-arbitrary
orderings on instances 6 - 30, and a better performance of HECT on sparse instances 1 - 5 over other orderings; on the other hand, there are also instances
where ECT performs poorly (see §3.6 for details).
Besides their performance, the running times of the algorithms that we consider are also important. The running time of an algorithm consists of two main
parts; computing the ordering and computing the schedule. On a Macbook Pro
with 2.53 GHz two processor cores and 6G memory, the five ordering rules, FIFO,
STPT, SMPT, SMCT and ECT, take less than 1 second to compute, whereas
the LP-based order can take up to 90 seconds. Scheduling with backfilling can be
computed in around 1 minute, whereas balanced backfilling computes the schedules with twice the amount of time, beause the balanced augmented matrices
have more non-zero entries. Besides improving performance, grouping can also
reduce the running time by up to 90%.

Algorithm 2: Construction of coflow data
m
Data: A single diagonal coflow D = (dij )i,j=1 .
 m
Result: Another coflow D̃ = d˜ij
, such that row and column sums
i,j=1

of the
Pmtwo matrices are all equal.
Let η(D̃) = i,j=1 d˜ij be the sum of all entries in D̃. Similarly,
Pm
η(D) = i=1 dii .
D̃ ← 0.
while (η(D̃) < η(D)) do
Pm
Pm
Si ← {i : j 0 =1 D̃ij 0 < dii }; Sj ← {j : i0 =1 D̃i0 j < djj }. Randomly
pick i∗ from set Si and j ∗ from set Sj . D̃ ← D̃ + pE, where
Pm
Pm
p = min{di∗ i∗ − j 0 =1 D̃i∗ j 0 , dj ∗ j ∗ − i0 =1 D̃i0 j ∗ }, Eij = 1 if i = i∗
and j = j ∗ , and Eij = 0 otherwise.
Pm
η ← i,j=1 d˜ij
end

4

Offline Algorithms with General Release Times

In this section, we examine the performances of the same class of algorithms
and heuristics as that studied in Section 3, when release times can be general.
We first extend descriptions of various heuristics to account for release times.
The FIFO heuristic computes
a coflow order according to nondecreasing release time r. (Note
that when all release times are
distinct, FIFO specifies a unique
ordering on coflows, instead of
any arbitrary order in the case
of zero release times.) The STPT
heuristic computes a coflow order
according
val- (a) Comparison of total weighted completion
PmtoPnon-decreasing
m
ues of i=1 j=1 dij + r, the to- times normalized using the base case (c) for each
tal amount of processing require- order.
ments over all the ports plus the
release time. The SMPT heuristic computes a coflow order according to non-decreasing values
of ρ + r, the sum of the coflow
load and release time. Similar to
the case of zero release times, the
SMCT heuristic first sequences
the coflows
P in non-decreasing order of Pj 0 dij 0 + r on each input
0
i and
i0 di j + r on each out- (b) Comparison of 6 orderings with general reput j, respectively, and then com- lease times on Facebook data.
putes the completion times C (i)
0
and C(j) , treating each input and Fig. 2: Facebook data are filtered by M ≥
output as independent machines. 50. Weights are equal.
Finally, the coflow order is computed according to non-decreasing values of C 0 = maxi,j {C (i) , C(j) }. The ECT
heuristic generates a sequence of coflows one at a time; each time it selects as
the next coflow the one that has been released and is after the preceding coflow
finishes processing and would be completed the earliest.
We compute the total weighted completion time for 6 orderings (namely, the
LP-based ordering (4) and the orderings from definitions with release times and
cases (b) - (e) (recall the description of these cases at the beginning of Section
3.3), normalized with respect to the LP-based ordering in case (c). The results for
Facebook data are illustrated in Figure 2a and Figure 2b. For general instances,
we generate the coflow inter-arrival times from uniform distribution [1, 100] and
present the ratios in Tables 6 to 9 in the Appendix. As we can see from e.g.,
Figure 2a, the effects of backfilling and grouping on algorithm performance are
similar to those noted in §3.6, where release times are all zero. The STPT and

LP-based orderings STPT appear to perform the best among all the ordering
rules (see Figure 2b), because the magnitudes of release times have a greater
effect on FIFO, SMPT, SMCT and ECT than they do on STPT.
By comparing Figures 1b and 2b, we see that ECT performs much worse than
it does with common release times. This occurs because with general release
times, ECT only schedules a coflow after a preceding coflow completes, so it
does not backfill. While we have kept the ECT ordering heuristic simple and
reasonable to compute, no backfilling implies larger completion times, hence the
worse performance.
4.1

Convergence of Heuristics with Respect to Release Times

In order to have a better understanding of release times, we scale the
release times of the coflows and observe the impact of release time distribution on the performance of different heuristics. For general instances,
recall that we generated the interarrival times with an upper bound
of 100. Here we also consider interarrival time distributions that are uniform over [0, 0], [0, 25], [0, 50], [0, 200],
[0, 400], [0, 800] and [0, 1600], respectively. We compute the total weighted
completion time with the adjusted release times in each case for 250 samples and take the average ratio with
respect to the LP-based order.
As we can see from Figures 3a to
3c, all the heuristics converge to FIFO
as the inter-arrival time increases.
This is reasonable as the release times
dominate the ordering when they are
large. The speed of convergence is
higher in 3a where the coflow matrices in the instance are sparse and
release times are more influential in
all heuristics. On the contrary, when
the coflow matrices are dense, release
times weigh less in heuristics, which
converge slower to FIFO as shown in
3c. We also note that for heuristics
other than FIFO, the relative performance of an ordering heurstic with respect to the LP-based order may de-

(a) Number of flows is 16

(b) Number of flows is uniform in
[16, 256]

(c) Number of flows is 256

Fig. 3: Comparison of total weighted completion times with respect to the upper
bound of inter-arrival time for each order on
general instances. Network size is 16. Number of Coflow is 160.

teriorate and then improve, as we increase the inter-arrival times. This indicates
that when inter-arrival times are comparable to the coflow sizes, they can have
a significant impact on algorithm performance and the order obtained.

5

Online Algorithms

We have discussed the experimental results of our LP-based algorithm and
several heuristics in the offline setting, where the complete information of coflows
is revealed at time 0. In reality, information on coflows (i.e., flow sizes) is often only revealed at their release times, i.e., in an online fashion. It is then
natural to consider online modifications of the offline algorithms considered
in earlier sections. We proceed as follows. For the ordering stage, upon each
coflow arrival, we re-order the coflows according to their remaining processing requirements. We consider all six ordering rules described in §3. For example, the LP-based order is modified upon each coflow arrival, by re-solving
the (LP) using the remaining coflow sizes (and the newly arrived coflow) at
the time. We describe the online algorithm with LP-based ordering in Algorithm 3. For the scheduling stage, we use case (c) the balanced backfilling
rule without grouping, because of its good performance in the offline setting.
Algorithm 3: Online LP-based Approximation

m
(k)
Data: Coflows dij
with different release times, for k = 1, . . . , n.
i,j=1

Result: A scheduling algorithm that uses at most a polynomial number
of different matchings.
– Step 1: Given na coflows in the system, na ≤ n, solve the linear program
(k)
(LP). Let an optimal solution be given by x̄l , for l = 1, 2, . . . , L and
k = 1, 2, . . . , na . Compute the approximated completion time C̄k by
C̄k =

L
X

(k)

τl−1 x̄l .

l=1

Order and index the coflows according to
C̄1 ≤ C̄2 ≤ . . . ≤ C̄na .
– Step 2: Schedule the coflows in order using Algorithm 5 until an release of a
new coflow. Update the job requirement with the remaining job for each
coflow in the system and go back to Step 1.
We compare the performance of the online algorithms and we compare the
online algorithms to the offline algorithms. We improve the time ratio for all
the orderings except FIFO by allowing re-ordering and preemption in the online
algorithm compared with the static offline version. Note that we do not preempt
with FIFO order. While several ordering heuristics perform as well as LP-based
ordering in the online algorithms, a natural question to ask is how close HA ’s

are to the optimal, where A ∈ {ST P T, SM P T, SM CT, ECT, LP }. In order to
get a tight lower bound of the coflow scheduling problem, we solve (LP-EXP)
for sparse instances. Since it is extremely time consuming to solve (LP-EXP) for
dense instances, we consider a looser lower bound, which is computed as follows.
We first aggregate the job requirement on each input and output and solve a
single machine scheduling problem for the total weighted completion time, on
each input/output. The lower bound is obtained by taking the maximum of the
results. The lower bounds are shown in the last column of Table 11. The ratio of
the lower bound over the weighted completion time under HLP is in the range
of 0.91 to 0.97, which indicates that it provides a good approximation of the
optimal.

6

Conclusion

We have performed comprehensive experiments to evaluate different
scheduling algorithms for the problem of minimizing the total weighted
completion time of coflows in a datacenter network. We also generalize
our algorithms to an online version
for them to work in real-time. For additional interesting directions in experimental analysis of coflow schedul- Fig. 4: Comparison of total weighted
ing algorithms, we would like to come completion times with respect to the
up with structured approximation al- base case for each order under the offline
gorithms that take into considera- and online algorithms. Data are filtered
tion other metrics and the addition by M 0 ≥ 50. Weights are equal.
of other realistic constraints, such as
precedence constraints, and distributed algorithms that are more suitable for
implementation in a data center. These new algorithms can be used to design
other implementable, practical algorithms.
Acknowledgment Yuan Zhong would like to thank Mosharaf Chowdhury and
Ion Stoica for numerous discussions on the coflow scheduling problem, and for
sharing the Facebook data.

References
1. Apache hadoop. http://hadoop.apache.org.
2. Google dataflow. https://www.google.com/events/io.
3. Mohammad Alizadeh, Shuang Yang, Milad Sharif, Sachin Katti, Nick McKeown,
Balaji Prabhakar, and Scott Shenker. pfabric: Minimal near-optimal datacenter
transport. SIGCOMM Computer Communication Review, 43(4):435–446, 2013.

4. Hitesh Ballani, Paolo Costa, Thomas Karagiannis, and Ant Rowstron. Towards
predictable datacenter networks. SIGCOMM Computer Communication Review,
41(4):242–253, 2011.
5. Dhruba Borthakur. The hadoop distributed file system: Architecture and design.
Hadoop Project Website, 2007.
6. Mosharaf Chowdhury and Ion Stoica. Coflow: A networking abstraction for cluster
applications. In HotNets-XI, pages 31–36, 2012.
7. Mosharaf Chowdhury, Matei Zaharia, Justin Ma, Michael I. Jordan, and Ion Stoica. Managing data transfers in computer clusters with orchestra. SIGCOMM
Computer Communication Review, 41(4):98–109, 2011.
8. Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. Efficient coflow scheduling
with Varys. In SIGCOMM, 2014.
9. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on
large clusters. In OSDI, pages 10–10, 2004.
10. Fahad Dogar, Thomas Karagiannis, Hitesh Ballani, and Ant Rowstron. Decentralized task-aware scheduling for data center networks. Technical Report MSR-TR2013-96, 2013.
11. Leslie A Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to
minimize average completion time: Off-line and on-line approximation algorithms.
Mathematics of Operations Research, 22(3):513–544, 1997.
12. Nanxi Kang, Zhenming Liu, Jennifer Rexford, and David Walker. Optimizing the
”one big switch” abstraction in software-defined networks. In CoNEXT, pages
13–24, 2013.
13. Joseph Y. Leung, Haibing Li, and Michael Pinedo. Order scheduling in an environment with dedicated resources in parallel. Journal of scheduling, 8(5):355–386,
2005.
14. Cynthia A. Phillips, Cliff Stein, and Joel Wein. Minimizing average completion
time in the presence of release dates. Mathematical Programming, 82(1-2):199–223,
1998.
15. Michael Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, New
York, NY, USA, 3rd edition, 2008.
16. Lucian Popa, Arvind Krishnamurthy, Sylvia Ratnasamy, and Ion Stoica. Faircloud:
Sharing the network in cloud computing. In HotNets-X, pages 22:1–22:6, 2011.
17. Zhen Qiu, Cliff Stein, and Yuan Zhong. Minimizing the total weighted completion
time of coflows in datacenter networks. In ACM Symposium on Parallelism in
Algorithms and Architectures, pages 294–303, 2015.
18. Konstantin Shvachko, Hairong Kuang, Sanjay Radia, and Robert Chansler. The
hadoop distributed file system. In MSST, pages 1–10, 2010.
19. Martin Skutella. List Scheduling in Order of α-Points on a Single Machine, volume 3484 of Lecture Notes in Computer Science, pages 250–291. Springer, Berlin,
Heidelberg, 2006.
20. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma,
Murphy McCauley, Michael J. Franklin, Scott Shenker, and Ion Stoica. Resilient
distributed datasets: A fault-tolerant abstraction for in-memory cluster computing.
In NSDI, pages 2–2, 2012.

APPENDIX

A

Algorithms

A.1

Offline Algorithm

We describe our offline LP-based approximation algorithm [17] in detail in
Algorithm 4:

Algorithm 4: Offline LP-based Approximation

m
(k)
Data: Coflows dij

, for k = 1, . . . , n.

i,j=1

Result: A scheduling algorithm that uses at most a polynomial number of
different matchings.
– Step 1 (ordering): Given n coflows, solve the linear program (LP). Let an optimal
(k)
solution be given by x̄l , for l = 1, 2, . . . , L and k = 1, 2, . . . , n. Compute the
approximated completion time C̄k by
C̄k =

L
X

(k)

τl−1 x̄l .

l=1

Order and index the coflows according to
C̄1 ≤ C̄2 ≤ . . . ≤ C̄n .
– Step 2 (scheduling): For each k, k = 1, 2, . . . n, compute the maximum total input
load Ik , the maximum total output load Jk and the maximum total load Vk by
( m k
)
( m k
)
X X (g)
X X (g)
Ik = max
dij 0 , Jk = max
di0 j
i=1,...,m

j 0 =1 g=1

and

j=1,...,m

i0 =1 g=1

Vk = max{Ik , Jk }.

Suppose that Vk ∈ (τr(k)−1 , τr(k) ] for some function r(·) of k. Let the range of
function r(·) consist of values s1 < s2 < . . . < sP , and define the sets
Su = {k : τsu −1 < Vk ≤ τsu }, u = 1, 2, . . . , P .
u ← 1.
while u ≤ P do
After all the coflows in setP
Su are released, schedule them as a single coflow
(k)
with transfer requirement k∈Su dij from input i to output j and finish
processing the coflow using Algorithm 5.
u ← u + 1;
end

The Birkhoff-von Neumann decomposition that produces an optimal schedule
for a coflow is described in detail in Algorithm 5.
Algorithm 5: Birkhoff-von Neumann Decomposition
m
Data: A single coflow D = (dij )i,j=1 .
Result: A scheduling algorithm that uses at most a polynomial number
of different matchings.
 m
, where d˜ij ≥ dij for all i and
– Step 1: Augment D to a matrix D̃ = d˜ij
i,j=1

j, and all row
sums
equal to oo
ρ(D).
n and column
nP
o of D̃ are
nP
m
m
0
0
Let η = min mini
, minj
be the minimum of
j 0 =1 dij
i0 =1 di j
row sums and column sums, and let ρ(D) be the load of coflow matrix D.
D̃ ← D.
while (η < ρ) do
Pm
Pm
i∗ ← arg mini j 0 =1 D̃ij 0 ; j ∗ ← arg minj i0 =1 D̃i0 j .
D̃ ← D̃ + pE,
Pm
where p = min{ρ − j 0 =1 D̃i∗ j 0 , ρ − i0 =1 D̃i0 j ∗ }, Eij = 1 if i = i∗ and
j = j ∗ , and
n Eij n=P0 otherwise.
o
nP
oo
m
m
0
0j
η ← min mini
D̃
,
min
D̃
0
0
ij
j
i
j =1
i =1
Pm

end
– Step 2: Decompose D̃ into permutation matrices Π.
while (D̃ 6= 0) do
(i) Define an m × m binary matrix G where Gij = 1 if D̃ij > 0, and
Gij = 0 otherwise, for i, j = 1, . . . , m.
(ii) Interpret G as a bipartite graph, where an (undirected) edge (i, j) is
present if and only if Gij = 1. Find a perfect matching M on G and
define an m × m binary matrix Π for the matching by Πij = 1 if
(i, j) ∈ M , and Πij = 0 otherwise, for i, j = 1, . . . , m.
(iii) D̃ ← D̃ − qΠ, where q = min{D̃ij : Πij > 0}. Process coflow D using
the matching M for q time slots. More specifically, process dataflow
from input i to output j for q time slots, if (i, j) ∈ M and there is
processing requirement remaining, for i, j = 1, . . . , m.
end

B

Tables

We present the total weighted completion time ratios with respect to the
base cases for general instances in Tables 1 to 11.

Table 1: General instances with zero release time, (a) without backfill and without grouping
Instance No. of flows in each coflow FIFO
1
m
2.33
2
m
2.49
3
m
2.43
4
m
2.41
5
m
2.47
6
m2
1.28
7
m2
1.26
8
m2
1.29
9
m2
1.27
10
m2
1.27
11
Unif[m, m2 ]
1.91
12
Unif[m, m2 ]
1.93
13
Unif[m, m2 ]
2.04
14
Unif[m, m2 ]
1.98
15
Unif[m, m2 ]
1.88
16
Unif[m, m2 ]
2.05
17
Unif[m, m2 ]
1.97
18
Unif[m, m2 ]
2.03
19
Unif[m, m2 ]
2.04
20
Unif[m, m2 ]
2.12
21
Unif[m, m2 ]
1.94
22
Unif[m, m2 ]
2.08
23
Unif[m, m2 ]
1.98
24
Unif[m, m2 ]
2.14
25
Unif[m, m2 ]
2.02
26
Unif[m, m2 ]
2.17
27
Unif[m, m2 ]
1.86
28
Unif[m, m2 ]
1.90
29
Unif[m, m2 ]
2.22
30
Unif[m, m2 ]
1.97

STPT
2.22
2.39
2.29
2.23
2.24
1.25
1.25
1.26
1.27
1.26
1.61
1.64
1.62
1.56
1.58
1.57
1.58
1.65
1.57
1.66
1.66
1.64
1.60
1.69
1.65
1.68
1.59
1.61
1.72
1.59

SMPT
2.06
2.18
2.15
2.11
2.09
1.24
1.23
1.24
1.24
1.23
1.60
1.63
1.61
1.55
1.56
1.56
1.57
1.64
1.56
1.65
1.64
1.63
1.59
1.67
1.64
1.67
1.58
1.59
1.71
1.58

SMCT
2.12
2.29
2.24
2.21
2.19
1.25
1.24
1.24
1.25
1.24
1.60
1.63
1.62
1.56
1.57
1.57
1.58
1.65
1.57
1.66
1.64
1.63
1.60
1.68
1.64
1.68
1.58
1.60
1.71
1.58

ECT LP-based
2.15
2.26
2.38
2.40
2.29
2.36
2.22
2.28
2.19
2.21
1.26
1.26
1.26
1.26
1.26
1.26
1.27
1.27
1.26
1.26
1.61
1.61
1.65
1.66
1.63
1.63
1.57
1.57
1.59
1.59
1.58
1.58
1.59
1.59
1.66
1.66
1.58
1.58
1.68
1.67
1.66
1.67
1.65
1.65
1.61
1.61
1.70
1.69
1.66
1.67
1.70
1.70
1.61
1.61
1.62
1.62
1.74
1.73
1.60
1.60

Table 2: General instances with zero release time, (b) with backfill and without
grouping
Instance No. of flows in each coflow FIFO
1
m
1.37
2
m
1.58
3
m
1.50
4
m
1.56
5
m
1.59
6
m2
1.04
7
m2
1.05
8
m2
1.04
9
m2
1.03
10
m2
1.03
11
Unif[m, m2 ]
1.35
12
Unif[m, m2 ]
1.35
13
Unif[m, m2 ]
1.45
14
Unif[m, m2 ]
1.42
15
Unif[m, m2 ]
1.33
16
Unif[m, m2 ]
1.48
17
Unif[m, m2 ]
1.42
18
Unif[m, m2 ]
1.42
19
Unif[m, m2 ]
1.47
20
Unif[m, m2 ]
1.45
21
Unif[m, m2 ]
1.33
22
Unif[m, m2 ]
1.47
23
Unif[m, m2 ]
1.43
24
Unif[m, m2 ]
1.47
25
Unif[m, m2 ]
1.44
26
Unif[m, m2 ]
1.51
27
Unif[m, m2 ]
1.30
28
Unif[m, m2 ]
1.46
29
Unif[m, m2 ]
1.29
30
Unif[m, m2 ]
1.46

STPT
1.36
1.40
1.36
1.41
1.44
1.01
1.03
1.02
1.02
1.03
1.06
1.05
1.05
1.05
1.05
1.05
1.04
1.06
1.04
1.06
1.06
1.06
1.05
1.06
1.05
1.07
1.05
1.08
1.06
1.05

SMPT
1.35
1.50
1.41
1.37
1.37
1.02
1.03
1.02
1.02
1.03
1.06
1.06
1.06
1.05
1.05
1.06
1.05
1.06
1.05
1.07
1.08
1.06
1.07
1.07
1.08
1.08
1.07
1.38
1.24
1.37

SMCT
1.43
1.53
1.44
1.35
1.43
1.02
1.02
1.02
1.02
1.03
1.05
1.06
1.06
1.06
1.06
1.06
1.05
1.08
1.05
1.05
1.07
1.06
1.06
1.07
1.06
1.09
1.06
1.38
1.24
1.38

ECT LP-based
1.33
1.36
1.52
1.41
1.41
1.45
1.33
1.48
1.38
1.48
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.06
1.05
1.05
1.06
1.06
1.04
1.05
1.05
1.05
1.05
1.06
1.05
1.04
1.05
1.06
1.07
1.05
1.04
1.06
1.06
1.05
1.06
1.07
1.06
1.05
1.05
1.05
1.06
1.06
1.06
1.08
1.08
1.05
1.05
1.45
1.07
1.28
1.05
1.45
1.05

Table 3: General instances with zero release time, (c) with balanced backfill and
without grouping
Instance No. of flows in each coflow FIFO
1
m
1.04
2
m
1.09
3
m
1.08
4
m
1.11
5
m
1.10
6
m2
1.03
7
m2
1.05
8
m2
1.04
9
m2
1.02
10
m2
1.03
11
Unif[m, m2 ]
1.31
12
Unif[m, m2 ]
1.29
13
Unif[m, m2 ]
1.42
14
Unif[m, m2 ]
1.39
15
Unif[m, m2 ]
1.30
16
Unif[m, m2 ]
1.44
17
Unif[m, m2 ]
1.40
18
Unif[m, m2 ]
1.37
19
Unif[m, m2 ]
1.42
20
Unif[m, m2 ]
1.41
21
Unif[m, m2 ]
1.28
22
Unif[m, m2 ]
1.42
23
Unif[m, m2 ]
1.38
24
Unif[m, m2 ]
1.42
25
Unif[m, m2 ]
1.40
26
Unif[m, m2 ]
1.44
27
Unif[m, m2 ]
1.26
28
Unif[m, m2 ]
1.30
29
Unif[m, m2 ]
1.48
30
Unif[m, m2 ]
1.41

STPT
1.00
1.04
1.00
1.01
1.03
1.01
1.02
1.01
1.01
1.03
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.01
1.00
1.01
1.01
1.00
1.00
1.01
1.02
1.03
1.01
1.01

SMPT
1.03
1.03
1.02
1.04
0.97
1.01
1.03
1.02
1.02
1.03
1.01
1.03
1.02
1.02
1.03
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.03
1.03
1.02
1.01

SMCT
0.98
1.03
1.03
0.98
1.00
1.02
1.02
1.01
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.01
1.01
1.02
1.01
1.02
1.02
1.01
1.02
1.02
1.02
1.02
1.02
1.02
1.02
1.01

ECT LP-based
0.89
1.00
0.89
1.00
0.92
1.00
0.91
1.00
0.89
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.99
1.00
0.99
1.00
1.00
1.00
1.00
1.00
0.99
1.00
0.99
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.99
1.00
0.99
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.99
1.00
1.00
1.00

Table 4: General instances with zero release time, (d) with backfill and with
grouping
Instance No. of flows in each coflow FIFO
1
m
1.25
2
m
1.26
3
m
1.18
4
m
1.31
5
m
1.30
6
m2
1.37
7
m2
1.37
8
m2
1.39
9
m2
1.39
10
m2
1.36
11
Unif[m, m2 ]
1.73
12
Unif[m, m2 ]
1.75
13
Unif[m, m2 ]
1.86
14
Unif[m, m2 ]
1.87
15
Unif[m, m2 ]
1.68
16
Unif[m, m2 ]
1.88
17
Unif[m, m2 ]
1.82
18
Unif[m, m2 ]
1.88
19
Unif[m, m2 ]
1.87
20
Unif[m, m2 ]
1.92
21
Unif[m, m2 ]
1.81
22
Unif[m, m2 ]
1.91
23
Unif[m, m2 ]
1.80
24
Unif[m, m2 ]
1.89
25
Unif[m, m2 ]
1.82
26
Unif[m, m2 ]
2.00
27
Unif[m, m2 ]
1.69
28
Unif[m, m2 ]
1.71
29
Unif[m, m2 ]
2.08
30
Unif[m, m2 ]
1.79

STPT
1.21
1.14
1.10
1.19
1.18
1.36
1.35
1.36
1.37
1.37
1.41
1.44
1.40
1.39
1.43
1.36
1.37
1.41
1.41
1.42
1.43
1.41
1.42
1.40
1.42
1.50
1.42
1.44
1.49
1.44

SMPT
1.21
1.22
1.18
1.33
1.13
1.38
1.37
1.35
1.36
1.38
1.39
1.43
1.41
1.41
1.43
1.39
1.38
1.43
1.41
1.44
1.45
1.43
1.42
1.44
1.43
1.49
1.44
1.43
1.46
1.42

SMCT
1.19
1.20
1.20
1.20
1.19
1.38
1.35
1.37
1.36
1.36
1.41
1.43
1.43
1.40
1.41
1.40
1.41
1.42
1.41
1.42
1.47
1.39
1.39
1.44
1.42
1.48
1.41
1.44
1.48
1.43

ECT LP-based
1.11
1.08
1.14
1.04
1.14
1.14
1.11
1.07
1.08
1.05
1.34
1.36
1.35
1.34
1.35
1.33
1.35
1.35
1.34
1.35
1.37
1.38
1.42
1.45
1.38
1.34
1.40
1.37
1.35
1.37
1.38
1.38
1.37
1.37
1.39
1.42
1.40
1.41
1.41
1.39
1.40
1.40
1.41
1.42
1.39
1.37
1.38
1.40
1.41
1.42
1.46
1.44
1.39
1.42
1.38
1.39
1.46
1.43
1.38
1.41

Table 5: General instances with zero release time, (e) with balanced backfill and
with grouping
Instance No. of flows in each coflow FIFO
1
m
1.18
2
m
1.19
3
m
1.13
4
m
1.23
5
m
1.23
6
m2
1.36
7
m2
1.35
8
m2
1.38
9
m2
1.37
10
m2
1.35
11
Unif[m, m2 ]
1.69
12
Unif[m, m2 ]
1.70
13
Unif[m, m2 ]
1.83
14
Unif[m, m2 ]
1.83
15
Unif[m, m2 ]
1.65
16
Unif[m, m2 ]
1.86
17
Unif[m, m2 ]
1.77
18
Unif[m, m2 ]
1.84
19
Unif[m, m2 ]
1.85
20
Unif[m, m2 ]
1.87
21
Unif[m, m2 ]
1.77
22
Unif[m, m2 ]
1.88
23
Unif[m, m2 ]
1.78
24
Unif[m, m2 ]
1.85
25
Unif[m, m2 ]
1.79
26
Unif[m, m2 ]
1.98
27
Unif[m, m2 ]
1.67
28
Unif[m, m2 ]
1.69
29
Unif[m, m2 ]
2.04
30
Unif[m, m2 ]
1.78

STPT
1.14
1.09
1.05
1.14
1.12
1.35
1.34
1.36
1.35
1.36
1.36
1.38
1.34
1.35
1.35
1.32
1.34
1.36
1.36
1.38
1.38
1.36
1.37
1.35
1.39
1.44
1.37
1.40
1.43
1.38

SMPT
1.15
1.16
1.12
1.21
1.08
1.35
1.36
1.35
1.35
1.36
1.35
1.39
1.36
1.37
1.37
1.35
1.35
1.38
1.35
1.42
1.40
1.37
1.37
1.38
1.39
1.44
1.38
1.39
1.41
1.37

SMCT
1.13
1.15
1.16
1.15
1.13
1.35
1.35
1.36
1.35
1.36
1.37
1.39
1.37
1.36
1.37
1.34
1.36
1.36
1.36
1.40
1.41
1.35
1.36
1.39
1.40
1.45
1.36
1.39
1.43
1.38

ECT LP-based
1.07
1.04
1.10
1.00
1.10
1.09
1.07
1.05
1.05
1.01
1.33
1.34
1.33
1.32
1.34
1.33
1.33
1.33
1.33
1.34
1.35
1.34
1.37
1.36
1.35
1.32
1.36
1.34
1.33
1.33
1.33
1.33
1.33
1.33
1.35
1.37
1.35
1.36
1.39
1.36
1.36
1.36
1.36
1.37
1.35
1.34
1.35
1.37
1.38
1.37
1.43
1.40
1.37
1.35
1.37
1.35
1.41
1.39
1.34
1.36

Table 6: General instances with general release times, (b) with backfill and without grouping
Instance No. of flows in each coflow FIFO
1
m
1.33
2
m
1.32
3
m
1.37
4
m
1.28
5
m
1.31
6
m2
1.04
7
m2
1.03
8
m2
1.03
9
m2
1.02
10
m2
1.03
11
Unif[m, m2 ]
1.44
12
Unif[m, m2 ]
1.45
13
Unif[m, m2 ]
1.37
14
Unif[m, m2 ]
1.43
15
Unif[m, m2 ]
1.38
16
Unif[m, m2 ]
1.42
17
Unif[m, m2 ]
1.37
18
Unif[m, m2 ]
1.33
19
Unif[m, m2 ]
1.25
20
Unif[m, m2 ]
1.43
21
Unif[m, m2 ]
1.38
22
Unif[m, m2 ]
1.40
23
Unif[m, m2 ]
1.35
24
Unif[m, m2 ]
1.36
25
Unif[m, m2 ]
1.45
26
Unif[m, m2 ]
1.45
27
Unif[m, m2 ]
1.38
28
Unif[m, m2 ]
1.39
29
Unif[m, m2 ]
1.42
30
Unif[m, m2 ]
1.38

STPT
1.28
1.34
1.38
1.27
1.26
1.03
1.02
1.02
1.02
1.03
1.07
1.08
1.06
1.07
1.07
1.05
1.07
1.05
1.04
1.06
1.04
1.06
1.05
1.04
1.06
1.06
1.08
1.07
1.07
1.05

SMPT
1.32
1.33
1.37
1.24
1.34
1.04
1.03
1.03
1.02
1.03
1.36
1.38
1.29
1.38
1.31
1.35
1.29
1.25
1.21
1.36
1.30
1.30
1.30
1.28
1.36
1.35
1.29
1.31
1.38
1.32

SMCT
1.32
1.32
1.36
1.31
1.32
1.04
1.03
1.03
1.02
1.03
1.36
1.36
1.29
1.37
1.32
1.35
1.29
1.26
1.21
1.36
1.30
1.31
1.29
1.28
1.37
1.37
1.30
1.31
1.37
1.31

ECT LP-based
1.33
1.30
1.32
1.33
1.37
1.34
1.30
1.29
1.37
1.33
1.03
1.01
1.03
1.01
1.03
1.01
1.02
1.01
1.03
1.01
1.44
1.06
1.44
1.05
1.32
1.04
1.43
1.07
1.37
1.05
1.41
1.05
1.36
1.04
1.31
1.04
1.24
1.03
1.44
1.06
1.38
1.04
1.38
1.05
1.34
1.05
1.35
1.04
1.40
1.06
1.42
1.04
1.36
1.06
1.38
1.05
1.42
1.05
1.37
1.05

Table 7: General instances with general release times, (c) with balanced backfill
and without grouping
Instance No. of flows in each coflow FIFO
1
m
1.03
2
m
1.03
3
m
1.09
4
m
1.03
5
m
1.02
6
m2
1.34
7
m2
1.33
8
m2
1.32
9
m2
1.32
10
m2
1.31
11
Unif[m, m2 ]
1.75
12
Unif[m, m2 ]
1.73
13
Unif[m, m2 ]
1.70
14
Unif[m, m2 ]
1.79
15
Unif[m, m2 ]
1.68
16
Unif[m, m2 ]
1.75
17
Unif[m, m2 ]
1.67
18
Unif[m, m2 ]
1.63
19
Unif[m, m2 ]
1.53
20
Unif[m, m2 ]
1.75
21
Unif[m, m2 ]
1.73
22
Unif[m, m2 ]
1.68
23
Unif[m, m2 ]
1.66
24
Unif[m, m2 ]
1.64
25
Unif[m, m2 ]
1.75
26
Unif[m, m2 ]
1.73
27
Unif[m, m2 ]
1.71
28
Unif[m, m2 ]
1.69
29
Unif[m, m2 ]
1.77
30
Unif[m, m2 ]
1.68

STPT
1.10
1.07
1.08
1.02
1.07
1.34
1.31
1.33
1.31
1.33
1.34
1.36
1.36
1.33
1.36
1.40
1.35
1.34
1.35
1.38
1.33
1.34
1.35
1.34
1.36
1.38
1.36
1.36
1.35
1.35

SMPT
1.07
1.07
1.09
1.05
1.09
1.34
1.33
1.32
1.32
1.31
1.68
1.68
1.61
1.69
1.60
1.65
1.58
1.58
1.50
1.65
1.61
1.62
1.61
1.58
1.64
1.66
1.60
1.59
1.70
1.62

SMCT
1.06
1.04
1.09
1.01
1.05
1.34
1.32
1.32
1.32
1.32
1.68
1.67
1.60
1.69
1.60
1.69
1.58
1.59
1.49
1.65
1.59
1.61
1.61
1.58
1.65
1.65
1.59
1.60
1.71
1.60

ECT LP-based
1.03
1.03
1.03
1.06
1.09
1.07
1.03
0.99
1.06
1.05
1.33
1.32
1.32
1.33
1.32
1.32
1.32
1.32
1.31
1.32
1.76
1.31
1.76
1.36
1.59
1.31
1.74
1.33
1.67
1.33
1.73
1.36
1.66
1.35
1.64
1.34
1.53
1.33
1.74
1.35
1.66
1.30
1.68
1.34
1.66
1.36
1.64
1.29
1.66
1.33
1.70
1.32
1.66
1.34
1.69
1.35
1.75
1.33
1.68
1.33

Table 8: General instances with general release times, (d) with backfill and with
grouping
Instance No. of flows in each coflow FIFO
1
m
1.03
2
m
1.03
3
m
1.09
4
m
1.03
5
m
1.02
6
m2
1.34
7
m2
1.33
8
m2
1.32
9
m2
1.32
10
m2
1.31
11
Unif[m, m2 ]
1.75
12
Unif[m, m2 ]
1.73
13
Unif[m, m2 ]
1.70
14
Unif[m, m2 ]
1.79
15
Unif[m, m2 ]
1.68
16
Unif[m, m2 ]
1.75
17
Unif[m, m2 ]
1.67
18
Unif[m, m2 ]
1.63
19
Unif[m, m2 ]
1.53
20
Unif[m, m2 ]
1.75
21
Unif[m, m2 ]
1.73
22
Unif[m, m2 ]
1.68
23
Unif[m, m2 ]
1.66
24
Unif[m, m2 ]
1.64
25
Unif[m, m2 ]
1.75
26
Unif[m, m2 ]
1.73
27
Unif[m, m2 ]
1.71
28
Unif[m, m2 ]
1.69
29
Unif[m, m2 ]
1.77
30
Unif[m, m2 ]
1.68

STPT
1.10
1.07
1.08
1.02
1.07
1.34
1.31
1.33
1.31
1.33
1.34
1.36
1.36
1.33
1.36
1.40
1.35
1.34
1.35
1.38
1.33
1.34
1.35
1.34
1.36
1.38
1.36
1.36
1.35
1.35

SMPT
1.07
1.07
1.09
1.05
1.09
1.34
1.33
1.32
1.32
1.31
1.68
1.68
1.61
1.69
1.60
1.65
1.58
1.58
1.50
1.65
1.61
1.62
1.61
1.58
1.64
1.66
1.60
1.59
1.70
1.62

SMCT
1.06
1.04
1.09
1.01
1.05
1.34
1.32
1.32
1.32
1.32
1.68
1.67
1.60
1.69
1.60
1.69
1.58
1.59
1.49
1.65
1.59
1.61
1.61
1.58
1.65
1.65
1.59
1.60
1.71
1.60

ECT LP-based
1.03
1.03
1.03
1.06
1.09
1.07
1.03
0.99
1.06
1.05
1.33
1.32
1.32
1.33
1.32
1.32
1.32
1.32
1.31
1.32
1.76
1.31
1.76
1.36
1.59
1.31
1.74
1.33
1.67
1.33
1.73
1.36
1.66
1.35
1.64
1.34
1.53
1.33
1.74
1.35
1.66
1.30
1.68
1.34
1.66
1.36
1.64
1.29
1.66
1.33
1.70
1.32
1.66
1.34
1.69
1.35
1.75
1.33
1.68
1.33

Table 9: General instances with general release times, (e) with balanced backfill
and with grouping
Instance No. of flows in each coflow FIFO
1
m
0.97
2
m
0.95
3
m
1.02
4
m
0.92
5
m
0.97
6
m2
1.34
7
m2
1.33
8
m2
1.32
9
m2
1.31
10
m2
1.31
11
Unif[m, m2 ]
1.72
12
Unif[m, m2 ]
1.74
13
Unif[m, m2 ]
1.64
14
Unif[m, m2 ]
1.76
15
Unif[m, m2 ]
1.68
16
Unif[m, m2 ]
1.74
17
Unif[m, m2 ]
1.65
18
Unif[m, m2 ]
1.63
19
Unif[m, m2 ]
1.52
20
Unif[m, m2 ]
1.74
21
Unif[m, m2 ]
1.72
22
Unif[m, m2 ]
1.66
23
Unif[m, m2 ]
1.67
24
Unif[m, m2 ]
1.63
25
Unif[m, m2 ]
1.73
26
Unif[m, m2 ]
1.71
27
Unif[m, m2 ]
1.68
28
Unif[m, m2 ]
1.66
29
Unif[m, m2 ]
1.78
30
Unif[m, m2 ]
1.68

STPT
0.98
0.96
1.02
0.91
0.98
1.33
1.31
1.32
1.30
1.32
1.32
1.35
1.35
1.32
1.34
1.37
1.32
1.31
1.35
1.34
1.31
1.31
1.33
1.32
1.35
1.34
1.32
1.33
1.34
1.34

SMPT
0.96
0.97
1.02
0.91
0.98
1.34
1.33
1.31
1.31
1.32
1.66
1.66
1.60
1.67
1.60
1.64
1.58
1.53
1.49
1.65
1.60
1.60
1.61
1.57
1.63
1.65
1.58
1.55
1.70
1.61

SMCT
0.96
0.96
1.02
0.91
0.97
1.34
1.32
1.32
1.31
1.32
1.66
1.64
1.60
1.67
1.60
1.67
1.58
1.53
1.49
1.65
1.59
1.60
1.60
1.57
1.63
1.64
1.58
1.56
1.69
1.60

ECT LP-based
0.97
0.95
0.95
0.98
1.02
0.97
0.92
0.91
0.98
0.96
1.33
1.31
1.32
1.33
1.32
1.32
1.31
1.31
1.31
1.31
1.74
1.29
1.74
1.32
1.58
1.32
1.72
1.30
1.67
1.31
1.72
1.31
1.65
1.32
1.64
1.32
1.52
1.31
1.74
1.30
1.65
1.29
1.66
1.30
1.67
1.32
1.60
1.28
1.64
1.31
1.69
1.31
1.65
1.31
1.64
1.33
1.75
1.30
1.67
1.31

Table 10: Offline algorithm on general instances with release times, (c) with
balanced backfill and without grouping
Instance No. of flows in each coflow FIFO
1
m
0.99
2
m
0.99
3
m
1.01
4
m
0.97
5
m
0.98
6
m2
1.02
7
m2
1.02
8
m2
1.04
9
m2
1.02
10
m2
1.04
11
Unif[m, m2 ]
1.40
12
Unif[m, m2 ]
1.32
13
Unif[m, m2 ]
1.39
14
Unif[m, m2 ]
1.35
15
Unif[m, m2 ]
1.40
16
Unif[m, m2 ]
1.27
17
Unif[m, m2 ]
1.42
18
Unif[m, m2 ]
1.33
19
Unif[m, m2 ]
1.42
20
Unif[m, m2 ]
1.40
21
Unif[m, m2 ]
1.35
22
Unif[m, m2 ]
1.30
23
Unif[m, m2 ]
1.35
24
Unif[m, m2 ]
1.34
25
Unif[m, m2 ]
1.30
26
Unif[m, m2 ]
1.30
27
Unif[m, m2 ]
1.28
28
Unif[m, m2 ]
1.35
29
Unif[m, m2 ]
1.32
30
Unif[m, m2 ]
1.28

STPT
0.98
0.99
0.99
0.97
0.97
1.02
1.02
1.02
1.02
1.03
1.01
1.01
1.01
1.02
1.02
1.01
1.01
1.01
1.02
1.02
1.01
1.03
1.02
1.02
1.01
1.02
1.01
1.01
1.02
1.01

SMPT
0.98
0.99
1.00
0.97
0.97
1.02
1.02
1.03
1.02
1.04
1.33
1.25
1.31
1.29
1.33
1.20
1.33
1.27
1.34
1.34
1.27
1.25
1.29
1.28
1.24
1.24
1.22
1.27
1.25
1.23

SMCT
0.98
0.99
0.99
0.98
0.98
1.02
1.02
1.03
1.02
1.04
1.33
1.25
1.31
1.29
1.33
1.20
1.33
1.27
1.34
1.34
1.27
1.25
1.28
1.28
1.24
1.24
1.22
1.27
1.25
1.23

ECT LP-based
1.00
1.00
0.99
1.00
1.01
1.00
0.97
1.00
0.98
1.00
1.02
1.00
1.02
1.00
1.03
1.00
1.03
1.00
1.04
1.00
1.39
1.00
1.31
1.00
1.38
1.00
1.34
1.00
1.40
1.00
1.26
1.00
1.40
1.00
1.33
1.00
1.41
1.00
1.40
1.00
1.34
1.00
1.30
1.00
1.35
1.00
1.33
1.00
1.29
1.00
1.29
1.00
1.27
1.00
1.34
1.00
1.31
1.00
1.28
1.00

Table 11: Online algorithm on general instances with release times, (c) with
balanced backfill and without grouping
Instance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

No. of flows
m
m
m
m
m
m2
m2
m2
m2
m2
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]
Unif[m, m2 ]

FIFO
0.99
0.99
1.01
0.97
0.98
1.02
1.02
1.04
1.02
1.04
1.40
1.32
1.39
1.35
1.40
1.27
1.42
1.33
1.42
1.40
1.35
1.30
1.35
1.34
1.30
1.30
1.28
1.35
1.32
1.28

STPT
0.95
0.98
0.98
0.96
0.95
1.00
1.01
1.01
1.01
1.01
1.00
1.00
0.99
1.00
1.00
1.00
1.00
1.00
1.01
0.99
0.99
1.00
1.00
1.00
1.00
1.01
1.00
1.01
1.01
1.00

SMPT
0.94
0.97
0.96
0.95
0.94
1.01
1.02
1.02
1.01
1.03
1.00
1.01
1.01
1.01
1.01
1.01
1.00
1.01
1.02
1.01
1.00
1.02
1.01
1.01
1.00
1.02
1.01
1.01
1.01
1.02

SMCT
0.97
0.97
0.97
0.96
0.94
1.01
1.02
1.01
1.01
1.02
1.00
1.01
1.00
1.00
1.00
1.02
1.00
1.01
1.01
1.00
1.01
1.02
1.01
1.01
1.00
1.02
1.01
1.01
1.01
1.01

ECT LP-based Lower bound
0.93
0.96
0.88
0.94
0.96
0.89
0.93
0.97
0.88
0.92
0.94
0.88
0.91
0.93
0.87
0.99
0.99
0.94
1.00
1.00
0.94
1.00
1.00
0.94
0.99
0.99
0.94
1.00
1.00
0.96
0.99
0.99
0.92
0.99
1.00
0.91
0.98
0.99
0.90
0.99
0.99
0.92
0.99
1.00
0.94
1.00
1.00
0.95
0.99
1.00
0.91
0.99
0.99
0.93
1.00
1.00
0.91
0.99
0.99
0.92
0.99
0.99
0.91
1.00
1.00
0.93
0.99
0.99
0.94
0.99
0.99
0.93
0.99
0.99
0.91
0.99
1.00
0.94
0.99
0.99
0.93
0.99
0.99
0.94
0.99
1.00
0.93
0.99
0.99
0.93

