Energy-efficient flow scheduling and routing with hard deadlines in data center networks

Lin Wang*, Fa Zhang, Kai Zheng, Athanasios V. Vasilakos, Shaolei Ren, Zhiyong Liu

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

The power consumption of enormous network devices in data centers has emerged as a big concern to data center operators. Despite many traffic-engineering-based solutions, very little attention has been paid on performance-guaranteed energy saving schemes. In this paper, we propose a novel energy-saving model for data center networks by scheduling and routing 'deadline-constrained flows' where the transmission of every flow has to be accomplished before a rigorous deadline, being the most critical requirement in production data center networks. Based on speed scaling and power-down energy saving strategies for network devices, we aim to explore the most energy efficient way of scheduling and routing flows on the network, as well as determining the transmission speed for every flow. We consider two general versions of the problem. For the version of only flow scheduling where routes of flows are pre-given, we show that it can be solved polynomially and we develop an optimal combinatorial algorithm for it. For the version of joint flow scheduling and routing, we prove that it is strongly NP-hard and cannot have a Fully Polynomial-Time Approximation Scheme (FPTAS) unless P=NP. Based on a relaxation and randomized rounding technique, we provide an efficient approximation algorithm which can guarantee a provable performance ratio with respect to a polynomial of the total number of flows.

Original languageEnglish
Title of host publicationProceedings - International Conference on Distributed Computing Systems
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages248-257
Number of pages10
ISBN (Electronic)9781479951680
DOIs
Publication statusPublished - 29 Aug 2014
Externally publishedYes
Event2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014 - Madrid, Spain
Duration: 30 Jun 20143 Jul 2014

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Conference

Conference2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014
CountrySpain
CityMadrid
Period30/06/143/07/14

Keywords

  • cloud computing
  • data center networks
  • energy efficiency

Fingerprint

Dive into the research topics of 'Energy-efficient flow scheduling and routing with hard deadlines in data center networks'. Together they form a unique fingerprint.

Cite this