Spatial multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps

Anastasios Giovanidis, Apostolos AvranasarXiv 2016 · DOI · arXiv

TL;DR

This paper introduces "spatial multi-LRU," a new family of decentralized caching policies for wireless networks that leverages overlapping coverage areas to improve content delivery. By intelligently managing cache updates across multiple nearby base stations, these policies significantly boost hit rates compared to traditional single-cache LRU, even approaching the performance of more complex centralized systems.

What Problem Does This Paper Address?

Modern networks are shifting towards Information-Centric Networking (ICN), where data is cached closer to users at edge nodes (like base stations). In wireless networks, these edge nodes often have overlapping coverage areas, meaning a user can be served by multiple stations. The challenge is to design efficient, decentralized caching policies that exploit this multi-coverage to maximize the probability of a user finding their requested content already cached (the "hit probability"). Existing single-cache LRU policies don't take advantage of multi-coverage, and centralized approaches can be too complex and resource-intensive for large-scale wireless deployments. This paper aims to bridge this gap by proposing and analyzing new distributed policies that leverage multi-coverage.

Methods

The core contribution is the "spatial multi-LRU" family of policies, an extension of the classic Least-Recently-Used (LRU) algorithm to scenarios with multiple overlapping caches. Two main variations are proposed:

  • multi-LRU-One: When a content request misses in all nearby caches, only one of the covering stations inserts the content. This promotes content diversity across neighboring caches.
  • multi-LRU-All: When a content request misses, all covering stations insert the content. This helps spread popular content rapidly across a wider geographic area.

The authors analyze these policies using two traffic models: the standard Independent Reference Model (IRM) and a more realistic model exhibiting temporal locality (where recent requests influence future ones). For the IRM model, they adapt a known approximation (Che's approximation) to derive new analytical formulas for hit probability, introducing "Cache Independence Approximation" (CIA) for multi-LRU-One and "Cache Similarity Approximation" (CSA) for multi-LRU-All. These approximations allow for simpler calculations of performance. The paper then uses numerical simulations to evaluate these policies and compare them against existing methods.

Datasets

Not discussed in the paper. The paper uses simulated traffic models (IRM and a temporal locality model) and network configurations rather than real-world datasets.

Key Insights and Ideas

  • Multi-coverage is a powerful asset: Even with modest overlap (low expected coverage number), the spatial multi-LRU policies show significant gains over single-LRU.
  • Diversity vs. Spread: multi-LRU-One favors content diversity, which is beneficial for stationary traffic (like IRM), while multi-LRU-All prioritizes rapid content spread, proving more effective for dynamic traffic with temporal locality.
  • Decentralization can rival centralization: The proposed policies perform close to centralized solutions, especially when multi-coverage is sufficient, offering a practical advantage.
  • Approximations are key: The Che-like approximations (CIA and CSA) provide accurate analytical tools for predicting performance, making the analysis tractable.
  • Popularity knowledge isn't always necessary: The spatial multi-LRU policies can outperform centralized methods that rely on accurate, up-to-date popularity information, especially when that information is unreliable or hard to obtain.

Key Results

  • Significant Hit Rate Improvement: For IRM traffic, multi-LRU-One showed relative gains of 35-42% over single-LRU with just two overlapping coverage areas, increasing to 60-70% with three.
  • Policy Preference: For IRM traffic, multi-LRU-One generally outperforms multi-LRU-All. For traffic with temporal locality, multi-LRU-All can be better, especially with sufficient cache memory.
  • Approximation Accuracy: The paper demonstrates that the CIA and CSA approximations provide a very good match to simulation results for the multi-LRU policies.
  • Performance vs. Coverage: Hit probability consistently increases with the expected number of covering stations (NBS).
  • Comparison to Benchmarks: The proposed policies generally outperform single-LRU and LFU, and approach the performance of more complex policies like PBP and GFI, often with less reliance on explicit popularity information.

Limitations and Future Work

  • Approximation Limitations: While generally accurate, the approximations for approximating the total area of coverage in multi-LRU-All can lead to divergences from simulations for very large coverage radii.
  • Traffic Model Simplifications: The paper uses simplified traffic models (IRM and a specific temporal locality model). More complex and realistic traffic patterns, including spatial locality, could be explored.
  • Cache Update Timing: The paper assumes a fixed characteristic time for cache updates. Investigating adaptive or more dynamic update strategies could be beneficial.
  • Future Work: The authors suggest exploring how performance is affected by spatial and temporal locality characteristics in more detail. They also mention that the analysis could be extended to unequal cache sizes and file sizes.

Summary updated

Abstract

This article introduces a novel family of decentralised caching policies, applicable to wireless networks with finite storage at the edge-nodes (stations). These policies, that are based on the Least-Recently-Used replacement principle, are here referred to as spatial multi-LRU. They update cache inventories in a way that provides content diversity to users who are covered by, and thus have access to, more than one station. Two variations are proposed, the multi-LRU-One and -All, which differ in the number of replicas inserted in the involved caches. We analyse their performance under two types of traffic demand, the Independent Reference Model (IRM) and a model that exhibits temporal locality. For IRM, we propose a Che-like approximation to predict the hit probability, which gives very accurate results. Numerical evaluations show that the performance of multi-LRU increases the more the multi-coverage areas increase, and it is close to the performance of centralised policies, when multi-coverage is sufficient. For IRM traffic, multi-LRU-One is preferable to multi-LRU-All, whereas when the traffic exhibits temporal locality the -All variation can perform better. Both variations outperform the simple LRU. When popularity knowledge is not accurate, the new policies can perform better than centralised ones.
BibTeX
@misc{giovanidis2016spatial,
  author = {Anastasios Giovanidis and Apostolos Avranas},
  title = {{Spatial multi-LRU: Distributed Caching for Wireless Networks with Coverage Overlaps}},
  year = {2016},
  eprint = {1612.04363},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.04363},
}

Loading related content...

Figure