Coded caching : convex optimization and graph theoretical perspectives

Data communications is an essential building block of everyday life. A fundamental challenge in communications networks has always been the limited capacity of the links that transfer data from sources to destinations. A core technique to alleviate the load on the network links is to cache popular content in intermediate nodes between the sources and destinations to avoid redundant transmission of the same data. Although the concept of caching has been well studied in the context of computer networks, new settings are emerging in communication networks for which the conventional caching techniques are significantly inefficient and deliver far less than the full benefits that caching can provide. One such setting is that of networks in which caches are connected to the backbone communications system through broadcast links. In the recent years, substantial amount of work has been devoted to characterizing the fundamental limits of the gain of caching in such networks, and coming up with techniques to achieve those limits. At the center of these attempts has been the introduction of coded caching, a technique rooted in information theory that takes advantage of network coding to minimize the amount of information that needs to be communicated in the network. This thesis is devoted to the development of coded caching techniques for three specific settings that are of significant practical interest. In particular, it adapts a convex optimization perspective to address the problem of caching in the presence of duplicate demands, and the problem of designing the optimal way to place the content in caches when different files are non-uniformly popular. The latter is a core problem in the caching literature, for which we derive the optimal placement scheme for certain settings of the problem. We further look into the problem of placement of files in caches without splitting them into sub-packets. We establish a graph theoretical model to study this problem and explore the efficiency of coded caching under this constraint. We believe that this thesis provides fundamental insights into these problems and solutions for them.Applied Science, Faculty ofElectrical and Computer Engineering, Department ofGraduat