Optimal cache placement for an academic backbone network

Than Nguyen Hau, Naonori Kakimura, Ken Ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, Yu Yokoi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)197-216
Number of pages20
JournalJournal of the Operations Research Society of Japan
Issue number2
Publication statusPublished - 2018 Apr


  • Combinatorial optimization
  • Facility planning
  • Graph theory

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research


Dive into the research topics of 'Optimal cache placement for an academic backbone network'. Together they form a unique fingerprint.

Cite this