PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Complexity of Optimal Routing and Content Caching in Heterogeneous Networks

Mostafa Dehghan, Anand Seetharam, Bo Jiang, Ting He, Theodoros Salonidis, Jim Kurose, Don Towsley, Ramesh Sitaraman

arXiv:1501.00216v1cs.NI

TL;DR

The paper asks how to jointly route requests and place content in heterogeneous networks to minimize access delay, while accounting for congestion-insensitive and congestion-sensitive uncached paths. It formulates both versions, proves their general computational hardness, derives tractable special cases and approximation methods, and evaluates greedy algorithms. These algorithms are within 1% of optimal on small feasible instances and reduce delay by up to 50% versus LRU-based caching, while the study also identifies scope-specific complexity boundaries.

  • Problem

    The central problem is choosing cache contents and request routes across heterogeneous paths to minimize average content access delay while understanding when joint optimization is computationally tractable.

  • Method

    The paper formulates congestion-insensitive and congestion-sensitive joint caching-routing problems, analyzes their complexity and special cases, and develops greedy algorithms using monotone submodular maximization under matroid constraints.

  • Results

    Both models are NP-complete in general; the greedy algorithms are within 1% of optimal for small feasible instances and achieve up to 50% lower delay than LRU-based caching.

  • Takeaways & Limitations

    The congestion-insensitive problem has polynomial-time optimal cases, whereas the congestion-sensitive problem remains NP-complete even with one cache and one distinct file per user; approximation is therefore useful for broader settings.

  • Takeaways & Limitations

    The study includes a congestion-insensitive two-cache case with an optimal polynomial-time solution and a congestion-sensitive single-cache, single-file-of-interest case that remains NP-complete.

Abstract

from arXiv · show

We investigate the problem of optimal request routing and content caching in a heterogeneous network supporting in-network content caching with the goal of minimizing average content access delay. Here, content can either be accessed directly from a back-end server (where content resides permanently) or be obtained from one of multiple in-network caches. To access a piece of content, a user must decide whether to route its request to a cache or to the back-end server. Additionally, caches must decide which content to cache. We investigate the problem complexity of two problem formulations, where the direct path to the back-end server is modeled as i) a congestion-sensitive or ii) a congestion-insensitive path, reflecting whether or not the delay of the uncached path to the back-end server depends on the user request load, respectively. We show that the problem is NP-complete in both cases. We prove that under the congestion-insensitive model the problem can be solved optimally in polynomial time if each piece of content is requested by only one user, or when there are at most two caches in the network. We also identify a structural property of the user-cache graph that potentially makes the problem NP-complete. For the congestion-sensitive model, we prove that the problem remains NP-complete even if there is only one cache in the network and each content is requested by only one user. We show that approximate solutions can be found for both models within a (1-1/e) factor of the optimal solution, and demonstrate a greedy algorithm that is found to be within 1% of optimal for small problem sizes. Through trace-driven simulations we evaluate the performance of our greedy algorithms, which show up to a 50% reduction in average delay over solutions based on LRU content caching.

I. INTRODUCTION

The paper studies joint request routing and content caching in heterogeneous networks to minimize average access delay, under congestion-insensitive and congestion-sensitive uncached paths. It characterizes computational complexity, develops approximation algorithms, and evaluates them against optimal and LRU-based solutions.

  • Problem and models: The joint problem chooses cache contents and routes requests among caches and a back-end server to minimize average content access delay.Content may reside permanently at the back-end server or temporarily in multiple in-network caches.
  • Complexity results: For the congestion-insensitive model, polynomial-time optimal solutions exist when each user requests one file or when the network has at most two caches.The paper also investigates structural conditions associated with computational hardness.
  • Complexity results: The paper identifies odd user-cache cycles as a structural property associated with mismatches between integer and relaxed formulations.In such cases, the constraint matrix is not totally unimodular.
  • Complexity results: The paper formulates both congestion-insensitive and congestion-sensitive versions and proves that each is NP-complete in the general case.The congestion-sensitive model makes uncached-path delay depend on traffic load.
  • Approximation and evaluation: The authors formulate the optimization as monotone submodular maximization under matroid constraints and develop two greedy algorithms.One has a (1−1/e) approximation guarantee; the other has lower complexity without known guarantees.
  • Approximation and evaluation: Both greedy algorithms are within 1% of optimal on small feasible instances, while trace-driven simulations show up to 50% lower delay than LRU-based caching.The evaluation uses numerical experiments and trace-driven simulations.

IV. CONGESTION-INSENSITIVE UNCACHED PATH

Under congestion-insensitive uncached-path delays, the routing and caching problem simplifies because fixed placement permits requests for cached content to use caches and remaining requests to use the uncached path. The resulting optimal routing is integral, although the joint optimization remains generally hard.

  • Model: When uncached-path delays do not depend on back-end traffic load, the average delay is determined by fixed placement and routing decisions.The model treats uncached-path delay as independent of traffic load.
  • Optimal routing: Given a content placement, optimal routing sends cached-content requests to caches and remaining requests to the uncached path.Under this routing policy, cache misses do not occur.
  • Optimization structure: The routing formulation restricts requests to caches that both connect to the user and store the requested content.This is represented by the constraint p_ijm ≤ x_jm · a_im.
  • Optimization structure: Because cached paths are no slower than uncached paths in this model, optimal routing does not split a content request between them, so routing variables are binary.Thus, no optimal routing variable has a fractional value.

A. Hardness of General Case

The joint caching-and-routing problem generalizes the NP-complete HDP, but becomes polynomially solvable in the one-file-per-user special case through maximum weighted matching.

  • The joint caching-and-routing formulation generalizes the NP-complete Helper Decision Problem (HDP).
  • One file per user: When each user requests one file, the optimal solution can be found through maximum weighted matching.Files are matched to unit-capacity micro-cache nodes using edge weights representing caching gains.
  • One file per user: The bipartite graph contains user/file nodes and micro-cache nodes, with edge weights encoding the corresponding placement gains.
  • One file per user: The selected matching edges determine cache placement, while users route cached files to caches and remaining files through the uncached path.
  • One file per user: The Hungarian algorithm solves the matching formulation in polynomial time, with contextual complexity O(M^3N^4).

C. Special Case: Network with Two Caches

For congestion-insensitive delays, two caches admit a polynomial-time optimal solution, while certain user-cache cycles create a gap between integral and relaxed placements. The congestion-sensitive model remains hard even under restrictive single-cache conditions.

  • Two caches admit a polynomial-time optimal solution, even when users may request arbitrarily many files.
  • The relaxed placement problem is polynomial-time solvable because its objective is convex, but fractional placements are not generally legitimate content placements.
  • In a three-user, three-cache cycle, the integral optimum replicates one file in two caches and stores the other in the third.
  • The same cycle’s relaxed solution stores half of each file in every cache and achieves strictly smaller average delay than the integral solution.
  • The authors conjecture polynomial-time solvability when the user-cache graph has no cycles of length 4k + 2, k ≥1.

A. Hardness of General Case

The joint caching-and-routing problem is NP-complete in the congestion-sensitive model, including a restrictive case with one cache and one requested file per user.

  • The congestion-insensitive model is a special case of the congestion-sensitive model when µ = +∞.
  • The congestion-sensitive decision problem asks whether placement and routing assignments achieve average delay at most d.
  • A proposed placement and routing policy can be verified in polynomial time, placing the decision problem in NP.
  • Equal Cardinality Partition is used as the NP-hard source problem for the hardness proof.
  • The resulting Congestion Sensitive Delay Decision Problem is NP-complete.

VI. APPROXIMATION ALGORITHMS

The paper converts joint caching and routing into monotone submodular maximization under matroid constraints. This yields a greedy algorithm with a (1−1/e) guarantee and a faster heuristic without known guarantees.

  • Cache-capacity constraints form a matroid over possible file-cache placements.
  • For any placement, optimal routing can be computed in polynomial time because the routing objective is convex.
  • The placement-value function F(X) is monotone increasing and submodular for both delay models.
  • The higher-complexity greedy algorithm achieves a (1−1/e) factor of the optimal solution.
  • The guaranteed algorithm has complexity O(M 2N 2K2 log (NK)).
  • A second greedy algorithm runs in O(M 3NK) time but has no known accuracy guarantee.

VII. PERFORMANCE EVALUATION

The evaluation compares greedy algorithms with optimal solutions where feasible and with a p-LRU baseline under the congestion-sensitive model.

  • The evaluation measures greedy performance against optimal solutions when optimization is feasible.
  • The evaluation also compares greedy algorithms with a baseline based on the p-LRU caching policy.

A. p-LRU

The p-LRU baseline models users probabilistically routing requests to connected caches while caches use LRU replacement. Its evaluation compares this policy with optimal solutions in small network instances.

  • A. p-LRU: p-LRU routes cache-connected users through cached paths with probability p and otherwise uses the uncached path.When a cached path is selected, the user chooses uniformly among connected caches; users without cache connections always use the back-end server.
  • A. p-LRU: p-LRU cache hit probabilities are estimated from aggregate file popularities and each cache’s characteristic time.The aggregate popularity is independent of p, and characteristic-time approximations determine the probability that each file resides in each cache.
  • A. p-LRU: The model computes average cache-access delay for each user from the caches reachable to that user, then aggregates delay across connected users.The formulation explicitly accounts for users connected to no caches and their uncached-path traffic.
  • A. p-LRU: The evaluation compares single-cache and five-cache architectures with different communication ranges and cache capacities.The single cache has five times the capacity of each cache in the five-cache architecture, while hit and miss delays depend on cache distance and misses add 25 time units.
  • A. p-LRU: GreedyWG differs from the optimal solution in less than 20% of runs, with relative inaccuracy never exceeding 1%.The comparison uses five users, one cache, 15 files, Zipf popularity with skewness 0.6, and back-end service rate µ = 1.

2) GreedyWG vs. Greedy:

GreedyWG and the lower-complexity Greedy algorithm are evaluated across cache budgets, back-end service rates, and trace-driven workloads. Greedy stays close to GreedyWG and reduces delay substantially relative to p-LRU.

  • 2) GreedyWG vs. Greedy:: Greedy is barely distinguishable from GreedyWG as the cache budget varies across five equally provisioned caches.The experiment uses aggregate request rate λ = 5 and back-end service rate 2.5.
  • 2) GreedyWG vs. Greedy:: Greedy remains within 1% of GreedyWG as the back-end service rate varies from 2 to 7 with aggregate traffic rate λ = 5.The cache budget is fixed in this comparison.
  • 2) GreedyWG vs. Greedy:: The trace-driven study uses approximately 9 million requests from 142,000 IP addresses and more than 3 million distinct files.Greedy is used because it has lower complexity and performs close to Algorithm 1.
  • 2) GreedyWG vs. Greedy:: Up to 50% lower average delay is observed with Greedy than with p-LRU in both single-cache and multi-cache networks.The trace is split into learning and evaluation segments for estimating popularities, p-LRU, placement, routing, and average delays.
  • 2) GreedyWG vs. Greedy:: Greedy’s advantage over p-LRU depends on cache architecture and available cache budget, whereas p-LRU performs similarly across the two architectures.The same architecture-dependent effect appears when varying the service-rate-to-request-rate ratio from 0.6 to 1.2 with cache budget 10,000.
  • 2) GreedyWG vs. Greedy:: The joint caching-and-routing problem differs from prior work by incorporating heterogeneous delays, both uncached-path congestion models, and computational-complexity analysis.The paper also proposes algorithms for the joint problem rather than treating caching and routing separately.
  • 2) GreedyWG vs. Greedy:: The conclusion reports a (1 − 1/e)-approximation algorithm and a lower-complexity heuristic within 1% of optimal on small instances.The heuristic also significantly reduces average delay relative to optimized traditional LRU caching.

APPENDIX A NETWORK WITH TWO CACHES

The two-cache appendix proves polynomial-time solvability by showing the relevant optimization matrix is totally unimodular.

  • APPENDIX A NETWORK WITH TWO CACHES: Selected rows are assigned signs so that their signed sums contain only entries from {0, ±1}.The construction groups rows and controls matrix blocks on either side of the indicated lines.
  • APPENDIX A NETWORK WITH TWO CACHES: Total unimodularity implies that the two-cache optimization problem can be solved in polynomial time.The proof derives total unimodularity from the signed-row construction and then applies the resulting integrality property.

APPENDIX B PROOF OF LEMMA 2

The appendix proves NP-hardness for the congestion-sensitive decision problem by reducing Equal Cardinality Partition to a minimum-delay instance.

  • APPENDIX B PROOF OF LEMMA 2: The reduction constructs a congestion-sensitive decision instance whose expected delay can be evaluated in polynomial time.This establishes membership in NP before the hardness argument.
  • APPENDIX B PROOF OF LEMMA 2: Setting cache delays to d^h_i and noncached delays to infinity forces p_i = x_i for every file.Thus files in the cache route all requests to the cache, while files outside it use the back-end server.
  • APPENDIX B PROOF OF LEMMA 2: The reduction requires exactly half the files in the cache and a weighted cache-selection sum of S/2.These constraints connect the optimization objective to equal-cardinality partitioning.
  • APPENDIX B PROOF OF LEMMA 2: The constructed instance reaches minimum delay (2n + 3)/S exactly when the source set can be partitioned into equal-cardinality subsets.The proof establishes both directions of this equivalence.

APPENDIX C PROOF OF LEMMA 4

The proof reduces the congestion-insensitive case to the congestion-sensitive model, then establishes structural properties of the caching objective and routing solution.

  • Proof strategy: The congestion-insensitive case is treated as a special case of the congestion-sensitive model with μ = +∞.The proof therefore addresses only the congestion-sensitive formulation.
  • Objective structure: Placing more content in caches cannot increase delay, so F is monotone increasing in the cache-placement variables.
  • Routing structure: The routing optimization is analyzed by forming its Lagrangian and applying K.K.T. conditions with respect to p_ij.The derivation uses the boundary cases p_ij = 0 and p_ij = 1, as well as the interior case 0 < p_ij < 1.
  • Routing structure: There is a threshold d* such that requests use p_ij = 0 when d_ij < d* and p_ij = 1 when d_ij > d*.
  • Objective structure: The marginal gain from adding content decreases between nested placement sets, establishing that F(x) is submodular.
Loading 1501.00216v1…