Cost-Aware Joint Caching and Forwarding in Networks with Heterogeneous Cache Resources

Faruk Volkan Mutlu, Edmund Yeh

TL;DR

This paper tackles the challenge of efficiently using diverse cache technologies (like fast but small DRAM and slower but larger flash storage) in high-throughput networks. They introduce a novel framework that jointly optimizes caching and data forwarding decisions, achieving a better balance between network performance and the cost of using these heterogeneous storage resources.

What Problem Does This Paper Address?

Modern high-throughput networks, especially those handling data-intensive applications, rely heavily on caching to speed up data delivery. Traditionally, DRAM has been the go-to for cache memory due to its high speed. However, DRAM is expensive and has limited capacity, making it a bottleneck for scaling. Fortunately, newer technologies like persistent memory and flash storage offer much larger capacities at lower costs. The problem is that these slower storage tiers have different performance characteristics (like lower read/write speeds) and incur different operational costs (like power consumption and wear-and-tear). Simply using them as a direct replacement or extension of DRAM caches doesn't work well. We need intelligent caching strategies that can leverage the strengths of each tier and minimize the downsides, all while considering the cost implications. This paper aims to bridge this gap by developing a system that can intelligently manage these heterogeneous cache resources.

Methods

The core of the paper's contribution lies in its novel approach to joint caching and forwarding. They build upon the VIP (Virtual Interest Packet) framework, which uses a separate "virtual control plane" to manage network resources.

Here's a breakdown of their methods:

  • Multi-Tiered Cache Model: They model a cache as a collection of storage blocks (tiers) with distinct rate parameters (how fast they can serve data) and utilization costs (admission, eviction, power, etc.).
  • Drift-Plus-Penalty Optimization: They employ the drift-plus-penalty method, a powerful technique from stochastic network optimization. This method aims to minimize a combination of "queue backlog" (representing network congestion and delay) and "penalty" (representing the costs associated with cache usage).
  • Virtual Control Plane Algorithm: They develop a distributed algorithm in the virtual plane that uses VIPs to track demand. This algorithm makes optimal decisions about which objects to cache in which tier and how to forward VIPs to balance queue growth and cache utilization costs. This is framed as an optimization problem that they show can be solved efficiently.
  • Data Plane Policy: They translate the decisions made in the virtual plane into practical caching and forwarding policies for the actual data plane. This involves adapting concepts like cache scores and benefit metrics to account for the multi-tiered nature and cost parameters.
  • Rectangular Assignment Problem (RAP) Formulation: For the caching subproblem, they show it can be formulated as a Rectangular Assignment Problem, which can be solved optimally in polynomial time.

Datasets

Not discussed in the paper. The authors use simulated network topologies (Abilene, GEANT, grid, 3-regular graph) for evaluation.

Key Insights and Ideas

  • Heterogeneity is Key: The paper strongly emphasizes that simply treating all cache tiers equally is suboptimal. Different storage technologies require tailored handling.
  • Joint Optimization Pays Off: Optimizing caching and forwarding together in the virtual plane leads to better overall network performance and cost efficiency than optimizing them separately.
  • Cost-Awareness is Crucial: Ignoring the operational costs (admission, eviction, wear) of slower storage tiers leads to inefficient cache management and can negate their benefits.
  • VIP Framework is Adaptable: The VIP framework, originally designed for single-tier caches, proves to be a powerful foundation for extending to multi-tiered, cost-aware scenarios.
  • Trade-off is Manageable: The drift-plus-penalty approach allows for a tunable trade-off between network delay (VIP backlog) and cache utilization costs (penalty), controlled by a weight parameter.

Key Results

  • Superior Performance: Their proposed VIP-based multi-tiered caching and forwarding policy significantly outperforms traditional naive policies (FIFO, LRU, RAND, LFU) in terms of total user delay and cache utilization costs.
  • Delay Reduction: In simulations, their approach achieved substantial reductions in total delay, outperforming even an adapted LFU policy. For instance, in the grid topology, their policy reduced delay by 95%, compared to a 267% increase with naive LRU.
  • Optimal Trade-off: The paper mathematically demonstrates that their algorithm achieves an optimal trade-off between queue backlog and penalty, allowing users to tune this balance.
  • Scalability: The approach is designed to handle the increasing demand for cache capacity by leveraging heterogeneous storage.

Limitations and Future Work

  • Object Size Assumption: The current model assumes all data objects have the same size. While they mention it can be generalized, the optimal solution for unequal sizes would become a more complex Generalized Assignment Problem (GAP), potentially requiring approximation algorithms.
  • Proactive Migration: The data plane policy can face issues when an object that was previously cached in a slower tier sees a surge in demand but cannot be moved to a faster tier because no requests are actively being forwarded upstream. They suggest proactive migration schemes as a future direction.
  • Shared Bandwidth: The virtual plane assumption that readout rates are independent for each object doesn't perfectly map to the data plane where cache devices share bandwidth. They propose expressing readout rates as dynamic, constrained parameters.
  • Real-world Deployment: The numerical values used in simulations are for illustrative purposes and not direct replications of specific hardware.

Summary updated

Abstract

Caching is vital for high-throughput networks in data-intensive applications. Dynamic random-access memory (DRAM), often used for caching due to its high data transfer rate, faces limitations in capacity and cost, hindering scalability needed to meet growing demand. Evolving flash storage can augment DRAM, but necessitates caching techniques adapted to its charac-teristics for optimal network performance. This paper models the cache as a set of storage blocks with varying rate parameters and utilization costs. Utilizing a framework that enables joint caching and forwarding, we introduce an optimization technique based on the drift-plus-penalty method. Our approach minimizes the drift-plus-penalty expression in a virtual control plane and offers a throughput-cache utilization cost trade-off. We implement a corresponding practical policy in the data plane. Simulations demonstrate the superior performance of our approach in total delay and cache utilization costs.
BibTeX
@inproceedings{mutlu2024cost,
  author = {Faruk Volkan Mutlu and Edmund Yeh},
  title = {{Cost-Aware Joint Caching and Forwarding in Networks with Heterogeneous Cache Resources}},
  booktitle = {ICC},
  year = {2024},
  url = {https://openreview.net/forum?id=dyQa9mNhdo},
}
Figure