Fundamental limits of stochastic shared-cache networks

Malik, Adeel; Serbetci, Berksan; Parrinello, Emanuele; Elia, Petros
IEEE Transactions on Communications, 22 March 2021

The work establishes the exact performance limits of stochastic coded caching when users share a bounded number of cache states, and when the association between users and caches, is random. Under the premise that more balanced user-to-cache associations perform better than unbalanced ones, our work provides a statistical analysis of the average performance of such networks, identifying in closed form, the exact optimal average delivery time. To insightfully capture this delay, we derive easy-to-compute closed-form analytical bounds that prove tight in the limit of a large number Λ of cache states. In the scenario where delivery involves K users, we conclude that the multiplicative performance deterioration due to randomness — as compared to the well-known deterministic uniform case — can be unbounded and can scale as Θ(log Λ/log log Λ) at K = Θ(Λ), and that this scaling vanishes when K = Ω(Λ log Λ). To alleviate this adverse effect of cache-load imbalance, we consider various load-balancing methods, and show that employing proximity-bounded load balancing with an ability to choose from h neighboring caches, the aforementioned scaling reduces to Θ(log(Λ/h)/log log(Λ/h)), while when the proximity constraint is removed, the scaling is of a much slower order Θ(log log Λ). The above analysis is extensively validated numerically.

Systèmes de Communication
Eurecom Ref:
© 2021 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.