Improved algorithms speed up coflow data scheduling efficiency
Improved Approximations for Coflow Scheduling via Iterated Rounding and Stable Matchings
Data Structures and Algorithms
Summary
Coflow scheduling is about planning how data moves through a computer network to finish jobs faster. The authors found new ways to schedule these data flows that work better and faster than previous methods. They used a smart step-by-step technique and a matching method originally designed to pair people evenly. Their improvements mean networks can handle complex data movement with fewer delays.
What this means in practice
- •For data center network operators: Optimize data transfer schedules to reduce job completion times and overall network congestion when handling multiple related data flows.
- •For cloud infrastructure engineers: Implement more efficient resource allocation algorithms for managing data movement priorities under varying job release times.
Authors
Mikhail Cherniavskii, Arseni Fedorovich, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev, Fedor Ozhegov, Alexander Shekhovtsov
Abstract
We study Coflow Scheduling, introduced by Chowdhury, Zhong, and Stoica (2014). We give deterministic polynomial-time algorithms achieving a $2.77$-approximation without release dates and a $3.17$-approximation with integer release dates. These improve the $3.42$ and $4.36$ guarantees of Rohwedder and Schnaars (2025). Our approach combines two ideas: (1) a novel iterated rounding scheme, and (2) Galvin's list edge coloring method, which is based on the Gale--Shapley stable matching algorithm.