We consider a basic caching system, where a single server with a database of @math files (e.g. movies) is connected to a set of @math users through a shared bottleneck link. Each user has a local cache memory with a size of @math files. The system operates in two phases: a placement phase, where each cache memory is populated up to its size from the database, and a following delivery phase, where each user requests a file from the database, and the server is responsible for delivering the requested contents. The objective is to design the two phases to minimize the load (peak or average) of the bottleneck link. We characterize the rate-memory tradeoff of the above caching system within a factor of @math for both the peak rate and the average rate (under uniform file popularity), improving state of the arts that are within a factor of @math and @math respectively. Moreover, in a practically important case where the number of files ( @math ) is large, we exactly characterize the tradeoff for systems with no more than @math users, and characterize the tradeoff within a factor of @math otherwise. To establish these results, we develop two new converse bounds that improve over the state of the art.
for @math , where @math is uniformly random in @math , and @math denotes the number of distinct requests in @math . Here the letter e'' in the subscript represents effective'', given that the function @math can also be interpreted as the effective'' number of files for any demand @math . Specifically, for any demand @math , the needed communication rate stated in equation ) is exactly the peak communication rate stated in equation ) for a caching system with @math files. Furthermore, for general (non-integer) @math , @math and @math are defined as the lower convex envelope of their values at @math , respectively. Specifically, for any non-integer @math , we have Rigorously, the fact that equations ) and ) define lower convex envelopes is due to the convexity of @math and @math on @math . This convexity was observed in @cite_4 and can be proved using elementary combinatorics. A short proof of the convexity of @math and @math can be found in Appendix . Given the above upper bounds, we develop improved converse bounds in this paper, which provides better characterizations for both the peak rate and the average rate.
@cite_4
2527594325
We consider a basic cache network, in which a single server is connected to multiple users via a shared bottleneck link. The server has a database of files (content). Each user has an isolated memory that can be used to cache content in a prefetching phase. In a following delivery phase, each user requests a file from the database, and the server needs to deliver users’ demands as efficiently as possible by taking into account their cache contents. We focus on an important and commonly used class of prefetching schemes, where the caches are filled with uncoded data. We provide the exact characterization of the rate-memory tradeoff for this problem, by deriving both the minimum average rate (for a uniform file popularity) and the minimum peak rate required on the bottleneck link for a given cache size available at each user. In particular, we propose a novel caching scheme, which strictly improves the state of the art by exploiting commonality among user demands. We then demonstrate the exact optimality of our proposed scheme through a matching converse, by dividing the set of all demands into types, and showing that the placement phase in the proposed caching scheme is universally optimal for all types. Using these techniques, we also fully characterize the rate-memory tradeoff for a decentralized setting, in which users fill out their cache content without any coordination.