Optimal storage placement for tree-structured networks with heterogeneous channel costs

Ge Ming Chiu*, Li-Hsing Yen, Tai Lin Chin

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

This work considers data query applications in tree-structured networks, where a given set of source nodes generate (or collect) data and forward the data to some halfway storage nodes for satisfying queries that call for data generated by all source nodes. The goal is to determine an optimal set of storage nodes that minimizes overall communication cost. Prior work toward this problem assumed homogeneous channel cost, which may not be the case in many network environments. We generalize the optimal storage problem for a tree-structured network by considering heterogeneous channel costs. The necessary and sufficient conditions for the optimal solution are identified, and an algorithm that incurs a linear time cost is proposed. We have also conducted extensive simulations to validate the algorithm and to evaluate its performance.

Original languageEnglish
Article number5661768
Pages (from-to)1431-1444
Number of pages14
JournalIEEE Transactions on Computers
Volume60
Issue number10
DOIs
StatePublished - 15 Sep 2011

Keywords

  • Algorithm/protocol design and analysis
  • information storage and retrieval
  • network problems

Fingerprint Dive into the research topics of 'Optimal storage placement for tree-structured networks with heterogeneous channel costs'. Together they form a unique fingerprint.

  • Cite this