... process^2.1

Definition of stationary distribution vector is given in Section 2.4.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... (DTMC)^2.2

Definition of a DTMC and $\P$ is given in Section 2.4.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... (CTMC)^2.3

Definition of a CTMC and ${\mathbf{Q}}$ is given in Section 2.4.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... process^2.4

Named after A.A. Markov (1856-1922), a Russian mathematician who made fundamental contributions to probability theory.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... process^2.5

In the literature, the boundary and the repeating portion of an infinite CTMC are also referred to as the non-homogeneous and the homogeneous parts of the CTMC, respectively [32].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Coxian^2.6

A given exponential phase $i$, $0 < i < n$, of a Coxian distribution is associated with two rates: $\lambda_i^1$ for reaching the next exponential phase and $\lambda_i^2$ for reaching the absorbing state of the underlying Markov chain. The total rate of leaving phase $i$ is $\lambda_i=\lambda_i^1+\lambda_i^2$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ${\mathbf{Q}}_{i,i}^{*}$^2.7

${\mathbf{Q}}_{i,i}^{*}$ means that the respective matrix ${\mathbf{Q}}_{i,i}$ is modified by adding the corresponding off-diagonal cumulative rate into its elements.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... overview^3.1

In this section and in the remainder of this dissertation, we assume continuous time Markov chains, or CTMCs unless otherwise stated, but our discussion applies just as well to discrete time Markov chains, or DTMCs.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... relation^3.2

This is similar to the simplest degenerate case of a QBD process, the straight forward birth-death M/M/1 case.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... obtain^3.3

Recall that $\overline{\mbox{\boldmath{$\pi$}}}$ is the stationary probability vector of the stochastic complement of states in ${\cal{A}}$ and $\mbox{\boldmath{$\pi$}}[{\cal{A}}]$ is the stationary probability vector of states in ${\cal{A}}$ in the original M/G/1 process. They relate to each other based on the equation $\overline{\mbox{\boldmath{$\pi$}}} = \mbox{\boldmath{$\pi$}}[{\cal{A}}]/(\mbox{\boldmath{$\pi$}}[{\cal{A}}] {\mathbf{1}}^T)$, which implies that any relation that holds among subvectors $\overline{\mbox{\boldmath{$\pi$}}}^{(j)}$ for $j \leq i$ would hold for subvectors $\mbox{\boldmath{$\pi$}}^{(j)}$ for $j \leq i$ as well

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... $(-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}]^{-1}\cdot {\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}])$^3.4

Only the entries of the last block column of $(-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}]^{-1})\cdot {\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}]$ are different from zero.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...NeutsMG1^3.5

The probabilistic interpretation of ${\mathbf{G}}$ is the same for both DTMCs and CTMCs.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... multiplications^3.6

Subtractions on these type of formulas present the possibility of numerical instability [69,75].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... matrices^3.7

A Toeplitz matrix has equal elements in each of its diagonals allowing the use of computationally efficient methods.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... slowdown^4.1

The mean slowdown metric is computed by dividing the average waiting time in the queue with the average service time.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... site^4.2

Available at http://ita.ee.lbl.gov/.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... CDH^4.3

The fitting algorithm is not sensitive to the amount of collected bins for the Erlang fitting, since we tried values in $(0.1\%, 1\%)$ and obtain similar results.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...FIG:OverallPDF-CDF^4.4

Trace 1 in the analysis of D&C EM comes from the same server logs as the data set we use for analysis of D&C MM. The PDF of Trace 1 in Figure 4.5 is more jagged than the PDF presented in Figure 4.13 because in the former case we use shorter bins for our plots.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... implementation^5.1

Code available at http://www.dm.unipi.it/~meini/ric.html.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... timings^5.2

We point out that our timing results do not take into consideration the computation of ${\mathbf{G}}$, which is used in all three methods

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... stable^5.3

We opt not to compare ETAQA-M/G/1 with the Fast FFT Ramaswami's formula because the FFTs may be the source of numerical instabilities [58].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... one.^5.4

We conducted a large number of stability experiments but due to space restrictions we only present a few experiments here. We note however that all of our experiments did produce consistent results with those presented in this section.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... packages^5.5

Available from http://www.netlib.org.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...${\cal{A}}_2$^6.1

We use indices in the case of stochastic complementation on non-disjoint subsets to distinguish from the case when the subsets are disjoint

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... complement^6.2

Actually we apply the pseudo stochastic complement to generate the M/G/1 process with set of states ${\cal{L}}\cup {\cal{G}}^-_g$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... site^7.1

Available at http://ita.ee.lbl.gov/.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...Crovella98^7.2

http://www.cs.bu.edu/faculty/crovella/aest.html.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... FW^7.3

We choose FW algorithm to fit the hybrid distribution into a hyperexponential because here we are dealing with distribution functions and FW performs well, i.e., it is fast and accurate, when fitting heavy-tailed distribution functions.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... rates^7.4

For presentation clarity, the $x$-axis of Figure 7.6(b) shows only the value of the $b$ parameter of the lognormal distribution for the corresponding data set, but we remind the reader that a different value of $b$ implies also a different value of $a$, to keep the same mean request size across all data sets.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... optimal^7.5

All our experiments are driven by the servers logs at the World CUP 1998 Web site. Using this workload, we always achieved with EQUILOAD almost optimal caching behavior. In the remainder of this chapter, whenever we claim close to optimal behavior for EQUILOAD, we assume that the Web cluster operates under similar workload as the one measured at the World CUP 1998 Web site.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... rate^7.6

Note that the system can sustain higher arrival intensities comparing to the results of previous subsections. This is a direct outcome of the fact that the service rates are much higher (by two orders of magnitude) if the file resides in cache.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... considered^7.7

$C$ is some real constant greater than one. Using a value close to one results in a fine DDH representation, but also in a larger value for $F$, since $C^F$ must exceed the size of the largest file that may be requested.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... requests^7.8

For the first batch, previous history is not available. In our simulation we simply discard its corresponding performance data, so we use the first $K$ requests just to compute the first DDH. In a practical implementation, instead, we would simply guess boundaries to be used for the first batch.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... requests^7.9

We also experimented using the Join Shortest Queue (JSQ) policy but we do not report the results because they are consistently inferior to those for JSWQ.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... MAMSolver^8.1

Details available at http://www.cs.wm.edu/MAMSolver/

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.