# Fair Coflow Scheduling via Controlled Slowdown

Francesco De Pellegrini∗, Vaibhav Kumar Gupta†, Rachid El Azouzi∗,
Serigne Gueye∗, Cedric Richier∗ and Jeremie Leguay⋆ ∗Laboratoire informatique
d’Avignon (LIA), Avignon University, France, †He was with LIA, Avignon
University, France and now he is with Interdisciplinary Centre for Security,
Reliability and Trust (SnT), University of Luxembourg, ⋆Huawei Technologies,
Paris Research Center, France.

###### Abstract

The average coflow completion time (CCT) is the standard performance metric in
coflow scheduling. However, standard CCT minimization may introduce unfairness
between the data transfer phase of different computing jobs. Thus, while
progress guarantees have been introduced in the literature to mitigate this
fairness issue, the trade-off between fairness and efficiency of data transfer
is hard to control.

This paper introduces a fairness framework for coflow scheduling based on the
concept of slowdown, i.e., the performance loss of a coflow compared to
isolation. By controlling the slowdown it is possible to enforce a target
coflow progress while minimizing the average CCT. In the proposed framework,
the minimum slowdown for a batch of coflows can be determined in polynomial
time. By showing the equivalence with Gaussian elimination, slowdown
constraints are introduced into primal-dual iterations of the CoFair
algorithm. The algorithm extends the class of the $\sigma$-order schedulers to
solve the fair coflow scheduling problem in polynomial time. It provides a
$4$-approximation of the average CCT w.r.t. an optimal scheduler. Extensive
numerical results demonstrate that this approach can trade off average CCT for
slowdown more efficiently than existing state of the art schedulers.

###### Index Terms:

data transfer, coflow scheduling, fairness, progress, primal-dual scheduler.

##  I Introduction

The coflow abstraction has been introduced in the seminal paper [1]. A coflow
denotes a group of flows produced by data-intensive computing frameworks,
e.g., Map Reduce, Giraph and Spark [2, 3, 4], during their data transfer
phases. In the same fashion, the workflows of most data-intensive machine
learning applications are based on data-transfers and operated by distributing
training tasks over hundreds of individual compute nodes. A well-studied
example of data transfer step is the shuffle phase of Hadoop MapReduce. The
shuffle phase acts as a synchronization barrier since the next phase of the
computation cannot be pursued until the end of the shuffle data transfer. Once
each mapper node finishes running their job, partial results are fetched in
the form of HTTP connections by peer reducer nodes and final results can be
generated for the next computation phase or storage. At the application level,
the shuffle phase has been shown to represent a significant part of the total
computation time [5]. For this reason, efficient coflow scheduling has become
a key aspect of traffic engineering in modern datacenters [6, 7, 8, 9, 10].

The standard metric to measure coflow scheduling performance is the weighted
Coflow Completion Time (CCT), i.e., the average time by which the last flow of
a coflow is completed. Minimizing the average CCT is indeed the appropriate
goal in order to increase the rate of computing jobs dispatched in a
datacenter and improve the execution time of applications. The corresponding
minimization problem is complicated by the fact that a shared datacenter
fabric can be contended by hundreds of coflows at the same time. Thus,
multiple congested links may appear under concurrent demands. In the last ten
years, the problem of average CCT minimization has been addressed by several
authors [1, 5, 11, 8], shading light on its complexity and devising several
algorithmic solutions. The problem is found NP-hard by reduction to the open-
shop problem [12], a mainstream operation research problem where jobs are
scheduled on multiple machines. While inapproximability below a factor $2$ has
been proved [7], to date the best deterministic approximation ratio is $4$ in
the case when coflows are released at same time[11, 8, 13].

In the literature, maximizing network performance is known to entail potential
unfairness among different flows [14]. Thus, the notion of per-flow fairness
has been studied to balance the resource allocation, i.e., link utilization,
among different flows. Max-min fairness and proportional fairness are
reference concepts in this context and a series of fundamental works on
utility-based fairness have showed that both the notions can be compounded
under the larger concept of $\alpha$-fairness [15].

Coflow fairness. Minimizing the average CCT suffers a similar fairness issue
due to starvation [16] and fairness has been studied in the context of coflow
scheduling as well [17][18][19][20]. To obtain a resource allocation able to
achieve a required trade-off between average CCT and fairness, it is tempting
to directly use CCT as the variable in conventional fairness utility
functions. However, a major obstacle to this approach exist. In fact, the
definition of CCT entails a minimization, so that using CCT as argument of
standard smooth convex functions such as the $\alpha$-fair utility leads to
minimization problems neither convex nor differentiable. The workaround is to
allow for a constant rate allocation [21]. But, CCT minimization is a finite
horizon problem for which optimizing stationary rates leads to suboptimal
resource allocation.

Fairness in coflow scheduling relies on the notion of coflow progress, i.e.,
by guaranteeing a minimum resource allocation to coflows [20, 18, 19]. In
particular, [19] studied the trade-off between performance and fairness by
showing that it is possible to balance between minimum coflow progress and
average CCT. In practice, since coflow links have intertwined dependencies,
the coflow progress approach builds on the notion of DRF (Dominant Resource
Fairness) [22] in order to allocate rates based on the maximum per port
demand. The progress of a coflow tracks the slowest flow – determining its CCT
– on the related bottleneck port at each instant, while all remaining flows of
the coflow are slowed down in order to improve network utilization without
impairing the CCT. Finally, a max-min fair argument grants a bottleneck share
per coflow in the form of a minimum rate allocation, i.e., a so-called minimum
coflow progress guarantee. Apart few exceptions [10], any further performance
optimization, e.g., minimization of average CCT or maximization of port
utilization, is pursued on top of this baseline constant rate allocation [19,
20, 18], denoted as static progress in the rest of the paper. Note that, from
the perspective of a coflow being served, this is just a lower bound on the
average rate received before completion.

The notion of coflow fairness based on static progress has limitations as
detailed formally in the next sections. In fact, it may not account for the
structure of coflows and their conflicting demands. Furthermore, ensuring a
constant minimal allocation corresponds to a non-preemptive definition of
progress because it requires every coflow to send a minimum amount of data
with no interruption over each engaged port.

Main contributions. The fairness framework introduced in this paper is based
on a notion of progress which is the average rate granted to a coflow while in
service. The coflow progress is tuned by controlling the inverse metric, e.g.,
the slowdown [20]. The slowdown measures the additional delay on the data
transfer time of a coflow compared to isolation, i.e., when a coflow is
scheduled alone in the datacenter fabric. An optimal scheduling problem is
formulated under a generalized slowdown constraint, obtaining a notion of
fairness more general than the notion of progress used in the literature.
Similar to $\alpha$-fair scheduling [15], the slowdown constraint acts as a
single parameter able to strike the trade-off between efficiency, i.e., CCT
performance, and fairness, i.e., the slowdown experienced by a coflow.
Furthermore, a fully polynomial time algorithm, namely MPS (Minimum Primal
Slowdown) provides an accurate estimation of the minimum feasible slowdown for
a batch of coflows.

Finally, a scheduling algorithm CoFair extends the family of the primal-dual
algorithms [23, 8]: by using the output of MPS, it produces a primal-feasible
$\sigma$-order and an approximation factor of $4$.

Actually, the target coflow progress is attained based on a per coflow
prioritization, avoiding expensive rate-control mechanisms. CoFair is tested
against Sincronia [8], near-optimal for CCT minimization, and against Utopia
[10] for coflow fairness. CoFair performs closely to Sincronia in CCT and to
Utopia in slowdown, thus improving the tradeoff, with low complexity since no
rate control is required. To the best of the authors’ knowledge, the formal
framework for fair scheduling in data-transfer based on controlled slowdown
and the solutions provided in this paper are new contributions to the
discussion on enforcing fairness in coflow scheduling.

The paper is organized as follows. Sec. II resumes existing works on fair
coflow scheduling. Sec. III introduces the system model and the relations
between CCT, coflow progress and slowdown. Sec. IV describes the mathematical
framework as a scheduling problem with slowdown constraints and its
feasibility. Algorithmic solutions are proposed in Sec. VI in the set of
primal-feasible $\sigma$-order schedulers. Sec. VII reports on numerical
results and a concluding section ends the paper.

##  II Related works

In the coflow literature only a few papers deal with fairness issues. The
seminal work [1] introduced the weighted CCT as objective function and later
works pursued same approach, e.g., [24], even though the relation between
coflow weights, CCT and coflow fairness remains elusive. In general, fairness
metrics based either on weights or on constant rate allocation [18, 24] lead
to sub-optimal scheduler and the usage of the CCT geometric mean [18] tends to
privilege shorter coflows. In the scheduler Varys [12] coflow prioritization
has been introduced as a means to mitigate starvation of coflows with low
priority. Actually, the smallest-effective-bottleneck-first heuristic used in
Varys is a pre-emptive scheduling which prioritizes greedily a coflow with the
smallest remaining bottleneck’s completion time.

Thus, granting a constant fraction of port bandwidth per coflow became the
accepted notion of coflow progress adopted later on in the literature [20,
19]. This coflow progress guarantee – already denoted static progress – has
been formalized for the first time in [20]. However, in that context the
progress is as a static rate constraint under the general objective of
maximizing the fabric utilization. The idea of a progress constraint coupled
to the CCT minimization appeared first in [19], where the (static) progress of
each flow is to be set above certain target threshold.

An interesting attempt to develop a formal framework based on max-min fairness
has been presented [17], based on lexicographic ordering for flow-level rate
allocation [25]. However, due to its ease of implementation, the notion of
fairness by static coflow progress guarantees has been preferred in the
literature. Other authors [26] define the fairness degree of a data-transfer
scheme with respect to standard schemes such as Hug [20] or DFR [22].

More recently, a relative fairness concept has been introduced in order to
compare coflow schedulers to benchmarks such as Hug or DFR [26]. In
particular, [10] has proposed a long term isolation guarantee by providing a
bound on CCTs relative to DRF performance. While this type of bound resembles
the slowdown constraint introduced in this work, the CCT-slowdown tradeoff
cannot be controlled.

In the coflow deadline satisfaction (CDS) problem [27, 28] each coflow is
subject to a completion deadline similar to a slowdown constraint. However, in
that context the target is to operate joint coflow admission control and
scheduling to maximize the number of admitted coflows which respect their
deadlines.

The solution proposed in this paper is rooted on the analysis of a scheduling
problem where the minimal slowdown constraint is connected to a primal-dual
formulation. The resulting scheduler has no need to perform rate control and
it can be fully implemented by greedy rate allocation via priority queuing
[8]. The key technical result is the equivalence of the weight adjustment step
introduced in [23][Alg. 3.1] – later applied in [8] to coflow scheduling –
with Gaussian elimination. Coupled with the novel results on primal-
feasibility, this leads to an approximation solution based on a $\sigma$-order
prioritization algorithm under generalized slowdown constraints.

In the rest of the paper, reference solutions are near-optimal Sincronia [8]
for CCT minimization and Utopia [10] for coflow fairness.

##  III Motivations

###  III-A System model

Symbol |  Meaning
---|---
${\mathscr{L}}$ |  set of switch links $k=1,\ldots,2M$
${\mathscr{M}}$ |  coflow schedule
${\mathscr{C}}$ |  set of coflows ${\mathscr{C}}=\\{1,\ldots,N\\}$
${\mathscr{F}}_{j}$ |  set of flows of coflow $j$; $n_{j}=|{\mathscr{F}}_{j}|$ (coflow width)
$p_{\ell j}$ |  volume of coflow $j$ on port $\ell$
$C_{j}$ |  coflow completion time for coflow $j$
$w_{j}$ |  weight of coflow $j$
$r_{j}$ |  release time of coflow $j$
$E$ |  slowdown constraint
$x_{j}^{i}(t)$ |  fraction of flow $i$ of coflow $j$ scheduled in slot $t$
$Y_{j}^{i}(t)$ |  progress of flow $i$ of coflow $j$ at time $t$
$Z_{j}(t)$ |  completed fraction of coflow $j$ at time $t$
$Z_{j}^{i}(t)$ |  completed fraction of flow $i$ of coflow $j$ at time $t$
$x_{j}^{i}(t)$ |  fraction of flow $i$ of coflow $j$ at time $t$
$X_{j}(t)$ |  indicating variable for coflow $j$ at slot $t$ (binary)
$X_{j}^{i}(t)$ |  indicating variable for for $i$ of. coflow $j$ at slot $t$ (binary)
$B_{\ell}$ |  capacity of link $\ell$
$T$ |  time horizon
$\Delta$ |  time slot duration
TABLE I: List of Key Notations

The most popular coflow scheduling model is based on a non blocking switch
connection of the type reported in Fig. 1, often called the Big Switch model.
This model is adequate because the bisection bandwidth of modern datacenters
exceeds access capacity, so that congestion events occur at the inbound or
outbound ports of top-of-rack switches. From now on the term link and port
will be used interchangeably. The set of switch links is
${\mathscr{L}}=\\{1,\ldots,2M\\}$, where links $1\leq\ell\leq M$ are ingress
ports and $M+1\leq\ell\leq 2M$ are egress ports. Each port has capacity
${B_{\ell}}$.

Let ${\mathscr{C}}=\\{1,\ldots,N\\}$ be an input set of coflows, i.e., a
batch. Each coflow $j$ is a set ${\mathscr{F}}_{j}$ of $n_{j}$ flows and a
flow represents a shuffle connection over a pair of input-output ports. The
release time $r_{j}\geq 0$ of coflow $j$ is the time when its shuffle phase
starts. A component flow $i\in{\mathscr{F}}_{j}$ has volume $v_{j}^{i}$. The
size of coflow $j$, that is the total volume of coflow $j$, is denoted by
$V_{j}=\sum_{i\in{\mathscr{F}}_{j}}v_{j}^{i}$. Let $\chi_{j}^{i}(\ell)$
indicate if flow $i\in{\mathscr{F}}_{j}$ is active on port $\ell$. The volume
of coflow $j$ active on port $\ell$ is denoted

$p_{\ell j}=\sum\limits_{i\in{\mathscr{F}}_{j}}v_{j}^{i}\chi_{j}^{i}(\ell)$

Tab. I summarizes all the important notations and their descriptions.

Let $C_{j}$ be the CCT of coflow $j$: $C_{j}$ is the epoch when the last flow
in ${\mathscr{F}}_{j}$ is fully transferred. Let $C_{j}^{0}$ be the coflow
completion time in isolation, i.e., if all network resources serve solely the
tagged coflow. It holds
$C_{j}^{0}=:r_{j}+\max\limits_{l\in{\mathscr{L}}}\frac{1}{B_{\ell}}\sum_{i\in{\mathscr{F}}_{j}}v_{j}^{i}\chi_{j}^{i}(\ell)$.
The standard coflow scheduling problem corresponds to determine a coflow
schedule ${\mathscr{M}}$ able to minimize the weighted sum of the CCTs under
the capacity constraints imposed by the network fabric. A coflow schedule
${\mathscr{M}}$ provides the set of rates which are assigned to each flow of
each coflow per port. The large class of $\sigma$-order schedulers [7], for
instance, prescribes to respect a static preemption priority $\sigma$ and only
requires monitoring of coflows at ingress/egress (I/E) ports of the Big
Switch. As proved in [8], the efficiency loss w.r.t. an optimal scheduler
respecting the given priority $\sigma$ is at most a factor $2$. In the
numerical evaluations in Sec.VII, rates are assigned following a strict
priority rule, namely the greedy rate allocation policy [8]. In practice, this
rule can be implemented with a priority queuing scheduler with a number of
queues equal to the number of coflows.

VUVUVUV$\ell_{3}$$\ell_{2}$$\ell_{1}$$\ell_{6}$$\ell_{5}$$\ell_{4}$

Figure 1: Coflow scheduling over a $3\times 3$ datacenter fabric with three
ingress and threee egress ports
${\mathscr{L}}=\\{\ell_{1},\ldots,\ell_{6}\\}$. Flows in ingress ports are
organized by destinations and color-coded by coflows: $j=1$ orange and $j=2$
blue.

###  III-B Static coflow progress

In the coflow literature, the standard definition of fairness [20, 18] is
based on the notion of coflow progress. Given an input batch of coflows, the
objective is to minimize the weighted CCT while ensuring that every coflow has
a target minimum progress per link, e.g., per input or output port in the Big
Switch model. Let $a_{\ell j}$ be the rate guaranteed to coflow $j$ on port
$\ell$. The progress of coflow $j$ is defined as

$P_{j}=\min_{\ell\in{\mathscr{L}}}\left\\{\frac{a_{\ell
j}}{d_{j\ell}}\right\\}$ (1)

where $d_{j\ell}:=\frac{p_{\ell j}}{C_{j}^{0}-r_{j}}$ is also called the rate
demand of flow $i$ of coflow $j$ and it represents the lowest possible rate to
dispatch $p_{\ell j}$ within $C_{j}^{0}$. From the definition of $C_{j}^{0}$
indeed $P_{j}\leq 1$. Finally, coflow fairness ensures a per-coflow minimum
progress

$P_{j}\geq P_{0},\quad\forall j\in{\mathscr{C}}$ (2)

It is worth remarking that, though equivalent to the definition appearing in
the literature, (1) has a straightforward interpretation in terms of per port
bitrates. In some works, the constant parameter $P_{0}$ is also called as
isolation guarantee [20]. The next example is meant to outline why the notion
of static progress does not fully capture the performance-fairness trade-off
in coflow scheduling.

a)$\ell_{3}$$\ell_{2}$$\ell_{1}$$\scriptsize 0$$U\\!\\!+\\!\\!2V$$\frac{U}{1-P_{0}}$Type Ib)$\ell_{3}$$\ell_{2}$$\ell_{1}$$\scriptsize 0$$U\\!\\!+\\!\\!2V$$\frac{2V}{1-P_{0}}$Type II |  slowdown ($\phi_{j}=1$) | progress
---|---|---
| $E_{1}$ | $E_{2}$ | $R_{1}$ | $R_{2}$
Type I | $\frac{1}{1-P_{0}}$ | $1+\frac{U}{2V}$ | $3(1-P_{0})$ | $\frac{4V}{2V+U}$
Type II | $1+\frac{2V}{U}$ | $\frac{1}{1-P_{0}}$ | $\frac{3U}{2V+U}$ | $2(1-P_{0})$

Figure 2: Example: a) schedule of Type 1 and b) schedule of Type 2.

#### Example

The sample coflow batch of Fig. 1 is served on a fabric with $M=3$ servers and
unitary bandwidth links. Coflow $1$ marked orange occupies all input and
output ports of the fabric; it has $3$ flows with volume $U$ traffic units
each. Coflow $2$ marked blue consists of flows of volume $V$ traffic units
each, two on port $\ell_{1}$ and two on port $\ell_{3}$. In Fig. 1 the index
of the virtual queues at ingress ports indicate the output port. For instance
the second flow of coflow $2$ sends $v_{2}^{2}=V$ traffic units to port
$\ell_{5}$.

Let $P_{0}$ denote the static progress guarantee. By the symmetry of the
problem, same rate guarantee is due on input ports for the two coflows, i.e.,
$P_{1}=a_{\ell_{1}1}=a_{\ell_{2}1}=a_{\ell_{3}1}\geq P_{0}$ and
$P_{2}=a_{\ell_{1}2}=a_{\ell_{3}2}\geq P_{0}$. Clearly, $P_{0}\leq 1/2$ due to
bandwidth constraints. As depicted in Fig. 2, based on the CCT order of
coflows, two types of schedules are possible: Type I where coflow $1$ finishes
first or Type II where coflow $1$ finishes last. For Type I schedules it holds
$C_{2}=U+V$, whereas $C_{1}=U/(1-P_{0})$. For Type II, $C_{1}=U+V$ and
$C_{2}=2V/(1-P_{0})$. By letting $P_{0}>0$, for Type I the CCT of coflow $1$
has been degraded with no gain for coflow $2$. Conversely, for Type II
schedules, the CCT of coflow $2$ is degraded with no gain for coflow $1$.
Thus, while the static progress guarantees a minimum rate allocation per
coflow, the CCT of some of the coflows can be degraded without any actual gain
for the slowdown of the other ones.

###  III-C Progress and slowdown

The progress of coflow $j$ under coflow schedule ${\mathscr{M}}$ is defined as
its average rate attained while in the system, i.e.,
$R_{j}=\frac{V_{j}}{C_{j}-r_{j}}$. To control the fairness-performance
tradeoff, it is convenient to use the coflow slowdown, which is in fact the
inverse quantity of the progress: a target progress guarantee can be enforced
via a constraint on the maximum slowdown. The slowdown is the ratio between
the progress in isolation $R_{j}^{0}$ and the progress under a given schedule
${\mathscr{M}}$. This plain notion of slowdown can be generalized to allow for
a non-negative weight per coflow which is a function of the coflow geometry.

######  Definition 1 (Generalized coflow slowdown).

The generalized slowdown of coflow $j$ under coflow schedule ${\mathscr{M}}$
is the weighted ratio
$E_{j}=\phi_{j}\,\frac{R_{j}^{0}}{R_{j}}=\phi_{j}\,\frac{C_{j}-r_{j}}{C_{j}^{0}-r_{j}}$.

The (generalized) slowdown captures the relative degradation of the data
transfer duration when a coflow is scheduled within a batch of competing ones
compared to its duration in isolation. In the numerical section, two variants
of slowdown are considered:

  * •

plain slowdown: $\phi_{j}=1$, this is the standard definition of slowdown [29,
12, 10] where, between two coflows, a bound on the maximum slowdown
prioritizes the coflow with smaller CCT in isolation;

  * •

slowdown with port-occupation: $\phi_{j}=V_{j}$, with this definition, between
two coflows with same volume, a bound on the maximum slowdown prioritizes the
coflow with smaller port-occupation.

#### Example

The tradeoff between average CCT and progress for Type I and for Type II
schedules is described in Fig. 2. For Type I schedules the slowdown of the
coflow finishing first is $1/(1-P_{0})$. The progress guarantee as a function
of the static progress guarantee $P_{0}$ writes
$\overline{R}_{\mbox{\scriptsize{I}}}=\min\\{3(1-P_{0}),\frac{4V}{2V+U}\\}$.
In case of Type II schedules it writes
$\overline{R}_{\mbox{\scriptsize{II}}}=\min\\{2(1-P_{0}),\frac{3U}{2V+U}\\}$.
Note that both functions are non increasing. Also, by letting $P_{0}=0$, both
$\overline{R}_{\mbox{\scriptsize{I}}}$ and
$\overline{R}_{\mbox{\scriptsize{II}}}$ attain their maximum and the attained
average CCT is also minimized for $P_{0}=0$ for both Type I and Type II
schedules.

Finally, the following cases hold. For $2V<U$ the Type II schedule attains the
minimum average CCT, i.e., $(5V+U)/2$ and the progress guarantee
$R^{*}=3U/(2V+U)$ is also better off than Type I. Conversely for $4V>3U$ a
Type I schedule attains the minimum average CCT, i.e., $V+U$ and the best
progress guarantee, i.e., $R^{*}=4U/(2V+U)$.

It is interesting to remark that in the above two cases there is no
performance-fairness tradeoff, because minimizing the average CCT is also
ensuring the largest minimum progress.

Conversely, for $2U<4V<3U$, a performance-fairness tradeoff does exist: a Type
II schedule attains better average CCT but worse progress than a Type I one;
on the contrary, a Type I schedule attains worse average CCT but better
progress than a Type II one.

From the example, the both Type I and Type II schedules do attain the best
progress guarantee and are better off w.r.t. CCT figures for $P_{0}=0$ than
for $P_{0}>0$. This fact is expressed as a general result in the next section,
ruling out static progress guarantees in fair coflow scheduling.

##  IV Scheduling under slowdown constraints

The standard coflow scheduling optimization framework determines a coflow
schedule ${\mathscr{M}}$ by minimizing the weighted sum of the CCTs under
capacity constraints imposed by the network fabric. It is often formulated as
a Mixed Integer Linear problem (MILP) for a finite horizon where time is
slotted into $T$ time slots of duration $\Delta$; let $\Delta=1$ without loss
of generality. The decision variables $\\{x_{j}^{i}(t)\\}$ represent the
fraction of flow $i\in{\mathscr{F}}_{j}$ of coflow $j$ scheduled in slot $t$.
The fraction of volume of flow $i$ of coflow $j$ already transmitted by slot
$t$ is $Z_{j}^{i}(t)=\sum_{v=1}^{t}x_{j}^{i}(v)$. The fraction of volume
coflow $j$ transmitted by time $t$ writes
$Z_{j}(t):=\frac{1}{V_{j}}\sum\limits_{i\in{\mathscr{F}}_{j}}v_{j}^{i}Z_{j}^{i}(t)$;
note that $C_{j}=\min\\{t|\,Z_{j}(t)=1\\}$. Finally, the standard formulation
with MILP representing the Progress Scheduling (PS) problem writes

minimize: $\displaystyle\sum w_{j}C_{j}$ (PS) subj. to:
$\displaystyle\sum_{t=1}^{T}x_{j}^{i}(t)=1,\quad\forall
j\in{\mathscr{C}},i\in{\mathscr{F}}_{j}$ (3) $\displaystyle X_{j}(t)\leq
Z_{j}(t),\;\forall j\in{\mathscr{C}},\forall t$ (4) $\displaystyle
Z_{j}(t)\leq 0,\forall t\leq r_{j}$ (5) $\displaystyle C_{j}\geq
1+\sum_{z=1}^{T}(1-X_{j}(z)),\;\forall j\in{\mathscr{C}}$ (6) $\displaystyle
E_{j}:=\frac{C_{j}-r_{j}}{C_{j}^{0}-r_{j}}\leq\frac{E}{\phi_{j}},\;\forall
j\in{\mathscr{C}}$ (7)
$\displaystyle\sum_{j\in{\mathscr{C}}}\sum_{i\in{\mathscr{F}}_{i}}v_{j}^{i}x_{j}^{i}(t)\chi_{j}^{i}(\ell)\leq
B_{\ell},\;\forall t,\forall\ell\in{\mathscr{L}}$ (8) $\displaystyle
x_{j}^{i}(t)\in[0,1],\;X_{j}(t)\in\\{0,1\\},\;\forall t$ (9)

where $E$ is a non-negative parameter and weight $w_{j}$ denotes the weight of
coflow $j$. Let denote $\\{C_{j}^{*}\\}$ a solution of the PS and
$\\{R^{*}\\}$ the corresponding progress vector.

The MILP makes use of coflow completion variables $Z_{j}(t)$ and binary
variables $X_{j}(t)$. Note that, due to minimization, $X_{j}(t)$ behaves as
the indicating variable of coflow completion, that is $X_{j}(t)=1$ if
$Z_{j}(t)=1$ and $X_{j}(t)=0$ if $Z_{j}(t)<1$. Constraint (3) states that each
flow should be completed by the end of the time horizon; (4) states that the
completion of a coflow is subject to the transfer of the whole coflow volume.
In (5) the release time of coflows imposes the constraint on the beginning of
a coflow transmission. Constraint (6) binds coflow completion time and coflow
completion variables, which appeared first in [7]. Finally, (8) provides the
constraint on the port capacity; $Z_{j}(t)$ is defined implicitly in (4) and
(5) for notation’s sake. Finally, (7) is the slowdown constraint to enforce a
target coflow progress, where constant $E\geq\max_{j}\phi_{j}$. Note that
$\phi_{j}$ permits to express a preference: for instance, when
$\phi_{j}=V_{j}$, if two coflows have same total volume, the one which
occupies the fabric ports for shorter time is preferred.

Clearly, adding progress constraints leads to a deterioration of the average
CCT with respect to the plain weighted CCT minimization ($E=+\infty$). For the
example in the previous section, when $\phi_{j}=V_{j}$, the constraint (7)
writes $C_{1}/C_{1}^{0}\leq E/3U$ and $C_{2}/C_{2}^{0}\leq E/4V$. Letting
$E=2(U+2V)$ attains the schedule of Type I. The schedule of Type II is
attained when $2V<U$. In such case (7) is inactive, i.e., there is no
tradeoff. However, Type I is to be preferred when the port occupation of
coflow $2$ is larger than that of coflow $1$.

Next, the notion of static progress (1) and (2) existing in the literature
[19] and that of progress based on coflow slowdown are compared. The Static
Progress Scheduling (SPS) problem is described below:

minimize: $\displaystyle\sum w_{j}C_{j}$ (SPS) subj. to:
$\displaystyle\eqref{eq:completion}\eqref{eq:indicating}\eqref{eq:release}\eqref{eq:CCT}\eqref{eq:capacity}$
(10)
$\displaystyle\sum\limits_{i\in{\mathscr{F}}_{j}}v_{j}^{i}x_{j}^{i}(t)\chi_{j}^{i}(\ell)\geq
a_{\ell j}\,\Delta\,,\;\forall t\;\forall\ell\in{\mathscr{L}}$ (11)
$\displaystyle x_{j}^{i}(t)\in[0,1],\;X_{j}(t)\in\\{0,1\\},\;\forall t$ (12)

where the minimum rate allocations $\\{a_{\ell j}\\}$ obey to (1) and (2) for
a given progress parameter $P_{0}$. With some abuse of terminology, let denote
$\\{{\overline{C}}_{j}\\}$ a solution of SPS.

From an analogous result for the weighted CCT minimization, it follows that
both PS and SPS problems are NP-hard and inapproximable below a factor $2$
[7].

Let ${\overline{R}}_{j}$ the average progress guarantee offered by SPS for
coflow $j$ corresponding to allocation $\\{a_{\ell j}\\}$ so that
${\overline{R}}_{j}:=\frac{1}{2}\sum_{\ell}\sum_{i\in{\mathscr{F}}_{j}}a_{j}^{i}\;B_{\ell}$.
As shown next, compared to (11), the slowdown constraint (7) allows more
flexible rate allocation since the rate on some links can be increased by
reducing or pausing the transmission on some other links used by the coflow.
Formally, for every SPS scheduler there exists a slowdown value $E$ and a PS
scheduler which is better off.

######  Theorem 1.

Let consider ${\mathscr{C}}$ and static progress defined for $P_{0}>0$
according to (1) and (2). There exists $E\geq 0$ such that a solution of SPS
is feasible for PS. Furthermore, there exists a schedule such that

$\sum C_{j}^{*}<\sum{\overline{C}}_{j},\quad\mbox{and}\quad
R_{j}^{*}\geq{{\overline{R}}}_{j}\quad\forall j\in{\mathscr{C}}$

###### Proof:

i. Let ${\mathscr{M}}$ be a schedule solving SPS for a given pair
$\\{a_{j\ell}\\}$ and $P_{0}$. Let $\\{{\overline{C}}_{j}\\}$ the
corresponding result. It is possible to determine $E$ so that such a schedule
is a solution of PS as well. From (1) and (2)

$\sum\limits_{i\in{\mathscr{F}}_{j}}v_{j}^{i}x_{j}^{i}(t)\chi_{j}^{i}(\ell)\geq
a_{j\ell}\,\Delta,\quad\quad\frac{a_{\ell j}\;(C_{j}^{0}-r_{j})}{p_{\ell
j}}\geq P_{0}$

For every coflow we can write

$\displaystyle\hskip-14.22636pt{\overline{C}}_{j}-r_{j}\leq\max_{\ell\in{\mathscr{L}}}\left\\{\frac{p_{\ell
j}}{a_{\ell
j}}\right\\}=\frac{(C_{j}^{0}-r_{j})}{\min\limits_{\ell\in{\mathscr{L}}}\frac{{a_{\ell
j}}\;(C_{j}^{0}-r_{j})}{p_{\ell j}}}$
$\displaystyle\hskip-14.22636pt=\frac{C_{j}^{0}-r_{j}}{P_{j}}\leq\frac{C_{j}^{0}-r_{j}}{P_{0}},\qquad\forall
j\in{\mathscr{C}}$ (13)

With the identification $E=\frac{\max V_{j}}{P_{0}}$, the schedule
${\mathscr{M}}$ is feasible also for PS.
ii. The attained progress guarantees can be bounded by

$\displaystyle\hskip-14.22636pt{\overline{R}}_{j}=\frac{1}{2}\sum_{\ell\in{\mathscr{L}}}a_{\ell
j}\;B_{\ell}\leq\frac{1}{2}\frac{1}{{\overline{C}}_{j}-r_{j}}\sum\limits_{t=r_{j}}^{{\overline{C}}_{j}}\sum_{\ell\in{\mathscr{L}}}\sum_{i\in{\mathscr{F}}_{j}}v_{j}^{i}x_{j}^{i}(t)\chi_{j}^{i}(\ell)$
$\displaystyle=\frac{1}{2}\frac{2V_{j}}{{\overline{C}}_{j}-r_{j}}=R_{j}$ (14)

where the factor $2$ appears since every flow is counted at the ingress at the
egress port. By adding feasible constraints $C_{j}-r_{j}\leq
V_{j}/{\overline{R}}_{j}$ to SPS and dropping (11) the thesis follows. ∎

From Thm. 1, scheduling with slowdown constraints provides larger feasibility
space and at least same progress guarantees than SPS. As seen in our example,
the corresponding minimum weighted CCT which can be attained under same
progress guarantees is strictly worse for $P_{0}>0$. However, the introduction
of slowdown constraints on top of weighted CCT minimization poses the issue of
feasibility, i.e., whether or not, for a given instance of the problem, a
target slowdown constraint is feasible and what is the smallest feasible value
of $E$.

##  V Slowdown feasibility

In this section the feasibility of PS is discussed and means to test it in
polynomial time are presented. In particular, the largest possible average
progress is obtained by minimizing $E$ in (7) while ensuring the feasibility
of (PS). Then, the class of $\sigma$-order preserving schedulers is extended
to account for slowdown constraints.

Testing slowdown feasibility is possible in the form of a linear program (LP)
feasibility test, from which the following result hold:

######  Theorem 2.

i. The feasibility of PS can be determined in polynomial time. ii. If an
instance of PS is feasible for a given value if $E$ where $r_{j}=0$ for all
$j\in{\mathscr{C}}$, then it is also feasible for all instances obtained by
letting some of the $r_{j}$s positive.

The proof and the actual LP formulation are detailed in the Appendix. We
denote $E^{*}$ the minimum feasible parameter appearing in (7). It is
interesting to remark that from the previous result the case of different
release times is beneficial with respect to the coflow progress; the intuition
is that for a later released coflow, it is convenient if some of earlier
coflows have been already dispatched. In the next section we shall introduce a
much faster approximated yet accurate algorithm to determine $E^{*}$ (namely
Alg. 1). From Thm. 2, $E^{*}$ can be determined in pseudo-polynomial time by
solving LP iteratively with a bisection search exploring the slowdown
parameter $E$. By simple calculations this search is
$O(\frac{(NV)^{3.5}}{\epsilon})$ where $V=\sum V_{j}$, and $\epsilon>0$ is a
tolerance, where we used the $O(n^{3.5})$ bound in the number of variables
$n$.

###  V-A $\sigma$-order schedulers

Even if the above result is encouraging, one fundamental problem with
techniques based on MILPs in coflow scheduling is that the number of flows per
coflow maybe large111It may range in the order of tenths of thousands [5] in
production datacenters. Furthermore, the number of variables involved in such
time-indexed systems increases with the inverse of the time slot $\Delta$.
Hence, the number of per slot rate decision variables easily range in hundred
of thousands for a time slot $\Delta$ in the order of seconds. Thus,
scalability issues do arise even for approximation algorithms obtained by
solving LPs from MILP relaxation [7],[11]. Same scalability issues occur
solving the time-indexed LP to determine the minimal slowdown $E^{*}$.

For the sake of striking a fairness-performance tradeoff, solving PS exactly
may not be feasible. Rather, it is possible to design a coflow scheduler to
approximate a target average progress guarantee, and yet perform near-
optimally with respect to the weighted CCT. We can regard this approach as a
soft coflow fairness guarantee versus the hard coflow fairness guarantee
provided by PS.

It is possible to do so using the class $\Sigma$ of $\sigma$-order preserving
schedulers ($\sigma$-order schedulers for short). These schedulers require to
set the priority of coflows and use such order to determ rate allocation [8,
13]. Let order $\sigma:{\mathscr{C}}\rightarrow{\mathscr{C}}$ be a permutation
of the coflow set: $j=\sigma(k)$ means that the $k$-th priority is assigned to
coflow $j$.

######  Definition 2.

Fix an order $\sigma:{\mathscr{C}}\rightarrow{\mathscr{C}}$: the scheduler
${\mathscr{M}}$ is a $\sigma$-order preserving scheduler if

  * •

it is pre-emptive;

  * •

it is work conserving;

  * •

it respects the pre-emption order: no flow of coflow $\sigma(j)$ can be pre-
empted by a flow of $\sigma(k)$, $k=j+1,\ldots N$ on any port on which it has
pending flows.

The greedy rate allocation, for instance, blocks a coflow $\sigma(j)$ on some
port iff it is occupied by some coflow $\sigma(k)$, $k<j$. As first proved in
[8], the design of $\sigma$-order schedulers can be performed using the
analogy of the Big Switch ports with correlated machines and using related
results for open-shop scheduling [23]. Following the same idea, once $E$ is
fixed, schedulers in $\Sigma$ can approximate the solution of PS problem. In
the rest of the discussion, we consider the case $r_{j}=0$, $\forall
j\in{\mathscr{C}}$.

###  V-B Extending $\sigma$-order schedulers: primal feasibility

The theory of $\sigma$-order scheduling is rooted on the work [23] for
concurrent open shop problems where jobs are scheduled on parallel machines.
Let define $p_{\ell j}=\sum v_{j}^{i}\chi_{j}^{i}(\ell)$ the total volume to
be transferred by coflow $j$ over port $\ell$. Denote $V_{\ell}=\sum
v_{j}^{i}\chi_{j}^{i}(\ell)$ the total volume on port ${\ell}$ and
${\mathscr{C}}_{\ell}$ is the set of coflows active on port $\ell$. The
equivalent slowdown constraint $D_{j}=\frac{EC_{j}^{0}}{V_{j}}$ is introduced
for notation’s sake. With the job scheduling terminology, $p_{\ell j}$ is the
duration of the job $j$ over machine $\ell$. The corresponding scheduling
formulation writes [23]

minimize: $\displaystyle\sum_{j\in{\mathscr{C}}}w_{j}C_{j}$ (Primal LP) subj.
to: $\displaystyle\sum_{j\in A}p_{\ell j}C_{j}\geq f_{\ell}(A),\quad\forall
A\subseteq{\mathscr{C}},\;\ell\in{\mathscr{L}}$ (15) $\displaystyle C_{j}\leq
D_{j},\;\forall j\in{\mathscr{C}}$ (16)

The set functions
$f_{\ell}:\mathscr{P}({\mathscr{C}}_{\ell})\rightarrow{\mathbb{R}}$ are
defined $f_{\ell}(S)=\frac{1}{2}[(\sum_{j\in S}p_{\ell j})^{2}+\sum_{j\in
S}p_{\ell j}^{2}]$ for $S\subset{\mathscr{C}}_{\ell}$. Constraints (15) are
known as parallel inequalities. Let restrict to the set of schedulers
$\Sigma_{b}$, that is the set of $\sigma$-order schedulers such that the
permutation $\sigma$ is primal-feasible, that is

$C_{k\ell}:=\frac{1}{B_{\ell}}\sum_{j=1}^{k}p_{\ell\sigma(j)}\leq
D_{k},\qquad\forall\ell\in{\mathscr{L}},\forall k\in{\mathscr{C}}$ (17)

In fact, it is always possible to consider just $\sigma$-order schedulers

######  Theorem 3.

If Primal LP is feasible, it is solved by $\sigma$-order which is primal-
feasible.

###### Proof:

Let consider the set of permutation schedules $\\{\sigma_{\ell}\\}$ which
schedule coflows active on port $\ell$ according to the EDD rule (Earliest Due
Date rule) [30]. Since Primal LP is primal-feasible, all such schedules
$\\{\sigma_{\ell}\\}$ are feasible. Now let derive a feasible $\sigma$-order
using the following procedure: select the coflow $k$ for which $C_{k}$ is
maximum, and modify $\sigma_{\ell}$s for all ports where $p_{\ell k}>0$ by
scheduling $k$ last on all its active ports, and leaving the order of the
others unchanged. After this operation it holds $C_{k\ell}\leq D_{k}$ and
$C_{j\ell}\leq D_{j}$ for all $j\not=k$ and for all ports $\ell$ so that the
resulting $\\{\sigma_{\ell}\\}$ are still feasible. Let
$\sigma(k)=|{\mathscr{C}}|$, and then remove it from $\\{\sigma_{\ell}\\}$.
Let ${\mathscr{C}}\leftarrow{\mathscr{C}}\setminus\\{k\\}$. By repeating this
procedure, in $N$ steps a feasible $\sigma$-order is obtained.∎

Let $E^{p}$ be the minimal value such that Primal LP is feasible. From the
proof of Thm. 4, a bisection search algorithm based on a per port EDD
scheduling can determine the value $E^{p}$ in pseudo-polynomial time. The next
result provides a connection between the Primal LP and PS:

######  Theorem 4.

If PS is feasible, then Primal LP is feasible, i.e.,
$\Sigma\subseteq\Sigma_{b}$.

###### Proof:

It is sufficient to consider a schedule ${\mathscr{M}}$ which is feasible for
PS and then consider the $\sigma$-order which sorts coflows according to the
CCTs produced by ${\mathscr{M}}$, denoted $\\{\overline{C}_{k}\\}$. In fact,
let consider coflow $k\in{\mathscr{C}}$ and port $\ell$ where the last of its
flows completes. Since coflow $k$ completes on port $\ell$ after all coflows
$j=1,\ldots,k-1$, the volume of all flows on $\ell$ which belong to
$j=1,\ldots,k-1$ must be over by time $\overline{C}_{k}$. This implies that

$D_{k}\geq\overline{C}_{k}\geq\sum_{j=1}^{k}p_{\ell j}$ (18)

so that (16) holds. Moreover, it holds

$\sum_{j\in{\mathscr{C}}}p_{\ell,j}\overline{C}_{j}\geq\sum_{j\in{\mathscr{C}}}p_{\ell,j}\sum_{k=1}^{j}p_{\ell
k}=f_{\ell}({\mathscr{C}})$

so that (15) is satisfied as well. By identifying
$C_{j}:=\sum_{k=1}^{j}p_{\ell k}$, the proof holds. ∎

Thus, if there exists a solution for PS in $\Sigma$, then it is to be found in
$\Sigma_{b}$. However, since primal-feasibility does not account for cross-
dependencies among ports, it provides a weaker estimate of the completion time
for the flows of a coflow according to a given $\sigma$-order.

######  Corollary 1.

$E^{p}\leq E^{*}$.

Nevertheless, the experimental results reported in Sec VII indicate that the
two values practically coincide. To this respect, the calculation of $E^{p}$
provides a substantial computational advantage since it can be performed by a
lightweight fully polynomial time algorithm. It is called MPS, which stands
for Minimum Primal Slowdown.

The pseudocode of MPS is reported in Alg. 1.

Algorithm 1 Pseudocode of MPS

Input: ${\cal C}$, $\\{\phi_{j}\\}$ $\\{p_{\ell,j}\\}$

Output: $E$

1: Sort ${\mathscr{C}}$ in decreasing order of
${\widetilde{R}}_{j}^{0}=\frac{\phi_{j}}{V_{j}}\frac{V_{j}}{C_{j}^{0}}$ %
sorting by $\mathscr{R}_{j}^{0}$

2: $E_{\ell}=+\infty,\quad\forall\ell\in{\mathscr{L}}$ % initialise slowdown

3: for $\ell=\ell_{1},\dots,\ell_{2M}$ do

4: for $j\in{\mathscr{C}}_{\ell}$ do

5: $Z_{j}={\widetilde{R}}_{j}^{0}\sum_{k=1}^{j}v_{k}^{\ell}$ % per coflow
estimate on $\ell$

6: end for

7: $E_{\ell}=\max\\{Z_{1},...,Z_{|{\mathscr{C}}_{\ell}|}\\}$ % slowdown
estimate per port

8: end for

9: $E=\max\\{E_{\ell_{1}},\ldots,E_{\ell_{2M}}\\}$ % for every port

10: return $E$ % return the slowdown

The value of $E$ which satisfies the slowdown constraint (7) is minimum when
the CCT of the coflow with the largest value $\frac{\phi_{j}C_{j}}{C_{j}^{0}}$
is minimized. The algorithm visits each port $\ell$ by sorting
${\mathscr{C}}_{\ell}$ in decreasing order of
${\widetilde{R}}_{j}^{0}=\frac{\phi_{j}}{V_{j}}\frac{V_{j}}{C_{j}^{0}}=\frac{\phi_{j}}{V_{j}}R_{j}^{0}$.
For each link $\ell$, the iteration at step $7$ provides a lower bound on
$E^{p}$ per coflow active on $\ell$ using (7). The maximum among such
estimates is selected at step $9$. Due to the sorting at line $1$ and the
$N_{\ell}$ products at line $5$, it is easy to see that the complexity of Alg.
1 is in $O(MN+N\log(N))$. The next result proves that the output of MPS is
correct.

######  Theorem 5.

MPS returns $E^{p}$

###### Proof:

From Primal LP, fixed a primal schedule, it holds
$E\geq{\widetilde{R}}_{j}^{0}\,C_{j}$ for $\forall j\in{\mathscr{C}}$, and
more precisely

$E^{p}=\min\limits_{\sigma\in\Sigma_{b}}\left\\{\max\limits_{\ell\in{\mathscr{L}}}\max\limits_{j\in{\mathscr{C}}}{\widetilde{R}}_{j}^{0}\,\sum\limits_{i\in{\mathscr{C}}}p_{\ell\sigma(i)}\right\\}$

Let show that $E^{p}$ is attained by a primal schedule which sorts coflows
with decreasing ${\widetilde{R}}_{j}^{0}$. Let assume
${\widetilde{R}}_{1}^{0}\geq\ldots\geq{\widetilde{R}}_{N}^{0}$. Let
$\sigma_{\ell}$ be the permutation induced by $\sigma$ on a tagged port
$\ell\in{\mathscr{L}}$. For the last scheduled coflow on port $\ell$ it holds

$E^{p}\geq\min\limits_{j\in{\mathscr{C}}}{\widetilde{R}}_{j}^{0}\,\sum\limits_{i\in{\mathscr{C}}}p_{\ell\sigma(i)}={\widetilde{R}}_{N_{\ell}}^{0}\sum_{i=1}^{N_{\ell}}p_{\ell
i}$ (19)

Also, let $\sigma^{\prime}=(\sigma(1),\ldots,\sigma(N_{\ell}-1))$, it holds

$E^{p}\geq\max_{j\in{\mathscr{C}}_{\ell}\setminus\\{N_{\ell}\\}}\max\left\\{{\widetilde{R}}_{j}^{0}\sum\limits_{\sigma^{\prime}(i)\leq\sigma^{\prime}(j)}p_{\ell\sigma^{\prime}(i)}\right\\}\\\
$

because by eliminating the last scheduled coflow $\sigma(N)$, the maximum
slowdown cannot increase. Now, it is possible to write

$\displaystyle\hskip-14.22636ptE^{p}\geq\max\limits_{\sigma_{\ell}(N_{\ell})}\left\\{{\widetilde{R}}_{\sigma(N_{\ell})}^{0}\sum_{i=1}^{N_{\ell}}p_{\ell
i},\max\limits_{j\in{\mathscr{C}}_{\ell}\setminus\\{N_{\ell}\\}}a_{j}\sum\limits_{\stackrel{{\scriptstyle
i\in{\mathscr{C}}_{\ell}\setminus\\{N_{\ell}\\}}}{{\sigma(i)\leq\sigma^{\prime}(j)}}}p_{\ell\sigma^{\prime}(i)}\right\\}$
$\displaystyle\hskip-14.22636pt\geq\max\left\\{{\widetilde{R}}_{N_{\ell}}^{0}\sum_{i=1}^{N_{\ell}}p_{\ell
i},\max_{j\in{\mathscr{C}}_{\ell}\setminus\\{N_{\ell}\\}}\sum\limits_{\sigma^{\prime}(i)\leq\sigma^{\prime}(j)}p_{\ell\sigma^{\prime}(i)}\right\\}$

Hence an optimal permutation writes
$\sigma=(\sigma_{1},\ldots,\sigma_{N_{\ell}-1},N_{\ell})$. The same argument
holds for $\sigma^{\prime}$ and ${\mathscr{C}}_{\ell}\setminus\\{N_{\ell}\\}$,
so that an optimal permutation writes
$\sigma=(\sigma_{1},\ldots,\sigma_{N_{\ell}-2},,N_{\ell-1},N_{\ell})$. After
$N_{\ell}$ iterations, the theorem follows. ∎

As a side result of the above proof it follows

######  Corollary 2.

Primal LP is feasible if and only if the schedule which sorts coflows with
decreasing ${\widetilde{R}}_{j}^{0}$ is feasible.

### On feasibility and primal feasibility.

Finally, the minimum value of the parameter $E^{p}$ for which the formulation
is primal-feasible is in general smaller than the minimum possible value
$E^{*}$ which renders PS feasible. The fact that they practically coincide –
as seen in the numerical section – is to be ascribed to the fact that the
largest slowdown corresponds invariably to the CCT of a coflow finishing last
on some port. Hence, it is in fact determined by the total volume transferred
on that port. This is actually the key step for the slowdown estimation
performed by MPS at line (5).

A primal-feasible $\sigma$-order may not grant the target slowdown in PS for
all coflows once rate allocation is performed. However, the objective is to
provide guarantees on the slowdown of coflows by using primal-feasibility as a
soft constraint. To this respect the feasibility of PS can be regarded as a
hard constraint on the slowdown. In all numerical experiments described in
Sec. VII the fraction of violations never exceeded a few percents.

##  VI Algorithmic solution

This section introduces a primal-dual algorithm, namely CoFair, which can
determine a primal-feasible $\sigma$-order in polynomial time. It generalizes
the primal-dual scheduling approach [23] for job scheduling over uncorrelated
machines, a technique later applied in the context of coflow scheduling in [8]
and [13]. The basic idea in [23] is to utilize the Smith rule over different
machines and sort jobs accordingly: machines are mapped into ports, jobs into
coflows and tasks into flows. Every port is treated as uncorrelated to the
others and a primal-dual iteration performs a coflow selection and weigh-
adjustment technique [23, 8]

Nevertheless, it is not obvious whether or not it is possible to perform a
similar primal-dual iteration while accounting for slowdown constraints and
ultimately obtain a primal-feasible schedule. The rest of the section shows
how to generate a primal-feasible $\sigma$-order if one exists. The pseudocode
of the algorithm described in this section requires specific notation which
are introduced next.

For the set of coflows $A\subseteq{\mathscr{C}}$, let $V_{\ell}(A)=\sum
v_{j}^{i}\chi_{j}^{i}(\ell)$ the total volume transmitted over port $\ell$; if
$A={\mathscr{C}}$ the notation is simply $V_{\ell}$. The set of ports engaged
by coflows in $A$ is
${\mathscr{L}}(A)=\\{\ell\in{\mathscr{L}}|V_{\ell}(A)>0\\}$.
${\mathscr{C}}_{\ell}(A)$ is the set of coflows in $A$ active over port
$\ell$. $T_{\ell}(A)=\frac{1}{B_{\ell}}V_{\ell}(A)$ is the minimum time
required to complete the last coflow of set $A$ over link $\ell$. Coflow $j$
is a feasible tail coflow of set $A$ if $T_{\ell}\leq D_{j}$ for each link
$\ell$ where $p_{\ell,j}>0$. Formally,
$F(A)=\\{j\in{\mathscr{C}}_{\ell}(A)|T_{\ell}(A)\leq
D_{j},\;\forall\ell\in{\mathscr{L}}(A)\\}$ is the set of feasible tail coflows
of set $A$. With no loss of generality, in the rest of this section
$B_{\ell}=1$.

Algorithm 2 Pseudocode of CoFair

1: Input: ${\cal C}$, $\\{p_{\ell,j}\\}$, $\\{D_{j}\\}$, $\\{\alpha_{j}\\}$

2: Output: $\sigma$ $\\{y_{{}_{\mu_{k},F_{k}}}\\}$ $\\{C_{j}\\}$

3: $\\{y_{\ell,S}\\}=0$ for $S\subseteq{\mathscr{C}}$ % initialise the dual
variables

4: $A_{N}={\mathscr{C}}$ % initial unscheduled coflows

5: $w_{j}^{(N+1)}=w_{j}+\alpha_{j}$ % initial weights

6: while $A_{k}\not=\emptyset$ do

7: $\mu_{k}\leftarrow$ pivot_bottleneck$(A_{k})$ % pivot bottleneck

8: $F_{k}\leftarrow F(A_{k})$ % set of feasible tail coflows in $A_{k}$

9: if ${\mathscr{F}}_{k}=\emptyset$ then

10: return $\emptyset$ % Primal LP non-feasible

11: end if

12: $\sigma(k)\leftarrow\arg\min_{j\in
F_{k}}\left\\{\frac{w_{j}^{(k)}}{p_{\mu_{k,j}}}\right\\}$ % pivot coflow
(Smith rule)

13: $w_{\sigma(k)}^{(k)}\leftarrow\frac{w_{\sigma(k)}^{(k+1)}}{p_{\mu_{k},j}}$
% update pivot coflow weight

14: $y_{{\mu_{k}},F_{k}}\leftarrow{w_{k}}^{(k)}$ % update dual problem
solution

15: for $j\in A_{k}\setminus\\{\sigma(k)\\}$ do

16: if $j\in{\mathscr{F}}_{k}$ then

17: $w_{j}^{(k)}\leftarrow
w_{j}^{(k+1)}-w_{\sigma(k)}^{(k+1)}\frac{p_{\mu_{k,j}}}{p_{\mu_{k},\sigma(k)}}$
% update weights

18: else

19: $w_{j}^{(k)}\leftarrow w_{j}^{(k+1)}$ % non tail-feasible coflows:
unchanged

20: end if

21: end for

22: $A_{k-1}\leftarrow A_{k}\setminus\\{\sigma(k)\\}$ % update unscheduled
coflow set

23: end while

24: $C_{j}:=\max_{\ell\in{\mathscr{L}}}\sum_{h=1}^{j}p_{\ell,\sigma(h)},\quad
j\in{\mathscr{C}}$ % CCT lower bound

25: return $\sigma$, $\\{y_{{}_{\mu_{k},F_{k}}}\\}$, $\\{C_{k}\\}$

The CoFair pseudocode in Alg. 2 describes the primal-dual iterations to
generate a $\sigma$-order which is primal-feasible. At each step $k$ it tries
to identify a pivot bottleneck-coflow pair (line $7$ and $12$). When this is
not possible, the algorithm exits with returning a non-feasibility result
(line $10$). Otherwise, first, a target bottleneck port $\mu_{k}$ is returned
for the unscheduled coflows $A_{k}=\\{\sigma(1),\sigma(2),\ldots,\sigma(k)\\}$
using a pivot_bottleneck procedure (line $7$). Second, it identifies the
coflow $\sigma(k)$ to be scheduled last over such port in the set of feasible
tail coflows $F_{k}$. On the selected bottleneck, a feasible tail coflow is
chosen according to the Smith rule [31]. Weight updates are only performed for
the pivot coflow (line $8$) and for feasible tail coflows (line $12$).
Afterwards, the algorithm eliminates the selected coflow from the set of
unscheduled ones (line $17$). Weights $\alpha_{j}$ have the meaning of
multipliers and can be used in order to enforce different $\sigma$-orders: as
it will be showed in the next section using such weights and pivot_bottleneck
it is possible to attain all possible primal-feasible $\sigma$-orders.

The pivot_bottleneck procedure can be fully general, but in the numerical
tests the selection is based on the heuristics that selects the most charged
bottleneck. This is the baseline rule adopted in [23, 13, 8]. Direct
calculations show that the computational complexity of CoFair is $O(N(M+N))$.

###  VI-A Correctness

We prove first that CoFair terminates in $N$ steps: at each iteration it is
possible to find at least one feasible tail coflow to be selected at step (8).

######  Lemma 1.

If Primal LP is feasible, then $F_{k}\not=\emptyset$ for $k=1,\ldots,N$.

###### Proof:

For $k=N$ the statement is true: $A_{N}={\mathscr{C}}\not=\emptyset$ and
$F_{N}\not=\emptyset$, otherwise Primal LP would not be feasible. Hence, Cor.
2 ensures that the $\sigma$-order which sorts coflows in order of decreasing
values of $R_{j}^{0}$ is feasible. From the proof of Thm. 5 such schedule is
feasible for any $A_{k}\subseteq{\mathscr{C}}$ so that $F_{k}\not=\emptyset$
for all $k=1,\ldots,N$. ∎

From the proof of Lemma 1, we can observe two facts: i) the statement is true
irrespective of the implementation of the pivot_bottleneck procedure; ii) it
holds also true if we replaced the Smith selection rule with any other
selection rule of coflows within set ${\mathscr{F}}_{k}$ as well.

We now show that the output of the algorithm belongs to the set of solutions
of Primal LP. Furthermore, the approximation properties of the proposed
algorithmic solution rely on the dual formulation

maximize:
$\displaystyle\sum_{\ell\in{\mathscr{L}}}\sum_{A\subseteq{\mathscr{C}}}y_{\ell,A}f_{\ell}(A)-\sum_{j}\alpha_{j}D_{j}$
(Dual LP) subj. to:
$\displaystyle\sum_{\ell\in{\mathscr{L}}}\sum_{A\subseteq{\mathscr{C}}:j\in
S}y_{\ell,A}\,p_{\ell,j}=w_{j}+\alpha_{j},\quad j\in{\mathscr{C}}$ (20)
$\displaystyle y_{\ell,A}\geq 0,\;\alpha_{j}\geq 0$ (21)

If Primal LP is feasible, the output of CoFair provides one solution for
Primal LP and one solution for Dual LP.

Finally, the following result demonstrates that the primal-dual iteration [23]
can be extended to account for primal feasibility, i.e., the output of CoFair
is a primal-feasible $\sigma$-order scheduler if one exists. Otherwise, the
algorithm provides a test of feasibility for Primal LP.

######  Theorem 6.

Let Primal LP be feasible. CoFair produces a primal-feasible solution
$\\{C_{k}\\}$ for Primal LP and a feasible solution $\\{y_{\ell,A}\\}$ for
Dual LP. Let Primal LP be not feasible, CoFair returns $\emptyset$.

###  VI-B Output completeness

Under feasibility conditions, the algorithm can always produce a solution
corresponding to a dual solution for $\alpha=0$. Nevertheless, it is possible
to use the multipliers of the dual problem in order to obtain any target
primal-feasible $\sigma$-order.

######  Theorem 7.

For every primal-feasible $\sigma$-order $\sigma^{*}$, there exist multipliers
$\\{\alpha_{j}\\}$, $\max\alpha_{j}=1$ so that $\sigma^{*}$ is the output of
Alg. 2 under rescaled weights $\\{\kappa\cdot w_{j}\\}$, for some
$0\leq\kappa\leq 1$.

###  VI-C Approximation factor

Let $C_{j}$ be the output of Alg. 2. Let define ${C_{j}^{\mbox{\tiny{OPT}}}}$,
$j\in{\mathscr{C}}$ a solution of PS and ${C_{j}^{\mbox{\tiny{LP}}}}$ an
solution of Primal LP. We also define ${\widehat{C}_{j}}$ the coflow
completion times of a $\sigma$-order using a priority output of Alg. 2.
${C_{j}^{\mbox{\tiny{OPT}}}}$ is defined accordingly. Let recall a few
results:

######  Lemma 2.

i.
$\sum_{k=1}^{N}w_{k}{C_{k}^{\mbox{\tiny{LP}}}}\leq\sum_{k=1}^{N}w_{k}{C_{k}^{\mbox{\tiny{OPT}}}}$
ii. $\Big{(}\sum_{j=1}^{k}p_{\mu_{k}\sigma(j)}\Big{)}^{2}\leq f_{\ell}(S)$,
for $\ell\in{\mathscr{L}}$ and $S\subseteq{\mathscr{C}}$ [23] Lemma 3.2
iii. ${\widehat{C}_{j}}-r_{j}\leq 2(C_{j}-r_{j})$ [8] Lemma 3

######  Theorem 8.

Alg. 2 produces a primal-feasible schedule such that for the corresponding
$\sigma$-order coflow schedule $\sigma^{*}$

$\sum w_{j}{\widehat{C}_{j}}\leq 4\sum
w_{j}{C_{j}^{\mbox{\tiny{OPT}}}}+4\sum\alpha_{j}D_{j}$ (22)

Assume $\alpha_{j}=0$ and $\sigma^{*}$ is feasible for PS, then it is a $4$
approximation w.r.t. an optimal scheduler.

###  VI-D Smith rule is Gaussian elimination

The proof of Thm. 6 described in the Appendix offers a simple interpretation
from basic linear algebra of the fact that the Smith rule is always leading to
a near-optimal, primal-feasible $\sigma$-order. Ultimately, the iterative
selection of a pivot bottleneck-coflow pair and the weight update operated
according to the Smith rule can be seen as simultaneous Gaussian elimination
and selection of a $N\times N$ sub-matrix over a suitable rectangular matrix
of size $N\times M\,2^{N}$ corresponding to the constraints of the dual
problem. In turn the existence of a coflow to be selected at each step is
granted by the feasibility of Primal LP, e.g., when using the output of MPS as
input slowdown parameter $E$. This permits to extend the proof of the result
in [23][Alg. 3.1] because under feasible slowdown constraints there is no need
to update the weights of non tail-feasible coflows at each step. Furthermore,
if one gives up the selection of the most charged bottleneck in the
pivot_bottleneck selection and Smith rule, the output is still primal-
feasible, but Thm. 8 may not hold.

##  VII Numerical results

This section reports on a set of extensive numerical experiments validating
the proposed coflow fairness framework and the related algorithms. The
numerical have been performed on a matlab${}^{\mbox{\tiny\textregistered}}$
coflow scheduling simulator equipped with a coflow generator222The simulator
is Open Source and it will be made available on GitHub; to obtain the source
code of the simulator the reader is encouraged to contact the authors of the
manuscript.. For the algorithms based on $\sigma$-order, namely Sincronia and
CoFair, the rate allocation is based on the greedy procedure. It assigns full
priority to coflow $k$ over coflow $h$ on all ports where they are both active
if $\sigma(k)\leq\sigma(k+1)$. This rate allocation has the advantage of
simplicity of implementation, at the price of some performance loss against,
for instance, the rate allocation adopted in Utopia which permits some rate
back-filling for coflows in lower priority.

Sample Coflow batches. As indicated in the analysis of Facebook traces
reported in [5], a typical coflow pattern observed in data centers may
comprise a significant fraction of small coflows but also coflows with large
width (i.e., number of flows). These type of instances are denoted wide-narrow
coflows batches (WN). The first set of coflow batches considered has a
fraction $q$ of coflows whose width is drawn uniformly from $M/3,\ldots,M$
($M$ being the number of ports) and a fraction $1-q$ of coflows containing
single flows. The second set of coflow batches are the Map-Reduce type (MR).
They are classified according to the number of mappers and the number of
reducers, which are drawn from a uniform distribution in $[1,m]$ and $[1,r]$,
respectively. Each reducer fetches data from each mapper. For all coflow
samples, individual flow volumes are exponentially distributed with average
$10$ and standard deviation $3$ in normalized traffic volume units. Links are
normalized with capacity $1$ traffic volume units per second.

Performance and fairness metrics. The metrics employed for numerical
validation are the CCT, the experimental slowdown and the stretch index (SI).
The experimental slowdown for a tagged coflow $j$ is
$\widehat{E}_{j}=\phi_{j}C_{j}/C_{j}^{0}$: it embraces the plain slowdown for
$\phi_{j}=1$ and the port-occupation one for $\phi=V_{j}$. Finally, for a
tagged coflow $j$, the stretch index (SI), i.e.,
$SI:=\sum\max(0,(\widehat{E}_{j}/E)-1)$, quantifies the relative magnitude of
violations w.r.t. the target slowdown constraint parameter $E$.

###  VII-A Minimum slowdown estimation.

$\phi_{j}=1$$\phi_{j}=V_{j}$

$\phi_{j}=1$$\phi_{j}=V_{j}$

a)b)

Figure 3: Relative error on the minimum slowdown for $N=M=10$: a) increasing
$q$ b) increasing $N$ and increasing $N$ for fixed $q=0.2$.

As described in Sec. IV, the minimum slowdown $E^{*}$ corresponds to the
largest average progress that can be ensured to all the coflows in a batch.
Fig. 3a and 3b reported on the relative error which is obtained by
approximating $E^{*}$ using the value attained for the primal value $E^{p}$
generated as output of MPS. Each point of those graphs is obtained by
averaging the relative error obtained over $100$ batch instances, where the LP
solution corresponds to a time slot of $1$ second.

Fig. 3a reports on the approximation results in the case or increasing values
of $q$, $M=N=10$, whereas Fig. 3b reports on the same experiment for
increasing values of $N$. In both cases, the approximation improves for larger
values of $q$ and $N$, respectively. The important information is that the
approximation improves the higher the fabric congestion, and it appears very
tight, i.e., the relative error is bounded below $10^{-4}$ for $\phi=V_{j}$
and $3\times 10^{-3}$ for $\phi=1$. These results confirm that the minimum
slowdown of the primal problem $E^{p}$ appears an extremely tight
approximation compared against the exact value $E^{*}$ obtained by solving the
corresponding LP. For each set of $100$ experiments we observed at most $1$
outlier, i.e., a batch for which the relative error falls above $1\%$. By
inspection, we found that this happens for very specific cases where a coflow
batch has several bottlenecks of same size, and where a primal-feasible
schedule may prioritize certain coflows on bottlenecks where in turn they slow
down others, thus increasing the maximum slowdown value for that batch.

###  VII-B Plain slowdown: $\phi_{j}=1$.

This set of experiments considers the plain slowdown, i.e., $\phi_{j}=1$. With
this choice, between two coflows with same volume, it is fair if the coflow
with the lowest CCT in isolation finishes first. In each experiment, same
coflow instances are processed using Sincronia, CoFair and Utopia. In all
experiments, CoFair receives $E^{*}$ as output of MPS. For the plain slowdown,
the Jain index
$J(\mathbf{R})=\frac{1}{K}\frac{\sum_{j=1}^{K}R_{j}^{2}}{(\sum_{j=1}^{K}R_{j})^{2}}$
can measure how fair is the progress distribution among coflows, i.e., the
average rate $R_{j}$.

a)

b)

Figure 4: Average CCT normalized against Sincronia for $M=30$: a) $p=0.2$ and
$N=30$ and b) $p=0.8$ and $N=100$; $95\%$ confidence intervals are
superimposed.

a)

b)

c)

d)

Figure 5: WN traces: a) and c) CCDF of the normalized slowdown; b) and d) CCDF
of the stretch index; setting: $M=30$, $q=0.2$ and $N=30$ for a) and b);
$q=0.8$ and $N=100$ for c) and d).

Fig. 4a, Fig. 5a and Fig. 5b refer to the performance figures measured for an
experiment with $100$ batches of coflows of NW type for $p=0.2$ and $N=30$.
Performance figures reported in Fig. 4b and Fig. 5c and d refer to $p=0.8$ and
$N=100$.

Fig. 4 reports on the average CCT attained by Sincronia, CoFair and Utopia: to
this respect, the average CCT of CoFair and Sincronia coincide. On the other
hand, the performance loss degradation of Utopia w.r.t. Sincronia and CoFair
is significant, i.e., on the order of $17\%$ for $p=0.2$ and $9\%$ for
$p=0.8$. For $p=0.2$ the Jain index of CoFair is $0.60$, for Sincronia is
$0.59$ whereas Utopia only scores $0.53$. Conversely, for $p=0.8$ the Jain
index of CoFair is $0.61$, for Sincronia is $0.60$ whereas Utopia scores
$0.58$.

Fig. 5 illustrates the complementary cumulative distribution function (CCDF)
of the slowdown and of the stretch index. The dashed vertical line seen in
Fig. 5a and Fig. 5c separates the inner interval on the left where
$\widehat{E}_{j}\leq E^{*}$, i.e., no violation occurs, and the outer interval
$\widehat{E}_{j}>E^{*}$, i.e., where the slowdown does not meet the target. As
observed in Fig. 5a, Sincronia and CoFair provide the best performance for
$\widehat{E}_{j}\leq E^{*}$. However, as expected, it suffers a larger number
of violations compared to Utopia. Finally, CoFair matches the behavior of
Sincronia for $\widehat{E}_{j}\leq E^{*}$ and Utopia for $\widehat{E}_{j}\geq
E^{*}$, even though the rare violations, when they occur, appear relatively
larger. Same behaviour is confirmed for $p=0.8$ in Fig. 4a, Fig. 5a and Fig.
5b. In this case, due to the increased congestion, the violations of Sincronia
are larger than in the previous experiments, and yet CoFair balances between a
near optimal CCT minimization and slowdown guarantees.

a)

b)

c)

d)

Figure 6: MR traces: a) and c) CCDF of the normalized slowdown; b) and d) CCDF
of the stretch index; setting: $M=30$, and $N=30$, $m=10$ and $r=3$ for a) and
b);$M=30$, and $N=100$, $m=10$ and $r=10$ $q=0.8$ and $N=100$ for c) and d).

The same experiments are repeated for MR coflow batches under different
configurations on the number of mappers and reducers. These coflow batches
generate severe congestion both at the input and at the output ports of the
fabric. Fig. 6a and Fig. 6b refer to the case of $100$ batches of coflows with
$N=30$ MR coflows where $m=10$ and $r=3$. As before, Sincronia and CoFair
provide the best performance in the inner interval. However, Sincronia has a
significant number of deviations, i.e., on the order of $10\%$ for coflows,
whereas Utopia provides a better performance in terms of deviation. This is
confirmed also by the Jain index, where CoFair scores $0.89$, Sincronia $0.88$
ad Utopia $0.87$. Ultimately, CoFair matches Sincronia in the inner interval
and Utopia in the outer one, providing a better tradeoff.

The experiment is hence performed for $m=10$ and $r=10$ and $N=100$ coflows.
Again, the slowdown CCDF of CoFair is practically superimposed to that of
Sincronia in the inner interval and incurs very few violations ($<10^{-3}$).
With respect to the Jain index for the coflow progress, CoFair and Sincronia
score $0.84$ whereas Utopia $0.80$.

a)

b)

Figure 7: Average CCT normalized against Sincronia for $M=30$: a) $p=0.2$ and
$N=30$; b) $p=0.8$ and $N=100$.

a)

b)

c)

d)

Figure 8: WN traces, $\phi_{j}=V_{j}$ a) and c) CCDF of the normalized
slowdown; b) and d) CCDF of the stretch index; setting: $M=30$, $q=0.2$ and
$N=30$ for a) and b); $q=0.8$ and $N=100$ for c) and d).

a)

b)

c)

d)

Figure 9: MR traces, $\phi_{j}=V_{j}$: a) and c) CCDF of the normalized
slowdown; b) and d) CCDF of the stretch index; setting: $M=30$, and $N=30$,
$m=10$ and $r=3$ for a) and b);$M=30$, and $N=100$, $m=10$ and $r=10$ $q=0.8$
and $N=100$ for c) and d).

a)

b)

c)

d)

Figure 10: WN traces, $\phi_{j}=V_{j}$: a) and c) scatter diagram and b) and
d) corresponding average CCT; setting:$M=30$, a) and b) $q=0.2$ and $N=30$ c)
and d) $q=0.8$ and $N=100$.

###  VII-C Slowdown with port occupation: $\phi_{j}=V_{j}$.

By letting $\phi_{j}=V_{j}$, the average port occupation is embedded in the
slowdown definition: between two coflows with the same volume, it is fair if
the one with lower average port occupation finishes first. Fig. 7a and Fig. 7b
describe the effect of the slowdown constraint $E$ onto the average CCT for a
fabric with $M=30$ ports and $N=30,50,100$ coflows of type WN for $p=0.2$.
Results are averaged on hundred sample batches and normalized against the
average CCT of the near optimal solution provided by Sincronia; $95\%$
confidence intervals are superimposed. The average CCT decreases for
increasing values of $E$: this behavior mimics the $\alpha$ parameter of
classic flow $\alpha$-fairness. As depicted in Fig. 7a, $E$ can be tuned in
order to attain a tradeoff between coflow slowdown and average CCT, where the
loss in CCT gain over Sincronia tops at $40\%$ for $p=0.2$ and $N=100$: this
represents the loss in performance in order to grant all coflows the target
slowdown. Same result is described in figure Fig. 4d for $p=0.8$: in presence
of many large coflows, the range of the tradeoff is smaller.

Fig. 8a/c and b/d report on the CCDF of the normalized slowdown and the
corresponding stretch index, respectively, for two experiments on $100$ coflow
batches. By comparing the distributions of the different algorithms for
$p=0.2$, i.e., Fig. 5a and Fig. 5b, it is apparent that CoFair provides the
best slowdown-efficiency tradeoff, whereas both baselines do not perform well
both in terms of normalized slowdown and in terms of stretch index. The same
behavior is observed for $p=0.8$: CoFair and Utopia perform similar in the
inner interval, but the slowdown CCDF of CoFair bends clearly in proximity of
$E^{*}$ thus attaining a negligible number of violations. The tail of the SI
distribution shows that their magnitude is relatively larger than those of
Utopia in the same region. In these experiments, both Utopia and Sincronia
have a rate of violations on the order of $10-20\%$.

The same experiment is repeated for the MR batches in Fig. 9. As in the
previous cases, Sincronia and CoFair provide the best performance in terms of
slowdown. In this case, not only Sincronia but also Utopia has a significant
number of deviations, i.e., on the order of $10\%$ for coflows in the inner
interval. CoFair provides the best tradeoff, outperforming Utopia in the outer
interval. The experiment is hence performed for $m=10$ and $r=10$ and $N=100$
coflows. In this case, the CCDF tail of ¡CoFair in the outer interval is
negligible, whereas Sincronia and Utopia show deviations larger than $15\%$.

Finally, in order to provide better understanding on the behavior of the
algorithms, Fig. 10a and Fig. 10b show the scatter diagram of the normalized
CCT and the slowdown for each coflow corresponding to the experiments of Fig.
8a and Fig. 8b. As seen in Fig. 10, in order to reduce the slowdown, CoFair
tends to concentrate several coflows in the region where the slowdown is
smaller at the price of higher CCT. In order to remark the tradeoff
efficiency-fairness, the resulds for the runs of CoFair for $E=1.1E^{*}$ have
been added. As seen before in Fig. 5, the performance in terms of slowdow is
very similar to Utopia. However, here parameter $E$ acts as a fairness-
efficiency knob as depicted in Fig. 9b. In fact, while matching the same CCT
of Utopia, CoFair attains a significantly smaller number of violations. Fig.
9c and d report on the settings of Fig. 5c and Fig. 5d. Here, by letting on
$E=1.4\,E^{*}$ CoFair overlaps the slowdown performance of Utopia, and yet it
provides average CCT figures very close to that of Sincronia.

##  VIII Conclusions and discussion.

The data transfer phase of modern computing frameworks requires to serve
several concurrent coflows. This paper introduces a framework for coflow
scheduling to trade off the average CCT for coflows’ slowdown. It requires a
single control parameter, that is the maximum slowdown for an input batch of
coflows. Scheduling under slowdown contraints has larger feasibility set
compared to the popular notion of progress based on minimum rate guarantees.
The maximum possible progress, i.e., the minimum possible slowdown, can be
calculated with great accuracy in $O(MN+N\log(N))$.

A new scheduler, i.e., CoFair, has extended the framework of primal-dual
$\sigma$-order schedulers to account for generalized slowdown constraints. The
experimental results indicate that slowdown-aware $\sigma$-order generated by
CoFair can adjust the priority of coflows with no apparent loss in performance
with respect to near optimal benchmarks for average CCT minimization. Finally,
based on the notion of generalized slowdown, CoFair and the proposed framework
can perform coflow scheduling by accounting for specific features, e.g., the
occupancy of the fabric ports.

## References

  * [1] M. Chowdhury and I. Stoica, “Coflow: A networking abstraction for cluster applications,” in _Proc. of ACM HotNets_ , Redmond, Washington, 2012, p. 31–36.
  * [2] J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” in _Proc. of USENIX OSDI_ , San Francisco, CA, 2004, pp. 137–150.
  * [3] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, I. Stoica _et al._ , “Spark: Cluster computing with working sets.” _in Proc. of USENIX HotCloud_ , vol. 10, no. 10-10, p. 95, 2010.
  * [4] M. Han and K. Daudjee, “Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems,” _in Proc. of VLDB_ , vol. 8, no. 9, pp. 950–961, 2015.
  * [5] N. M. K. Chowdhury, “Coflow: A networking abstraction for distributed data-parallel applications,” Ph.D. dissertation, University of California, Berkeley, 2015.
  * [6] Y. Chen and J. Wu, “Joint coflow routing and scheduling in leaf-spine data centers,” _Elsevier Journal of Parallel and Distributed Computing_ , vol. 148, pp. 83–95, 2021.
  * [7] M. Chowdhury _et al._ , “Near optimal coflow scheduling in networks,” in _Proc. of ACM SPAA_ , Phoenix, AZ, USA, June 22-24 2019, pp. 123–134.
  * [8] S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, D. Shmoys, and A. Vahdat, “Sincronia: Near-optimal network design for coflows,” in _Proc. of ACM SIGCOMM_ , 2018, pp. 16–29.
  * [9] R. Mao, V. Aggarwal, and M. Chiang, “Stochastic non-preemptive co-flow scheduling with time-indexed relaxation,” in _Proc. of IEEE INFOCOM, DCPerf Workshop_ , Honolulu, Hawaii, US, April 16 2018, pp. 385–390.
  * [10] L. Wang, W. Wang, and B. Li, “Utopia: Near-optimal coflow scheduling with isolation guarantee,” in _Proc. of IEEE INFOCOM_ , Honolulu, Hawaii, US, April 16 2018, pp. 891–899.
  * [11] M. Shafiee and J. Ghaderi, “Scheduling coflows in datacenter networks: Improved bound for total weighted completion time,” _SIGMETRICS Perform. Eval. Rev._ , vol. 45, no. 1, p. 29–30, Jun. 2017.
  * [12] M. Chowdhury, Y. Zhong, and I. Stoica, “Efficient coflow scheduling with Varys,” in _Proc. of ACM SIGCOMM_ , Chicago, Illinois, USA, 2014, p. 443–454.
  * [13] S. Ahmadi, S. Khuller, M. Purohit, and S. Yang, “On scheduling coflows,” _Algorithmica_ , vol. 82, no. 12, p. 3604–3629, dec 2020. [Online]. Available: https://doi.org/10.1007/s00453-020-00741-3
  * [14] S. Shakkottai and R. Srikant, “Network optimization and control,” _Foundations and Trends in Networking_ , vol. 2, no. 3, pp. 271–379, 2008\.
  * [15] J. Mo and J. C. Walrand, “Fair end-to-end window-based congestion control,” _IEEE/ACM Trans. on Networking_ , vol. 8, no. 5, pp. 556–567, 2000.
  * [16] M. Alizadeh, S. Yang, M. Sharif, S. Katti, N. McKeown, B. Prabhakar, and S. Shenker, “Pfabric: Minimal near-optimal datacenter transport,” _SIGCOMM Comput. Commun. Rev._ , vol. 43, no. 4, p. 435–446, aug 2013. [Online]. Available: https://doi.org/10.1145/2534169.2486031
  * [17] L. Chen, W. Cui, B. Li, and B. Li, “Optimizing coflow completion times with utility max-min fairness,” in _Proc. of IEEE INFOCOM_ , April 2016, pp. 1–9.
  * [18] L. Chen, Y. Feng, B. Li, and B. Li, “Efficient performance-centric bandwidth allocation with fairness tradeoff,” _IEEE TPDS_ , vol. 29, no. 8, pp. 1693–1706, 2018.
  * [19] W. Wang, S. Ma, B. Li, and B. Li, “Coflex: Navigating the fairness-efficiency tradeoff for coflow scheduling,” in _Proc. of IEEE INFOCOM_ , Atlanta, GA, USA, 1-4 May 2017, pp. 1–9.
  * [20] M. Chowdhury, Z. Liu, A. Ghodsi, and I. Stoica, “HUG: Multi-resource fairness for correlated and elastic demands,” in _Proc. of USENIX NSDI_ , Santa Clara, CA, March 2016, pp. 407–424.
  * [21] L. Chen, Y. Feng, B. Li, and B. Li, “Efficient performance-centric bandwidth allocation with fairness tradeoff,” _IEEE TPDS_ , vol. 29, no. 8, pp. 1693–1706, 2018.
  * [22] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, “Dominant resource fairness: Fair allocation of multiple resource types,” in _Proc. of USENIX NSDI_ , USA, 2011, p. 323–336.
  * [23] M. Mastrolilli, M. Queyranne, A. S. Schulz, O. Svensson, and N. A. Uhan, “Minimizing the sum of weighted completion times in a concurrent open shop,” _Operations Research Letters_ , vol. 38, no. 5, pp. 390–395, 2010\.
  * [24] T. Zhang, R. Shu, Z. Shan, and F. Ren, “Distributed bottleneck-aware coflow scheduling in data centers,” _IEEE TPDS_ , vol. 30, no. 7, pp. 1565–1579, July 2019.
  * [25] B. Radunovic and J.-Y. Le Boudec, “A unified framework for max-min and min-max fairness with applications,” _IEEE/ACM Trans. on Networking_ , vol. 15, pp. 1073 – 1083, 11 2007.
  * [26] H. Qu, R. Xu, W. Li, W. Qu, and X. Zhou, “OSTB: Optimizing fairness and efficiency for coflow scheduling without prior knowledge,” in _Proc. of IEEE HPCC_ , 2019, pp. 1587–1594.
  * [27] S.-H. Tseng and A. Tang, “Coflow deadline scheduling via network-aware optimization,” in _in Proc. of the Annual Allerton Conference on Communications, Control and Computing_ , 2018, pp. 829–833.
  * [28] Q. Luu, O. Brun, R. El Azouzi, F. De Pellegrini, B. J. Prabhu, and C. Richier, “DCoflow: deadline-aware scheduling algorithm for coflows in datacenter networks,” in _Proc. of IFIP Networking_ , June 13-16 2022, pp. 1–9.
  * [29] W. Wang, S. Ma, B. Li, and B. Li, “Coflex: Navigating the fairness-efficiency tradeoff for coflow scheduling,” in _Proc. of IEEE INFOCOM_ , Atlanta, GA, USA, 1-4 May 2017, pp. 1–9.
  * [30] J. Cheriyan, R. Ravi, and M. Skutella, “A simple proof of the moore-hodgson algorithm for minimizing the number of late jobs,” _Operations Research Letters_ , vol. 49, no. 6, pp. 842–843, 2021.
  * [31] M. Queyranne, “Structure of a simple scheduling polyhedron,” _Mathematical Programming_ , vol. 58, pp. 263–285, 1993.

## Proof of Thm. 2

###### Proof:

The feasibility of the PS problem can be formulated with the following LP

$\displaystyle\mbox{minimize:}\;0$ (23) subj. to:
$\displaystyle\sum_{t=1}^{T}x_{j}^{i}(t)=1,\quad\forall
j\in{\mathscr{C}},i\in{\mathscr{F}}_{j}$ (24) $\displaystyle Z_{j}(t)\leq
0,\forall t\leq r_{j}$ (25) $\displaystyle Z_{j}(t)\geq 1,\forall
t>\frac{E\cdot(C_{j}^{0}-r_{j})}{V_{j}}+r_{j}$ (26)
$\displaystyle\sum_{j\in{\mathscr{C}}}\sum_{i\in{\mathscr{F}}_{i}}v_{j}^{i}x_{j}^{i}(t)\chi_{j}^{i}(\ell)\leq
B_{\ell},\;\forall t,\forall\ell\in{\mathscr{L}}$ (27) $\displaystyle
x_{j}^{i}(t)\in[0,1],\;\forall t$ (28)

The above LP is obtained by considering any rate allocation for which the
constraints of PS are respected: (26) has replaced the constraints (6) and (7)
in PS. Since LP is in P this completes the proof of the first part of the
statement. The second part statement follows by observing that from (26),
$\frac{E\cdot(C_{j}^{0}-r_{j})}{V_{j}}+r_{j}\geq\frac{E\cdot
C_{j}^{0}}{V_{j}}$ if and only if $E\geq V_{j}$ for all $j\in{\mathscr{C}}$,
which holds true since $C_{j}\geq C_{j}^{0}$ for all $j\in{\mathscr{C}}$. ∎

## Proof of Thm. 6

###### Proof:

Let define a feasible solution for the Primal LP problem. For every pair
$(\mu_{k},\sigma(k))$ let define $C_{\sigma(k)}=\sum_{j\leq
k}p_{\mu_{k},\sigma(j)}$; since Primal LP is feasible, the slowdown constraint
in the primal formulation is satisfied at each step as from Lemma 1. Parallel
inequalities hold by applying port-wise results in single machine scheduling
[31].

For the Dual LP, let consider solutions of the type

$y_{\ell,A}=\begin{cases}\theta_{k}>0&\ell=\mu_{k}\;\mbox{and}\;A=F_{k}\;\mbox{for
some}\;k\\\ 0&\mbox{otherwise}\end{cases}$ (29)

where $\mu_{k}$ is the bottleneck selected at step $k$ and ${\mathscr{F}}_{k}$
is the corresponding set of tail-feasible coflows. The corresponding form of
the constraints of the dual problem

$\sum_{k=j}^{N}q_{\mu_{k},\sigma(j)}\,y_{\mu_{k},F_{k}}=w_{\sigma(j)}+\alpha_{\sigma(j)},\quad
j\in{\mathscr{C}}$ (30)

where $q_{\mu_{k},j}=p_{\mu_{k},j}{\mathbf{1}}\\{j\in F_{k}\\}$. If at each
step $k=N,\ldots,2,1$ the selection is

$\sigma(k)=\operatorname*{\arg\\!\min}\limits_{j\in
F_{k}}\left\\{\frac{w_{j}^{k}}{p_{\mu_{N},j}}\right\\}$ (31)

the algorithm produces a non-negative solution of the linear system (30). In
fact, let first consider step $k=N$. The full rank system of the constraints
of the dual system writes

$\left(\begin{array}[]{cccc|c}q_{{}_{\mu_{N}\sigma(N)}}&0&\ldots&0&w_{\sigma(N)}^{(N+1)}\\\
q_{{}_{\mu_{N}\sigma(N-1)}}&q_{{}_{\mu_{N-1}\sigma(N-1)}}&\ldots&0&w_{\sigma(N-1)}^{(N+1)}\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
q_{{}_{\mu_{N}\sigma(1)}}&q_{{}_{\mu_{N-1}\sigma(1)}}&\ldots&q_{{}_{\mu_{1}\sigma(1)}}&w_{\sigma(1)}^{(N+1)}\\\
\end{array}\right)$

The Gaussian elimination using $\sigma(N)$ as pivot renders the new equivalent
system

$\small\left(\\!\\!\begin{array}[]{cccc|c}1&0&\ldots&0&\frac{w_{{}_{\sigma(N)}}^{N}}{p_{{}_{\mu_{N},\sigma(N)}}}\\\\[8.53581pt]
0&p_{{}_{\mu_{N-1}\sigma(N-1)}}&\ldots&0&w_{{}_{\sigma(N-1)}}^{N}\\!-\\!w_{{}_{\sigma(N)}}^{N}\frac{p_{{}_{\mu_{N}\sigma(N-1)}}}{p_{{}_{\mu_{N}\sigma(N)}}}\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&p_{{}_{\mu_{N-1}\sigma(1)}}&\ldots&p_{{}_{\mu_{1},\sigma(1)}}&w_{\sigma(1)}^{N}\\!-\\!w_{\sigma(N)}^{N}\frac{p_{{}_{\mu_{N}\sigma(1)}}}{p_{{}_{\mu_{N}\sigma(1)}}}\\\
\end{array}\\!\\!\right)$

Observe that the first column is nullified irrespective of the chosen
permutation $\sigma(j)$ for $j<N$. The system has been transformed in the
equivalent one where Gaussian elimination can now be performed on the
rightmost square sub-matrix. Let replace in the column on the right with the
following values

$\displaystyle\small\hskip-19.91692ptw_{j}^{N-1}=\frac{w_{\sigma(N)}^{N}}{p_{{}_{\mu_{N}\sigma(N)}}},j=\sigma(N)$
$\displaystyle\small\hskip-19.91692ptw_{j}^{N-1}=w_{j}^{N}-w_{\sigma(N)}^{N}\frac{p_{\mu_{N},j}}{p_{\mu_{N},\sigma(N)}}\geq
0,j\in F_{k}\setminus\\{\sigma(N)\\}$
$\displaystyle\small\hskip-19.91692ptw_{j}^{N-1}=w_{j}^{N},j\not\in F_{k}$

where $w_{j}^{N-1}\geq 0$ for all $j\in{\mathscr{C}}$. Indeed,
$y_{\mu_{N}F_{N}}=\frac{w_{\sigma(N)}^{N}}{p_{{}_{\mu_{N}\sigma(N)}}}$. The
algorithm iterates the procedure on the remaining subsystem using the corner
element of $\sigma(k)$ as pivot so that at each step
$y_{\mu_{k},F_{k}}=\theta_{k}=\frac{w_{\sigma(k)}^{N}}{p_{{}_{\mu_{k}\sigma(k)}}}\geq
0$. ∎

Note that unscheduled coflows which are non primal-feasible at a given step do
not take part to gaussian elimination.

## Proof of Thm. 7

###### Proof:

The sketch of the proof is as follows. First, by linearity rescaling weights
$\\{\kappa\cdot w_{j}\\}$ is irrelevant. The Smith ratio at the $k$-th step
for a candidate coflow

$\small\\!\frac{w_{{}_{\sigma(N-k)}}^{{}^{(N-k)}}}{P_{{}_{\mu_{k}\sigma(N-k)}}}\\!=\\!\frac{w_{{}_{\sigma(N-k)}}\\!\\!\\!+\alpha_{{}_{\sigma(N-k)}}\\!\\!\\!-\sum_{h=1}^{k}w_{{}_{\sigma(N-k+h)}}^{{}^{(N-k+h)}}\frac{P_{{}_{\mu_{h}\sigma(N-k)}}}{P_{{}_{\mu_{h}\sigma(N-k+h)}}}}{P_{{}_{\mu_{k}\sigma(N-k)}}}$

Hence, to enforce the desired $\sigma$-order $\sigma^{*}$ as output, let start
by an input set $\alpha_{j}=1$, for all $j$, and choose
$\alpha_{\sigma^{*}(N-k)}$ such in a way that the Smith ratio of for
$\sigma^{*}(N-k)$ be minimal among all candidate coflows, simply by rendering
$(w_{{}_{\sigma(N-k)}}+\alpha_{{}_{\sigma(N-k)}})$ small enough as compared to
the other coflows, possibly rescaling all weights $w_{j}$ by $\kappa$. Using
$\\{\alpha_{j}\\}$ as input to the algorithm produces the desired output
$\sigma^{*}$. ∎

## Proof of Thm. 8

###### Proof:

For $C_{j},$ output of Alg. 2, it holds

$\displaystyle\sum_{j=1}^{N}w_{j}C_{j}=\sum_{j=1}^{N}C_{j}\Big{(}\sum_{\ell\in{\mathscr{L}}}\sum_{A\subseteq{\mathscr{C}}:j\in
S}y_{\ell,A}\,p_{\ell,j}-\alpha_{j}\Big{)}$
$\displaystyle=\sum_{j=1}^{N}C_{\sigma(j)}\Big{(}\sum_{k=j}^{N}p_{\mu_{k},\sigma(j)}y_{\mu
F_{k}}-\alpha_{\sigma(j)}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\sum_{k=1}^{N}y_{\mu_{k}F_{k}}\sum_{j=1}^{k}p_{\mu_{k}\sigma(j)}C_{\sigma(j)}-\sum_{j=1}^{N}\alpha_{j}C_{j}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\sum_{k=1}^{N}y_{\mu_{k}F_{k}}\Big{(}\sum_{j=1}^{k}p_{\mu_{k}\sigma(j)}\Big{)}^{2}-\sum_{j=1}^{N}\alpha_{j}C_{j}$
$\displaystyle\leq
2\Big{(}\sum_{k=1}^{N}y_{\mu_{k}F_{k}}f_{\mu_{k}}(F_{k})-\alpha_{k}C_{k}\Big{)}+\sum_{j=1}^{N}\alpha_{j}(2D_{j}-C_{j})$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}2\sum_{k=1}^{N}w_{k}{C_{k}^{\mbox{\tiny{LP}}}}+\sum_{j=1}^{N}\alpha_{j}(2D_{j}-C_{j})$
$\displaystyle\leq
2\sum_{k=1}^{N}w_{k}{C_{k}^{\mbox{\tiny{OPT}}}}+2\sum_{j=1}^{N}\alpha_{j}D_{j}$

Where the following arguments hold: $(i)$ follows from the fact that in
general $j\in F_{k}$ does not imply $j\in F_{k+1}$ and $(ii)$ follows from the
fact that $C_{\sigma(k)}=\sum_{j=1}^{k}p_{\mu_{k}\sigma(j)}\geq C_{\sigma(j)}$
for all $k=1,\ldots,j$. According to Lemma. 2, it holds

$\sum_{j=1}^{N}w_{j}{\widehat{C}_{j}}\leq 2\sum_{j=1}^{N}w_{j}C_{j}\leq
4\sum_{k=1}^{N}w_{k}{C_{k}^{\mbox{\tiny{OPT}}}}+4\sum_{j=1}^{N}\alpha_{j}D_{j}$

which concludes the proof. ∎