\documentclass{article} \usepackage{amssymb} \usepackage{amsmath} \newcommand{\Comment}[1]{} \newcommand{\ruleOne}[2]{\arraycolsep=14pt\renewcommand{\arraystretch}{1.75}% \begin{array}[c]{c}#1\\ \hline\multicolumn{1}{c}{#2} \end{array}} \newcommand{\statespace}[1]{\mathcal{#1}} \newcommand{\myset}[1]{\{ #1\}} \begin{document} \begin{center} {\bf COURSE 336 \\ PERFORMANCE ANALYSIS\\ P.G. HARRISON \\ Solutions 5 \\ March 2006 \\ } \end{center} \begin{enumerate} \item In an M/M/1 queue, assume that customers arrive as a Poisson process with parameter one per $12$ minutes, and that the service time is exponential at rate one service per $8$ minutes. Calculate the following quantities: \begin{enumerate} \item $L$ the average number of customers in the system; \item $W$ the average amount of time that a customer spends in the system; \item $W_{Q}$ the average amount of time a customer spends in the queue, waiting to start service. \end{enumerate} If there are no customers waiting to be served on arrival, what is the value of the queueing time random variable? \\ {\bf Solution} Since $\lambda = \frac{1}{12}$ and $ \mu = \frac{1}{8}$ minute$^{-1}$, then \begin{enumerate} \item $L = \frac{\lambda}{\mu -\lambda}$, then $L = \ruleOne{\frac{1}{12}}{ \frac{1}{24}}= 2 $; thus the average number of customers in the queue is $2$. \item $ W = \frac{1}{\mu - \lambda}$, so $W = 24$; thus the average time spent in the system is $24$ minutes. \item $W_{Q} = W - \frac{1}{\mu}$, so $W_{Q} = 16$; thus the average time spent in the queue waiting to start service is $16$ minutes. \end{enumerate} Intuitively, if the queue is empty, the only time waiting is the service time. Formally, observing that $W = W_{Q}+ \frac{1}{\mu}$ and $W_{Q}= 0$, we derive $ W= \frac{1}{\mu}=8$ minutes. \\ \\ \item Consider an M/M/1 queue where the jobs' willingness to join the queue is influenced by the queue size. More precisely, a job which finds $i$ other jobs in the system joins the queue with probability $1/(i+1)$ and departs immediately otherwise ($i=0,1,\ldots$). Draw the state diagram for this system with arrival rate $\lambda$ and mean service time $1/\mu$. Write down and solve the balance equations for the equilibrium probabilities $\pi_i$ and show that a steady-state distribution always exists. Find the utilisation of the server, the throughput , the average number of jobs in the system and the average reponse time for a job that decides to join. Note that the form of equilibrium probabilities is the same as that of the M/M/$\infty$ queue. \\ {\bf Solution} Diagram is the same as for the M/M/1 queue drawn in lectures, with rates from states $i+1$ to $i$ all having rate $\mu$ and the rate from $i$ to $i+1$ having rate $\lambda \times \frac{1}{i+1}$ since a fraction $\frac{i}{i+1}$ of arrivals do not join the queue at all ($i \geq 0$). Balance equation for contour round states $1,2,\ldots,i$ is therefore: $$p_i \lambda / (i+1) = p_{i+1} \mu$$ so that $$p_{i} = \rho^i/i! p_0$$ where $\rho = \lambda/\mu$. Normalising, $p_0 = e^{-\rho}$, so steady state always exists. Utilisation = $1-p_0 = 1-e^{-\rho}$. Throughput = $(1-e^{-\rho})\mu$ since service rate is constant. Mean queue length $L = \sum_{i=1}^\infty ip_i = p_0\sum_{i=1}^\infty i\rho^i/i! \\= p_0\rho\sum_{i=1}^\infty \rho^{i-1}/(i-1)! = \rho$ By Little's result, mean response time $W = L/(1-e^{-\rho})\mu = \rho/(1-e^{-\rho})\mu = \lambda/(1-e^{-\rho})\mu^2$ \\ \\ \item Consider an M/M/$\infty$ queue with discouraged arrivals but with the following birth-and-death coefficients: $$ \lambda(i) = \frac{\lambda}{(i+1)^b}~~~\mbox{and }~~~\mu(i)=i^c\mu $$ where $c$ is the ``pressure-coefficient'' -- a constant that indicates the degree to which the service rate of the system is affected by the system state -- and $b$ is the ``discouraging coefficien''. Obtain the equilibrium probabilities $\pi_i$ for this birth-and-death process. What is the equilibrium distribution when $b+c = 1$? \\ {\bf Solution} As in the previous question, $$p_i \lambda / (i+1)^b = p_{i+1} \mu (i+1)^c$$ i.e. $$p_{i+1} = p_i \rho / (i+1)^{b+c}$$ Thus $$p_{i} = \rho^i/(i!)^{b+c} p_0$$ $$p_0 = \left[ \sum_{k=0}^\infty \rho^k/(k!)^{b+c} \right]^{-1}$$ Same as previous question / IS queue when $b+c =1 $. \\ \\ \item Let $D$ be a random interval between two consecutive departures from an M/M/$1$ queue at equilibrium. If, just after the first departure, the queue was not empty, then $D$ coincides with the service time of the next job. If the queue was empty, then $D$ consists of the period up to the next arrival, as well as the service time of the next job. Assuming that the probability of a non-empty system just after departure is the same as the utilisation, show that $D$ is exponentially distributed with parameter $\lambda$. \\ {\bf Solution} Recall that $\rho = \frac{\lambda}{\mu}$ is the utilisation of the server. Write $X$ and $Y$ for the random variables corresponding to the interarrival time and the service time respectively. Let $D$ have probability distribution function $F$. Then: \begin{eqnarray*} F(t) &=& P(D \leq t) \;=\; \rho P(Y \leq t) + (1-\rho)P(X+Y \leq t) \\ &=& \rho(1-e^{-\mu t}) + (1-\rho) \int_0^t P(X \leq t-u) \mu e^{-\mu u} du \\ &&(\mbox{since $X,Y$ are independent}) \\ &=& \rho(1-e^{-\mu t}) + (1-\rho) \int_0^t \mu e^{-\mu u} - \mu e^{-\lambda t}e^{-(\mu-\lambda) u} du \\ &=& \rho(1-e^{-\mu t}) + (1-\rho) \left[1 - e^{-\mu t} - e^{-\lambda t} (\mu / (\mu-\lambda)) (1-e^{-(\mu-\lambda) t})\right] \\ &=& 1-e^{-\mu t} - e^{-\lambda t} (1-e^{-(\mu-\lambda) t}) \\ &=& 1-e^{-\lambda t} \end{eqnarray*} as required. \\\\ %%{\it Some notes on the convolution} %%In the previous solution we have used the convolution $F_{X + Y}$, which is the distribution %%function of the sum of two independent random variables $X_1$ and $X_2$, with %%distribution function $F_{X_1}$ and $F_{X_2}$ respectively. %%Let the probability density function (pdf) of $F_{X_1}$ be $f(x)$ and $g(x)$ \item Let $X_1$ and $X_2$ be two independent exponential random variables with parameters $\lambda_1$ and $\lambda_2$. Prove that the random variable $Z= \min(X_1,X_2)$ is an exponential random variable with parameter $\lambda_1 + \lambda_2$. \\ {\bf Solution} %%Since $X_1$ and $X_2$ are two independent random variables with rate $\lambda_1$ and $\lambda_2$, we have: %%\[\begin{array}{rcl} %%P ( X_1 \leq t)& =& 1- e^{-\lambda_1 t}\\ %%P ( X_2 \leq t)& =& 1- e^{-\lambda_2 t}\\ %%\end{array} \] For the random variable $Z$ we are interested in the time until either $X_1$ or $X_2$ occurs, so: \[\begin{array}{rcl} P(Z \leq t) & = & 1 -P(Z > t) \\ &=& 1 -P( \min(X_1,X_2) > t) \\ & =& 1 - P( X_1 > t, X_2 > t) \\ &=& 1 - P(X_1 > t)P(X_2 > t) \,\,\,\, \mbox{ by independence} \\ & = & 1 - (e^{- \lambda_1 t})(e^{- \lambda_2 t})\\ & =& 1- e^{ - (\lambda_1 + \lambda_2) t}\\ \end{array} \] \end{enumerate} \end{document}