\(n\) coflows, coflow will be represented as matrix \(D^j = [d^j_{io}]\)
For every coflow \(j\):
\(r_j\): release time
\(w_j\): weight
Minimize: \(\sum_{i=1}^n w_j\cdot C_j\).
\(C_j\): completion time. A coflow is finished when all its flows are scheduled
Problem Description
\(d^j_{io}\): demand from input port \(i\) to output port \(o\)
Discrete time
At each time slot an input/output port can send/receive at most one unit of flow.
Schedule a single coflow: matching!
Matching
Matching
Matching
Theorem
A coflow \(G\) with largest degree \(\Delta(G)\) can be scheduled in \(\Delta(G)\) time.
Existing Results*
Deterministic
Randomized
Zero release time
\(\frac{64}{3}\)
\(8 + \frac{16\sqrt{2}}{3}\)
Arbitrary release time**
\(\frac{76}{3}\)
\(9 + \frac{16\sqrt{2}}{3}\)
*: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 (pp. 294-303). 2015, ACM.**:The authors claimed a ratio of \(\frac{67}{3}\), but the proof only holds when all release times are the same.
Improvements
S. Khuller and M. Purohit* use black-box reduction to Concurrent Open Shop, and get
Use LP (or Primal-Dual) to find a solution, which generates an ordering of coflows according to the non-decreasing order of completion time.
Consider each coflow \(i\) according to the ordering, move edges backward, i.e. move flows to previous coflows \(j < i\) without violating the largest degree \(\Delta(G_j)\). The new graph is denoted as \(G_i'\).
Schedule the coflows one by one, within \(\Delta(G_i')\) time, using modified Hall's Theorem.
Concurrent Open Shop
\(n\) jobs to be scheduled on \(m\) different machines
Each job \(j\) consists of many tasks. For each machine \(i\), there is an task that takes \(d^j_i\) time to finish
Use LP (or Primal-Dual) to find a solution, which generates an ordering of coflows according to the non-decreasing order of completion time.
Consider each coflow \(i\) according to the ordering, move edges backward, i.e. move flows to previous coflows \(j < i\) without violating the largest degree \(\Delta(G_j)\). The new graph is denoted as \(G_i'\).
Schedule the coflows one by one, within \(\Delta(G_i')\) time, using modified Hall's Theorem.
Consider the most loaded port \(i\) and the coflow \(j\) with largest release time
Test if \(r_j > \kappa \cdot L_i\):
If \(r_j > \kappa \cdot L_i\): put coflow \(j\) at last
If \(r_j \leq \kappa \cdot L_i\): raise the corresponding dual variable, put it at first if some constraint gets tight
Loop through step 1, 2, until all coflows got a position
Use the ordering above to move edges backward, and schedule each coflow
Open questions
Consider flow time instead of completion time, possibly using augmented resources.
Since coflow scheduling generalizes concurrent open shop, it is NP-hard to approximate it within a factor better than \((2-ε)\)*. We have an approximation factor of 4.