Treffer: Cache Networks of Counting Queues.

We consider a cache network in which intermediate nodes equipped with caches can serve content requests. We model this network as a universally stable queuing system, in which packets carrying identical responses are consolidated before being forwarded downstream. We refer to resulting queues as $\mathtt {M/M/1c}$ or counting queues, as consolidated packets carry a counter indicating the packet’s multiplicity. Cache networks comprising such queues are hard to analyze; we propose two approximations: one via $\mathtt {M/M/\infty }$ queues, and one based on $\mathtt {M/M/1c}$ queues under the assumption of Poisson arrivals. We show that, in both cases, the problem of jointly determining (a) content placements and (b) service rates admits a poly-time, $1-1/e$ approximation algorithm. We also show that our analysis, with respect to both algorithms and associated guarantees, extends to (a) counting queues over items, rather than responses, as well as to (b) queuing at nodes and edges, as opposed to just edges. Numerical evaluations indicate that our proposed approximation algorithms yield good solutions in practice, significantly outperforming competitors. [ABSTRACT FROM AUTHOR]

Copyright of IEEE/ACM Transactions on Networking is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)