Hold’em Caching: Proactive Retention-Aware Caching with Multi-path Routing for Wireless Edge Networks

Abstract We consider the problem of proactive retention aware caching in a heterogeneous wireless edge network consisting of mobile users connected to a server and associated to one or more edge caches. Our goal is to design a caching policy that minimizes the sum of content storage costs and server access transmissions costs over two design variables: the retention time of each cached content and the probability that a user routes content requests to its associated caches. We develop a model captures multiple aspects such as cache storage costs and several capabilities of modern wireless technologies, such as server multicast/unicast transmissions, device multipath routing, and cache access constraints. We formulate the problem of Proactive Retention Routing Optimization (PRRO) as a non-convex, non-linear mixed-integer program. We prove that it is NP-Hard under both multicast/unicast modes, even when the caches have a large capacity, and develop a greedy algorithm that has provable performance bounds. Finally, we propose a heuristic for the capacitated cache case that has low computational complexity. Systematic evaluations including real data sets demonstrate the effectiveness of our approach, compared to the existing caching schemes.
  • Samta Shukla
  • Onkar Bhardwaj (IBM US)
  • Alhussein Abouzeid
  • Theodoros Salonidis (IBM US)
  • Ting He (PSU)
Date Jul-2017
Venue 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2017