Characterizing the Rate-Memory Tradeoff in Cache Networks Within a Factor of 2
| Autor: | Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Cache coloring Computer science CPU cache Computer Science - Information Theory Parallel computing 02 engineering and technology Cache pollution Cache-oblivious algorithm Library and Information Sciences Bottleneck Set (abstract data type) Non-uniform memory access Write-once Cache invalidation Server Factor (programming language) 0202 electrical engineering electronic engineering information engineering 0601 history and archaeology Cache algorithms computer.programming_language Snoopy cache 060102 archaeology business.industry Information Theory (cs.IT) MESI protocol Cache-only memory architecture 020206 networking & telecommunications 06 humanities and the arts MESIF protocol Computer Science Applications Smart Cache Bus sniffing Page cache State (computer science) Cache business Least frequently used computer Information Systems Computer network |
| Zdroj: | ISIT |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2018.2870566 |
| Popis: | We consider a basic caching system, where a single server with a database of N files (e.g. movies) is connected to a set of K users through a shared bottleneck link. Each user has a local cache memory with a size of M 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 2.00884 for both the peak rate and the average rate (under uniform file popularity), where the best proved characterization in the current literature gives a factor of 4 and 4.7 respectively. Moreover, in the practically important case where the number of files (N) is large, we exactly characterize the tradeoff for systems with no more than 5 users, and characterize the tradeoff within a factor of 2 otherwise. We establish these results by developing novel information theoretic outer-bounds for the caching problem, which improves the state of the art and gives tight characterization in various cases. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|