2018/04/02 by Seyed Ali Saberali, Saberali, Seyed Ali, Lutz Lampe +3
Computer Science · #Caching and Content Delivery #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1804.00807
openalex publication_date 2018/04/02 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We investigate the problem of coded caching for nonuniform demands when the\nstructured clique cover algorithm proposed by Maddah-Ali and Niesen for\ndecentralized caching is used for delivery. We apply this algorithm to all user\ndemands regardless of their request probabilities. This allows for coding among\nthe files that have different request probabilities but makes the allocation of\nmemory to different files challenging during the content placement phase. As\nour main contribution, we analytically characterize the optimal placement\nstrategy that minimizes the expected delivery rate under a storage capacity\nconstraint. It is shown that the optimal placement follows either a two or a\nthree group strategy, where a set of less popular files are not cached at all\nand the files within each of the other sets are allocated identical amounts of\nstorage as if they had the same request probabilities. We show that for a\nfinite set of storage capacities, that we call the base-cases of the problem,\nthe two group strategy is always optimal. For other storage capacities, optimal\nplacement is achieved by memory sharing between certain base-cases and the\nresulting placement either follows a two or a three group strategy depending on\nthe corresponding base-cases used. We derive a polynomial time algorithm that\ndetermines the base-cases of the problem given the number of caches and\npopularity distribution of files. Given the base-cases of the problem, the\noptimal memory allocation parameters for any storage capacity are derived\nanalytically.\n