Entropy, Vol. 21, Pages 324: Efficient Algorithms for Coded Multicasting in Heterogeneous Caching Networks (Entropy)

Coded multicasting has been shown to be a promising approach to significantly improve theperformance of content delivery networks with multiple caches downstream of a common multicastlink. However, the schemes that have been shown to achieve order-optimal performance require contentitems to be partitioned into several packets that grows exponentially with the number of caches, leadingto codes of exponential complexity that jeopardize their promising performance benefits. In this paper,we address this crucial performance-complexity tradeoff in a heterogeneous caching network setting,where edge caches with possibly different storage capacity collect multiple content requests that mayfollow distinct demand distributions. We extend the asymptotic (in the number of packets per file)analysis of shared link caching networks to heterogeneous network settings, and present novel codedmulticast schemes, based on local graph coloring, that exhibit polynomial-time complexity in all the systemparameters, while preserving the asymptotically proven multiplicative caching gain even for finite filepacketization. We further demonstrate that the packetization order (the number of packets each file issplit into) can be traded-off with the number of requests collected by each cache, while preserving thesame multiplicative caching gain. Simulation results confirm the superiority of the proposed schemesand illustrate the interesting request aggregation vs. packetization order tradeoff within several practicalsettings. Our results provide a compelling step towards the practical achievability of the promisingmultiplicative caching gain in next generation access networks.