Paper Info
Title
On Cost-Driven Collaborative Data Caching: A New Model Approach
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 xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(mn)$</tex-math><alternatives><inline-graphic xlink:href="wang-ieq1-2868642.gif"/></alternatives></inline-formula> time-space complexity by using cache, migration as well as replication to serve a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math><alternatives><inline-graphic xlink:href="wang-ieq2-2868642.gif"/></alternatives></inline-formula> -length request sequence in a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$m$</tex-math><alternatives><inline-graphic xlink:href="wang-ieq3-2868642.gif"/></alternatives></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 xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(m)$</tex-math><alternatives><inline-graphic xlink:href="wang-ieq4-2868642.gif"/></alternatives></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.
Year
DOI
Venue
2019
10.1109/TPDS.2018.2868642
IEEE Transactions on Parallel and Distributed Systems
Keywords
Field
DocType
Heuristic algorithms,Data models,Servers,Trajectory,Streaming media,Dynamic programming,Electronic mail
Online algorithm,Data modeling,Dynamic programming,Cache,Computer science,Server,Node (networking),Cache algorithms,Rendering (computer graphics),Distributed computing
Journal
Volume
Issue
ISSN
30
3
1045-9219
Citations 
PageRank 
References 
1
0.37
0
Authors
5
Name
Order
Citations
PageRank
Yang Wang118845.73
Shuibing He210920.45
Xiaopeng Fan359769.90
Z. Chen43443271.62
Xian-he Sun51987182.64