We study a problem of fundamental importance to ICNs, namely, minimizingrouting costs by jointly optimizing caching and routing decisions over anarbitrary network topology. We consider both source routing and hop-by-hoprouting settings. The respective offline problems are NP-hard. Nevertheless, weshow that there exist polynomial time approximation algorithms producingsolutions within a constant approximation from the optimal. We also producedistributed, adaptive algorithms with the same approximation guarantees. Wesimulate our adaptive algorithms over a broad array of different topologies.Our algorithms reduce routing costs by several orders of magnitude compared toprior art, including algorithms optimizing caching under fixed routing.
展开▼
