Fair Caching Networks

Abstract We consider caching networks in which the routing cost for serving a content request can be reduced by caching the requested content item in cache nodes closer to the users. We refer to the cost reduction enabled by caching as the caching gain, and the product of the caching gain of a content request and its request rate as caching gain rate. We aim to study fair content allocation strategies through a utility-driven framework, where each request achieves a utility of its caching gain rate, and consider a family of α -fair utility functions to capture different degrees of fairness. The resulting problem is an NP-hard problem with a non-decreasing submodular objective function. Submodularity allows us to devise a deterministic allocation strategy with an optimality guarantee factor arbitrarily close to 1 − 1 ∕ e . When 0 α ≤ 1 , we further propose a randomized strategy that attains an improved optimality guarantee, ( 1 − 1 ∕ e ) 1 − α , in expectation. Through extensive simulations over synthetic and real-world network topologies, we evaluate the performance of our proposed strategies and discuss the effect of fairness.