Probabilistic model of parallel web servers

126 Views Asked by At

Note: The following probabilistic model of parallel web servers is abstracted from an engineering project. I am not good at probability theory and I am seeking some evaluations and suggestions.

  • Is the probabilistic model well-defined mathematically?
  • Are the three problems on the model reasonable?
  • Are they "solvable" (or quite difficult to solve), especially under the assumptions of the random variables in the model? If not, what is your suggestion?
  • Any references to similar problems are also appreciated.

Probabilistic model:

Consider $n$ web servers $S_1, S_2, \cdots, S_n$, each of which (denoted $S_i$) is responsible to process an individual stream (denoted $s_i$) of read/write requests.

  1. All servers come into work simultaneously and they operate independently and parallelly.
  2. Stream $s_1$ for server $S_1$ consists only of write requests. All other streams consist only of read requests.
  3. The processing time $t$ of each request (either read or write) is modeled as independently, exponentially distributed variables [wiki], with a rate $\lambda_1$.
  4. The request arrival process for each stream is modeled as independently, homogeneous Poisson process [wiki], with a rate $\lambda_2$.

Some notations: For each request $q$, we denote its start time, finish time, processing interval by $q_{.st}$, $q_{.ft}$, and $[q_{.st}, q_{.ft}]$, respectively.

Problems:

(1). For a read request $r$, what is the probability that it starts during the processing interval of some write request (denoted $w$) (i.e., $r_{.st} \in [w_{.st}, w_{.ft}]$)?

Note that if $w$ exists, it is unique (for there is a total order of all the write requests).

(2). For a read request $r$, the set of read requests that finished before $r$ started is denoted by $r^{\prec} = \{\text{read request } r': r'_{.ft} \le r_{.st} \}$.
When (1) happens, what is probability that there exists some read request $r' \in r^{\prec}$ which overlaps $w$?

Note that we already have $r'_{.ft} \le r_{.st}$ and $r_{.st} \in [w_{.st}, w_{.ft}]$, so it is sufficient to check whether $r'_{.ft} \ge w_{.st}$ is satisfied, as shown in the following figure.

overlapping

(3). As an extension to (2), what is the probability that there are exactly $m$ read requests in $r^{\prec}$ of which each overlaps $w$?