M/G/1 queuing system
G means general distribution / more general situation. In this case, service time of the server has a general distribution with mean $X=E[x ]=1/\mu$ and standard deviation $\sigma_x$, where $mu$ is the mean service rate (services per second, etc.)
Mean waiting time for a service request can be described by P-K formula:
$$W=\frac{\lambda E[x^2]}{2(1-\rho)} $$
Using Little's Law, we can obtain the mean number of service requests in the buffer:
$$N_Q=\lambda W=\frac{\lambda^2 E[x^2]}{2(1-\rho)} $$
Therefore, mean time a service request spends in this system is:
$$T=W+X=\frac{\lambda E[x^2]}{2(1-\rho)}+\frac 1 \mu $$
So, mean number of service requests in this system is:
$$N=\lambda T=\frac{\lambda^2 E[x^2]}{2(1-\rho)}+\frac \lambda \mu $$
In this case, $P_b=0$ as all the incoming requests will be stored in the buffer.
Proof of P-K formula:
Assume that:
- $w_i$ = waiting time in the queue for i-th service request
- $R_i$ = remaining service time seen by the i-th service request (remaining service time for the request that is currently being served)
- $N_i$ = number of requests in the queue found by i-th service request
- $x_i$ = service time of i-th service request
We can derive that:
$$w_i = R_i + \sum_{j=i-N_i}^{i-1} x_j $$
So,
$$E[w_i]=E[R_i]+E\left[\sum_{j=i-N_i}^{i-1} x_j\right] $$
The second term in the right hand is the random sum of independent statistical variables. So,
$$E\left[\sum_{j=i-N_i}^{i-1} x_j\right]=E[N_i]E[x ]=\frac 1 \mu E[N_i] $$
where $E[x ]$ indicates the mean service time of all requests and equals to $X=1/\mu$. Take $i\to\infty$, we get:
$$W = R+\frac 1 \mu N_Q $$
where $R$ is the average residual time (remaining service time for each service request). From Little's Law, we have $N_Q=W\lambda$. Then we get:
$$W = R+\frac \lambda \mu W \Rightarrow W = \frac 1 {1-\rho}R $$
Next, let's consider $R$.
Special cases: M/D/1 and M/M/1
For M/D/1 system, service time is a constant, which means that the standard deviation of service time is 0. As $\sigma_x = E[x^2]-E[x ]^2$, we can have $E[x^2]=\sigma_x + E[x ]^2=0+(1/\mu)^2=1/\mu^2$. Therefore, the mean waiting time in M/D/1 system is expressed as:
$$W = \frac{\lambda}{2\mu^2(1-\rho)}=\frac {\rho}{2\mu(1-\rho)} $$
Similarly, for M/M/1 system, as the service time satisfies exponential distribution, the standard deviation is $1/\mu^2$. Thus, $E[x^2]=2/\mu^2$, we can get:
$$W = \frac{2\lambda}{2\mu^2(1-\rho)}=\frac{\rho}{\mu(1-\rho)} $$
which is the same result as we got before. From comparison, we can derive that $W_{\mathrm{M/D/1}} < W_{\mathrm{M/M/1}}$. For the same $\lambda$ and $\mu$, the $W, T, N_Q$ and $N$ for an M/D/1 system are the lower bounds for an M/G/1 queuing system.
Priority queuing system
Two categories of priority queuing system:
- Preemptive priority queuing system: interruptive, a service may be interrupted when a higher-priority service request arrives, the server will turn to serving this higher-priority request
- Non-preemptive priority queuing system: the service will not be interrupted when a higher-priority service request arrives
M/G/1 non-preemptive priority queuing
Let's assume:
- $\lambda_k$ = Mean arrival rate of customers of priority class k
- $X_k=E[x ]=1/\mu_k$ = Mean service time of customers of priority class k
- $N_{Q,k}$= Mean number of customers in the queue for priority class k
- $W_k$ = Mean waiting time in queue for priority class k
- $\rho_k=\lambda_k/\mu_k$ = Server utilization factor for priority class k
- $R$ = Mean residual service time for all customers in the system
For the highest priority class, using P-K formula, we have:
$$W_1 = \frac R {1-\rho_1} $$
For the second priority class, the waiting time should include additional time for waiting the requests of highest priority to be served. So we get:
$$\begin{align*} W_2 &= R+\frac 1 {\mu_1}N_{Q,1} + \frac 1 {\mu_2} N_{Q,2} + \frac 1 {\mu_1}\lambda_1 W_2\\ &=R + \rho_1 W_1 + \rho_2 W_2 + \rho_1 W_2\\ \end{align*} $$
Therefore,
$$W_2 = \frac{R+\rho_1 W_1}{1-\rho_1-\rho_2} $$
M/G/1 preemptive priority queuing
The key point is to calculate the mean time $T_k$ that a request of priority class $k$ will spend in the system. There are three components:
- mean service time of service request: $X_k = E[x ] = 1/\mu_k$
- the mean time required to service all the requests that are already in the system when a request of priority class $k$ arrives. This part of time is equal to the mean waiting time in M/G/1 queuing system (without priorities), where requests of priority $k+1$ to $n$ are all neglected: (and in this case, $\rho$ is replaced by $\sum_{i=1}^k \rho_i$)
$$\frac{R_k}{1-\rho_1-\rho_2-\cdots-\rho_k} $$
where $R_k$ is the mean residual time of requests of priority class 1 to $k$ and it is equal to:
$$R_k = \frac 1 2\sum_{j=1}^k \lambda_j E[x_j^2] $$
- The mean time required to service customers of priority classes 1 to $k-1$ who arrive while the customer of priority class $k$ is in the system
$$\sum_{j=1}^{k-1} \frac 1 {\mu_j} \lambda_j T_k = \left(\sum_{j=1}^{k-1} \rho_j\right) T_k $$
Combining the above three parts, we get:
$$T_k = \frac{R_k}{1-\sum_{j=1}^k \rho_j} + \frac 1 {\mu_k} + \sum_{j=1}^{k-1} \rho_j T_k $$ $$\Rightarrow T_k = \frac{(1-\rho_1+\rho_2+\cdots+\rho_k)+\mu_k R_k}{\mu_k(1-\rho_1-\rho_2-\cdots-\rho_{k-1})(1-\rho_1-\rho_2-\cdots-\rho_k)} $$
M/G/1 conservation law
“You don’t get something for nothing.” When some classes of customers are privileged and have shorter waiting times, it is at the expense of other customers who pay for this by having longer waiting times.
Consider an n-class non-preemptive priority queuing system. Assume the system to be work-conserving, which means that the system remains busy as long as there are customers present and the customers do not leave before being served. The weighted sum of mean waiting time for each class is a constant:
$$\sum_{k=1}^N \rho_k W_k = \mathrm{Constant} = \frac {\rho R}{1-\rho} $$
M/G/1 queuing system with service vacation
After serving all the customers in the waiting queue, the system may take a rest or so called vacation. Rules for service vacations are:
- If the system remains empty upon a return, it may turn to another new vacation
- Customers/request services can only be served after the server returns from a vacation
- From a given queue's point of view, the server goes for a vacation after completing serving all the customers in the queue
Differ from general M/G/1 queuing system, the residual service time $R(\tau)$ for this situation should contain both residual service time for serving requests and residual vacation time. Thus, the time average of $R(\tau)$ is:
$$\frac 1 t\int_0^t R(\tau) = \frac 1 t \sum_{i=1}^{M(t)}\frac 1 2 x_i^2 + \frac 1 t \sum_{i=1}^{L(t)}\frac 1 2 v_i^2 $$ $$\Rightarrow R(\tau) = \frac{\lambda E[x^2]}{2} + \frac{(1-\rho)E[v^2]}{2V} $$
where:
- $L(t)$: average number of vacations completed in time interval $[0, t]$
- $\rho$: fraction of time that the service is busy serving customers
- $1-\rho$: fraction of time that the service spent on vacations
- $t(1-\rho)$: total time that the service spent on vacations
- $V$: average duration of vacations
- $\frac{t(1-\rho)}{V}$: average duration of one vacation
