Joint Caching and Routing in Congestible Networks of Arbitrary Topology
- 16 August 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Internet of Things Journal
- Vol. 6 (6) , 10105-10118
Abstract
In-network caching constitutes a promising approach to reduce traffic loads and alleviate congestion in both wired and wireless networks. In this paper, 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.Keywords
Funding Information
- National Natural Science Foundation of China (61729101)
- Natural Science Foundation of Hubei Province (2016CFA009)
- Fundamental Research Funds for the Central Universities (2015ZDTD012)
- National Science Foundation (CNS 1815676)
- Bodossaki Foundation
This publication has 39 references indexed in Scilit:
- Approximation Algorithms for Mobile Data Caching in Small Cell NetworksIEEE Transactions on Communications, 2014
- On computing the distribution function for the Poisson binomial distributionComputational Statistics & Data Analysis, 2013
- Submodular Maximization over Multiple Matroids via Generalized Exchange PropertiesMathematics of Operations Research, 2010
- Approximation Algorithms for Data Placement ProblemsSIAM Journal on Computing, 2008
- Tight approximation algorithms for maximum general assignment problems2006
- Combinatorial Algorithms for the Unsplittable Flow ProblemAlgorithmica, 2005
- On the optimization of storage capacity allocation for content distributionComputer Networks, 2005
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability ProblemSIAM Journal on Discrete Mathematics, 1994
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963