Regularization-Based Coflow Scheduling in Optical Circuit Switches

Haisheng Tan, Chi Zhang, Chao Xu, Y P LI, Zhenhua Han, Xiang Yang Li

Research output: Contribution to journalArticlepeer-review

Abstract

To improve the application-level data efficiency, the scheduling of coflows, defined as a collection of parallel flows sharing the same objective, is prevailing in recent data centers. Meanwhile, optical circuit switches (OCS) are gradually applied to provide high data rate with low power consumption. However, so far few research outputs have covered the flow, let alone the coflow, scheduling in the context of OCS. In this work, we investigate coflow scheduling in OCS-based data centers. We first derive a novel operation called regularization processed respectively on the flow traffic demands and the flow start times, which can be efficiently implemented and reduce the circuit reconfiguration frequency dramatically. We then propose a 2-approximation algorithm, called Reco-Sin, for single coflow scheduling to minimize the coflow completion time (CCT). For multiple coflows, we derive Reco-Mul to minimize the total weighted CCT, which can transform any non-preemptive multi-coflow scheduling in packet switches to a scheduling scheme in OCS. Reco-Mul can achieve a constant approximation under the assumption that no tiny flows will be transmitted in OCS. To get rid of this assumption, we present another multiple coflow scheduling scheme, named Reco-Mul+, which has an approximation ratio of O(K). Here, K is the total number of coflows. Extensive simulations based on Facebook data traces show that our approaches outperform state-of-the-art schemes significantly, i.e., one single coflow can be finished up to 1.97times faster with Reco-Sin, and multiple coflows can be completed up to more than 2times faster with Reco-Mul and Reco-Mul+.

Original languageEnglish
Article number9359108
Pages (from-to)1280-1293
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume29
Issue number3
DOIs
Publication statusPublished - Jun 2021

Scopus Subject Areas

  • Software
  • Electrical and Electronic Engineering
  • Computer Networks and Communications
  • Computer Science Applications

User-Defined Keywords

  • Approximation Algorithm
  • Coflow Scheduling
  • Data centers
  • Integrated circuit modeling
  • Optical Circuit Switch
  • Optical packet switching
  • Optical switches
  • Scheduling
  • Scheduling algorithms

Fingerprint

Dive into the research topics of 'Regularization-Based Coflow Scheduling in Optical Circuit Switches'. Together they form a unique fingerprint.

Cite this