Fundamental Limits of Caching

Fundamental Limits of Caching

July 2013 | Mohammad Ali Maddah-Ali and Urs Niesen
This paper introduces a novel coded caching scheme that achieves both local and global caching gains, leading to a multiplicative improvement in peak rate compared to conventional caching schemes. The local caching gain is derived from storing popular content locally at users, while the global caching gain arises from jointly optimizing the placement and delivery phases to enable efficient multicast transmissions. The proposed scheme achieves a rate of $ K \cdot (1 - M/N) \cdot \frac{1}{1 + KM/N} $, which is within a constant factor of the information-theoretic optimum for all values of the problem parameters. The scheme is shown to be effective in both scenarios where the local cache size is large enough to store a significant fraction of the total content and where the aggregate global cache size is sufficiently large. The paper also provides a detailed analysis of the performance of the scheme, including lower bounds on the rate required in the delivery phase and a comparison with conventional uncoded caching schemes. The results demonstrate that the proposed scheme significantly reduces the peak rate of the shared link, achieving a reduction by a factor of up to 12 in some cases. The paper concludes with a discussion of the connection between the caching problem and index and network coding problems, as well as directions for future research, including decentralized and online caching schemes.This paper introduces a novel coded caching scheme that achieves both local and global caching gains, leading to a multiplicative improvement in peak rate compared to conventional caching schemes. The local caching gain is derived from storing popular content locally at users, while the global caching gain arises from jointly optimizing the placement and delivery phases to enable efficient multicast transmissions. The proposed scheme achieves a rate of $ K \cdot (1 - M/N) \cdot \frac{1}{1 + KM/N} $, which is within a constant factor of the information-theoretic optimum for all values of the problem parameters. The scheme is shown to be effective in both scenarios where the local cache size is large enough to store a significant fraction of the total content and where the aggregate global cache size is sufficiently large. The paper also provides a detailed analysis of the performance of the scheme, including lower bounds on the rate required in the delivery phase and a comparison with conventional uncoded caching schemes. The results demonstrate that the proposed scheme significantly reduces the peak rate of the shared link, achieving a reduction by a factor of up to 12 in some cases. The paper concludes with a discussion of the connection between the caching problem and index and network coding problems, as well as directions for future research, including decentralized and online caching schemes.
Reach us at info@study.space