Asymptotically Optimal Approximation Algorithms for
Coflow Scheduling

arXiv:1606.06183v5 [cs.DC] 9 Mar 2018

Hamidreza Jahanjou∗

Erez Kantor∗

ABSTRACT
Many modern datacenter applications involve large-scale computations composed of multiple data flows that need to be
completed over a shared set of distributed resources. Such
a computation completes when all of its flows complete. A
useful abstraction for modeling such scenarios is a coflow,
which is a collection of flows (e.g., tasks, packets, data transmissions) that all share the same performance goal.
In this paper, we present the first approximation algorithms for scheduling coflows over general network topologies with the objective of minimizing total weighted completion time. We consider two different models for coflows
based on the nature of individual flows: circuits, and packets. We design constant-factor polynomial-time approximation algorithms for scheduling packet-based coflows with
or without given flow paths, and circuit-based coflows with
given flow paths. Furthermore, we give an O(log n/ log log n)approximation polynomial time algorithm for scheduling circuitbased coflows where flow paths are not given (here n is the
number of network edges).
We obtain our results by developing a general framework
for coflow schedules, based on interval-indexed linear programs, which may extend to other coflow models and objective functions and may also yield improved approximation
bounds for specific network scenarios. We also present an
experimental evaluation of our approach for circuit-based
coflows that show a performance improvement of at least
%22 on average over competing heuristics.

1.

INTRODUCTION

In modern datacenter network applications, a large-scale
computation over a big data set is often composed of multiple tasks or multiple data flows that need to be completed
∗

All authors are with the College of Computer and Information Science, Northeastern University, Boston, MA
02115, USA. Email: {hamid, erezk, rraj}@ccs.neu.edu. Supported in part by NSF grants Grant CSR-1217981 and CCF1422715, and a Google Research Award.

over a shared set of distributed resources. Such a computation completes when all the data flows in the computation
complete. A useful abstraction for modeling such scenarios is
that of a coflow [6], which is a collection of flows (e.g., tasks,
packets, data transmissions) that all share the same performance goal. Coflows arise frequently in distributed computing and datacenters [3, 6, 7, 14, 24, 30, 31]. A prominent
example is parallel data processing; in certain MapReduce
computations, the reduce phase at a particular reducer can
begin only after all the relevant data from the map phase
has arrived at the reducer [11]. Similar examples occur in
Dryad [15], and Spark [29].
In this paper, we study the problem of designing coflow
schedules that minimize total weighted completion time. We
consider two different models for coflows based on the nature
of individual flows: circuits and packets.
• Circuit-based coflows a flow is a connection request
(data transmission) from source to sink on a network.
• Packet-based coflows a flow is a packet that needs
to be routed from source to sink on a network.
Before going into formal definitions, Figure 1 illustrates
a circuit-based coflow scheduling scenario. Three coflows
A, B, and C require bandwidth assignment and scheduling
on a triangle network with unit edge capacities. Coflow A
consists of two flows A1 of size 2 and A2 of size 1 whereas the
other two have one flow each of size 1. Three solutions are
proposed. In (s1), each flow is given a bandwidth of 1/2; all
flows are scheduled to run in parallel. The total completion
time is 4 + 2 + 4 = 10. In (s2), coflow A has the highest
priority followed by coflow B and C. The total completion
time is 2 + 2 + 4 = 8. But, it is possible to do even better
by observing that flow C can run at the same time as either
flow A2 or flow B; this gives rise to an optimal solution,
shown in (s3), with a total completion time of 4 + 2 + 1 = 7.
We now present the models and problem formulations, our
main results and techniques, and a review of related work.

1.1
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
c 2018 ACM. ISBN 978-1-4503-2138-9.
DOI: 10.1145/1235

Rajmohan Rajaraman∗

Models and Notation

Regardless of the model, the following notation is used.
The set of all flows is denoted by F = {f1 , ..., fn }. We
define a coflow Fi to be a subset {f1i , ..., fni i } of flows such
that the set of all coflows, denoted by F, provides a partition
of F . Each flow fi has a source si , a destination di , and,
depending on the model, a size σi . Additionally, each flow
has a release time ri at which point it becomes available.
Notice that in our formulation each flow has a release time

σ(C) = 2
y
b(C)
A1

1
1

x
σ(A1 ) = 2
B

C

1

σ(A2 ) = 1

z

1/2

b(C)

b(B)

1/2

b(B)

b(A2 )

1/2

b(A2 )

b(A1 )
A2

0

1

2

3

4

1/2
time

1

1

b(A2 )

b(A1 )
2

1

b(A1 )

1
1

1

b(B)

1
1
0

b(C)

3

4

time

0

1

2

3

4

1
time

σ(B) = 1
(N)

(s1)

(s2)

(s3)

Figure 1: Three possible bandwidth assignments for the set of coflows {A, B, C}. Coflow A has two flows (A1
of size 2 and A2 of size 1); the other two have each one flow of size 1. The objective is to minimize sum of
completion times. (N) The network is a triangle where each edge has unit capacity. Flows are drawn around
the edges along with their size. (s1) A bandwidth of 1/2 is assigned to each flow; total completion time is 10.
(s2) Priority is given to coflow A then to coflow B and then to coflow C; total completion time is 8. (s3) An
optimal solution; total completion time is 7.
whereas in previous works, release times are at the level of
coflows.
We also have a network modeled as a directed graph G =
(V, E) which, in the case of circuit-based coflows, also features edge capacities {c(e)}e∈E .
The completion time of a flow fi is denoted by ci . The
completion time Ck of a coflow Fk is defined to be the completion time of its last flow; that is,
Ck = max cf .
f ∈Fk

The goal is to minimize the weighted sum of coflow completion times
X
X
C=
ωk Ck =
ωk max cf .
(1)
k

k

f ∈Fk

Note that if there is only one coflow, the problem reduces
to makespan minimization. Similarly, if every coflow has
one flow, the problem reduces to minimizing total weighted
(flow) completion time. Therefore, in a sense, coflow scheduling bridges two well-studied minimization objectives. In particular, this means that hardness results for either of these
problems also hold for coflow scheduling. Below, we consider
the particulars of each model.

Circuits
In this model, a flow fi is a connection request (data transmission) from a source node si to a destination node di on
a network G = (V, E) with edge capacities {c(e)}e∈E . A
coflow is a set of connection requests. To each connection
request in F , we need to assign a path pi (if not given already) and a bandwidth bi such that C is minimized without violating edge capacities. In general, the bandwidth of
a connection request is an integrable function of time, bi (t),
and its completion time ci is defined as the smallest value
satisfying
Z ci
bi (t)dt = σi ,
0

where σi is the size of the connection request.
As we will see, one can assume, without loss of generality,
that the bandwidth functions are piece-wise constant. We

can further subdivide this problem into two cases: (a) paths
are given for each connection request and we only need to
assign bandwidths, (b) paths are not given; hence, each connection request requires routing and bandwidth assignment.

Packets
In this case, each flow fi is a packet residing (at its release
time ri ) on its source node si waiting to be routed to its
destination node di ∈ V − {si }. A coflow is a set of packets.
Each link e ∈ E can serve at most one packet at a time (i.e.
edge capacities are set to 1). A coflow Fk completes at time
Ck when all of its packets have reached their destination.
As before, the goal is to minimize C.
This model can be seen as a discrete version of circuitbased coflows. As in the previous model, we will consider
two subproblems: (a) a path is given for each packet; only
scheduling is needed (b) paths are not given; both routing
and scheduling are required for each packet.

1.2

Our Results and Techniques

We give asymptotically optimal approximation algorithms
for minimizing total weighted completion time under the
different models defined above.
• We present O(1)-approximation algorithms for circuitbased coflows with given paths, packet-based coflows
with given paths, and packet-based coflows where paths
are not given.
• We present an O(log n/ log log n)-approximation algorithm for circuit-based coflows where paths are not
given.
• We also present an experimental evaluation of our approach for circuit-based coflows which shows %22 or
more performance improvement on average over competing heuristics.
Note that, all of the above problems are at least NP-hard.
Table 1 summarizes our results.
A noteworthy contribution of our work is a common framework for developing coflow schedules, which applies to all the

Model
Packet-based
Circuit-based

Paths
given
not given
given
not given

Approx.
O(1)
O( logloglog|E|
)
|E|

Hardness
APX-hard
NP-hard
Ω( logloglog|E|
)
|E|

Table 1: Approximation ratio of our algorithms and
corresponding lower bounds for different models.

models we study. The framework consists of three parts.
First, we reformulate the coflow scheduling problem as an
instance of minimizing total weighted flow completion time
problem with precedence constraints in form of depth-1 intrees. Second, we devise an interval-index linear program
for each problem instance, and then reduce the problem of
finding flow schedules that minimize total weighted completion time (with aforementioned precedences) to multiple
instances of the problem of finding flow schedules that minimize makespan. Third, we perform rounding. The specifics
of each step varies across models. In particular, the last step
is achieved by a careful rounding of the associated linear
program solution. Though our approximation bounds are
optimal to within constant factors, we have not attempted
to optimize these constants. We believe that our framework
provides a general approach for solving coflow scheduling
problems under diverse models and objectives.
The algorithms given for circuit-based coflows provide the
first provable approximation bounds, and apply in the general setting of arbitrary capacitated networks, arbitrary sourcesink pairs, arbitrary demands, and arbitrary release times.
To the best of our knowledge, packet-based coflows have
not been studied earlier, though related models have been
analyzed, as we discuss in previous work.

1.3

Previous Work

Coflows
The notion of coflow was first proposed by Chowdhury and
Stoica as “a networking abstraction to express the communication requirements of prevalent data parallel programming
paradigms” [6, 7]. In [8], Chowdhury et al. present effective
heuristics for coflow scheduling without release times on a
non-blocking switch network. They also show that coflow
scheduling is NP-hard for P × P switches, P ≥ 2, via a
reduction from the concurrent open shop scheduling problem. Approximation algorithms for coflow scheduling on a
non-blocking switch with (coflow) release times are given
in [24, 16, 27, 1]. Zhao et al. consider coflow scheduling over general network topologies; thereby, routing the
flows becomes an additional requirement [31]. They provide heuristics based on the observation that simultaneous
routing and scheduling of coflows is required to obtain good
performance.

their survey, Leung et al., classify order scheduling problems
into three categories based on capabilities of the machines
[22]. Specifically, in the fully-dedicated case, each machine
can process only one type P
of component (task). This model,
sometimes denoted by G|| ωj Cj , is also known as the concurrent open shop scheduling since, in contrast to the latter,
components of a job can be processed at the same time [12].
In the fully-flexible case, all machines can process all types
of component (task). Lastly, in the arbitrary case, unrestricted subsets of machines can process arbitrary subsets of
components (tasks).
Machine scheduling problems are described [13] by three
values α|β|γ where α represents the machine environment, β
describes job constraints and γ specifies the objective function to be minimized.
The task-based coflow scheduling model, where a flow is
simply a task, corresponds to the fully-flexible case on (unrelated) parallel machines. For this model, Blocher and Chhajed observe that the problem is strongly NP-complete even
when all machines are identical [5]. Correra, Skutella and
Verschae give a 13.5 approximation algorithm for this problem on unrelated machines [10].

Circuit-based coflows
Circuit-based coflow scheduling
with fixed paths is a generP
alization of 1|rj , pmtn| ωj Cj which is strongly NP-hard
[19]. On the other hand, the version with variable paths is
related to congestion minimization. Chuzhoy et al. show
that congestion minimization on directed graphs is hard to
) unless NP has N O(log log N ) approximate within Ω( logloglog|E|
|E|
time randomized algorithms [9].

Packet-based coflows
The problem of scheduling packets on store-and-forward networks with given paths is equivalent to the job shop scheduling problem with unit processing times. Leighton, Maggs
and Rao [21] show that there exists a schedule achieving a
makespan of O(C + D) where C and D denote maximum
edge congestion and maximum path dilation respectively.
In [20], Leighton et al. give a polynomial-time algorithm
for finding such a schedule. Peis et al. [23] show that for
all  > 0 there is no (6/5 − )-approximation algorithm for
the packet scheduling problem with given paths (minimizing
makespan) unless P = NP.
An O(1)-approximation algoP
rithm for J|rij , pij = 1| S CS is given in [25]; the authors
consider a generalized minsum objective function.
On the other hand, when paths are not given, Srinvasan
and Teo give the first constant-ratio approximation algorithm for packet routing and scheduling to minimize makespan
[28]. Koch et al. [17] extend this result to messages which
consist of packets having the same source and sink.
The rest of this paper is organized as follows. We study
circuit-based coflows in §2 and packet-based coflows in §3.
We present experimental results in §4 and conclude in §5.

Machine scheduling and task-based coflows

2.

Although coflow scheduling is a relatively recent development, the related problem of scheduling jobs consisting of
tasks on parallel machines where a job completes when all
of its tasks complete, has been studied before. This model
is known in the literature as order scheduling; the goal is
to minimize the (weighted) sum of job completion times. In

We now consider our main model. In this setting, we
have a network G = (V, E) with edge capacities {c(e)}e∈E .
A coflow Fi has a weight ωi ∈ R≥0 and consists of a number
of connection requests (data transmissions) fji . Each connection request has a source sij ∈ V , a sink dij ∈ V , a release
time rji ∈ R≥0 and a size σji ∈ R≥0 . A solution must specify

CIRCUIT-BASED COFLOWS

a path pij from source to sink (if not given), and a bandwidth
function bij for each connection request fji . In general, the
bandwidth bij (t) is an integrable function of time such that
Z cij
bij (t)dt = σji ,
(2)
rji

where cij , the completion time of fji , is the smallest value for
which the equality holds. In addition, we require that edge
capacities are respected. Hence, any solution must satisfy
X i
∀e ∈ E :
bj (t) ≤ c(e)
(3)
fji ∈P (e)

for all t, where P (e) is the set of paths that use edge e.
There are two natural versions of this problem. In one
version, a path pij is given as a part of the input for each
connection request fji and we need to assign a bandwidth bij
to each request with the goal of minimizing total weighted
(coflow) completion time C without violating edge capacities. Note that any network topology in which there is a
unique path between pairs of vertices, e.g. trees or nonblocking switches, falls into this category. In another version, paths are not given; hence, assigning a (single) path to
each connection request becomes an additional requirement.
The rest of this section is organized as follows. First,
we present two key lemmas used in deriving our results.
Next, in §2.1, we give a 17.6-approximation algorithm for the
circuit-based coflow problem with given paths. Finally, in
)-approximation algorithm is presented
§2.2, an O( logloglog|E|
|E|
for the case where paths are not given.

Two lemmas
The following two lemmas are simple but crucial. The first
one (Lemma 1) states that, without loss of generality, we can
assume that bandwidth functions are piece-wise constant.
Lemma 1. Suppose that there exist a capacitated network
(G, c) and a set of feasible flows {f1 , ..., fn }, where each flow
fi is specified by a triple (pi , bi (t), ri ) consisting of its path,
bandwidth, and release time. Given two time points T1 < T2
such that ri ≤ T1 for all i ∈ [n], there exists a set of feasible
constant bandwidths {b0i }1≤i≤n delivering the same amount
as {bi (t)}1≤i≤n for every flow over the time interval [T1 , T2 ].
Proof. Let σi denote
R T the amount of flow delivered on
path pi ; that is, σi = T12 bi (t)dt. Define new bandwidths
b0i = σi /(T2 − T1 ). Clearly, the volume delivered remains
the same and release times are respected. Moreover, for
any edgeP
e, the sum of flow bandwidths passing through e
0
satisfies
i∈P (e) bi ≤ c(e), where P (e) is the set of paths
0
that use
P e. Indeed, assume that there exists an edge e for
which i∈P (e0 ) b0i > c(e0 ). Then, it follows that
X 0
X
bi =
σi /(T2 − T1 ) > c(e0 )
i∈P (e0 )

i∈P (e0 )

R T2
⇒

X
i∈P (e0 )

⇒

X Z
i∈P (e0 )

T1

bi (t)dt

T2 − T1
T2

> c(e0 )

bi (t)dt > (T2 − T1 )c(e0 )

T1

which is a contradiction since the total volume delivered can
not be more than (T2 − T1 )c(e0 ).

The second lemma (Lemma 2) shows that it is possible to
discretize the bandwidth usage among all flows over a given
path.
Lemma 2. Suppose that there exist a path p in a capacitated network (G, c) and a set of feasible flows {f1 , ..., fn }
over this path, where each flow fi has a bandwidth bi (t) and
a release time ri . Given two time points T1 < T2 such that
ri ≤ T1 for all i ∈ [n], there exists a set of feasible bandwidths {b00i }1≤i≤n such that at any point in time t ∈ [T1 , T2 ],
there is at most one active flow (i.e. with non-zero bandwidth). Furthermore, for every flow, the delivery amount
over the time interval [T1 , T2 ] is as before.
Proof. Let cm = mine∈p c(e) denote the minimum edge
capacity of the path. Also, let σi denote the volume corresponding
to bi delivered over the time interval; that is,
RT
σi = T12 bi (t)dt.
The idea is to assignPfull bandwidth to flows one at a time.
k
, for i ∈ [n]. Define the new
Set t0 = 0 and ti = ik=0 cσm
bandwidths as follows. For i ∈ [n],
(
cm , if t ∈ (T1 + ti−1 , T1 + ti ]
00
bi (t) =
0,
otherwise
It is obvious that b00i (t) is feasible and can be non-zero
only in the interval (T1 + ti−1 , T1 + ti ]. Furthermore, this
schedule does not require any additional time. Indeed,
R T2
n
n
X
X
b (t)dt
σk
T1 k
T1 + tn = T1 +
= T1 +
cm
cm
k=0
k=0
Z T2
Z T2 X
n
bk (t)
dt ≤ T1 +
= T1 +
dt = T2 ,
cm
T1
T1
k=0

where the inequality follows from the requirement that ∀t :
P
k bk (t) ≤ cm .

2.1

Paths Are Given

In this setting, each connection request comes with a path.
We give a 17.6-approximation algorithm for this problem.
We begin with an observation.
Observation 3. The circuit-based coflow scheduling with
given paths is strongly NP-complete.
This resultP
follows directly from the NP-completeness of
1|pmtn, ri | ωi ci which seeks to minimize total weighted
completion time on a single machine with preemption and
release times [19]. Indeed, given an instance of the schedult such that
ing problem, consider a single edge e : s
every job j with a processing time of pj corresponds to a
coflow consisting of just one flow of size σj = pj from s to
t and with the corresponding release time. Now, Lemma
2 states that we can turn a solution returned by solving
the circuit-based coflow problem into a preemptive schedule: simply determine the order of release and completion
times on the time line and apply the lemma to each interval.
We follow our general framework for coflow scheduling. In
order to get the best approximation ratio, we optimize over
some parameters such as interval length.
Reformulation. We transform the problem of minimizing total weighted coflow completion time to an instance of
minimizing total weighted flow completion time. To capture
completion times at the level of coflows, we (a) introduce a

dummy flow f0i in each coflow Fi , and (b) assign new weights
0
ωij
to each flow. In more detail, the dummy flow comes with
precedence constraints from fji , j 6= 0 to f0i , requiring that in
each coflow, f0i finishes last. In effect, the precedence graph
is a forest of n depth-1 in-trees. We set the weight to ωi for
0
the dummy flow f0i (i.e. ωi0
= ωi ) and to zero for all other
0
flows (i.e. ωij = 0, j 6= 0). Finally, note that dummy flows
do not have source, destination or size but are required to
finish no sooner than other flows in the same coflow.
P P Now,
0 i
the new objective function to be minimized is i j ωij
cj .
The linear program. In this step, we devise an intervalindexed linear program. The time line is divided into segments [0, 1], (1, 1 + ], (1 + , (1 + )2 ], ..., (τ` , τ`+1 ] for
` ∈ {0, 1, ..., L}, where τ` = (1 + )`−1 , τ0 = 0,  > 0 will be
determined later, and L is a sufficiently large integer.
In the linear program below, xij` is the portion of connection request fji completed in the `th interval (τ` , τ`+1 ] and
bij` is the bandwidth of pij (i.e. fji ’s path) during the `th
interval. Notice that release times are assumed to occur at
the start of intervals; we show that this restriction costs us
no more than a factor of 1 + . Constraints (6) ensure that
the dummy connection request finishes last in each coflow.
Constraints (7) calculate the bandwidth of each path pij for
every time interval (which is the fraction of flow size delivered, divided by interval length). Constraints (8) ensure
that no capacity violation occurs; note that P (e) denotes the
set of connection requests whose paths use edge e. Finally,
constraints (9) ensure that release times are respected.
XX 0 i
Minimize
ωij cj
subject to
i

X

j

xij` = 1

∀i, j

(4)

τ` xij` ≤ cij

∀i, j

(5)

∀i, j

(6)

∀i, j, `

(7)

∀`, e

(8)

∀i, `

(9)

`≤L

X
`≤L

cij ≤ ci0
X

bij`

σji xij` /τ`

=

bij`

≤ c(e)

fji ∈P (e)

Finally, for each interval (τ` , τ`+1 ], apply Lemma 1 to get
constant bandwidth for each connection request. More precisely, we set
R τ`+1 i
bj (t)dt
τ
i
bj` = `
τ`
for each fji . Clearly, constraints (7) are satisfied; furthermore, the lemma ensures that constraints (8) stay satisfied
as well. This setting of variables satisfies all the remaining
constraints as well.
Rounding. The next step after solving the linear program is to construct a schedule. Let {x̂ij` }ij` denote an optimal solution to the LP. Set b̂ij` according to equation (7).
For some 0 < α ≤ 1, define the α-interval hα
ij of a connecα
tion request fji to be the interval (τhα
,
τ
]
hij +1 which contains
ij
the earliest point in time that a cumulative α-fraction of the
connection request has been completed; that is
(
)
`
X
α
i
hij = min ` :
xjt ≥ α .
t=0

The exact value of α will be determined later.
In the schedule, each connection request fji will run entirely in (τhα
, τ hα
]–that is, the Dth interval after its
ij +D
ij +D+1
α-interval. The parameter D ∈ N, the displacement factor,
will be determined later. Note that the length of this interval is (1 + )D−1 times the cumulative length of intervals
from the beginning to the end of the α-interval.
Fix a k. Let S[k] denote the set of connection requests
scheduled to run in (τk , τk+1 ]. Clearly, the α-interval of all
these connection requests is k−D. Consider a connection request fji ∈ S[k]. According to the optimal solution obtained
by solving the LP, its bandwidth function is
 i
b̂j0 , if t ∈ [0, 1],




b̂ij1 , if t ∈ (τ1 , τ2 ],
b̂ij (t) =
..
 ...

.


 i
b̂jk , if t ∈ (τk−D , τk−D+1 ].
We now define a new constant bandwidth

rji > τ`+1 ⇒ xij` = 0
xij`

≥0

∀i, j, `, e

(10)

b̃ij =

`=k−D
X
`=0

1
times the optimal value of the above linear
Lemma 4. 1+
program is a lower bound on the weighted sum of completion
times for circuit-based coflows with paths and release times.

Proof. Consider a schedule hpij , bij (t)i achieving average
coflow completion time Ĉ. We show that it corresponds to
a feasible solution to the linear program with an objective
value ≤ (1 + )Ĉ. Start by setting the variables xij` for each
connection request fji according to the interval in which they
finish. Next, note that release times are arbitrary; hence, a
connection request may arrive in the middle of an interval.
On the other hand, constraints (7) require constant bandwidth in each interval. To remedy this, move all release
times to the end of the interval in which they occur and
update xij` if necessary; this clearly increases Ĉ by no more
than a factor of 1 + .

`=k−D
X
α−1 b̂ij`
α−1 b̂ij` τ`
=
.
τk
(1 + )k−`

(11)

`=0

Observe that we have scaled and added up each bandwidth
value depending on how far its interval is from the kth interval. For each connection request in S[k], at least an α
fraction of its size σji was delivered by the end of the αinterval. But now, with the new bandwidth, the entire flow
is delivered over the stretched time line. More precisely,
Z τhα +1
Z τk−D+1
ij
∀fji ∈ S[k] :
b̂ij (t)dt =
b̂ij (t)dt = αb̃ij τk .
0

0

This also means that the new bandwidth and the displacement factor have to satisfy
l
1m
+ 1.
(12)
D ≥ log1+
α
Furthermore, we must ensure that no capacity violation oc-

curs. In the schedule, for every k and for every edge e,
X

b̃ij =

`=k−D
X

X
fji ∈P (e)

fji ∈P (e)

=

`=k−D
X
`=0

≤ c(e)

`=0

α−1 b̂ij`
(1 + )k−`

−1

α
(1 + )k−`

`=k−D
X
`=0

(21) are the usual flow constraints per time interval.
XX 0 i
ωij cj
subject to
Minimize
i

X

j

=1

∀i, j

(15)

τ` xij` ≤ cij

∀i, j

(16)

∀i, j

(17)

∀i, j, `

(18)

∀i, j, `

(19)

∀i, j, `

(20)

∀`, e

(21)

∀i, j, `

(22)

∀i, j, `, e

(23)

`≤L

X

b̂ij`

X

fji ∈P (e)

`≤L

cij ≤ ci0

α−1
,
(1 + )k−`

X

where the inequality follows from constraints (8). Thus, we
P`=k−D α−1
require that `=0
≤ 1, for all k. Hence,
(1+)k−`
1
≤ α.
(1 + )D−1

(1 + )D+2
(1 + )τk+1
=
.
(1 − α)τk−D
1−α

xeij`

=0

e∈N (v)
v6∈{sij ,dij }

X

xeij` = σji xij` /τ`

e∈N (dij )

(13)

Finally, note that the blow up factor in completion time
for each connection request in S[k], taking into account the
(1 + )-factor loss in the LP, is at most

X
e∈N (sij )

XX
i

X

xeij` = −

xeij`

e∈N (dij )

xeij` ≤ c(e)

j

rji > τ`+1 ⇒ xij` = 0
(14)

Numerically minimizing (14) subject to (13) and displacement factor constraint (12), we get an approximation factor
of 17.5319 for α = 0.5, D = 3, and  ≈ 0.5436.

2.2

xij`

Paths Are Not Given

In this section, we consider circuit-based coflow scheduling when paths are not given. Our O( logloglog|E|
) approxi|E|
mation ratio for this case is asymptotically tight since an
) hardness follows from hardness of congestion
Ω( logloglog|E|
|E|
minimization on directed graphs [9]. Recall that, in the congestion minimization problem, given a directed graph and
source-sink pairs, the goal is to connect each pair by a path
such that congestion, the maximum number of paths crossing an edge, is minimized. But, regarding the source-sink
pairs as connection requests of unit size in a single coflow,
the congestion is equivalent to makespan, where all edge capacities are set to 1. So, essentially, congestion minimization
can be seen as a special case of our problem.
We now go over our algorithm (see Algorithm 1).
Algorithm 1: Circuit-based coflow scheduling
input : Coflows F, Network (G, c)
1 Construct the LP L;
2 Solve L; perform rounding and scaling to get flow
values xfe and completion times cf ;
3 foreach flow f ∈ F do
4
PathSet[f ] = FlowDecomposition(f );
5
Path[f ] = Rounding(PathSet[f ]);
6 end
return : Flow paths and ordering based on cf

Reformulation. Identical to §2.1.
The linear program. The linear program is similar to
§2.1, where we have set  = 1. Notice that constraints (18)-

xeij` , xij` ≥ 0

Next, we show that the optimal value of the linear program gives us a relaxed lower bound.
Lemma 5. Half the optimal value of the above linear program provides a lower bound on the weighted sum of completion times for circuit-based coflows with release times.
Proof. Following the proof of Lemma 4, move release
times if necessary, set the variables xij` and calculate bandwidths per interval. Next, set the value of flow variables xeij`
based on the paths pij and the calculated bandwidths. This
setting of variables satisfies all constraints.
Rounding. This step involves scaling followed by flow
decomposition and randomized rounding. Let hx̂eij` , x̂i` i denote an optimal solution to the LP. Analogous to the previous case in §2.1, define the half interval hij of each connection
request fji . All connection requests whose half interval is H
will be scheduled to run entirely in interval (τH+3 , τH+4 ]. In
analogy with §2.1, set α = 12 and D = 3. Now, fix a k and
let S[k] denote the set of connection requests scheduled to
run in (τk , τk+1 ]. Perform scaling and adding up of flows for
every edge to get updated flow variables
x̃eij =

`=k−3
X
`=0

x̂eij`
.
k−`−1
2

(24)

The calculations in §2.1 apply here as well (where we use
inequalities (21) instead of (8)). Hence, the entire size of
every connection request is delivered in the new settings and
all edge capacities are respected. The next step is to apply
the well-known flow decomposition theorem (see e.g. [2]) to
the flow variables x̃eij to get a set of flow paths Pij = {pij }
from sij to dij for each connection request fji ∈ S[k].
At this point, after computing the flow paths, we have
for each k a set of connection requests S[k] expressed in
terms of flow paths. Unfortunately, this is not enough since
each connection request must have exactly one path from
source to sink. What we have, instead, is a set of flow paths

Pij = {pij1 , ..., pijnij } for each connection request fji . This
brings us to the final step.
Let bij denote the total amount of flow in Pij ;
X
bij =
|pijk |.

dij
G
sij

k∈[nij ]

We apply the randomized rounding technique of Raghavan
and Thompson [26] to choose a single path from Pij : we
randomly choose a flow path from Pij where the probability
of pijk being selected is |pijk |/bij . All of the flow in Pij will go
over the chosen path. Let b̄e denote the total flow passing
through e after the rounding. Using a Chernoff-Hoeffding
bound, we can show that for every e ∈ E and every δ > 0:
c(e)/|E|
 

eδ
.
Pr b̄e ≥ (1 + δ)c(e) ≤
1+δ
(1 + δ)
Hence,

 X 

b̄e
b̄e
Pr max
≥ (1 + δ) ≤
Pr
≥ (1 + δ)
e
c(e)
c(e)
e
c(e)/|E|
X
eδ
≤
(1 + δ)1+δ
e
(mine c(e))/|E|

eδ
.
≤ |E|
1+δ
(1 + δ)
If we set δ = O( logloglog|E|
), we obtain that the bandwidth
|E|
used exceeds the capacity of any edge by at most O( logloglog|E|
)
|E|
with probability at most 1/nc for some constant c > 0. Consequently, by scaling down the bandwidth allocated by 1+δ,
and scaling up in time by the same factor, we obtain a feasible set of connection requests with a blowup in completion
).
times at most O( logloglog|E|
|E|

3.

PACKET-BASED COFLOWS

In this model, a flow corresponds to a single packet (flow
size is 1) and a coflow is a collection of packets. The schedule
is based on discrete time steps. During a step, each packet
can either stay at a node (in a queue) or move along an
edge with the restriction that at most one packet can use
the edge at a time. On the hardness side, packet scheduling
can not be approximated within 6/5− , for all  > 0, unless
P = NP [23]. This is true even if paths are given. In §3.1,
we observe that when paths are given, we can apply known
results for job shop scheduling. Next, in §3.2, we consider
the case where paths are not given. We present an O(1)approximation algorithm for this case.

3.1

Paths Are Given

When a path pij is given for each packet fji , the only remaining problem is scheduling. It is well-known that the
problem of scheduling packets on a store-and-forward network with fixed paths is an instance of job-shop scheduling. Specifically, each packet fji can be regarded as a job
which needs to be executed on a number of machines (edges)
in a prescribed order (given by pij ) such that a machine
can process one job at a time. Consequently, the packetbased coflow problem with given
P paths, is an instance of
shop scheduling J|rj , pij = 1| S ωS CS with unit processing times and a generalized min-sum objective; hence, the
algorithm of [25] immediately gives an O(1)-approximation.

(dij , 0)

(dij , 1)

(dij , 2)

(sij , 0)

(sij , 1)

(sij , 2)

Figure 2: An example graph G (above) and its timeexpanded version GT for T = 2 (below). Packet fji
needs to be routed from node sij to node dij in G.
Corresponding to fji , flows of combined size 1 are
sent from (sij , 0) to (dij , k) for k = 1, 2. Dashed lines
correspond to queue edges.
Theorem 6 ([25]). There exists a polynomial-time O(1)approximation algorithm for the
P(generalized) min-sum jobshop problem J(P )|rj , pij = 1| j ωj Cj .

3.2

Paths Are Not Given

This is the more general case where one needs to both
route and schedule packets. We give a polynomial-time
O(1)-approximation algorithm for this problem.
An ingredient in our solution is the notion of time-expanded
graphs first introduced by Ford and Fulkerson [18]. In more
detail, given a (directed) graph G = (V, E) and n coflows
{Fi = {f1i , ..., fni i }}i∈[n] , we construct a time-expanded graph
GT as follows. Each node in the time-expanded graph is labeled by a tuple (v, t) where v is a node in G and 0 ≤ t ≤ T
is the timestamp. Therefore, the edge set of GT is
E(GT ) = {((u, t), (v, t + 1)) : (u, v) ∈ E(G), 0 ≤ t ≤ T − 1}
∪ {((v, t), (v, t + 1)) : v ∈ V (G), 0 ≤ t ≤ T − 1}
where the second group of edges are called queue edges and
their role is to simulate packets waiting for one or more
rounds at a node (see Figure 2). Let us denote by E 0 the
set E(GT ) excluding the queue edges.
The overall idea of the algorithm is as follows. By a netflow we mean a network flow in the ordinary sense. We
express each packet as multiple net-flows to the packet’s
destination in different times in GT ; this will become clear
shortly. The remaining steps involve writing an intervalindexed linear program, assigning packets to intervals, and
performing routing and scheduling packets for each interval.
Reformulation. Consider a packet fji ∈ Fi to be routed
from sij to dij in G. Corresponding to this packet, we send a
t
t
set of net-flows fij
in GT : net-flow fij
has node (sij , rji ) as
i
source (demand is -1) and node (dj , t) as destination where
t ∈ {ri + 1, ..., T } and sum of demands of these nodes is
1 (the exact values will be determined by solving the linear
programP
below). Also, we set T to a sufficiently large integer
(say |E| i∈[n] ni ). As before, we introduce dummy flows f0i
0
and update weights ωij
accordingly.

The linear program. Let T 0 = log T , τ0 = 1 and τ` =
2
for ` ∈ [T 0 ]. Let cij denote the earliest time when a nett
flow fij
in GT reaches its destination; that is cij = mint ctij
t
t
where cij is the completion time of fij
.
`−1

Minimize

ni
XX

0 i
ωij
cj

subject to

i∈[n] j=0
ft

X

X

xeij = fij`

∀i, j, `

(25)

τ` fij` ≤ cij

∀i, j

(26)

cij ≤ ci0

∀i, j

(27)

∀`, e

(28)

∀i, j, `

(29)

∀i, j

(30)

∀i, j

(31)

∀i, j, t, e

(32)

τ` <t≤τ`+1 e∈E((dij ,t))

X
`≤T 0

ni

ft

XX X

xeij ≤ τ`+1

i∈[n] j=0 t≤τ`+1
ft

X X

xeij ≤ τ`+1

e∈E 0 t≤τ`+1

X

btij = 1

t∈T
t

t

t

N fij xfij = bfij
t
fij

0 ≤ xe

≤1

ft

Variables xeij denote the amount of flow corresponding
t
to fij
over edge e ∈ E(GT ). In constraints (25), fij` is
t
the total amount of flow, corresponding to net-flows fij
,
i
that enter their destination nodes (dj , t) for t ∈ (τ` , τ`+1 ].
By E((dij , t)) we mean the set of incoming edges to (dij , t)
in constraints (25). Moreover, btij is the demand of node
t
t
t
(dij , t) and N fij xfij = bfij specify the obvious requirements
of sending a net-flow of size btij from (sij , ri ) to (dij , t) for
ri ≤ t ≤ T , as well as flow conservation at nodes other than
source and sink. Constraints (28) and (29) restrict respectively the congestion and dilation of packets which reach
their destination in interval [0, τ`+1 ]. As can be seen, queue
edges don’t contribute to path dilation.
Lemma 7. The optimal value of the linear program (25)0
0
(32) with weights ωi0
= ωi and ωij
= 0, j 6= 0, is a lower
bound on the optimal weighted sum of packet-based coflow
completion times.
Proof. Given a set S = h{pij }, {qji }ii∈[n],j∈[ni ] of paths
and schedules {qji }, we show that S constitutes a feasible solution to the LP. Without loss of generality, let g denote the maximum amount of time any packet has to wait
in the schedule; the existence of g ∈ O(1) follows from [21]
(note that g is the maximum queue size.) Each packet fji
is routed, on a path of length |pij |, from sij ∈ V to dij ∈ V
according to the schedule {qji } which specifies the amount
of time ∈ [0, g] the packet has to wait before crossing the
next edge on its path. Let Tji denote the time step when fji
reaches its sink. Furthermore, we define T = maxij Tji .
T
For each packet fji , we construct an integral flow fijij in
the time-expanded graph GT . Consider a packet fji with
release time rji in G going from sij to dij on a path specified
by pij according to the schedule qji and arriving at time Tji .
T
The corresponding flow, fijij , in GT from (sij , rji ) to (dij , Tji )
{pij }

is constructed in steps. We keep a current time step t which
is initially set to rji . For each edge e = (u, v) on the path
pij , starting from sij , the flow fji follows the edge(s)
((u, t), (u, t + 1)) → · · · → ((u, t + h), (v, t + h + 1)),
in GT where h is the delay specified by qji before crossing
the edge. Next, we update t ← t + 1 and repeat until we
reach dij . Clearly, Tji is the sum of the path length |pij | and
total amount of delay prescribed by the schedule qji .
It follows from the construction that constraints (31) are
satisfied. Furthermore, since the schedule does not allow
more than one packet to cross an edge at the same time,
the path followed by a flow is exclusive to that flow except,
possibly, the edges ((u, t), (u, t + 1)) which effectively simulate queues. At this point, we can set the value of variables
ft

Ti

xeij according to the flow fijj . We also set cij = Tji and
ci0 = maxj∈[ni ] cij . It is easy to verify that constraints (25)(27) are satisfied. Regarding congestion constraints (28),
observe that, for all `, packets that have reached their destination by time τ`+1 , can not cause an edge to have a congestion value more than τ`+1 . The same argument applies
to dilation constraints (29).
Rounding. At a high-level, this step consists of two
parts (a) Assign the packets to time intervals; (b) Route
and schedule packets in each interval by applying the algorithm of Srinivasan and Teo [28].
ft
Let Ŝ = hx̂eij , fˆij` , ĉij i denote an optimal solution to the
LP (25)-(32). We start by filtering the solution and assigning
packets to intervals. Specifically, define the half-interval of
a packet fji to be the interval (τhi , τhi +1 ] such that hij =
j
j
 P
min ` : t<` fˆijt ≥ 12 ; then, set
(
P
fˆij` /(1 − t≥` fˆijt ), if τ`+1 ≤ hij ,
¯
fij` =
0,
if τ`+1 ≥ hij .
ft

Also, set the other variables x̄eij and c̄ij according to (25)
and (26) respectively. Clearly, the blowup in each variable
and the right hand side of (28)-(29) is at most 2.
Next, we assign each packet fji to its half-interval. Let
P [`] denote the set of packets that have been assigned to the
interval (τ` , τ`+1 ]. At this stage, we go over all time intervals
sequentially and, for each one, route and schedule all packets
in it. Fix an ` and consider all packets fji ∈ P [`]. Collapse
the portion of the time-expanded graph GT , corresponding
to the times t ≤ τ`+1 , back to G by combining nodes and
edges which differ only in time stamp and by removing queue
edges altogether.
Observe that the removal of queue edges will not cause any
problem since any amount of flow passing through them will
have left the queue by the end of the last interval. Now, the
ft
filtered solution S̄ = hx̄eij , f¯ij` , c̄ij i satisfies
X
f
xeij ≤ τ`+2
∀e ∈ E
(33)
i,j:fji ∈F [`]

X

f

xeij ≤ τ`+2

∀fji ∈ P [`]

(34)

∀fji ∈ P [`]

(35)

∀fji

(36)

e∈E

N̄ fij xfij = b̄fij
0≤

f
xeij

≤1

∈ P [`] ∀e ∈ E

where the constraints N̄ fij xfij = b̄fij express the flow requirements in the collapsed graph. Formally,
0

f
x̄eij

Lemma 8. For every ` ∈ [T ], the set of flows
corresponding to packets fji in P [`] satisfy the LP in (33)-(36)
with respect to the (collapsed) graph G.
This LP is exactly the one considered in [28] and by applying their theorem, we can route and schedule all packets
in P [`] such that the last packet arrives in time O(τ`+2 ).
Theorem 9 ([28]). There are constants c0 , c00 > 0 such
that the following holds. For any packet routing problem
on any network, there is a set of paths and a corresponding
schedule that can be constructed in polynomial time such that
the routing time is at most c0 times the optimal, and the
maximum queue size at each edge is bounded by c00 .
We do this for P [1], P [2] and so on. Note that the coflow
release times are respected. The optimal completion time of
a packet fji ∈ P [`] in the LP (25)-(32) is ĉij = O(τ`+1 ). On
the other hand, the completion time of the same packet in
our algorithm is
X
X
c̃ij =
O(τt+1 ) =
O(2t ) = O(2` ) = O(τ`+1 ). (37)
t≤`

4.3

Performance

We measure the weighted sum of completion times. As
in [31], we compare our algorithm to the following schemes.
• Baseline: flows are routed and ordered randomly.
• Schedule-only: flows are routed randomly; ordering is
by minimum completion time which is computed as
the ratio of flow size to path bandwidth.
• Route-only: flows are routed for achieving good load
balance and edge utilization; ordering is arbitrary.
We investigate the impact of two parameters. First is the
number of flows in each coflow, which we refer to as coflow
width. Second is the number of coflows.

Coflow width
In this case, we fix the number of coflows to 10 and run
experiments for coflow widths in {4, 8, 16, 32}. As illustrated
in Figure 3, LP-Based completes every instance faster than
the baseline, Schedule-only, and Route-only schedules. On
average, the improvement over the baseline, Schedule-only
and Route-only is by %126, %96, and %22, respectively.

t≤`
Simulation on 128 servers on 10 coflows

Consequently, the weighted completion time of our algorithm is within a O(1) factor of the optimal solution.

9000

8000

6000

Average complition time

In this section, we describe some experiments conducted
to evaluate the practical performance of our circuit-based
scheduling algorithm in §2.2.

4.1

7000

EXPERIMENTS

Methodology

We use a simulator to assess the performance of our algorithm in practice. Packet-level simulators are not suitable
for this setting due to their high level of overhead [4, 31].
Therefore, like previous works [4, 31, 8], we developed a
flow-based simulator. At a high level, the simulator is an
event queue. Each flow corresponds to an event which happens at its release time. The simulator chooses the next flow
based on the ordering prescribed by a scheduling algorithm
or scheme. A second event occurs when a flow completes; at
which time, its reserved bandwidth is released.
We use a 128-server Fat-Tree with 1Gbs links as the network topology. Due to the complexity of the linear program
to be solved, simulations of large instances were prohibitively
slow. Each coflow instance is randomly generated with flow
release times, flow sizes, and coflow weights based on Poisson
distributions. Each result is the average of 10 tries.

5000

4000

3000

2000

1000

0
4 flows

8 flows

16 flows

32 flows

Number of flows per coflow
LP-Based

Route-only

Schedule-only

Baseline

Simulation on 128 servers on 10 coflows
1.2

1

0.8

Ratio with respect to baseline

4.

0.6

0.4

4.2

Implementation

We implement Algorithm 1 in §2.2 with some minor
tweaks. In particular, to avoid wasting time and bandwidth,
each flow starts as soon as it can (in the order prescribed by
the linear program), as opposed to starting at the beginning
of its half-interval.
The path decomposition algorithm tries to minimize the
number of paths per flow by finding the “thickest” paths; this
is done using a well-known version of Dijkstra’s shortestpath algorithm. We implemented the above algorithm in
C++ using Lemon libraries and IBM CPLEX 12.6.3. to
solve the linear program.

0.2

0
4 flows

8 flows

16 flows

32 flows

Number of flows per coflow
LP-Based

Route-only

Schedule-only

Baseline

Figure 3: Changing the coflow width; the number
of coflows is set to 10.

Number of coflows
Using a fixed coflow width of 16, we vary the number of
coflows from 10 to 25, in increments of 5. The results are
illustrated in Figure 4. We find that again LP-Based completes every instance faster than the baseline as well as the
Schedule-only and Route-only schedules. On average, the
improvement over the baseline, Schedule-only and Routeonly is by factors of %110, %72, and %26, respectively.

Simulation on 128 servers with different number of coflows

of further research is to obtain improved constant-factor
bounds for general networks and improved algorithms for
special network classes that are of particular interest to datacenter applications. More broadly, we would like to pursue
algorithms for other important objectives and coflow models.
Specifically, we are interested in designing approximation
algorithms for the total weighted response time objective,
where the response time is the difference between completion time and release time. Another line of research is the
design of schedules for coflows in optical networks.

35000

6.

30000

We would like to thank the reviewers for their useful comments and pointing out the relevant work done in [10].

ACKNOWLEDGMENTS

Average Completion time

25000

7.

20000

15000

10000

5000

0
10 coflows

15 coflows
LP-Based

20 coflows
Route-only

Schedule-only

25 coflows

30 coflows

Baseline

Simulation on 128 servers with different number of coflows
1.2

1

Ratio with respect to Baseline

0.8

0.6

0.4

0.2

0

10 coflows

15 coflows
LP-Based

20 coflows
Route-only

Schedule-only

25 coflows

30 coflows

Baseline

Figure 4: Changing the number of coflows; coflow
width is set to 16.
We note that, as can be seen in the experiments, the worstcase approximation ratio of O(log |E|/ log log |E|), does not
happen in practice. The main reason is that in the fat-tree
topology there are a few paths between pairs of servers; furthermore, uniform link bandwidth causes the path decomposition routine to return fewer flow paths. Indeed, in all
of our experiments, the path decomposition routine returns
one path per flow.

5.

CONCLUSION AND OPEN PROBLEMS

We have presented algorithms for scheduling task-based
coflows, packet-based coflows, and circuit-based coflows for
general networks. All of our algorithms achieve asymptoticallyoptimal total weighted completion time. An immediate line

REFERENCES

[1] Saba Ahmadi, Samir Khuller, Manish Purohit, and
Sheng Yang, On scheduling coflows, IPCO, 2017.
[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network
flows: Theory, algorithms, and applications, 1993.
[3] M. Al-Fares, S. Radhakrishnan, B Raghavan,
N. Huang, and A. Vahdat, Hedera: Dynamic flow
scheduling for data center networks, NSDI, 2010.
[4] Mohammad Al-Fares, Sivasankar Radhakrishnan,
Barath Raghavan, Nelson Huang, and Amin Vahdat,
Hedera: Dynamic flow scheduling for data center
networks, USENIX, 2010.
[5] J. D. Blocher and D. Chhajed, The customer order
lead-time problem on parallel machines, Naval
Research Logistics 43 (1996), no. 5.
[6] M. Chowdhury and I. Stoica, Coflow: A networking
abstraction for cluster applications, HotNets, 2012.
[7] M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and
I. Stoica, Managing data transfers in computer
clusters with orchestra, SIGCOMM, 2011.
[8] M. Chowdhury, Y. Zhong, and I. Stoica, Efficient
coflow scheduling with varys, SIGCOMM, Comput.
Commun. Rev. 44 (2014), no. 4.
[9] J. Chuzhoy, V. Guruswami, S. Khanna, and
K. Talwar, Hardness of routing with congestion in
directed graphs, STOC, 2007.
[10] José R. Correa, Martin Skutella, and José Verschae,
The power of preemption on unrelated machines and
applications to scheduling orders,
APPROX/RANDOM, 2009.
[11] J. Dean and S. Ghemawat, Mapreduce: simplified data
processing on large clusters, Commun. ACM 51
(2008), no. 1.
[12] N. Garg, A. Kumar, and V. Pandit, Order scheduling
models: Hardness and algorithms, FSTTCS, 2007.
[13] R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.
Rinnooy Kan, Optimization and approximation in
deterministic sequencing and scheduling: a survey,
Discrete Mathematics, vol. 5, 1979.
[14] C. Hong, M. Caesar, and B. Godfrey, Finishing flows
quickly with preemptive scheduling, ACM Conference,
SIGCOMM.
[15] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly,
Dryad: distributed data-parallel programs from
sequential building blocks, Proc. of the EuroSys
Conference, 2007.

[16] S. Khuller and M. Purohit, Brief announcement:
Improved approximation algorithms for scheduling
co-flows, SPAA, 2016.
[17] R. Koch, B. Peis, M. Skutella, and A.s Wiese,
Real-time message routing and scheduling,
Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques, Lecture
Notes in Computer Seince, vol. 5687, 2009.
[18] Jr. L. R. Ford and D. R. Fulkerson, Constructing
maximal dynamic flows from static flows, Operations
Research 6 (1958), no. 3.
[19] J. Labetoulle, E.L. Lawler, J.K. Lenstra, and
A.H.G. Rinnooy Kan, Preemptive scheduling of
uniform machines subject to release dates, Progress in
Combinatorial Optimization (William R. Pulleyblank,
ed.), Academic Press, 1984.
[20] F. T. Leighton, B.M. Maggs, and A.W. Richa, Fast
algorithms for finding o(congestion + dilation) packet
routing schedules, Combinatorica 19 (1999), no. 3.
[21] F.T. Leighton, B.M. Maggs, and S.B. Rao, Packet
routing and job-shop scheduling in
o(congestion+dilation) steps, Combinatorica (1994).
[22] J. Y-T. Leung, H. Li, and M. Pinedo, Order
scheduling models: An overview, 2005.
[23] B. Peis, M. Skutella, and A. Wiese, Packet routing:
Complexity and algorithms, WAOA, 2009.
[24] Z. Qiu, C. Stein, and Y. Zhong, Minimizing the total
weighted completion time of coflows in datacenter
networks, SPAA, 2015.
[25] M. Queyranne and M. Sviridenko, Approximation
algorithms for shop scheduling problems with minsum
objective, Journal of Scheduling (2002).
[26] P. Raghavan and C. Thompson, Randomized rounding:
A technique for provably good algorithms and
algorithmic proofs, Combinatorica 7 (1987).
[27] Mehrnoosh Shafiee and Javad Ghaderi, Brief
announcement: A new improved bound for coflow
scheduling, SPAA, 2017.
[28] A Srinivasan and C.-P. Teo, A constant-factor
approximation algorithm for packet routing and
balancing local vs. global criteria, SIAM Journal on
Computing 30 (2001), no. 6.
[29] M. Zaharia, M Chowdhury, M. J. Franklin,
S. Shenker, and I. Stoica, Spark: Cluster computing
with working sets, HotCloud, 2010.
[30] D. Zats, T. Das, P. Mohan, D. Borthakur, and R. H.
Katz, Detail: reducing the flow completion time tail in
datacenter networks, SIGCOMM, 2012.
[31] Y. Zhao, K. Chen, W. Bai, M. Yu, C. Tian, Y. Geng,
Y. Zhang, D. Li, and S. Wang, Rapier: Integrating
routing and scheduling for coflow-aware data center
networks, INFOCOM, 2015.

