We study the problem of minimizing routing costs by jointly optimizing caching and routing decisions over an arbitrary network topology. We consider both
source routing and hop-by-hop routing settings. The respective offline problems are NP-hard. Nevertheless, we show that there exist polynomial time approximation algorithms producing solutions within a constant approximation from the optimal. We also
produce distributed, adaptive algorithms with the same approximation
guarantees. We simulate our adaptive algorithms over a broad
array of different topologies. Our algorithms reduce routing costs
by several orders of magnitude compared to prior art, including
algorithms optimizing caching under fixed routing.