1
$\begingroup$

In the beginning, I am gonna explain a system with a homogeneous process for the distribution of arrival rates of data items to the system. In the second part, I explain my main question in which an inhomogeous distribution is used for the arrival rates of data items to the system.

1) System with homogeneous process for the distribution of arrival rates of data items to the system:

Suppose there are $N$ data items requested by users. The requests are processed at a system comprises $K$ servers. We assume that items are mapped uniformly to servers according to a hash function $f_H : [1 \dots N] \rightarrow [1 \dots K]$ to get service. Therefore, we can model the assignment of an item $i$ to a server using a Bernoulli random variable $X_i$ such that: \begin{equation} f_{X_i}(x)= \begin{cases} \frac{1}{K}, & x= 1 \\ 1- \frac{1}{K}, & x= 0 \end{cases} \end{equation}

The arrival rate of data items follows a homogeneous Poisson process with mean $\lambda$. Data item $i$ is requested by users with probability of $p_i$. As a result, the request rate for data item $i$ is $\lambda p_i$.

We can now express the fraction of requests that each server receives as:

$L = \sum_{i=1}^{N}X_i \lambda p_i$

2) System with inhomogeneous process for the distribution of arrival rates of data items to the system:

Now, we need to consider an inhomogeneous Poisson process for the arrival of each data item. In such a system, we don't have a fixed number of data items. New data items are introduced to the system at random. For simplicity, this is taken to be according to a homogeneous Poisson process with rate $\gamma$. In addition, we assume that arrival rate of data item $i$ changes over time as: $\lambda_i(t) = V_i \beta(t-\tau_i)$; in which $\tau_i$ is the time that item $i$ is introduced into the system. $V_i$ is also the total number of request for data item $i$. We assume that volumes of requests for different items form an i.i.d. sequence of random variables distributed around some reference $V$. Moreover, $\beta(t)$ satisfies the following conditions:

  1. $\beta(t) \ge 0\ \forall t$ with $\beta(0^+)>0$,
  2. $\beta(t) = 0\ \forall t < 0$,
  3. $\beta(t)$ continuous almost everywhere,
  4. $\int_0^{\infty}\beta(t)dt = 1$.

The question is now how we can get the mean fraction of requests that each server receives?

I have an answer for this question down below; but I am not sure if it is correct or not?!

$\endgroup$
2
  • $\begingroup$ Does the first part of your question have anything to do with the second (other than providing context)? If not, you might want to edit your post to make that more clear. $\endgroup$
    – Math1000
    Oct 15, 2016 at 4:36
  • $\begingroup$ @Math1000 thanks for comment. I modified the text. I hope it makes sense more now. $\endgroup$ Oct 15, 2016 at 7:42

1 Answer 1

1
$\begingroup$

The fraction of requests that each server receives will be a function of $t$ as follows:

$L(t) = \big(\sum_{i=1}^{\gamma t} X_i \lambda_i(t)\big)/ \big(\sum_{i=1}^{\gamma t} \lambda_i(t)\big)$

in which $\lambda_i(t)$ is the number of requests generated by users for data item $i$ at time $t$.

So, we have $L(t) = \big(\sum_{i}^{\gamma t} X_i V_i \beta(t-\tau_i)\big) / \big(\sum_{i}^{\gamma t} V_i \beta(t-\tau_i)\big)$,

Consequently:

$E[L(t)] = E[\big(\sum_{i}^{\gamma t} X_i V_i \beta(t-\tau_i)\big)/\big(\sum_{i}^{\gamma t} V_i \beta(t-\tau_i)\big)]=$

$\big(\sum_{i}^{\gamma t} E[X_i V_i \beta(t-\tau_i)]\big) / \big(\sum_{i}^{\gamma t} E[ V_i \beta(t-\tau_i)]\big) =$

$ \big(\sum_{i}^{\gamma t} E_X[X_i] E_V[V_i] E_\tau[\beta(t-\tau_i)]\big) /\big(\sum_{i}^{\gamma t} E_V[V_i] E_\tau[\beta(t-\tau_i)]\big) = \frac{1}{K}$

To calculate $Var[L(t)]$, I need to calculate $ E_{\tau}[\beta(t-\tau_i)]$ as follows:

$ E_{\tau}[\beta(t-\tau_i)] = \frac{1}{t}\int_{0}^{t}\beta(t-\tau_i)d\tau_i$

having $\theta = t - \tau_i$ results in the following?

$ E_{\tau}[\beta(t-\tau_i)] = \frac{1}{t}\int_{0}^{t}\beta(\theta)d\theta$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .