Joint Caching and Routing in Congestible Networks of Arbitrary Topology

Abstract

In-network caching constitutes a promising approach to reduce traffic loads and alleviate congestion in both wired and wireless networks. In this article, we study the joint caching and routing problem in congestible networks of arbitrary topology (JoCRAT) as a generalization of previous efforts in this particular field. We show that JoCRAT extends many previous problems in the caching literature that are intractable even with specific topologies and/or assumed unlimited bandwidth of communications. To handle this significant but challenging problem, we develop a novel approximation algorithm with guaranteed performance bound based on a randomized rounding technique. Evaluation results demonstrate that our proposed algorithm achieves near-optimal performance over a broad array of synthetic and real networks, while significantly outperforming the state-of-the-art methods.