| The first part of this thesis focuses on Web caching, a technique that attempts to bring more popular documents closer to end-users so that the download latency and network congestion can be reduced. One of the key components of engineering efficient Web caching systems is designing document placement (replacement) algorithms that are selecting and possibly dynamically updating a collection of frequently accessed documents. The design of these algorithms has to be done with special care since the latency and network congestion may actually increase if documents with low access frequencies and/or short expiration times are brought into the cache. Thus, our main design objective is to achieve high cache hit ratios, while maintaining ease of implementation and scalability. In this regard, the first contribution of this thesis is the extension of the performance analysis of the well known Least-Recently-Used (LRU) caching algorithm under the assumption of moderately heavy request distributions, that are commonly observed in practice. What is more, based on the insights from the analysis, we propose a new, easy to implement, cache replacement rule called Discrete-Persistent-Access-Caching (DPAC), whose near optimality is proved using our novel large deviation technique. In addition, we characterize the miss sequence of a LRU cache, which is aiming at extending the analysis of a single cache to networks of caches. The main technical difficulty for the preceding problems is decoupling the dependency of infinite sequences of weakly correlated random variables.;In the second part of the thesis, we study scheduling algorithms, whose objective is to achieve the desirable performance by appropriately assigning the service priority among jobs in the system. For jobs with heavy-tailed distributions, scheduling is especially important since large jobs appear much more frequently for heavy-tailed distributions than for the light-tailed ones, implying that schedulers that may assign the server exclusively to a very large job, e.g., first come first serve (FIFO) discipline, can cause very large delays and, in general, suboptimal performance. In this context, we refine the analysis for medium size jobs under the heavy-tailed assumptions for three most popular scheduling algorithms: Processor Sharing (PS), Shortest Remaining Processing Time first (SRPT) and Foreground Background Processor Sharing (FBPS). Based on the analytical results, we discuss the analysis of new algorithms which can address the scalability and adaptability issues in the existing scheduling schemes. In addition, we study the PS scheme in more detail since it is widely employed in practice due to its fairness, and is used for modeling TCP protocol. Specifically, we investigate the induced delay caused by PS scheme when the statistically long jobs (subexponential) and short ones (exponentially bounded) are mixed and served together. First, we derive a general result by showing that mixing light-tailed (short) jobs with heavy-tailed (long) ones causes long delays for all jobs in system. Then, we quantify the preceding result when the long jobs follow the widely observed power law distribution x-alpha, alpha > 0, where we discover the criticality of the lognormal distribution for the delay characteristics of the possibly lighter jobs. Explicit logarithmic asymptotic results are also derived for the delay of lighter jobs when they have much lighter tails, including exponential, Gaussian and Weibull distributions.;We discuss the potential extensions of our results in the last chapter of this thesis. In particular, we consider extending the analysis of a single LRU-based caching algorithm to the distributed, e.g. hierarchical, caching systems. To this end, we discuss how our results on characterizing the miss sequences of an LRU cache can lead to potential analysis of a network of caches. For scheduling, we discuss the possible solutions to the discovered induced delay of the PS system, such as admission control, jobs classification, prioritization and/or reservation mechanisms. Finally, we briefly discuss the potential of developing a unified theory for caching and scheduling since they typically appear jointly in practice. (Abstract shortened by UMI.)... |
