Amazing technological breakthrough possible @S-Logix

Office Address

  • #5, First Floor, 4th Street Dr. Subbarayan Nagar Kodambakkam, Chennai-600 024 Landmark : Samiyar Madam
  • +91- 81240 01111

Social List

Deadline Flow Scheduling in Datacenters with Time-Varying Bandwidth Allocations - 2017

Deadline Flow Scheduling in Datacenters with Time-Varying Bandwidth Allocations

Research Area:  Cloud Computing


Many production datacenters nowadays service multiple applications with dynamically allocated network bandwidth, and some applications are time-critical so their data transfers or flows are constrained by deadlines. To meet deadlines, several flow scheduling schemes for datacenter networks are proposed, but most of them are unaware of bandwidth variations, leading to suboptimal throughputs. In this paper, we present a flow scheduling scheme, called UBAS, to improve deadline-meeting throughputs for time-critical applications with uncertain time-varying bandwidth allocations. First, we model an optimization problem of scheduling deadline-constrained flows under uncertain time-varying bandwidth allocations to maximize the expected deadline-meeting throughput. The problem is NP-hard. Then, we propose an approximation algorithm under a mild condition for the problem in a special case, where bandwidth allocations are certain, as well as a conditional approximation algorithm for the problem in general. To adapt to practice, scalable and online variants of the algorithm are also presented. In evaluation, we conduct simulations based on a real traffic trace in a production datacenter. The results demonstrate that, with severe practical settings, UBAS still achieves nearly optimal deadline-meeting throughputs. Moreover, the throughput improvements of UBAS against existing bandwidth-agnostic schemes are more substantial when the variance of bandwidth allocations over time increases.


Author(s) Name:  Jiann-Min Ho,Pi-Cheng Hsiu and Ming-Syan Chen

Journal name:  IEEE Transactions on Services Computing

Conferrence name:  

Publisher name:  IEEE

DOI:  10.1109/TSC.2017.2701363

Volume Information:  May-June 2020, pp. 437-450, vol. 13