Joint Scheduling and Source Selection for Background Traffic in Erasure-Coded Storage
- 11 June 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 29 (12) , 2826-2837
Abstract
Erasure-coded storage systems have gained considerable adoption recently since they can provide the same level of reliability with significantly lower storage overhead compared to replicated systems. However, background traffic of such systems — e.g. repair, rebalance, backup and recovery traffic — often has large volume and consumes significant network resources. Independently scheduling such tasks and selecting their sources can easily create interference among data flows, causing severe deadline violation. We show that the well-known heuristic scheduling algorithms fail to consider important constraints, thus resulting in unsatisfactory performance. In this paper, we claim that an optimal scheduling algorithm, which aims to maximize the number of background tasks completed before deadlines, must simultaneously consider task deadline, network topology, chunk placement, and time-varying resource availability. We first show that the corresponding optimization problem is NP-hard. Then we propose a novel algorithm, called Linear Programming for Selected Tasks (LPST) to maximize the number of successful tasks and improve overall utilization of the datacenter network. It jointly schedules tasks and selects their sources based on a notion of Remaining Time Flexibility, which measures the slackness of the starting time of a task. We evaluated the efficacy of our algorithm using extensive simulations and validate the results with experiments in a real cloud environment. Our results show that, under certain scenarios, LPST can perform $7\times\;\sim\;10\times$ better than the heuristics which blindly treat the infrastructure as a collection of homogeneous resources, and $21.7\%\sim65.9\%$ better than the algorithms that only take the network topology into account.
Keywords
This publication has 25 references indexed in Scilit:
- A Nearly Linear-Time PTAS for Explicit Fractional Packing and Covering Linear ProgramsAlgorithmica, 2013
- BCubeACM SIGCOMM Computer Communication Review, 2009
- FIFO-Based Multicast Scheduling Algorithm for Virtual Output Queued Packet SwitchesIEEE Transactions on Computers, 2005
- Erasure Coding Vs. Replication: A Quantitative Comparison2002
- Duality and linear programs for stability and performance analysis of queuing networks and scheduling policiesIEEE Transactions on Automatic Control, 1996
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent SetOperations Research, 1994
- A new algorithm for scheduling periodic, real-time tasksAlgorithmica, 1989
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- Finding a Maximum Independent SetSIAM Journal on Computing, 1977