Codes Can Reduce Queueing Delay in Data Centers

Abstract

In this paper, we quantify how much codes can reduce the data retrieval latency in storage systems. By combining a simple linear code with a novel request scheduling algorithm, which we call Blocking-one Scheduling (BoS), we show analytically that it is possible to reduce data retrieval delay by up to 17% over currently popular replication-based strategies. Although in this work we focus on a simplified setting where the storage system stores a single content, the methodology developed can be applied to more general settings with multiple contents. The results also offer insightful guidance to the design of storage systems in data centers and content distribution networks.

References in corpus (1)

• On the Delay of Network Coding over Line Networks

Cited by in corpus (9)

• Speeding Up Distributed Machine Learning Using Codes
• On Delay-Optimal Scheduling in Queueing Systems with Replications
• Taming Tail Latency for Erasure-coded, Distributed Storage Systems
• FAST CLOUD: Pushing the Envelope on Delay Performance of Cloud Storage with Coding
• Coded FFT and Its Communication Overhead
• Tail Index for a Distributed Storage System with Pareto File Size Distribution
• Optimized Video Streaming over Cloud: A Stall-Quality Trade-off
• TOFEC: Achieving Optimal Throughput-Delay Trade-off of Cloud Storage Using Erasure Codes
• Sprout: A functional caching approach to minimize service latency in erasure-coded storage