OPTIMAL CACHE PLACEMENT FOR AN ACADEMIC BACKBONE NETWORK

Than Nguyen Hau, Naonori Kakimura, Ken‐ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, Yu YokoiJournal of the Operations Research Society of Japan 2018 · DOI

Abstract

Deploying caches on a network is an effective way to reduce the amount of data transmitted in a network. Recently, in an academic backbone network such as SINET (the Science Information Network) in Japan, the amount of transmitted data has significantly increased. It is desired to design an efficient mechanism to allocate caches in an optimal way. In this paper, we begin by formulating a discrete optimization model to find a cache allocation that minimizes the total transmission cost. We then design two efficient algorithms to solve our proposed model. The first one makes use of the fact that a backbone network has small treewidth. The algorithm runs in polynomial time when the number of items is fixed and a graph has a bounded treewidth. The other one reduces the problem to the minimum-cost flow problem under the practical assumption that each item has at most one copy. This yields a polynomial-time combinatorial algorithm. Our numerical experiments on the real SINET network show that our algorithms can solve the cache placement problem efficiently in practice.

1. Introduction

As cloud computing and e-learning platforms, such as MOOCs, become central to modern academia, backbone networks are facing a massive surge in data traffic. In Japan, the Science Information Network (SINET) connects over 800 institutions and millions of users. When popular data, such as high-definition lecture videos, is stored in a single central location, it creates significant bottlenecks, increases latency, and spikes transmission costs across the entire infrastructure.

This research addresses the Cache Placement Problem: Given a specific network topology, limited storage at "core" nodes, and varying user demands, where should copies of data items be placed to minimize the total cost of moving data? While this is related to classic problems like p-median or facility location, the network context introduces complexities involving multiple distinct items and strict link capacity constraints.

2. Methodology

The authors approach the optimization problem through three distinct algorithmic lenses, prioritizing both theoretical rigor and practical efficiency:

2.1 Integer Optimization & Approximation

The problem is first formulated as an integer program. By demonstrating its relationship to the matroid median problem, the authors prove that an 8-approximation algorithm exists for the general case, providing a baseline for performance.

2.2 Exploiting Treewidth

Real-world backbone networks are rarely random; they typically exhibit a "tree-like" structure. The authors utilize the concept of treewidth—a graph-theoretic measure of how close a graph is to being a tree. They developed a dynamic programming (DP) algorithm that solves the placement problem in polynomial time for graphs with small treewidth, provided the number of items is fixed.

A tree-based decomposition used for the dynamic programming algorithm, leveraging the low treewidth of backbone networks.

2.3 Minimum-Cost Flow Reduction

Under the practical assumption that each file exists in its original location plus at most one cache, the authors reduced the problem to a minimum-cost flow problem. This allows the use of highly efficient, standard combinatorial algorithms to find optimal placements. For more complex scenarios where multiple copies are allowed, they propose IterativeFlow, a heuristic that repeatedly applies the network flow algorithm to find high-quality solutions.

3. Experimental Setup: The SINET Network

The study validates these algorithms using real-world data from SINET 4, the version of the Japanese academic network active during the study. The topology consists of 11 core nodes and over 100 edge nodes. Traffic volumes were measured via SNMP (Simple Network Management Protocol), and demands were modeled using both Uniform distributions and Zipf’s law—the latter mimicking real-world internet behavior where a small number of items account for the majority of traffic.

The SINET network topology across Japan, showing the distribution of core nodes and edge nodes.

4. Key Insights and Results

Numerical experiments on the SINET topology yielded several critical findings:

  • Significant Cost Savings: Optimal cache placement reduced total transmission costs by approximately 50% compared to a network without caching.
  • Congestion Relief: In the Tokyo area, a major network bottleneck, caching reduced the maximum data transmitted through critical links by about 80%.
  • The "Tree-ish" Advantage: The core of SINET has a treewidth of only 2. This low treewidth allows problems that are typically NP-hard on general graphs to be solved efficiently.
  • Heuristic Efficiency: The IterativeFlow heuristic performed exceptionally well, often staying within 1% to 5% of the theoretical optimal value while remaining computationally light.
  • Impact of Demand Distribution: Caching is most effective when demand follows Zipf's law. If user interest is biased toward a few popular items, strategic caching yields massive gains.

5. Conclusion and Future Work

While the proposed algorithms are highly effective, the treewidth-based DP algorithm is only polynomial if the number of items remains a fixed constant. Additionally, the current model assumes static demand estimates. Future research will focus on developing online management mechanisms capable of modifying cache allocations in real-time as user demands shift throughout the day. This evolution is necessary to maintain efficiency in the increasingly volatile landscape of academic data traffic.

Summary updated

Abstract

Deploying caches on a network is an effective way to reduce the amount of data transmitted in a network. Recently, in an academic backbone network such as SINET (the Science Information Network) in Japan, the amount of transmitted data has significantly increased. It is desired to design an efficient mechanism to allocate caches in an optimal way. In this paper, we begin by formulating a discrete optimization model to find a cache allocation that minimizes the total transmission cost. We then design two efficient algorithms to solve our proposed model. The first one makes use of the fact that a backbone network has small treewidth. The algorithm runs in polynomial time when the number of items is fixed and a graph has a bounded treewidth. The other one reduces the problem to the minimum-cost flow problem under the practical assumption that each item has at most one copy. This yields a polynomial-time combinatorial algorithm. Our numerical experiments on the real SINET network show that our algorithms can solve the cache placement problem efficiently in practice.
BibTeX
@article{hau2018optimal,
  author = {Than Nguyen Hau and Naonori Kakimura and Ken‐ichi Kawarabayashi and Yusuke Kobayashi and Tatsuya Matsuoka and Yu Yokoi},
  title = {{OPTIMAL CACHE PLACEMENT FOR AN ACADEMIC BACKBONE NETWORK}},
  journal = {Journal of the Operations Research Society of Japan},
  year = {2018},
  doi = {10.15807/jorsj.61.197},
}
Figure