Data Caching in Networks with Reading, Writing and Storage Costs
Bin Tang, Himanshu Gupta · 2006
Caching can signiflcantly improve the e‐ciency of information access in networks by reducing the access latency and bandwidth/energy usage. However, caching in too many nodes can take up too much memory, incur extensive caching-related tra‐c, and hence, may even result in performance degradation. In this article, we address the problem of caching data items in networks with the objective of minimizing the overall cost under the constraint that the data item can be cached at only a limited number of network nodes. More formally, given a network, the access pattern of the data item to be shared (i.e., read and write frequencies to the data item by each node), and the storage cost (cost of caching the data item) at each node, our goal is to select at most P cache nodes so as to minimize the sum of reading, writing, and storage costs. We flrst consider networks with a tree topology and design an optimal dynamic programming algorithm which runs in O(n 2 P 2 ), where n is the size of the network and P is the allowed number of caches. For the general graph topology, where the problem is NP-complete, we present a centralized heuristic which is amenable to an e‐cient distributed implementation. Through extensive simulations in general topology graphs, we show that the centralized heuristic performs very close to the exponential optimal algorithm for small networks. In larger networks, we observe that the distributed implementation as well as the dynamic programming algorithm on an appropriately extracted tree perform quite close to the centralized heuristic.