DocumentCode :
1243178
Title :
Objective-optimal algorithms for long-term Web prefetching
Author :
Wu, Bin ; Kshemkalyani, Ajay D.
Author_Institution :
Dept. of Comput. Sci., Illinois Univ., Chicago, IL, USA
Volume :
55
Issue :
1
fYear :
2006
Firstpage :
2
Lastpage :
17
Abstract :
Web prefetching is based on Web caching and attempts to reduce user-perceived latency. Unlike on-demand caching, Web prefetching fetches objects and stores them in advance, hoping that the prefetched objects are likely to be accessed in the near future and such accesses would be satisfied from the caches rather than by retrieving the objects from the Web server. This paper reviews the popular prefetching algorithms based on popularity, good fetch, API characteristic, and lifetime, and then makes the following contributions: 1) The paper proposes a family of linear-time prefetching algorithms, objective-greedy prefetching, wherein each algorithm greedily prefetches those Web objects that most significantly improve the performance as per the targeted metric. 2) The hit rate-greedy and bandwidth-greedy algorithms are shown to be optimal for their respective objective metrics. A linear-time optimal prefetching algorithm that maximizes the H/B metric as the performance measure is proposed. 3) The paper shows the results of a performance analysis via simulations, comparing the proposed algorithms with the existing algorithms in terms of the respective objectives - the hit rate, bandwidth, and the H/B metrics. The proposed prefetching algorithms are seen to provide better objective-based performance than any existing algorithms. Further, H/B-greedy performs almost as well as H/B-optimal.
Keywords :
Internet; cache storage; file servers; greedy algorithms; randomised algorithms; Web caching; Web prefetching; Web server; bandwidth-greedy algorithm; hit rate-greedy algorthim; objective-greedy prefetching; objective-optimal algorithm; performance analysis; Cache memories; File servers; Internet; Index Terms- Web server; Web caching; Web object; Web prefetching; World Wide Web; bandwidth; content distribution; hit rate; optimal object selection; randomized algorithm.;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.2006.12
Filename :
1545747
Link To Document :
بازگشت