On Cost-Driven Collaborative Data Caching: A New Model Approach
Lists
Only you see this
Abstract
In this paper we consider a new caching model that enables data sharing for network services in a cost-effective way. The proposed caching algorithms are characterized by using monetary cost and access information to control the cache replacements, instead of exploiting capacity-oriented strategies as in traditional approaches. In particular, given a stream of requests to a shared data item with respect to a homogeneous cost model, we first propose a fast off-line algorithm using dynamic programming techniques, which can generate an optimal schedule within <inline-formula><tex-math notation="LaTeX">$O(mn)$</tex-math></inline-formula> time-space complexity by using cache, migration as well as replication to serve a <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> -length request sequence in a <inline-formula><tex-math notation="LaTeX">$m$</tex-math></inline-formula> -node network, substantially improving the previous results. Furthermore, we also study the online form of this problem, and present an 3-competitive online algorithm by leveraging an idea of anticipatory caching. The algorithm can serve an online request in constant time and is space efficient in <inline-formula><tex-math notation="LaTeX">$O(m)$</tex-math></inline-formula> as well, rendering it more practical in reality. We evaluate our algorithms, together with some variants, by conducting extensive simulation studies. Our results show that the optimal cost of the off-line algorithm is changed in a parabolic form as the ratio of caching cost to transfer cost is increased, and the online algorithm is less than 2 times worse in most cases than its optimal off-line counterpart.
BibTeX
@article{wang2018cost,
author = {Yang Wang and Shuibing He and Xiaopeng Fan and Chengzhong Xu and Xian‐He Sun},
title = {{On Cost-Driven Collaborative Data Caching: A New Model Approach}},
journal = {IEEE Transactions on Parallel and Distributed Systems},
year = {2018},
doi = {10.1109/tpds.2018.2868642},
}Loading related content...