Efficient Approximation Algorithms for Scheduling Coflows With Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion Time

Research output: Contribution to journalArticlepeer-review

Abstract

This paper focuses on the problem of coflow scheduling with precedence constraints in identical parallel networks, a well-known <inline-formula><tex-math notation="LaTeX">$\mathcal {NP}$</tex-math></inline-formula>-hard problem. Coflow is a relatively new network abstraction that characterizes communication patterns in data centers. When considering workload sizes and weights that are dependent on the network topology in the input instances, the proposed algorithm for the flow-level scheduling problem achieves an approximation ratio of <inline-formula><tex-math notation="LaTeX">$O(\chi )$</tex-math></inline-formula> where <inline-formula><tex-math notation="LaTeX">$\chi$</tex-math></inline-formula> is the coflow number of the longest path in the directed acyclic graph (DAG). Additionally, when taking into account topology-dependent workload sizes, the algorithm achieves an approximation ratio of <inline-formula><tex-math notation="LaTeX">$O(R\chi )$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$R$</tex-math></inline-formula> represents the ratio of maximum weight to minimum weight. For the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of <inline-formula><tex-math notation="LaTeX">$O(m\chi )$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula> is the number of network cores when considering workload sizes and weights that are topology-dependent. Moreover, when considering topology-dependent workload sizes, the algorithm achieves an approximation ratio of <inline-formula><tex-math notation="LaTeX">$O(Rm\chi )$</tex-math></inline-formula>. In the coflows of multi-stage job scheduling problem, the proposed algorithm achieves an approximation ratio of <inline-formula><tex-math notation="LaTeX">$O(\chi )$</tex-math></inline-formula>. Although our theoretical results are based on a limited set of input instances, experimental findings show that the results for general input instances outperform the theoretical results.

Original languageEnglish
Pages (from-to)1-16
Number of pages16
JournalIEEE Transactions on Services Computing
DOIs
Publication statusAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Efficient Approximation Algorithms for Scheduling Coflows With Precedence Constraints in Identical Parallel Networks to Minimize Weighted Completion Time'. Together they form a unique fingerprint.

Cite this