EEL6507sp09L13

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 13, Friday 2009/02/06 (Notes created by Nathan Blythe)

Covered in this lecture:

  • Solving a discouraged arrival queueing problem
  • Introduction to M/M/\infty systems

Discouraged arrivals

For discouraged arrivals, the probability of joining the queue depends on the length of the queue. Consider taking arrival rate λ and "throwing away" an arrival to a queue with length k with some probability rk, so that the actual arrival rate of customers to the queue is λk = rkλ.

As per problems 2.1 and 2.2 in the text, if the arrivals to the queue are Poisson, so are the arrivals after being "split" into two streams (one of which constitutes the "thrown away" arrivals, and the other the arrivals that are actually processed in the queue).

Solving the discouraged arrivals queueing problem

Customers arrive with rate λ and join the queue with probability r_k = \frac{1}{k + 1}. For example, if there are no customers enqueued, the first arriving customer joins the queue with probability 1; if there are 1 customers enqueued, the second arriving customer joins the queue with probability 1 / 2; if there are 2 customers enqueued, the third customer joins the queue with probability 1 / 3.

Consider state k = 0. The flow out of this state is λ0p0 and the flow into this state is μ1p1, which generalizes to λkpk and μk + 1pk + 1. For equilibrium, flow out must equal flow in, so λkpk = μk + 1pk + 1.

Applying the product trick, we have \prod_{k = 0}^{n - 1} \frac{\lambda_k}{\mu_{k + 1}} = \prod_{k = 0}^{n - 1} \frac{p_{k + 1}}{p_k} = \frac{p_n}{p_0}. After applying the definition of \lambda_k = \frac{1}{1 + k} and <\math>\mu_k = \mu</math> we find that p_n = p_0 \left(\frac{\lambda}{\mu}\right)^n \frac{1}{n!}.

Next we normalize to find p0. We recognize that

∑pn = 1
n

and p_0 \sum_{n = 0}^{\infty} \left(\frac{\lambda}{\mu}\right)^n \frac{1}{n!} = p_0 e^{\lambda / \mu}. Then p0eλ / μ = 1 yields p0 = e − λ / μ.

We have now found p_n = e^{-\lambda / \mu} \left(\frac{\lambda}{\mu}\right)^n \frac{1}{n!}, which is Poisson.

Ergodicity

Next we want to determine when this queue is ergodic, recurrent null, and transient. We expand the sums S1 and S2 to find:

S_1 = \sum_{n = 0}^{\infty} \prod_{k = 0}^{n - 1} \frac{\lambda_k}{\mu_{k + 1}}

S_2 = \sum_{n = 0}^{\infty} 1 / \left\lbrace \lambda_n \prod_{k = 0}^{n - 1} \frac{\lambda_k}{\mu_{k + 1}} \right\rbrace = \frac{1}{\lambda} \sum_{n = 0}^{\infty} \left(\frac{\lambda}{\mu}\right)^{-n} (n + 1)! = \frac{1}{\lambda} \sum_{n = 0}^{\infty} \frac{(n + 1) (n) (n - 1) \cdots}{(\lambda / \mu) (\lambda / \mu) (\lambda / \mu) \cdots}

Next we check convergence. S1 converges \forall \lambda, \mu such that \frac{\lambda}{\mu} is well defined. Thus \lambda < \infty and μ > 0. S2 always diverges, as we can show that \exists n > \frac{\lambda}{\mu} (and so the numerator will eventually increase faster than the denominator, and in the limit increase without bound).

Ergodicity

The queue is ergodic if S1 converges and S2 diverges. This occurs iff μ > 0. (Stating \lambda < \infty is true, but trivial, since λ is non-negative real-valued.) In conceptual terms, this implies that in the limit, the rate at which customers arrive is less than the rate at which they are served.

Recurrence null

The queue is recurrent null if both S1 and S2 diverge. This cannot occur, because for S1 to diverge, μ = 0, which reduces S2 to a trivial sum ( = 0). The queue can therefore never be recurrent null.

Transience

The queue is transient if S1 diverges and S2 converges. This corresponds to (as described in "Recurrence null" above) the case where μ = 0. It is obvious that such a queue would be transient; if the service rate is 0, the queue will never empty, and will increase in length (although the arrival rate becomes very small as per λk).

Average number of customers in the system

Next we want to find \bar{N}, the average number of customers in the system. We take \bar{N} to be the expected value of the state of the queue, and solve \bar{N} = \sum_{k = 0}^{\infty} k p_k = \sum_{k = 0}^{\infty} k e^{-\lambda/\mu} \left(\frac{\lambda}{\mu}\right)^k \frac{1}{k!} to find \bar{N} = \frac{\lambda}{\mu}.

Average system time

Now we want to find \bar{T}, the average time in the system. We start by looking at Little's Result, and stating that \bar{N} = \lambda \bar{T}. However, this λ is not the same as λ used elsewhere in these notes! This λ corresponds to the arrival rate at the queue itself, without respect to arrivals that were "thrown away". We will continue this next lecture.

Brief look at M/M/\infty queues

Consider a M/M/\infty queue: a Markovian queue with an infinite number of servers. We could represent this as a queue with arrival rate λk = λ and service rate μk = kμ. In other words, if there are k customers in the system, the service rate is such that it can service them all with the same service time.

From this we find that p_k = p_0 \prod_{i = 0}^{k - 1} \frac{\lambda_{i}}{\mu_{i + 1}} = p_0 \frac{\lambda}{\mu} \prod_{i = 0}^{k - 1} \frac{1}{i + 1} and ultimately \bar{N} = \frac{\lambda}{\mu} and \bar{T} = \frac{1}{\mu}, which implies that there is no time spent waiting. This is expected, since an infinite number of servers may service any number of customers without delay.

Lecture Voice Recording

lecture_recording

Retrieved from "http://boykin.acis.ufl.edu/wiki/index.php/EEL6507sp09L13"