| In the past few years, modern communication networks experienced a paradigm shift from traditional, exclusively transportation medium to a distributed storage system (e.g., the Internet), where every node is a possible source of information and services, such as data, audio, software downloads, remote service hosting (e.g., the World-Wide-Web).; The general problem in these emerged distributed storage systems is how to deliver a requested content to users in a timely manner. This would not be possible without help of Web caching, which represents a concept of bringing some of the more popular documents closer to end-users in order to improve network performance and, therefore, reduce the download latency and network congestion. One of the key components in engineering efficient Web caching systems is designing document placement/replacement algorithms that are selecting and dynamically updating a collection of frequently accessed documents. This thesis proposes new, easy to implement cache replacement rules and novel analytic tools for proving their near optimality in the Web environment.; Our design and analysis concentrates on replacement policies for a cache in isolation, given that most of the existing solutions for a single cache do not unify desirable characteristics of a replacement policy in the Web environment, such as: adaptability to fluctuations in information demands, ease of implementation, excellent (nearly optimal) performance that is usually characterized through cache fault probability. We propose a new, Persistent-Access-Caching (PAC) policy that, in the case of i.i.d. requests, can approach the optimal performance arbitrarily close with almost negligible additional complexity when compared to the widely implemented Least-Recently-Used (LRU) policy. In the case of the ordinary LRU policy, which is a special case of the PAC rule, we develop an explicit asymptotic characterization of the cache fault probability taking into account empirically observed strong statistical correlation in request patterns, Zipf's law document popularities and variability in their sizes.; Finally, using the semi-Markov modulation technique for capturing the statistical correlation in request patterns, we prove that for large cache sizes, it is long-term optimal to keep in the cache documents with the largest marginal probabilities. This result may appear surprising given the lack of explicit results for the problem of optimal caching in the presence of dependent requests. (Abstract shortened by UMI.)... |
