Graduate School and Research Center in Digital Sciences

Fundamental limits of stochastic caching networks

Malik, Adeel; Serbetci, Berksan; Parrinello, Emanuele; Elia, Petros

Submitted on ArXiV, 28 May 2020

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 $Lambda$ 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 $Thetaleft( frac{log Lambda}{log log Lambda} right)$ at $K=Thetaleft(Lambdaright)$, and that this scaling vanishes when $K=Omegaleft(Lambdalog Lambdaright)$. 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 $Theta left(frac{log(Lambda / h)}{ log log(Lambda / h)} right)$, while when the proximity constraint is removed, the scaling is of a much slower order $Theta left( log log Lambda right)$. The above analysis is extensively validated numerically.  

Arxiv Bibtex

Title:Fundamental limits of stochastic caching networks
Keywords:Coded caching, shared caches, load balancing, heterogeneous networks, femtocaching
Department:Communication systems
Eurecom ref:6275
Copyright: © EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Submitted on ArXiV, 28 May 2020 and is available at :
Bibtex: @inproceedings{EURECOM+6275, year = {2020}, title = {{F}undamental limits of stochastic caching networks}, author = {{M}alik, {A}deel and {S}erbetci, {B}erksan and {P}arrinello, {E}manuele and {E}lia, {P}etros}, booktitle = {{S}ubmitted on {A}r{X}i{V}, 28 {M}ay 2020}, address = {}, month = {05}, url = {} }
See also: