0
$\begingroup$

In the case of specifying the requests' inter-arrival times of a web server.

Let us suppose the following case: (imagine they came from an exponential random function)

  • client1 a stream of $15$ samples of a random variable with seed $1$:

$$ c1 = \{ 1, 1, 3, 2, 1, 2, 1, 3, 4, 2, 1, 1, 1, 2, 1\} $$

  • client2 a stream of $15$ samples of a random variable with seed $2$:

$$ c2 = \{ 2, 4, 1, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 1, 2\} $$

client1 and client2 are different series, however they have the same frequency:

\begin{array}{c|c} \hline Value & Frequency \\ \hline 1 & 8\\ 2 & 4\\ 3 & 2\\ 4 & 1\\ \hline \end{array}

Put the values in a temporal vector, where $0$ is inative and $1$ is client doing a request:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline time &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&21&22&23&24&25&26\\ \hline client1&1&1&0&0&1&0&1&1&0&1&1&0&0&1&0&0&0&1&0&1&1&1&1&0&1&1\\ \hline client2&0&1&0&0&0&1&1&1&0&1&1&0&0&1&1&1&1&0&1&1&0&0&1&1&0&1\\ \hline server&1&2&0&0&1&1&2&2&0&2&2&0&0&2&1&1&1&1&1&2&1&1&2&1&1&2 \\ \hline arrivals&1&1&-&-&3&1&1&1&-&2&1&-&-&3&1&1&1&1&1&1&1&1&1&1&1&1 \\ \hline \end{array}

Then, at the instant of time $1$ the server received $1$ request, at $2$ two requests, and at $3$ none requests were perceived. By merging the inter-arrival times of client 1 and 2, the server's requests time line was generated. The arrivals row in the table corresponds to time between requests, and so we can obtain the stream perceived by the server:

$$ server = \{1, 1, 3, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\} $$

The frequency, now, is different from client 1 and 2:

\begin{array}{c|c} \hline Value & Frequency \\ \hline 1 & 18\\ 2 & 1\\ 3 & 2\\ \hline \end{array}

There were $9$ instants of time where there was $2$ concurrent requests at a time. I counted (is it right?) as interval of $1$. By the frequency table above, we get $18+1+2=21$ and $9+21=30$. Which is the amount of requests generated by client 1 and 2 ($15$ each).

To compute the frequency with a more expressive quantity of samples, consider the following R code:

make_time_vector <- function(seed, nrequests = 1e5) {
  set.seed(seed)
  client <- as.integer(rexp(nrequests) * 10)
  # compute the instant of time where request will happen
  csc = cumsum(client)
  # set a temporal vector and mark requests as one
  req = rep(0, max(csc))
  req[csc] = 1

  req
}

# generate client 1 and 2 vector of requests
client1 <- make_time_vector(1234)
client2 <- make_time_vector(4567)

# create a zeroed vector of maximum size
maxsize = max(length(client1), length(client2))
server <- rep(0, maxsize)
# IMPORTANT:
#   here is where the things happen.
#   After these two lines, server will contain the
#   the perceived workload by it. Is this workload still an exponential?
server <- server[1:length(client1)] + client1
server <- server[1:length(client2)] + client2

# generating PDF and CDF of the server vector time.
css = which(server >= 1)
ss = diff(css)
dss = density(ss)
css = ecdf(ss)
plot(dss)
plot(css)

I would like to know:

  • If after combine the clients (say 50 clients), will the server still receives an exponential inter-arrival time?

  • How do I formalize this situation?

  • Will it work for exponential with different means? Or even, will it work for different distributions?

  • What is the theory I should know?

$\endgroup$
  • $\begingroup$ Since all quantities are integer, what you have here is a discrete-time queueing problem. A lot of work on the steady-state behaviour of such queueing systems was done by the group of Herwig Bruneel, among others (smacs.ugent.be/publications.php). $\endgroup$ – StijnDeVuyst Sep 1 '15 at 12:44
  • $\begingroup$ Your "exponential inter-arrival time" model comes from arrivals whose time of occurrence is continuous, and the probability of two arrivals from the two separate processes occurring simultaneously is $0$. In your discrete-time model where the arrival times are integers, arrivals from the two processes can occur simultaneously quite frequently, and you need to take this into account. Instead, the server seems to be discarding one of the simultaneous arrivals. $\endgroup$ – Dilip Sarwate Sep 1 '15 at 12:52
1
$\begingroup$

This is essentially a queueing problem.

There are two complementary measures for the same process: The interarrival times and the number of arrivals per unit time. If the interarrival times are exponentially distributed with rate $\lambda$ per time unit, then the number of arrivals per time unit has a Poisson distribution with parameter $\lambda$.

So if client 1 generates server requests at an exponential rate $\lambda_1$ and client 2 generates requests with rate $\lambda_2$, then, under some technical assumptions (to rule out simultaneous arrivals), the combined arrival rate will be exponential with rate $\lambda_1 + \lambda_2$.

$\endgroup$
  • $\begingroup$ Then, if client1 has the rate $\lambda_1 = 1$ and client2 the rate $\lambda_2 = 1$, server will have $\lambda_s = \lambda_1 + \lambda_2 = 1 + 1 = 2$. But, by the example or the simulation, I realize the rate decreases, more precisely, it tends to $1$. Am I missing something? $\endgroup$ – Lourenco Aug 31 '15 at 13:36
  • $\begingroup$ The example is not representative, since all interarrival times are integer. I cannot speak to the simulation, since you did not present it. $\endgroup$ – user3697176 Sep 1 '15 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.