2015/11/23 by Giuseppe Vettigli, Mingyue Ji, Vettigli, Giuseppe +7 · 1 citation
Computer Science · Mathematics · #Caching and Content Delivery #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #Mobile Ad Hoc Networks #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1511.07531
6 pages, 7 figures, Published in Infocom CNTCV 2015
openalex publication_date 2015/11/23 · arxiv created 2015/11/24 · arxiv updated 2015/11/25 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28
Coded multicasting has been shown to be a promis- ing approach to significantly improve the caching performance of content delivery networks with multiple caches downstream of a common multicast link. However, achievable schemes proposed to date have been shown to achieve the proved order-optimal performance only in the asymptotic regime in which the number of packets per requested item goes to infinity. In this paper, we first extend the asymptotic analysis of the achievable scheme in [1], [2] to the case of heterogeneous cache sizes and demand distributions, providing the best known upper bound on the fundamental limiting performance when the number of packets goes to infinity. We then show that the scheme achieving this upper bound quickly loses its multiplicative caching gain for finite content packetization. To overcome this limitation, we design a novel polynomial-time algorithm based on random greedy graph- coloring that, while keeping the same finite content packetization, recovers a significant part of the multiplicative caching gain. Our results show that the order-optimal coded multicasting schemes proposed to date, while useful in quantifying the fundamental limiting performance, must be properly designed for practical regimes of finite packetization.