Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Waiting time in a Queue using Poisson arrival

  1. Jan 31, 2017 #1
    Dear colleagues.
    I have a difficulty in calculating waiting time of the first packet arriving in a buffer using aggregation. Arrival follow Poisson process with rate lambda and the aggregation is done for a maximum 'm' packets or with the expiry of timer T_maximum. Can anyone help me how to consider interarrival time in case if i have e.g., T_maximum in milliseconds?
     
  2. jcsd
  3. Jan 31, 2017 #2

    StoneTemplePython

    User Avatar
    Gold Member

    Can you be a bit more explicit, perhaps with a simple example to work through your problem?

    It sounds like you have a problem with ##P(k, \tau, \lambda) = \frac{(\lambda \tau)^k e^{-\lambda \tau}}{k!}## (though I think you are using m where I'd use k) and you're just looking to get either (a) the Erlang density (b) density for time between two arrivals or (c) expected time for inter-arrivals, or (d) something else. This is where writing up a simple example in LaTeX, to work through, would be quite helpful -- especially if you show your work on what you've done so far and where you get stuck.
     
  4. Jan 31, 2017 #3

    Dear friend, StoneTemplePython, Thanks for your feedback. Yes, I can explain a little bit more.
    I am considering a buffer for aggregating packets based on two rules. Either based on the aggregation time e.g., Tmax, or based on the full buffer i.e., (max. 'm' packets which can be aggregated). It means that if the buffer receives 'm' packets before Tmax expire, it will send the aggregated packet. OR if the buffer receives less than 'm' packets, and Tmax expires, then It will also send the aggregated packet.

    I am interested to find out the expected value of the waiting time of the FIRST packet entering the buffer. Also, an arrival of a packet triggers the timer Tmax. It means that the first packet is offcourse will come to buffer to trigger this process, the rest of the 'm-1' packets will follow the Poisson process.

    Now, we assume the arrival of packets follow poisson distribution with mean Inter arrival time 1/lambda. Now, I am interested to model the expected values of the waiting time of the first packet entering the buffer. For sure, if the multiplexing is done due to full buffer, meaning that the aggregated packet contains 'r' packet before timer expiry, the waiting time of the first packet follows erlang distribution, and will have a delay of (r-1)/lambda. I wrote 'r-1' because as a said earlier we should not count the first packet that triggers the aggregation process. On the other hand, if aggregation is done due to Tmax, expiry, then what would be the delay. I just suspect that there should be some superposition to make a general formula that should work automatically for any arrival rate lambda. Here I am stuck when I kept my lambda low, meaning multiplexing is done due to Tmax, I am getting wrong answer, but for very large lambda, results from simulator matches with the (r-1)/lambda.

    Also, Can I get your email? I can sent a document to discuss. If you like.
     
  5. Jan 31, 2017 #4

    StoneTemplePython

    User Avatar
    Gold Member

    I've been looking through the forums about Poisson processes (coincidentally over the last week or so) and it seems there are a handful of questions, but people would really benefit from more posts on them. Typically, though certainly not always, there is a simple and elegant way to solve (or if that fails, bound) these problems. Accordingly its really is best to keep things on the forum. Perhaps you can post an image of your document (via imgur or dropbox or whatever).

    I think it's great that you're doing a simulation, btw, as they are great for checking your work and building intuition for what's going on.

    A couple of preliminaries -- how familiar are you with probability theory? There is a great walkthrough of poisson processes here:

    https://ocw.mit.edu/courses/electri...-applied-probability-fall-2010/lecture-notes/ (see 13 - 15). There is also some very good stuff here: https://ocw.mit.edu/courses/electri...tochastic-processes-spring-2011/course-notes/ -- see chapter 2.
    - - - - -
    If I understood you right, you have a clock (in units of ##\tau## that starts ticking after the first arrival. There is a drop dead point where ##\tau## = Tmax. The issue is that by construction, an Poisson process is an aggregation of an infinite number exponential arrivals distributions -- this is where the memoryless process comes into play. If your expect time until the next arrival is ##\frac{1}{\lambda}## given that you have had one arrival, it is also ##\frac{1}{\lambda}## given that you've had 2 and are waiting on the third, and so on. That means the expected time until the next arrival is ##\frac{1}{\lambda}## given that you've had zero arrivals. The fact is these arrivals are memoryless and their expected times don't change whether or not you have a clock sitting next to them. Further -- as long as you are careful with conditioning-- it doesn't matter whether you look at these processes going forward in time, or backward in time.

    Now it occurs to me that there is a lot of jargon here, and that may not be exactly what you wanted... Instead you may be interested in knowing the percent of the time that Tmax is reached and the complement to that is the percent that your reached maximal aggregation size. Then the expected time of the whole process ##= ExpectedTimeUntilFirstArrival + p * T_{max} + (1-p)(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})## , via Linearity of Expectations and Law of Total Expectation.

    Evaluating ##p## and ##(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})## will take some care, but they should be doable. Btw, the simplest way to calculate P is

    ##\Sigma_{k=0}^{r-2} P(k, \tau = T_{max}, \lambda)##

    this quite literally means to set your time = ##T_{max}## and then add up all the probabilities where ##k \leq r-2##. This can be interpreted as adding up the first r-2 terms in the power series for ##exp(\lambda T_{max})##, times the normalizing constant of ##e^{-\lambda T_{max}}##, of course. (There are of course ways to approximate / bound that, though such a thing is really outside the scope.)

    Perhaps you want to take a shot at evaluating ##(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})##?
     
    Last edited: Jan 31, 2017
  6. Jan 31, 2017 #5


    Dear friend! I am quite happy that you understood it very well. Yes, I have studied this probability theory also extensively in the last couple of months. Interestingly, the document over the second link I also studied it.

    Actually, I have
    Actually you have understood the issue quite well. I have studied interestingly the document on the second link provided by you.
    considering p using this ##\Sigma_{k=0}^{r-2} P(k, \tau = T_{max}, \lambda)##, the probabilities will be calculated using standard poisson pmf function by inserting t=Tmax and varying the index, k? where Po reflects probability of (no arrival), I mean other than the first one that trigger timer. p1, one arrival in Tmax, .. to P_r-2 means probability of (r-2) more arrivals in Tmax? Yes, I would be happy to see some help for this one, ##(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})##
     
  7. Jan 31, 2017 #6
    Let me share with you few more things. {writing}

    As a max. of 'r' arrivals can be aggregated based on Tmax, or sufficient arrivals before Tmax, expiry. So, for calculating the longest waiting time of the first arrival, from your above formula, I tried to use it this way. As Poisson PMF says that ##p_{i} = \frac{(\lambda T_{max})^i e^{-\lambda T_{max}}}{i!}##.
    Now, as the clock is always trigger due to the first arrival, it means it reaches at time=0. and after the first arrival, we have ##T_{max} ## for the rest 'r-1' more arrivals. For Poisson we will not count the first arrival.
    In the Poisson pmf, ##p_{0} ## means zero arrival in time ##T_{max} ##, ##p_{1} ## means 1 arrival in time ##T_{max} ##, .... similarly, ##p_{i-1} ## means 'i-1' arrivals in time ##T_{max} ##
    Using your approach. ExpectedTimeFirstArrival I consider it to happen always at 0.
    Then, Its means if I will have less than 'r-1' arrivals, if means aggregation is done due to Tmax. On the other hand, if 'r-1' arrivals occur in Tmax, it means the aggregation will not wait for clock, and it will be sent immediately upon the arrival of 'r-1'th arrival.
    So we have two cases to compute the longest time of the first packet, as you also mentioned in your post, for the first case i.e., Tmax, we have sum up all prob. from i=0 to r-2, i.e, ##(p_{0} ## + ##p_{1} ## +.....+##p_{r-2} )## * ##T_{max} ##. However, for the second case it should be 1-sum##(p_{0} ## + ##p_{1} ## +.....+##p_{r-2} )##*##(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})##. Now as in case of aggregation due to max. 'r' arrivals before Tmax expiry, the first packet passes through 'r-1' stages, so the considering Poisson process I believe that ##(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})## should follow Erlang(r-1,k,Lambda) distribution and will be ##(r-1)/ \lambda##. So, the expectation values of waiting time of the first segment should look like the sum of both portions which I mentioned above (as You said also in your post).

    Do you also agree for ##(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})## to be replaced by ##(r-1)/ \lambda##.?

    w more things. {writing}
     
    Last edited by a moderator: Feb 8, 2017
  8. Jan 31, 2017 #7

    StoneTemplePython

    User Avatar
    Gold Member

    I think the last piece you need to think about is the mechanics of *exactly* how an Erlang distribution of order k, actually works. Here is a quick recap:
    - - - -
    The Erlang distribution of order k is given by:

    ##f_{Y{_k}}(y) = \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!}##

    The CDF for this distribution, up until some time ##\tau## given by

    ##F_{Y{_k}}(\tau) = \int_{0}^{\tau} \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!} dy ##

    and of course, since this is a valid CDF

    ##\lim_{\tau \to \infty}F_{Y{_k}}(\tau) = \lim_{\tau \to \infty} \int_{0}^{\tau} \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!} dy = \int_{0}^{\infty} \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!} dy = 1##

    Now, for the expected time until the kth arrival, over some interval ##[0, \tau]## is given by

    ##E[k_{ArrivalTime} \big | y \leq \tau]= \int_{0}^{\tau} y \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!} dy = \big( \frac{k}{\lambda} \frac{\lambda}{k} \big) \int_{0}^{\tau} y \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!} dy = \frac{k}{\lambda}\int_{0}^{\tau} \frac{\lambda}{k} * y \frac{\lambda^k y ^{k-1} e^{-\lambda y}}{(k-1)!} dy = \frac{k}{\lambda}\int_{0}^{\tau} \frac{\lambda^{k + 1} y ^{k} e^{-\lambda y}}{(k)!} dy = \frac{k}{\lambda} \Big( F_{Y{_{k+1}(\tau)}}\Big)##

    and of course if we don't want to truncate this expectation at some finite value of ##\tau## we can take a limit:

    ##E[k_{ArrivalTime}] = \lim_{\tau \to \infty} E[k_{ArrivalTime} \big | y \leq \tau] = \lim_{\tau \to \infty} \frac{k}{\lambda} \Big( F_{Y{_{k+1}(\tau)}}\Big) = \frac{k}{\lambda} \big(1 \big) = \frac{k}{\lambda}##

    So the expected time of the kth arrival is ##\frac{k}{\lambda}## times the CDF associated with arrival K + 1. The issue is that the CDF for Erlang is, roughly speaking, the complement of your Poisson distribution, so you need to use a series again, in order to calculate this. By construction, a CDF will have values in [0, 1], hence you can easily upper bound ##E[k_{ArrivalTime} \big | y \leq \tau]## by ##\frac{k}{\lambda}##. Alternatively, with large enough ##\lambda## you may be able to do a normal approximation to a Poisson (and then use the CDF of associated normal distribution, which is a common analytic-ish maneuver).

    - - - -
    This should give you all the building blocks you need to solve or approximate or bound your problem. It would be interesting if you compared results here with your simulation. I suppose I broke my own rule here for probability -- I only solved it one way, when in fact solving / checking via another method like a simulation is vital to squeezing out bugs in your thinking, in my opinion.
     
    Last edited: Jan 31, 2017
  9. Jan 31, 2017 #8
    I fully agree with this. "The expected time of the kth arrival is ##\frac{k}{\lambda}## times the CDF associated with arrival K + 1". Since in my case instead of 'r', I am considering 'r-1' more arrivals following Poisson, thats why I mentioned to ##\frac{r-1}{\lambda}##. Exactly, we can represent erlang cdf as complement of poisson cdf. So this, the expectation value of the waiting time of the first arrival would be Tmax*(po+p1+p2+..+p_r-2)+(1- sum((po+p1+p2+..+p_r-2)))*(r-1/lamda). I just compared results form this with simulations. Actually for very higher arrival rate, the simulation results fully match with this formula as (1- sum((po+p1+p2+..+p_r-2))) is almost 1 because aggregation is mainly done due to arrival of 'r' segments before Tmax expiry. resultantly, (r-1)/lambda is the delay and simulations agree with them as well. However for low lambda, like 50 arrivals/sec , 100, 200, etc... I saw the delay from this expression is firstly slightly increasing with increasing lambda, and later start decreasing and for very higher values of lambda, it then starts following the simulations results
     
  10. Jan 31, 2017 #9
    Res-01.jpg
     
  11. Jan 31, 2017 #10
    We represented expectation value of the waiting time of the first arrival as Tmax*(po+p1+p2+..+p_r-2)+(1- sum((po+p1+p2+..+p_r-2)))*(r-1/lamda). The results I showed in the graph you can see show some mis-tmatch for lower lambda, i.e., in the part of Tmax. Its means in the first portion of the formula related to Tmax, sum of all probabilities results more values compared to actual simulations results. As In simulations, sometime 1,2,3 or any number of arrivals < 'r-1' (excluding the first one) are multiplexed, however, the formula some how gives upper bound of the expectation values (i feel).
    Now, I just removed the ##p_{r-2}## and kept the sum from ##p_{0}## to ##p_{r-3}## and Multiplied with Tmax, however, the second portion of the formula is kept same i.e., it considers the ##p_{r-2}## when calculating 1- sum(##p_{0}+p_{1}+p_{2}+p_{3}+.....+p_{r-2})## * ##(r-1)/ \lambda## And surprisingly results fully match for all cases, for any Tmax, and for any 'r' ..But I could not get why deleting ##p_{r-2}## from the first part result this.
     
  12. Jan 31, 2017 #11
    Here you can see the results.
    Res-02.jpg
     
  13. Jan 31, 2017 #12

    StoneTemplePython

    User Avatar
    Gold Member

    The pictures are a great way to think about this. In particular https://www.physicsforums.com/attachments/112341/ is a very good picture.

    Keep in mind that the actual analytical result is
    ##E[k_{ArrivalTime} \big | y \leq \tau]= \frac{k}{\lambda} \Big( F_{Y{_{k+1}(\tau)}}\Big)##, but so far as I can tell, in the first picture you are just using ##\frac{k}{\lambda}##. Put differently you are using the upper bound, not the exact analytical solution.

    I just want to be sure that you realize that when I originally said:
    ## = ExpectedTimeUntilFirstArrival + p * T_{max} + (1-p)(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})##

    we can now rewrite this as :
    ## = ExpectedTimeUntilFirstArrival + p * T_{max} + (1-p) \Big(\frac{k}{\lambda} \Big( F_{Y{_{k+1} (\tau)}}\Big)\Big)##

    hence you'll see something that looks like a complement of a Poisson twice in the term ##(1-p) \Big(\frac{k}{\lambda} \Big( F_{Y{_{k+1}(\tau)}}\Big)\Big)##, first in the ##(1-p)## component, and second, something similar in ##\Big( F_{Y{_{k+1} (\tau)}}\Big)##

    - - - -
    edit: it looks like your second picture *might* agree with your simulation as you seem to have done some additional cancellations / simplification related to the different complements. Even then, the agreement almost looks too good ;-)
     
    Last edited: Jan 31, 2017
  14. Jan 31, 2017 #13

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Congratulations on getting an analytical solution! I think you can see from this example that queuing problems quickly get too hard to solve analytically except for the most idealistically simplified cases. Computer simulation is the only way to do complicated work in this area.
     
  15. Feb 1, 2017 #14
    Hi. Good morning! A great help indeed by you. Yes, In the first picture where there are some mismatches, I computed the analytical results using ## = ExpectedTimeUntilFirstArrival + p * T_{max} + (1-p)(ExpectedTimeUntilArrival_{r-1}| \tau < T_{max})##, I considered ExpectedTimeUntilFirstArrival=0, p is summation from ##p_{0}+p_{1}+...+p_{r-2}##. So, the overall formula was ##p*T_{max} + (1-p)*((r-1)/\lambda)##. To be a bit clear, I used ##((r-1)/\lambda)## instead of ##r/\lambda## as in this case we will have have 'r-1'th as our last arrival neglecting the FIRST one. If i use ##r/\lambda##, the matched part of the first figure over the higher arrival rate also mistmatches with simulation by a value of##1/\lambda##.

    You are right. If I consider your actual proposed expression
    ## = ExpectedTimeUntilFirstArrival + p * T_{max} + (1-p) \Big(\frac{k}{\lambda} \Big( F_{Y{_{k+1} (\tau)}}\Big)\Big)##

    If I am not wrong, if the max. ##r## arrivals can be multiplexed, the above formula can be considered as,
    ## = ExpectedTimeUntilFirstArrival + p * T_{max} + (1-p) \Big(\frac{r-1}{\lambda} \Big( F_{Y{_{r} (\tau)}}\Big)\Big)##. Right?

    I mean, I used, ## (1-p) \Big(\frac{r-1}{\lambda} \Big( F_{Y{_{r} (\tau)}}\Big)\Big)##, Then yes, you are right probability factor in the second part of the equation will appear twice. The expression will like, ## = p * T_{max} + (1-p)* (\frac{r-1}{\lambda} * (1-p)## as ExpectedTimeUntilFirstArrival=0; and ##\Big( F_{Y{_{r} (\tau)}}\Big)## is actually also ##(1-p)##. Also, I can check the results quickly.Let me share with you.
     
  16. Feb 1, 2017 #15
    I have just computed the results using this expressions, ## = [ExpectedTimeUntilFirstArrival=0] + p * T_{max} + (1-p) \Big(\frac{r-1}{\lambda} \Big( F_{Y{_{r} (\tau)}}\Big)\Big)##, in which
    ##p= \Sigma_{k=0}^{r-2} p_{k}## , 1-p= 1-## \Sigma_{k=0}^{r-2} p_{k}## and ##\Big( F_{Y{_{r} (\tau)}}\Big) = 1-\Sigma_{k=0}^{r-2} p_{k}##
    I got these results, a bit mismatch again for lower lambda, however, the analytical values decreased some Res-03.jpg whow,
     
  17. Feb 1, 2017 #16

    StoneTemplePython

    User Avatar
    Gold Member

    My gut tells me there is an indexing by one error in one of your terms. That is, I think it should be ##\Big( F_{Y{_{r} (\tau)}}\Big) = 1-\Sigma_{k=0}^{r-1} p_{k}##

    But I'll have to take closer look after some sleep. In general, indexing errors are quite easy to come by in math and programming -- especially when you switch between something that zero indexes like python to a one based indexing like matlab!

    One way or the other you're basically there.
     
  18. Feb 1, 2017 #17
    OK Many Thanks. Yes, I can recheck again my terms if something off by one error.. Sure, you take sleep and I will update again. Thanks once again for this great help.
     
  19. Feb 1, 2017 #18
    I just tried to solve this.., for calculating Erlang CDF for rth arrival. The upper limit go to 'r-1' instead of 'r-2'
    Here is the explanation. Unfortunately, results dont match for lower lambda,

    doc_mehmood.png
     
  20. Feb 1, 2017 #19
    Hi. Yes, I fully agree with you. Its always quite complex using Queueing models for some kind of representation/phenomenon. I have realized it.
     
  21. Feb 1, 2017 #20

    StoneTemplePython

    User Avatar
    Gold Member

    try this instead:

    ##
    = [ExpectedTimeUntilFirstArrival=0] + p * T_{max} + \Big(\frac{r-1}{\lambda} \Big( F_{Y{_{r} (\tau)}}\Big)\Big)
    ##

    notice that the (1-p) is gone. There is a subtle conditioning issue here. Technically the (1-p) was ok to have in the model to begin with but after choosing the specific way to represent ##ExpectedTimeUntilArrival_{r-1}| \tau < T_{max}## that I did, I should have recognized that I was in effect double counting (read: double using) the 1-p term.

    Basically it's already in the erlang density. You can see this if you look at the definition of erlang as ##
    f_{Y_k} \approx \delta^{-1} * \big(TotalProbabilityAtLeastKArrivals(y + \delta) - TotalProbabilityAtLeastKArrivals(y) \big)## for some small ##\delta > 0##. Note the approximation becomes exact in ##\lim_{\delta \to 0}##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted