M.Sc Thesis

M.Sc StudentFarbman Barak
SubjectCoded Caching for Content Distribution Networks
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROF. Yuval Cassuto
Full Thesis textFull thesis text - English Version


The massive growth in high-capacity streams (mostly video) over the internet warranted the establishment of content distribution networks (CDNs), which bring the content closer to the consumer and hence reduce delays and congestion in the network.  In this thesis we address the setup of multiple Internet service providers (ISPs) sharing a federated cache. When multiple ISPs with different demands share a cache, storage cost can be reduced when the cache is coded, that is, storing objects that are linear combinations of multiple content objects.

In this thesis we address the problem of optimizing the coded cache to fulfill all demands from all ISPs, where in this optimization we consider simultaneously the cache's three main operational costs: storage, communication, and computation (to encode and decode objects). Low coding-computation cost is central to our investigations, aiming to reduce the implementation costs sufficiently to become a practical alternative to uncoded caches. In particular, the thesis is strongly focused on coded caching with only simple bit-wise XOR operations, whereas the majority of related work allows high-order finite-field arithmetic for the coding operations.

In the first part of the thesis we address the static setup, where all ISP demands are submitted to the cache and then the storage cost is minimized given the demands. When the number of ISPs is less or equal to 4, we give an efficient algorithm that for any demand matrix achieves optimal storage with only bit-wise XOR operations and with guaranteed low computation costs. For larger numbers of ISPs we present randomized algorithms that achieve optimal storage when the demand vectors come from a probability distribution; the expected running time of the algorithms grow with the number of ISPs.

In the second part of the thesis we move to the dynamic setup, where ISP demands are changing constantly, and demand updates are submitted on-line. The core of our results in the dynamic setup is a coding scheme based on degree-2 XOR operations, which has the desired property that only the ISP changing its demand needs to be involved in the cache update. For this scheme we give an algorithm that jointly minimizes the storage cost and the communication cost needed for the updates. We also derive a probabilistic analysis of the storage-cost evolution in the dynamic setup.