1

Stochastic Non-preemptive Co-flow Scheduling with
Time-Indexed Relaxation

arXiv:1802.03700v2 [cs.DC] 23 Feb 2018

Ruijiu Mao, Vaneet Aggarwal, and Mung Chiang

Abstract—Co-flows model a modern scheduling setting that
is commonly found in a variety of applications in distributed
and cloud computing. A stochastic co-flow task contains a set
of parallel flows with randomly distributed sizes. Further, many
applications require non-preemptive scheduling of co-flow tasks.
This paper gives an approximation algorithm for stochastic nonpreemptive co-flow scheduling. The proposed approach uses a
time-indexed linear relaxation, and uses its solution to come up
with a feasible schedule. This algorithm
√ is shown to achieve a
competitive ratio of (2 log m + 1)(1 + m∆)(1
√ + m∆)(3 + ∆)/2
for zero-release times, and (2 log m + 1)(1 + m∆)(1 + m∆)(2 +
∆) for general release times, where ∆ represents the upper bound
of squared coefficient of variation of processing times, and m is
the number of servers.
Index Terms—Co-flow scheduling, stochastic flow size, nonpreemptive scheduling, time-indexed relaxation, input-queued
switch.

I. I NTRODUCTION
Computation frameworks such as MapReduce [2], Hadoop
[3], Spark [4], and Google Dataflow [5] are growing at
an unprecedented speed. These frameworks enable users to
offload computation to the cloud. In order for cloud service
provider to maintain efficient services, they need to schedule
the different jobs so as to minimize the completion time of
the jobs. One of the key challenges in cloud computing is
the data transmission across machines [6], which typically
happens during the shuffle phase in the MapReduce based
computations. In this paper, we will provide algorithms to
reduce this communication time for different flows required
in each of computational jobs.
Scheduling for shuffle phase is studied in the literature as
co-flow scheduling [7]. In this framework, a flow consists of
data transfer between two servers. A co-flow task consists of
multiple flows. A co-flow task is complete when all these flows
are complete. Co-flow scheduling problem aims to schedule
multiple co-flow tasks so that the weighted completion time
of the co-flow tasks is minimized. In most realistic big data
computing jobs, the size of the flows to be transfered is not deterministic. The authors of [8] provide an overview of various
scheduling problems with random parameters. For instance,
processing times can be regarded as independent random
variables drawn from given probability distributions. Further,
many scenarios do not allow for stopping a transfer once
started [9] and thus non-preemptive scheduling strategies are
important. The key reasons for practicality of non-preemption
The authors are with Purdue University, West Lafayette IN 47907 (email:
{mao95, vaneet, chiang}@purdue.edu). This paper will be presented in part
at the IEEE Infocom Workshop on Big Data in Cloud Performance (DCPerf),
April 2018 [1].

include additional signaling overhead, flow switching latency,
packet drops, and limitations on hardware. Thus, this paper
considers non-preemptive stochastic scheduling of multiple coflow tasks.
Aiming to reduce weighted completion time of tasks, this
paper proposes a co-flow scheduling algorithm to order each
constituent flow of each co-flow task with a random data size
on each link. The non-preemptive constraint implies that each
flow occupies whole capacity of its source and sink machines,
namely one unit per time slot, until the completion of the flow.
Stochastic non-preemptive co-flow model provides flexibility
and efficiency based on parallelism: constituent flows from
several co-flows might be processed at same time. The problem
even with deterministic flow sizes is NP-hard. The authors of
[10] considered a non-preemptive co-flow problem, where the
different links were assigned bandwidth and thus the links
were independent. In the standard co-flow problem [11], [12],
[13] that is also considered in this paper, there are flow
constraints at the source and the sink ends.
We note that the problem of scheduling preemptive co-flows
with deterministic flow time has been considered in [11], [12],
[13], where O(1)-approximation algorithms are provided for
minimizing the weighted completion time. However, there are
no corresponding results for scheduling non-preemptive coflows. This is the first paper, to the best of our knowledge, that
provides approximation guarantees for the non-preemptive coflow scheduling problem. Let ∆ represents the upper bound
of squared coefficient of variation of processing times and
m is the number of servers.Then,√the algorithm proposed in
this paper is an (2 log m + 1)(1 + m∆)(1 + m∆)(3 + ∆)/2
approximation
algorithm for zero release time, and (2 log m +
√
1)(1 + m∆)(1 + m∆)(2 + ∆) approximation algorithm for
general release times.
The proposed algorithm uses a time-slotted model, where
the processing times are integer multiple of the length of
the time slot. A linear programming (LP) based relaxation
algorithm is formulated, that has variable of probability distribution of start of co-flow on each link, thus providing
the average completion time of each co-flow. Since this is
only a relaxation, the schedule may not be feasible. Based
on weighted shortest expected processing time algorithm
(WSEPT), an optimal rule for single-machine scheduling with
stochastic processing time [14], we generate tentative start
time for every constituent flow suggested by the LP solution,
and group the flows by their tentative start time. Further, a
grouping of coflows (originally used for input-queued switches
[15]) is used which provides groups of co-flows which could
be scheduled simultaneously since they have no conflicts.

2

Scheduling these groups in order gives the proposed algorithm.
The main contributions of the paper can be summarized as
follows.
1) This paper is the first paper, to the best of our knowledge, that gives approximation guarantees for stochastic
non-preemptive co-flow scheduling. The results have
been provided both with zero release times, and general
release times.
2) As a special case of stochastic, ∆ = 0 gives the results
for deterministic non-preemptive co-flow scheduling.
These are also the first approximation results, to the best
of our knowledge, for this case, where the approximation
guarantees are 3/2(2 log m+1) approximation algorithm
for zero release times, and 2(2 log m+1) approximation
algorithm for general release times.
The rest of this paper is organized as follows. Section II
introduces the related work of co-flow scheduling and inputqueued switches. Section III presents the formulation of the
problem. In Section IV, the proposed algorithm is provided.
Section V proves the approximation bounds of the proposed
algorithm. Section VI extends the algorithm and the results
to general release times. Finally, Section VII concludes the
paper.
II. R ELATED W ORK
In this section, we will describe the related work for this
paper in three categories of co-flow scheduling, input-queued
switch, and stochastic scheduling on parallel machines.
A. Co-flow Scheduling
The concept of co-flow was first proposed in 2012 by
Chowdhury [7]. Further, the authors of [16] proposed an efficient implementation of co-flow scheduling. However, these
works did not provide approximation guarantees for the proposed algorithm.
Polynomial-time approximation algorithms have been proposed for deterministic preemptive co-flow scheduling in [11],
[12], [13]. The authors of [11] use a relaxed linear program
followed by a Birkhoff-von-Neumann (BV) decomposition
to schedule flows. In contrast, this paper considers nonpreemptive scheduling, and has stochastic task sizes.
Non-preemptive deterministic co-flow scheduling has also
been studied in [10]. However, the authors assumed fixed
bandwidth links between every pair of servers. In contrast,
this paper considers bandwidth constraints at source and sink
which is typical for co-flow scheduling literature.
B. Input-queued switch
To decrease the frequency of matching computation for
crossbar configuration in high-speed core routers, frame-based
scheduling has being widely studied [17], [18]. One of the
essential steps of frame-based scheduling is the computation
of a list of input/output pair. The pairing step is similar to coflow scheduling in the sense of grouping constituent flows to
be processed in the same time slot. The listing step is similar to
co-flow scheduling in the sense of sequencing the groups flows

at each time slot. The authors of [15] introduced Greedy Low
Jitter Decomposition (GLJD) Algorithm to solve list pairing
scheduling problem. The GLJD algorithm can be seen in nonpreemptive scheduling as an algorithm that has a similar goal
as the BV decomposition for preemptive scheduling in [11].
C. Stochastic scheduling on parallel machines
For scheduling of jobs, the size of tasks is unknown
apriori. Thus, introducing randomness in the task sizes is
a natural abstraction. In 1966, the authors of [14] proved
that WSEPT rule (weighted shortest expected processing time
first) is optimal for minimizing weighted completion time of
jobs on a single server. Based on WSEPT rule, the authors
of [19] studied the stochastic variant of unrelated parallel
machine scheduling. This approach uses a time-indexed linear
programming relaxation for stochastic machine scheduling,
whose ideas have been used in this paper to formulate a timeindexed linear relaxation for stochastic co-flow scheduling.
III. P ROBLEM F ORMULATION
In this section, we will describe the problem of Stochastic Non-preemptive Co-flow scheduling. Consider set of m
servers given as M = {1, 2, · · · , m}. A flow represents a
data communication between a server i ∈ M and a server
j ∈ M. Each co-flow task is composed of multiple flows. Let
there be N co-flow tasks, where co-flow task k is indexed by
a set Tk . This set Tk is composed of a set of flows represented
by a set of (i, j, k), where i, j ∈ M, and k ∈ {1, · · · , N }. For
each such flow, the size of the flow is characterized by Si,j,k ,
which is the random variable indicating the size of flow (or
data transfer) from i to j. More, formally, a co-flow task is
defined as follows.
Definition 1. k-th co-flow task is defined as a set of flows, or
Tk ⊆ {(i, j, k) : i, j ∈ M, k ∈ {1, · · · , N }}. Further, Si,j,k
is the random variable indicating the size of flow (or data
transfer) from i to j.
We note that the size of flows can be discretized to positive
integers, while only loosing a factor 1 + ǫ in the objective
function value for any ǫ > 0, where the number of discrete
levels are O(1/ǫ) following similar proof as in [19, Lemma
1]. Thus, we will assume that the random variable Si,j,k only
takes non-negative integer values.
We next define the notion of co-flow scheduling. Coflow scheduling problem is to schedule the different flows
on each link (i, j), where the different flows are given as
∪N
k=1 {(i, j, k) : Pr(Si,j,k = 0) < 1}. Non-preemptive
scheduling implies that once a task (i, j, k) ∈ Tk is started, it
will be processed till completion. By stochastic, we mean that
the Si,j,k is the random variable, whose cumulative distribution
function is known. We assume that the probability that Si,j,k
is at least t be pi,j,k,t , or pi,j,k,t = Pr(Si,j,k ≥ t).
We assume a time-slotted model. We partition time into time
slots (t ∈ {0, 1, · · · }). For example, t = 0 is the first time slot
with unit time length. Further, we assume that each source
port can only send one unit of data per time slot and every
sink port can only receive one unit of data per time slot.

3

Let wk , k ∈ {1, · · · , N } be the weights of the different coflows. Let the expected completion time of a co-flow (i, j, k) ∈
Tk be Ci,j,k . Further, the expected completion time of a coflow task Tk is given as max(i,j,k)∈Tk Ci,j,k . Based on these,
the Stochastic Non-Preemptive Co-flow scheduling is defined
as follows.
Definition 2. Stochastic Non-Preemptive Co-flow scheduling
wishes to find the order of scheduling non-preemptive co-flows
on
PNeach link with stochastic processing times, so as to minimize
k=1 wk Ck .

We first derive a LP relaxation of the stochastic nonpreemptive co-flow scheduling problem. Let yi,j,k,t be the
indicator that the flow (i, j, k) will be started processing
at time slot t. In the relaxation, we will relax the integer
constraint so that yi,j,k,t represents the probability that flow
(i, j, k) will be started processing at time slot t. Further, let
the optimization problem variable Ck represent the expected
completion time of k-th co-flow. Then, the LP relaxed problem
to minimize the weighted expected completion time of the coflows can be formulated as follows.

min
Source Ports

Sink Ports

s.t.

N
X

k=1
∞
X

wk Ck

(1)

yi,j,k,t = 1

(2)

t=0

∀i, j ∈ M,
1

1, 2

2

3
2, 3

3
4

1

1

X

j∈M k=1 t=0

3
1

3
4

X

N X
s
X

i∈M k=1 t=0

∀k ∈ {1, · · · , N };

yi,j,k,t pi,j,k,s−t ≤ 1

∀i ∈ M,

2
3

N X
s
X

(3)

s ∈ {0, 1, · · · };

yi,j,k,t pi,j,k,s−t ≤ 1

∀j ∈ M, s ∈ {0, 1, · · · };
∞
X
Ck ≥
yi,j,k,t (t + E[Si,j,k ])

(4)

(5)

t=0

5

2

5

∀i, j ∈ M,
yi,j,k,t ≥ 0
∀i, j ∈ M,

Fig. 1. An example to demonstrate the co-flows on each link. The number
on the links represents the task numbers that has a flow on that link.

As an example, consider m = 5 servers as depicted in
Figure 1. We wish to schedule three co-flows given as follows.
T1 = {(1, 1, 1), (2, 4, 1), (4, 3, 1)},

T2 = {(1, 1, 2), (2, 2, 2), (5, 5, 2)},
T3 = {(2, 1, 3), (2, 2, 3), (3, 4, 3), (5, 1, 3)}.

All flows have stochastic sizes Si,j,k , but we know their
distributions. By capacity constraints, flows (1, 1, 1), (1, 1, 2),
(2, 1, 3), and (5, 1, 3) can not be processed simultaneously
since they share the same sink port. Similarly, (2, 1, 3),
(2, 2, 2), (2, 2, 3), (2, 4, 1) can not be processed simultaneously since they share the same source port.
IV. P ROPOSED A LGORITHM
The proposed algorithm uses a linear programming (LP)
relaxation of the co-flow scheduling problem. Since the solution of the relaxed problem may not in general be feasible,
an algorithm using the solution of the relaxed problem that
gives a feasible schedule will be provided. Guarantees that the
proposed algorithm is approximately optimal will be derived
in Section V.

k ∈ {1, · · · , N };
∀k ∈ {1, · · · , N },

(6)
t ∈ {0, 1, · · · }.

Constraint (2) says that every constituent flow (i, j, k) will
be assigned some time. Constraints (3) and (4) are matching
constraints, where on an average, at most one unit of data
leaves the source or enters the sink. Constraint (5) says
the expected completion time of a co-flow task is at least
the maximum among all of its constituent flows’ expected
completion time. Constraint (6) says the probability that every
constituent flow (i, j, k) starts at time t (t ∈ {0, 1, · · · }) is
non-negative.
We denote the optimal value of Ck from the LP relaxLP
ation problem as CkLP , the optimal yi,j,k,t as yi,j,k,t
, and
LP
the expected completion time of flow (i, j, k) as Ci,j,k
=
P∞ LP
y
(t
+
E[S
])
i,j,k
t=0 i,j,k,t
We first note that even though t is being summed till ∞, it
only needs to be summed till the sum of maximum flow sizes
on each link. In theorem 1, we will show that the infinite
time-indexed LP relaxation can be approximated by a finite
time-indexed relaxation. Further, we see that the constraints
are necessary for the co-flow scheduling problem. Thus, the
weighted expected completion time as the optimal objective of
the LP relaxation is less than or equal to the optimal expected
weighted completion time of the co-flows. In other words,
N
X

k=1

wk CkLP ≤

N
X

k=1

wk Ck∗ ,

(7)

4

∗
} are the expected completion times of
where {C1∗ , · · · , CN
the optimal co-flow scheduling.
We give a definition of pseudo-permutation matrix, which
is used in the following algorithm.

Definition 3. A pseudo-permutation matrix is a square binary
matrix that has at most one entry of 1 in each row and each
column and 0s elsewhere.
We will now describe the proposed algorithm, NonPreemptive Stochastic Co-flow Scheduling (NPSCS), which
is summarized in Algorithm 1
For non-preemptive scheduling, the problem reduces to deciding the start time of all the constituent flows. The proposed
scheduling algorithm, NPSCS, summarized in algorithm 1,
consists of 4 steps.
In Step 1 (line 3), we solve the relaxed LP problem (1)LP
(6) and get the optimal probability yi,j,k,t
for each constituent
flow (i, j, k) starting at each time slotPt. Although we can
solve the LP and get optimal solution k∈{1,··· ,N } wk CkLP ,
the
PNsolutionLPis not in general a feasible schedule. However,
is a lower bound for the optimal scheduling,
k=1 wk Ck
LP
and yi,j,k,t
can provide insights on scheduling the start time
of flow (i, j, k).
In Step 2 (lines 4-12) and Step 3 (lines 13-37), we show
how to turn the time-indexed LP relaxation to a feasible
schedule. In Step 2, we generate t with probability mass
LP
function yi,j,k,t
and r ∈ {0, 1, · · · } with probability mass
function pi,j,k,r /E[Si,j,k ]. We define the tentative start time
t(i, j, k) for each flow (i, j, k) by summing up t and r.
In Step 3 (line 13-27), we group all the flows with same
tentative start time s as J (s). We build a matrix D(s) ∈
Rm×m with only non-negative elements. The intersection of
sets {(i, j, k)|k ∈ {1, · · · , N } and J (s) is the set of flows
with tentative start time s and transfer data from server i
to server j. We sum the expectation
size of flows in the

intersection set up and set D(s) i,j to be the value of this
sum. We want to process all flows within J (s) simultaneously,
but the capacity constraints of each server do not allow flows
with same source server or same sink server to be processed
on one time slot. Only flows having no interference on source
or sink servers can be processed at the same time slot. As
a result, we use Greedy Low Jitter Decomposition algorithm
(GLJD) given in algorithm 2 to get a set of pseudo-permutation
matrices {X(s)1 , · · · , X(s)ls }, where ls is the number of
resulting pseudo-permutation matrices. For any X(s)l where
l ∈ {1, · · · , ls }, we denoteall flows in J (s) from server i to
server j for which X(s)l i,j is 1 as I(s)l .
GLJD has originally been proposed in [15] to enable traffic
scheduling with low-jitter guarantees. GLJD returns a set
of pseudo-permutation matrices, whose structures provides
feasible co-flow scheduling satisfying capacity constraints. For
s ∈ {0, 1, · · · }, GLJD algorithm (algorithm 2) first sort the
expectation size of all flows from J (s) in non-increasing order
to create a list L. We record the source server and sink server
locations of the n-th largest expected size as ρ(n) and κn. We
greedily pick elements from the top to the bottom of the list
L as long as the elements do not share same source server
or sink server with the help of ρ(·) and κ(·). Once we finish

Algorithm 1 Non-Preemptive Stochastic Co-flow Scheduling
(NPSCS)
1: Input: pi,j,k,t , E[Si,j,k ], (i, j ∈ M, k ∈ {1, · · · , N }).
2: Output: A list of perfect matching co-flows to be scheduled in turn, Γ.
LP
3: Solve LP problem (1)-(6), and obtain yi,j,k,t
for all (i, j ∈
M, k ∈ {1, · · · , N }).
4: for i ∈ {1, · · · , m} do
5:
for j ∈ {1, · · · , m} do
6:
for k ∈ {1, · · · , N } do
7:
Choose t ∈ {0, 1, · · · } such that the probability
LP
mass function of t is Pr(t = a) = yi,j,k,a
.
8:
Choose r ∈ {0, 1, · · · , } such that the probability mass function of r is Pr(r = b) =
pi,j,k,b /E[Si,j,k ].
9:
Compute t(i, j, k) = t + r as the tentative start
time of flow (i, j, k).
10:
end for
11:
end for
12: end for
13: for s ∈ {0, 1, · · · } do
14:
Create a matrix D(s) ∈ Rm×m . Denote D(s)i,j as the
(i, j) entry of D(s). Initialize each entry of D(s) as
zero.
15:
Create a set J (s) = { }
16:
for i ∈ {1, · · · , m} do
17:
for j ∈ {1, · · · , m} do
18:
for k ∈ {1, · · · , N } do
19:
if t(i, j, k) == s then
20:
D(s)i,j = D(s)Si,j + E[Si,j,k ]
21:
J (s) = J (s) (i, j, k)
22:
end if
23:
end for
24:
end for
25:
end for
26:
Input matrix D(s) to algorithm 2 to obtain a set
of pseudo-permutation matrices {X(s)1 , · · · , X(s)ls },
where ls is the number of resulting pseudo-permutation
matrices from algorithm 2
27:
for l ∈ {1, · · · , ls } do
28:
I(s)l = { }
29:
for i ∈ {1, · · · , m} do
30:
for j ∈ {1, · · · , m} do
31:
if X(s)l i,j ==
 S 1 then
T
N
l
32:
I(s) =
(i,
j,
k)
J (s)
k=1
33:
end if
34:
end for
35:
end for
36:
end for
37: end for
38: Γ = [ ]
39: for s ∈ {0, 1, · · · } do
40:
for l ∈ {1, · · · , ls } do
41:
Γ = [Γ, I(s)l ]
42:
end for
43: end for

5

searching the list, we create a pseudo-permutation matrix Xsl
(l is the number of times we search the list from the beginning)
with entry (i, j) equal to one if and only if at least one element
picked from L has ρ(·) = i and κ(·) = j (∀i, j ∈ {1, · · · , m}).
Next, we delete the corresponding elements from list L and
start constructing for the next pseudo-permutation matrix until
the list L becomes empty.
In Step 4 (lines 38-43, algorithm 1), the NPSCS algorithm
schedules flows in the order of Γ, which is a concatenation of
I(s)l , for all s ∈ {0, 1, · · · }, and l ∈ {1, · · · , ls } as can be
seen in algorithm 1.
Algorithm 2 Greedy Low Jitter decomposition (GLJD):
1: Input: A matrix D(s) ∈ Rm×m with only non-negative
elements
2: Output: A set
of pseudo-permutation matrices
{X(s)1 , · · · , X(s)ls }, where ls is the number of
resulting matrices in the set
3: Create a list L of all non-zero entries in D(s) by nonincreasing order of their values
4: aL = |L| (|L| is the number of elements in list L)
5: Set M = {(i, j)|for all D(s)i,j > 0, i ∈ {1, · · · , m}, j ∈
{1, · · · , m}}
6: for n ∈ {1, · · · , aL } do
7:
for (i, j) ∈ M do
8:
if L(n) == D(s)i,j then
9:
set ρ(n) = i and κ(n) = j
10:
Remove (i, j) from M
11:
end if
12:
end for
13:
n=n+1
14: end for
15: Initialize l = 1
16: while L =
6 ∅ do
17:
Set X(s)l = 0m×m
18:
Set a = 1
19:
Set C[k] = 0 ∀k ∈ {1, · · · , m}
20:
while a ≤ aL do
21:
while C[ρ(a)]
== 0 and C[κ(a)] == 0 do

22:
X(s)l ρ(a),κ(a) = 1
23:
C[ρ(a)] = C[κ(a)] = 1
24:
Eliminate entry a from list L
25:
end while
26:
a=a+1
27:
end while
28:
l =l+1
29: end while
For a single s, we now provide an example to explain step
3 (line 13-27) and step 4 (line 38-43). Suppose we have 4
servers and 3 co-flows. Further, suppose that the flows given
in Table IV have s as their tentative start time. The flows in
Table IV form the matrix D(s), which is given as


0.38
0
0.22 0.40
0.11 0.24 0.60 0.05
,
D(s) = 
 0
0.53 0.14 0.33
0.51 0.23 0.04 0.22

(i, j, k)
(1, 1, 1)
(2, 1, 3)
(4, 1, 1)
(4, 1, 3)
(1, 4, 1)
(2, 4, 1)
(3, 4, 2)

E[Si,j,k ]
0.38
0.11
0.20
0.31
0.40
0.05
0.33

(i, j, k)
E[Si,j,k ]
(2, 2, 2)
0.24
(3, 2, 1)
0.19
(3, 2, 2)
0.31
(3, 2, 3)
0.03
(4, 2, 2)
0.23
(4, 4, 1)
0.22
TABLE I

(i, j, k)
(1, 3, 2)
(2, 3, 1)
(2, 3, 2)
(2, 3, 3)
(3, 3, 3)
(4, 3, 3)
-

E[Si,j,k ]
0.22
0.20
0.20
0.20
0.14
0.04
-

T HE FLOWS WITH TENTATIVE START TIME s IN THE EXAMPLE

and J (s) is given as
J (s)

= {(1, 1, 1), (2, 1, 3), (4, 1, 1), (4, 1, 3), (2, 2, 2),
(3, 2, 1), (3, 2, 2), (3, 2, 3), (4, 2, 2), (1, 3, 2),
(2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 3, 3), (4, 3, 3),
(1, 4, 1), (2, 4, 1), (3, 4, 2), (4, 4, 1)}.

From Algorithm
matrices:

0
0
1
X(s) = 
0
1

0
1
X(s)3 = 
0
0

0

0
X(s)5 = 
0
0

2, we have the set of psedo-permutation
0
0
1
0
0
0
0
1

0
1
0
0
1
0
0
0

0
0
0
0

0
0
0
0



1 0
1
0 1
0
2
, X(s) = 
0 0
0
0 0
0


0 0
0

0
, X(s)4 = 0 0
0 0
0
0 0
0

0
1
.
0
0

0
0
0
1
0
0
1
0


0
0
,
1
0

0
0
,
0
1

Thus, algorithm 2 gives ls = 5. For l = 1,
we take all the flows in J (s) having in the form of
(1, 4, ·), (2, 3, ·), (3, 2, ·), (4, 1, ·) to I(s)1 . Therefore,
I(s)1

=

{(1, 4, 1), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 2, 1),
(3, 2, 2), (3, 2, 3), (4, 1, 1), (4, 1, 3)}.

For l = 2, we take all the flows in J (s) having in the form
of (1, 1, ·), (2, 2, ·), (3, 4, ·), (4, 3, ·) to I(s)2 . Therefore,
I(s)2 = {(1, 1, 1), (2, 2, 2), (3, 4, 2), (4, 3, 3)}.

For l = 3, we take all the flows in J (s) having in the form
of (1, 3, ·), (2, 1, ·), (4, 2, ·) to I(s)3 . Therefore,
I(s)3 = {(1, 3, 2), (2, 1, 3), (4, 2, 2)}.

For l = 4, we take all the flows in J (s) having in the form
of (3, 3, ·), (4, 4, ·) to I(s)4 . Therefore,
I(s)4 = {(3, 4, 2), (4, 4, 1)}.

For l = 5, we take all the flows in J (s) having in the form
of (2, 4, ·) to I(s)5 . Therefore,
I(s)5 = {(2, 4, 1)}.

We add I(s)1 , I(s)2 , I(s)3 , I(s)4 , I(s)5 to Γ in order.
When all flows with tentative start time less than s are
scheduled, we start processing the flows in I(s)1 on different

6

servers simultaneously. By processing, we mean that these
flows are enqueued in the corresponding links thus forming
a schedule for this task. We start to process flows in I(s)i+1
after all the flows in I(s)i are scheduled. Also, we process
flows in I(s + 1)1 after all flows in I(s)ls are scheduled.
V. A PPROXIMATION G UARANTEE

FOR

A. Approximation by truncating the number of time slots
Recall that the LP formulation (1)-(6) contains infinitely
many variables and constraints since t is summed till ∞.
Inspired by Lemma 4 and Theorem 5 from [19], we show
a pseudo-polynomial upper bound on the largest time index
for t in co-flow case.
Theorem 1. Suppose
max

k∈{1,··· ,N }

F2 , 2mN

N
X XX

E[Si,j,k ],

i∈M j∈M k=1

max

i,j∈M,k∈{1,··· ,N }

E[Si,j,k ].

Let F , 2F1 + F2 . Then, there is a set of optimal solutions of
LP ∗
|i, j ∈ M, k ∈ {1, · · · , N }, t ∈
LP relaxation (1)-(6): {yi,j,k,t
LP ∗
{0, 1, · · · }} such that yi,j,k,t
= 0 for i, j ∈ M, k ∈
{1, · · · , N }, t > F .
Proof. This result is akin to Lemma 4 in [19], which we prove
here for completeness. For any i ∈ M, we have the following:
N X
XX

yi,j,k,t

j∈M k=1 t≥2F1

=

N
XX

j∈M k=1

≤

P

j∈M

N X
XX

≤
≤

N
XX

i∈M k=1

P

k=1 E[time to start (i, j, k)]

2F1

F1
2F1
1
.
(8)
=
2
The first equality follows from the definition of yi,j,k,t . Recall
that
Pyi,j,k,t is the probability of starting flow (i, j, k) at time
t, t≥2F1 yi,j,k,t is the probability of starting flow (i, j, k) no
early than 2F1 . The second inequality follows from Markov’s
inequality. The expected start time of an
 arbitrary flow starting at server is upper bounded by maxk∈{1,··· ,N } rk +

P
P
PN
i∈M
j∈M
k=1 E[Si,j,k ] . Since there are at most mN
flows transferring data from server i. Therefore, the summation

i∈M

Pr(time to start (i, j, k) ≥ 2F1 )

PN

k=1

E[time to start (i, j, k)]
2F1

1
≤ .
2
Recall that pi,j,k,r is the probability that the Si,j,k is greater
or equal to r. Based on the definition of F2 and Markov’s
inequality, for any r ≥ F2 , we have the following:
pi,j,k,r = Pr[Si,j,k ≥ r]

≤

Pr[Si,j,k ≥ 2mN · E[Si,j,k ]]
1
.
2mN

≤

(9)

LP ∗
Now we define a set of new LP solution {yi,j,k,r
|i, j ∈
M, k ∈ {1, · · · , N }}:
 LP
yi,j,k,r
r < F,



 X LP
LP ∗
yi,j,k,r′
r = F,
yi,j,k,r
,

r ′ ≥F



0
r > F.

The new set of solutions will not get worse objective
function (1) since the change will not make the original CkLP
larger based on (5). Now we prove that the new set of solutions
is feasible, satisfying constraints (2)-(6). Satisfying of (2) and
(6) can be seen in a straightforward fashion and are thus
omitted.
LP ∗
LP
For (3), if s < F , yi,j,k,t
equals yi,j,k,t
for all t ∈ {0, · · · , s}
by definition, (3) remains the same:
N X
s
XX

Pr(time to start (i, j, k) ≥ 2F1 )

PN

yi,j,k,t

i∈M k=1 t≥2F1

NPSCS

In this section, we will show that the proposed algorithm,
NPSCS, is an approximation algorithm with bounded worst
case approximation factor. First, we will show that even though
the LP problem has unbounded time slots, we can upper bound
the number of time slots to be a pseudo-polynomial in the input
size. This will be followed by the approximation guarantee of
the proposed algorithm.

F1 , mN

of expected start time of all flows from i is bounded by F1 ,
leading to the third inequality.
Similarly, for any j ∈ M, we have the following:

j∈M k=1 t=0

LP ∗
yi,j,k,t
pi,j,k,s−t ≤ 1.

If s ≥ F ,
N X
s
XX

≤

LP ∗
yi,j,k,t
pi,j,k,s−t

j∈M k=1 t=0

=

N 2F
1 −1
XX
X

LP
yi,j,k,t
pi,j,k,s−t

j∈M k=1 t=0

+

N X
s
XX

LP ∗
yi,j,k,t
pi,j,k,s−t

j∈M k=1 t=2F1

≤

N 2F1 −1
N X
XX
1 XX X
LP
LP
yi,j,k,t
yi,j,k,t
+
2mN
t=0

≤

1 1
+ = 1.
2 2

j∈M k=1

j∈M k=1 t≥2F1

7

The first inequality follows from (9), pi,j,k,t ≤ 1, and the
LP ∗
definition of yi,j,k,t
. The second inequality follows from (8),
and yi,j,k,t ≤ 1.
LP ∗
LP
Similarly, for (4), if s < F , yi,j,k,t
equals yi,j,k,t
for all
t ∈ {0, · · · , s} by definition, (3) remains the same:
N X
s
XX

i∈M k=1 t=0

LP ∗
yi,j,k,t
pi,j,k,s−t ≤ 1.

If s ≥ F ,

N X
s
XX

=

LP ∗
yi,j,k,t
pi,j,k,s−t

i∈M k=1 t=0
N 2F
1 −1
XX
X

LP
yi,j,k,t
pi,j,k,s−t

N X
s
XX

LP ∗
pi,j,k,s−t
yi,j,k,t

i∈M k=1 t=2F1

≤

N 2F1 −1
N X
XX
1 XX X
LP
LP
yi,j,k,t
yi,j,k,t
+
2mN
t=0

≤

1 1
+
2 2
1.

=

i∈M k=1

Definition 4 (Efficient Size). Every stochastic co-flow can be
represented as a matrix D ∈ Rm×m with its entry Dij =
P
n
k=1 E[Si,j,k ] representing the expected size of its constituent
flow from server i to server j. The efficient size of a stochastic
co-flow is the maximum of the maximum column-sum and the
maximum row-sum of its representative matrix. Namely, the
efficient size of D is:
n
o
XX
XX
max max
E[Si,j,k ], max
E[Si,j,k ] .
i

i∈M k=1 t=0

+

grouped by tentative start time has expected efficient size less
or equal to one.

i∈M k=1 t≥2F1

The first inequality follows from (9), pi,j,k,t ≤ 1, and the
LP ∗
definition of yi,j,k,t
. The second inequality follows from (8),
and yi,j,k,t ≤ 1.
Thus, we have constructed a set of optimal solutions of LP
LP ∗
LP ∗
relaxation (1)-(6): {yi,j,k,t
}, satisfying yi,j,k,t
= 0 for i, j ∈
M, k ∈ {1, · · · , N }, t > F .
Based on this result, we have reduced the problem with
infinite number of variables to a truncated time-indexed LP of
pseudo-polynomial size.
We note that the intervals of geometrically increasing
lengths can be chosen, as in [20, Chapter 2.13]. In this
discretization, the first interval I0 = [0, 1], and the other
intervals are Il = [(1 + ǫ)l−1 , (1 + ǫ)l ] for l ≥ 1. This can lead
to solving an approximation of time-indexed LP, albeit at an
expense of losing a factor 1 + ǫ in the objective function.
B. Approximation Result
In this section, we will prove that NPSCS is an approximation
√ algorithm with a competitive ratio of (2 log m + 1)(1 +
m∆)(1 + m∆)(3 + ∆)/2, where ∆ is the upper bound of
CV[Si,j,k ]2 for all i, j ∈ M, k ∈ {1, · · · , N }. More formally,
we have the following result.
Theorem 2. We aim to optimize the weighted completion time
of N co-flows on m servers. The completion time of the k-th
coflow tasks under scheduling
algorithm NPSCS is at most
√
CkLP (2 log m + 1)(1 + m∆)(1 + m∆)(3 + ∆)/2, where ∆
is the upper bound of CV[Si,j,k ]2 for all i, j ∈ M, k ∈
2
{1, · · · , N }. CV[Si,j,k ]2 , (E[Si,j,k
] − E[Si,j,k ]2 )/E[Si,j,k ]2
is the squared coefficient of variation of Si,j,k .
Before the proof of Theorem 2, we give a definition of
efficient size for co-flow. We will later prove that each co-flow

j

j

k

i

k

From Definition 4, we note that every J (s) has representative matrix D(s).
To prove Theorem 2, we use four lemmas. The first lemma
proves that for all flows having the same tentative start time
s, the stochastic co-flows grouped by same tentative start
time J (s) has expected efficient size less or equal to 1. If
we assume the expected time to process a stochastic co-flow
with efficient size less or equal to 1 by Algorithm 2 has
upper bound H, namely the processing time for an arbitrary
J (s) is bounded by H, then the summation of expected time
scheduled before any flow with tentative start time s has upper
bound (s + 1/2)H.
Lemma 1. Assume the expected time to process a stochastic
co-flow with expected efficient size less or equal to 1 by
Algorithm 2 has upper bound H. If we schedule all of the N
co-flows by policy NPSCS, the total expected processing time
before flow (i, j, k) is at most (t(i, j, k) + 1/2)H. Namely,
the expected start time of flow (i, j, k) is less or equal to
(t(i, j, k) + 1/2)H, where t(i, j, k) is the tentative start time
of flow (i, j, k) in Algorithm 1. In other words, the start time
of set {I(s)1 , · · · , I(s)ls } is less or equal to (s + 1/2)H.
Proof. From the scheduling policy,
P r[t(i, j, k) = s] =

s
X
t=0

yi,j,k,t

pi,j,k,s−t
.
E[Si,j,k ]

(10)

From the above equation and constraints (3)-(4), we have
XX
max
E[Si,j,k′ ]P r[t(i, j, k ′ ) = s′ ]
i

j

k′ 6=k

′

=

max
i

s
XXX
j

k′ 6=k t′ =0

yi,j,k′ ,t′ pi,j,k′ ,s′ −t′ ≤ 1;

and
max
j

XX
i

E[Ti,j,k′ ]P r[t(i, j, k ′ ) = s′ ]

k′ 6=k
′

=

max
j

s
XXX
i

k′ 6=k t′ =0

yi,j,k′ ,t′ pi,j,k′ ,s′ −t′ ≤ 1.

Since we combine the set of flows with same tentative start
time s as a stochastic co-flow J (s), which has expected
efficient size less or equal to 1, the expected processing time
of each J (s) is upper bounded by H by assumption in this
lemma. In the proposed algorithm, the flows with less tentative

8

start time are scheduled earlier. Therefore, the summation
of expected time scheduled before co-flow (i, j, k) (suppose
t(i, j, k) = s) is at most
H

X

E[Si′ ,j ′ ,k′ ]

s−1
X

P r[t(i′ , j ′ , k ′ ) = s′ ]

their coefficient of variation is ∆, then the random variable
T1 + T2 + · · · + Tk has coefficient of variation that is upper
bounded by ∆.
Proof. We have
E[T1 + T2 + · · · + Tk ] =

k
X

E[Ti ],

V ar(T1 + T2 + · · · + Tk ) =

k
X

V ar(Ti ),

s′ =0

(i′ ,j ′ ,k′ )6=(i,j,k)

1
1
P r[t(i′ , j ′ , k ′ ) = s] ≤ (s + )H.
2
2
This proves the required result.


+

lemma 1 shows that the expected start time of any flow
(i, j, k) is at most (t(i, j, k) + 1/2)H. corollary 1, given next,
gives an upper bound of expected completion time of flow
(i, j, k).
Corollary 1. Assume the expected time to process a stochastic co-flow with expected efficient size less or equal to 1
by algorithm 2 has upper bound H. For any i, j ∈ M,
k ∈ {1, · · · , N }, and s ∈ {0, 1, · · · }, given t(i, j, k) = s,
the conditional upper bound of expected completion time of
flow (i, j, k), E[Ci,j,k |t(i, j, k) = s] is at most (s + 1/2)H +
E[Si,j,k ].
Proof. The result follows directly from Lemma 1 since the
expected completion time can be obtained by adding the
expected start time and the transfer time.
Proposition 1 (Lemma 2, [19]). For every i, j ∈ M, k ∈
{1, · · · , N } and r ∈ {0, 1, · · · }, we have
X
1 + CV[Si,j,k ]2
1 pi,j,k,r
=
E[Si,j,k ],
(r + )
2 E[Si,j,k ]
2
r∈Z≥0

where CV[Si,j,k ]2 is Si,j,k ’s squared coefficient of variation.
The following few results will be needed to prove lemma 2
which gives an upper bound for H given in lemma 1.
The next proposition is from Theorem 6 in [15], giving us
a guarantee for GLJD decomposition
Proposition 2 (Theorem 6, [15]). For any s ∈ {0, 1, · · · }, if a
co-flow J (s) to be processed on m servers has an efficient size
less or equal to 1, GLJD
P provides a decomposition J (s) =
s
≤
⊔ll=1
X l such that
l∈{1,··· ,ls } max(i,j,k)∈X l E[Si,j,k ]
(2 log m + 1).
The next corollary, Corollary 2, follows directly from the
Proposition 2.
Corollary 2. Suppose the number of servers |M| = m ≥ 2.
s
For any s ∈ {0, 1, · · · }, J (s) = ⊔ll=1
X(s)l , we have
P ls
l=1 max(i,j,k)∈X(s)l E[Si,j,k ] ≤ (2 log m + 1).
Recall that in Step 3 of algorithm 1, we sum up all flows
between same servers with same tentative start time, and regard the summed flow as a single flow. The following lemma 2
shows that the coefficient of variations of the resulting flow
will be bounded by the one of the original flows.
Lemma 2. Suppose T1 , T2 , · · · , Tk are k independent random
variables with expectation E[Ti ] (i ∈ {1, · · · , k}), and variances V ar(Ti ) (i ∈ {1, · · · , k}). Suppose the upper bound of

i=1

and
i=1

since T1 , T2 , · · · , Tk are independent.
Recall that the coefficient of variation of a random variablepT is V ar(S)/T[S]. Note that ∆ =
maxi∈{1,··· ,k} V ar(Ti )/E[Ti ]. Therefore,
p
V ar(T1 + T2 + · · · + Tk )
E[T1 + T2 + · · · + Tk ]
p
V ar(T1 ) + · · · + V ar(Tk )
=
E[T1 ] + · · · + E[Tk ]
p
∆ E[T1 ]2 + · · · + E[Tk ]2
≤
E[T1 ] + · · · + E[Tk ]
≤ ∆.
The first equality follows from the independence between
T1 , · · · , Tk , the first inequality follows from Jensen’s inequality.
2
provides
a
upper
bound
of
PCorollary
ls
max
l
E[S
].
However,
we
are
more
i,j,k
(i,j,k)∈X(s)
l=1
Pls
interested in
l=1 E[max(i,j,Si,j,D(s) )∈X(s)l Si,j,D(s) ] which
is the expected total processing time of all co-flows X(s)l
(l ∈ {1, · · · , ls }) from J (s). The following proposition 3
connects the two expressions.
Proposition 3 ([21]). If T1 , T2 , · · · , Tm are m random variables with finite means and finite variances, then
p
√
E[max Ti ] ≤ max E[Ti ] + m max V ar(Ti ),
i

i

i

In the following Lemma, we give a upper bound for H in
lemma 1.
Lemma 3. For every s ∈ {0, 1, · · · }, the expected total
processing
time of J (s) has upper bound (2 log m + 1)(1 +
√
m∆), where ∆ is the upper bound of squared coefficient
of variation of all processing times, and m is the number
of servers. Namely, the upper bound on the expected time to
process a stochastic co-flow with expected efficient size less
or equal to 1 is given as
√
H = (2 log m + 1)(1 + m∆).
Proof. The set of stochastic flows J (s) for any s ∈
{0, 1, · · · }, is a stochastic co-flow with efficient size less or
equal to one:
o
n
X
X
E[Si,j,k ] ≤ 1.
E[Si,j,k ], max
max
max
(i,j,k)∈σ(s)

i

j

j

i

9

We use their representative matrice D(s) (∀s ∈
{0, 1, · · · }) for GLJD algorithm. Suppose we get ls coflows X(s)1 , · · · , X(s)ls with perfect matchings between the
servers. From corollary 2,

(a)

=

E[Ci,j,k ]
X
E[Ci,j,k |t(i, j, k) = s]P r[t(i, j, k) = s]

s∈Z≥0
(b)

≤

ls
X
l=1

max

(i,j,k)∈X(s)l

E[Si,j,k ] ≤ 2 log m + 1.

(11)

(c)

≤

(d)

≤

However, the ultimate processing time for co-flow J (s) is
E[max(i,j,k)∈X(s)l Si,j,k ]. From Proposition 3, the expected
total processing time for all co-flows {X(s)1 , · · · , X(s)ls } is

≤

(f )

≤

=

l=1

E[ max

(i,j,k)∈X l

Si,j,k ] ≤

ls
X
l=1

max

(i,j,k)∈X l

E[Si,j,k ]( 1 +

√

m∆).
(12)

Combining the inequalities (11)-(12), the expected processing time of stochastic co-flow J (s) is at most

(h)

=

≤

≤
≤

l=1
ls
X
l=1

(k)

max

(i,j,k)∈X(s)l

max

(i,j,k)∈X(s)l

≤

Si,j,k ]

X


X 
1
pi,j,k,r
H(t + r + ) + E[Si,j,k ] yi,j,k,t
2
E[Si,j,k ]

r∈Z≥0 t∈Z≥0

H

X

X 

t+r+

r∈Z≥0 t∈Z≥0

H

X


X
1 pi,j,k,r 
(r + )
yi,j,k,t t + E[Si,j,k ] +
2 E[Si,j,k ]

X



1 + CV[Si,j,k ]2
E[Si,j,k ]
yi,j,k,t t + E[Si,j,k ] +
2

X



3 + CV[Si,j,k ]2
yi,j,k,t t +
E[Si,j,k ]
2

X

yi,j,k,t


3 + CV[Si,j,k ]2
t + E[Si,j,k ]
2

X

yi,j,k,t


3+∆
t + E[Si,j,k ]
2

t∈Z≥0

H
H
H

r∈Z≥0

t∈Z≥0

H

t∈Z≥0

H


pi,j,k,r
1
+ E[Si,j,k ] yi,j,k,t
2
E[Si,j,k ]

3 + ∆ LP
Ci,j,k
2

√
3 + ∆ LP
m∆)
Ci,j,k ,
2
where ∆ is the upper bound of CV[Si,j,k ]2 for all i, j ∈ M,
k ∈ {1, · · · , N }. The above steps hold because of the
following. (a) is uncondtioning expectation
X
E[X] =
E[X|Y = y]P r[Y = y],
(l)

E[Si,j,k ]( 1 +

(2 log m + 1)(1 +

s∈Z≥0

t∈Z≥0
(i)

≤

E[

s
X
X 
1
pi,j,k,s−t
H(s + ) + E[Si,j,k ]
yi,j.k.t
2
E[Si,j,k ]
t=0

t∈Z≥0

(j)

ls
X

s∈Z≥0

(e)

(g)
ls
X


X 
1
H(s + ) + E[Si,j,k ] P r[t(i, j, k) = s]
2

√

m∆)

√
m∆),

≤

(2 log m + 1)(1 +

y

which proves the result as in the statement of the Lemma.

Having the required results, we will now prove theorem 2.

(b) follows from Corollary 1, (c) follows from (10), (d) sets
r = s − t, (e) extracts H outside since H ≥ 1, (f ) exchanges
the summation order of s and t, (g) follows from proposition 1,
(h) combines the two terms with E[Si,j,k ] together, (i) extracts
3+CV[Si,j,k ]2
≥ 1 out, (j) follows from the notation that ∆ is
2
the upper bound of all squared coefficient of variation of all
variables Si,j,k ∀i, j ∈ M, k ∈ {1, · · · , N }, (k) follows from
(5), and (l) follows from Lemma 3.
Since E[Ck ] = E[maxi,j∈[m] C(i,j,k) ], note that {(i, j) :
i, j ∈ {1, · · · , m}} contains m2 elements, applying Proposition 3, we have
√
E[Ck ] ≤ CkLP (2 log m + 1)(1 + m∆)(1 + m∆)(3 + ∆)/2.
This proves the result as in the statement of Theorem 2.

Proof. Recall that yi,j,k,t is the probability of starting flow
(i, j, k) at time slot t.
PThe expected completion time of flow
(i, j, k): E[Ci,j,k ] is t∈Z≥0 yi,j,k,t (t + E[Si,j,k ]).

Remark 1. We note that when the flow sizes are deterministic,
the result in the statement of Theorem 2 can be used with
∆ = 0.

10

VI. R ESULTS FOR

Further, we have

GENERAL RELEASE TIMES

(a)

=

E[C(i,j,k) ]
X
E[C(i,j,k) |t(i, j, k) = s]P r[t(i, j, k) = s]

s∈Z≥0
(b)

≤

So far, we assumed that the co-flow tasks were released at
time zero. If flow (i, j, k) has release time ri,j,k , it has zero
possibility to be processed before ri,j,k . We can simply add a
set of constraints to LP problem (1)-(6):

(c)

≤

(d)

≤


X 
1
H(2s + ) + E[Si,j,k ] P r[t(i, j, k) = s]
2

s∈Z≥0

s
X
X 
pi,j,k,s−t
1
yi,j,k,t
H(2s + ) + E[Si,j,k ]
2
E[Si,j,k ]
t=0

s∈Z≥0

X

r∈Z≥0 t∈Z≥0

(e)

≤

∀i, j ∈ M, k ∈ {1, · · · , N }, t < ri,j,k .

yi,j,k,t = 0

≤
=

E[Ci,j,k |t(i, j, k) = s]
1
s + (s + )H + E[Si,j,k ]
2
1
(2s + )H + E[Si,j,k ],
2

2t + 2r +

r∈Z≥0 t∈Z≥0

X


X
1 pi,j,k,r 
(2r + )
yi,j,k,t 2t + E[Si,j,k ] +
2 E[Si,j,k ]


X
1 pi,j,k,r 
(r + )
H
yi,j,k,t 2t + E[Si,j,k ] + 2
2 E[Si,j,k ]
r∈Z≥0
t∈Z≥0


X

H
yi,j,k,t 2t + E[Si,j,k ] + 1 + CV[Si,j,k ]2 E[Si,j,k ]

=

t∈Z≥0

r∈Z≥0

X

t∈Z≥0

(i)

=

H

X




yi,j,k,t 2t + 2 + CV[Si,j,k ]2 E[Si,j,k ]

X

yi,j,k,t 2 + CV[Si,j,k ]2

X



yi,j,k,t 2 + ∆ t + E[Si,j,k ]

t∈Z≥0

H

t∈Z≥0
(k)

≤

(l)

H

t∈Z≥0

≤

LP
H(2 + ∆)C(i,j,k)

≤

(2 log m + 1)(1 +

(m)



t + E[Si,j,k ]

√
LP
,
m∆)(2 + ∆)C(i,j,k)

where ∆ is the upper bound of ∆ij for all i, j ∈ [m], m is
the number of servers. The steps above can be explained as
follows. (a) is uncondtioning expectation
E[X] =

X

E[X|Y = y]P r[Y = y],

y

(b) follows from (13), (c) follows from (10), (d) sets r = s−t,
(e) extracts H out since H ≥ 1, (f ) exchanges the summation
order of s and t, (g) extract 2 out, (h) follows from Proposition
1, (i) combines the two terms having E[Si,j,k ], (j) follows
from the notation that ∆ is the upper bound of all squared
coefficient of all variables Si,j,k ∀i, j ∈ M, k ∈ {1, · · · , N },
(k) follows from (5), and (l) follows from Lemma 3.
Since E[Ck ] = E[maxi,j∈[m] C(i,j,k) ], applying Proposition
3, we have
E[Ck ] ≤ CkLP (2 log m + 1)(1 +

(13)


1
pi,j,k,r
+ E[Si,j,k ] yi,j,k,t
2
E[Si,j,k ]

(g)

=

Since H ≥ 1, we have

X 

H

(j)

Proof. If a flow (i, j, k) has release time more than s, then
yi,j,k,t = 0 for all t ≤ s. The tentative time generated cannot
be less or equal to s. In other word, a flow with tentative
start time s has release time less or equal to s. The expected
completion time of a flow with tentative start time s is less
than the summation of its release time (less than s) and the
expected total processing time of flows before ((s + 1/2)H)
by Lemma 1.

X

≤

(h)

Theorem 3. With release times constraints, the completion
time of the k-th coflow tasks under scheduling
algorithm
√
NPSCS is at most CkLP (2 log m+ 1)(1 + m∆)(1 + m∆)(2 +
∆), where ∆ is the upper bound of CV[Si,j,k ]2 for all
2
i, j ∈ M, k ∈ {1, · · · , N }. CV[Si,j,k ]2 , (E[Si,j,k
]−
2
2
E[Si,j,k ] )/E[Si,j,k ] is the squared coefficient of variation of
Si,j,k .

H

(f )

≤

We propose the same LP based algorithm, NPSCS, for this
general case with the above additional constraint in the linear
program. With this modification, the following result gives the
approximation result for general release times.


X 
pi,j,k,r
1
H(2t + 2r + ) + E[Si,j,k ] yi,j,k,t
2
E[Si,j,k ]

√
m∆)(1 + m∆)(2 + ∆).

This proves the result as in the statement of the Theorem.

11

We also note that Theorem 1 can also be easily extended
with general release times, by changing
F1 , mN



max

k∈{1,··· ,N },i∈M,j∈M

ri,j,k +

N
X XX


E[Si,j,k ] .

i∈M j∈M k=1

(14)
Thus, the number of time slots can be truncated, yielding a
polynomial time algorithm.
Remark 2. We note that when the flow sizes are deterministic,
the result in the statement of Theorem 3 can be used with
∆ = 0.
VII. C ONCLUSIONS
This paper studies stochastic non-preemptive co-flow
scheduling, and gives an approximation algorithm. The results are provided for both zero and general release times.
The results can also be specialized to deterministic co-flow
scheduling.
R EFERENCES
[1] R. Mao, V. Aggarwal, and M. Chiang, “Stochastic non-preemptive
co-flow scheduling with time-indexed relaxation,” in IEEE Infocom
Worshop on Big Data in Cloud Performance (DCPerf), Apr 2018.
[2] J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on
large clusters,” Commun. ACM, vol. 51, no. 1, pp. 107–113, Jan. 2008.
[Online]. Available: http://doi.acm.org/10.1145/1327452.1327492
[3] K. Shvachko, H. Kuang, S. Radia, and R. Chansler, “The hadoop
distributed file system,” in Mass storage systems and technologies
(MSST), 2010 IEEE 26th symposium on. IEEE, 2010, pp. 1–10.
[4] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley,
M. J. Franklin, S. Shenker, and I. Stoica, “Resilient distributed datasets:
A fault-tolerant abstraction for in-memory cluster computing,” in Proceedings of the 9th USENIX conference on Networked Systems Design
and Implementation. USENIX Association, 2012, pp. 2–2.
[5] google.
Google
dataflow.
[Online].
Available:
https://www.google.com/events/io
[6] M. Chowdhury, M. Zaharia, J. Ma, M. I. Jordan, and I. Stoica,
“Managing data transfers in computer clusters with orchestra,” in ACM
SIGCOMM Computer Communication Review, vol. 41, no. 4. ACM,
2011, pp. 98–109.
[7] M. Chowdhury and I. Stoica, “Coflow: A networking abstraction
for cluster applications,” in Proceedings of the 11th ACM
Workshop on Hot Topics in Networks, ser. HotNets-XI. New
York, NY, USA: ACM, 2012, pp. 31–36. [Online]. Available:
http://doi.acm.org/10.1145/2390231.2390237
[8] E. L. Lawler, J. K. Lenstra, A. H. R. Kan, and D. B. Shmoys, Sequencing
and scheduling: Algorithms and complexity.
CWI. Department of
Operations Research, Statistics, and System Theory [BS], 1989.
[9] K. M. Kavi, R. Giorgi, and J. Arul, “Scheduled dataflow: Execution
paradigm, architecture, and performance evaluation,” IEEE Transactions
on Computers, vol. 50, no. 8, pp. 834–846, 2001.
[10] R. Yu, G. Xue, X. Zhang, and J. Tang, “Non-preemptive coflow scheduling and routing,” in Global Communications Conference (GLOBECOM),
2016 IEEE. IEEE, 2016, pp. 1–6.
[11] Z. Qiu, C. Stein, and Y. Zhong, “Minimizing the total
weighted completion time of coflows in datacenter networks,”
in Proceedings of the 27th ACM Symposium on Parallelism
in Algorithms and Architectures, ser. SPAA ’15. New York,
NY, USA: ACM, 2015, pp. 294–303. [Online]. Available:
http://doi.acm.org/10.1145/2755573.2755592
[12] M. Shafiee and J. Ghaderi, “Scheduling coflows in datacenter networks:
Improved bound for total weighted completion time,” in Proceedings of
the 2017 ACM SIGMETRICS/International Conference on Measurement
and Modeling of Computer Systems. ACM, 2017, pp. 29–30.
[13] S. Im and M. Purohit, “A tight approximation for coflow scheduling for minimizing total weighted completion
time,” CoRR, vol. abs/1707.04331, 2017. [Online]. Available:
http://arxiv.org/abs/1707.04331

[14] M. H. Rothkopf, “Scheduling with random service times,” Management
Science, vol. 12, no. 9, pp. 707–713, 1966.
[15] I. Keslassy, M. Kodialam, T. Lakshman, and D. Stiliadis, “On guaranteed
smooth scheduling for input-queued switches,” in INFOCOM 2003.
Twenty-Second Annual Joint Conference of the IEEE Computer and
Communications. IEEE Societies, vol. 2. IEEE, 2003, pp. 1384–1394.
[16] M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow
scheduling with varys,” SIGCOMM Comput. Commun. Rev.,
vol. 44, no. 4, pp. 443–454, Aug. 2014. [Online]. Available:
http://doi.acm.org/10.1145/2740070.2626315
[17] N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input-queued switch,” IEEE Transactions on
Communications, vol. 47, no. 8, pp. 1260–1267, 1999.
[18] N. McKeown, “The islip scheduling algorithm for input-queued
switches,” IEEE/ACM Transactions On Networking, vol. 7, no. 2, pp.
188–201, 1999.
[19] M. Skutella, M. Sviridenko, and M. Uetz, “Unrelated machine scheduling with stochastic processing times,” Mathematics of operations research, vol. 41, no. 3, pp. 851–864, 2016.
[20] M. Skutella, Approximation and randomization in scheduling. Cuvillier,
1998.
[21] L. P. Devroye, “Inequalities for the completion times of stochastic pert
networks,” Mathematics of Operations Research, vol. 4, no. 4, pp. 441–
447, 1979.

