Efficient redundancy techniques to reduce delay in Cloud systems

Cloud services are changing the world by providing millions of people low-cost access to the computing power of data centers. Storing and processing data on shared servers in the cloud provides scalability and flexibility to these services. However the large-scale sharing of resources also causes unpredictable fluctuations in the response time of individual servers. In this thesis we use redundancy as a tool to combat this variability. We study three areas of cloud infrastructure: cloud computing, distributed storage, and streaming communication. In cloud computing, replicating a task on multiple machines and waiting for the earliest copy to finish can reduce service delay. But intuitively, it costs additional computing resources, and increases queueing load on the servers. In the first part of this thesis we analyze the eect of redundancy on queues. Surprisingly, there are regimes where replication not only reduces service delay but also reduces queueing load, thus making the system more ecient. Similarly, we can speed-up content download from cloud storage systems by requesting multiple replicas of a le and waiting for any one. In the second part of the thesis we generalize from replication to coding, and propose the (n, k) fork-join model to analyze the delay in accessing an (n, k) erasure-coded storage system. This analysis provides practical insights into how many users can access a piece of content simultaneously, and how fast they can be served. Achieving low latency is even more challenging in streaming communication because the packets need to be delivered fast and in-order. The third part of this thesis develops erasure codes to transmit redundant combinations of packets and ensure smooth playback. This thesis blends a diverse set of mathematical tools from queueing, coding theory, and renewal processes. Although we focus on cloud infrastructure, the techniques and insights are applicable to other systems with stochastically varying components.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2016

Author dc:creator

• Joshi, Gauri

Advisor dc:contributor.advisor

• Gregory W. Wornell.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/105944

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/105944