Universally Stable Cache Networks

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 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 M/M/∞ queues, and one based on 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. Numerical evaluations indicate that both approximations yield good solutions in practice, significantly outperforming competitors.

Index Terms-DR-submodularity, cache networks, Jackson networks

• We introduce networks of M/M/1c queues, aiming to capture network behavior with greater realism. In contrast to M/M/1 queues, resulting networks are not Kelly networks, and intermediate queue arrivals are not Poisson.

• We show that M/M/∞ queues approximate M/M/1c queues; we show this both experimentally and analytically, through a mutual stochastic dominance (c.f. Thm. 1). Most importantly, both queues lead to networks that are universally stable.

• Motivated by the above observations, we study two cache network design problems, each serving as an approximation of a cache network with counting queues. Both problems optimize content placement and service assignment decisions jointly. In the first problem, MINCOST M/M/∞ , we approximate counting queues with M/M/∞ queues; in the second problem, MINCOST M/M/1c , we use M/M/1c steady-state distributions, assuming however Poisson arrivals in intermediate queues.

• We show that both problems are NP-hard (c.f. Thm. 2), and construct a 1 -1/e poly-time approximation algorithm for the joint optimization of item placements and service assignments (c.f. Thm. 4).

• Finally, we conduct extensive experiments over multiple topologies: our joint item placements and service rate