Joint Data Compression and Caching: Approaching Optimality with Guarantees

Abstract We consider the problem of optimally compressing and caching data across a communication network. Given the data generated at edge nodes and a routing path, our goal is to determine the optimal data compression ratios and caching decisions across the network in order to minimize average latency, which can be shown to be equivalent to maximizing the compression and caching gain under an energy consumption constraint. We show that this problem is NP-hard in general and the hardness is caused by the caching decision subproblem, while the compression sub-problem is polynomial-time solvable. We then propose an approximation algorithm that achieves a (1 − 1/e)-approximation solution to the optimum in strongly polynomial time. We show that our proposed algorithm achieve the near-optimal performance in synthetic-based evaluations. In this paper, we consider a tree-structured network as an illustrative example, but our results easily extend to general network topology at the expense of more complicated notations.
  • Jian Li (UMass)
  • Faheem Zafari (Imperial)
  • Don Towsley (UMass)
  • Kin Leung (Imperial)
  • Ananthram Swami (ARL)
Date Apr-2018
Venue Proceedings of the 2018 ACM/SPEC International Conference on Performance Engineering Pages 229-240 [link]