Joint Caching and Routing in Cache Networks With Arbitrary Topology

Tian Xie, Sanchal Thakkar, Ting He, Patrick McDaniel, Quinn Burke

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In-network caching and flexible routing are two of the most celebrated advantages of next generation network infrastructures. Yet few solutions are available for jointly optimizing caching and routing that provide performance guarantees for networks with arbitrary topology. We take a holistic approach towards this fundamental problem by analyzing its complexity in all the cases and developing polynomial-time algorithms with approximation guarantees in important special cases. We also reveal the fundamental challenge in achieving guaranteed approximation in the general case and propose an alternating optimization algorithm with good empirical performance and fast convergence. Our algorithms have demonstrated superior performance in both routing cost and congestion compared to the state-of-the-art solutions in evaluations based on real topology and request traces.

Original languageEnglish (US)
Pages (from-to)2237-2250
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number8
StatePublished - Aug 1 2023

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this