Grainger College of Engineering, All Events

View Full Calendar

A Practical 4-Approximation Algorithm for Coflow Schedulingl

Event Type
Seminar/Symposium
Sponsor
ISE Graduate Seminar
Date
Oct 4, 2019   10:00 - 10:50 am  
Speaker
David Shmoys, Cornell University
Views
109
Originating Calendar
ISE Seminar Calendar

ABSTRACT:
Coflows are an emerging network abstraction introduced to model traffic patterns within a datacenter. This abstraction naturally leads to several scheduling optimization problems, and we consider, in particular, optimizing for the sum of weighted completion times. There has been recent work from both the theory and systems communities on this scheduling problem, leading to either practical solutions that perform well in practice and are easy to implement, or theoretical solutions with bounded performance guarantees, albeit not both. In this work, we bridge this gap, and present Sincronia, a network design that matches the best known approximation guarantee, while empirically outperforming the existing state-of-the-art network designs. Sincronia achieves this using a key technical result — we show that given a “right” ordering of coflows, any per-flow rate allocation mechanism achieves average coflow completion time within a factor of 4 of the optimal as long as (co)flows are prioritized with respect to the ordering. We obtain this right ordering of coflows using a primal-dual algorithm.

This is joint work with Saksham Agarwal, Shijin Rajakrishnan, Akshay Narayan, Rachit Agarwal, and Amin Vahdat.

link for robots only