Single Station Queueing Systems
*******************************

Single Station Queueing Systems contain a single station, and can usually be analyzed easily. The queueing package contains functions for handling the following types of queues:

The M/M/1 System
================

The M/M/1 system contains a single server connected to an unbounded FCFS queue. Requests arrive according to a Poisson process with rate \lambda; the service time is exponentially distributed with average service rate \mu. The system is stable if \lambda < \mu.

 -- Function File: [U, R, Q, X, P0] = qsmm1 (LAMBDA, MU)
 -- Function File: PK = qsmm1 (LAMBDA, MU, K)

     Compute utilization, response time, average number of requests and throughput for a M/M/1 queue.

     INPUTS

     LAMBDA
          Arrival rate (LAMBDA ≥ 0).

     MU
          Service rate (MU > LAMBDA).

     K
          Number of requests in the system (K ≥ 0).

     OUTPUTS

     U
          Server utilization

     R
          Server response time

     Q
          Average number of requests in the system

     X
          Server throughput. If the system is ergodic (MU > LAMBDA), we always have X = LAMBDA

     P0
          Steady-state probability that there are no requests in the system.

     PK
          Steady-state probability that there are K requests in the system. (including the one being served).

     If this function is called with less than three input parameters, LAMBDA and MU can be vectors of the same size. In this case, the results will be vectors as well.

     REFERENCES

       * G. Bolch, S. Greiner, H. de Meer and K. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998, Section 6.3

     qsmmm, qsmminf, qsmmmk

The M/M/m System
================

The M/M/m system is similar to the M/M/1 system, except that there are m \geq 1 identical servers connected to a shared FCFS queue. Thus, at most m requests can be served at the same time. The M/M/m system can be seen as a single server with load-dependent service rate \mu(n), which is a function of the number n of requests in the system:

     mu(n) = min(m,n)*mu

where \mu is the service rate of each individual server.

 -- Function File: [U, R, Q, X, P0, PM] = qsmmm (LAMBDA, MU)
 -- Function File: [U, R, Q, X, P0, PM] = qsmmm (LAMBDA, MU, M)
 -- Function File: PK = qsmmm (LAMBDA, MU, M, K)

     Compute utilization, response time, average number of requests in service and throughput for a M/M/m queue, a queueing system with m identical servers connected to a single FCFS queue.

     INPUTS

     LAMBDA
          Arrival rate (LAMBDA>0).

     MU
          Service rate (MU>LAMBDA).

     M
          Number of servers (M ≥ 1). Default is M=1.

     K
          Number of requests in the system (K ≥ 0).

     OUTPUTS

     U
          Service center utilization, U = \lambda / (m \mu).

     R
          Service center mean response time

     Q
          Average number of requests in the system

     X
          Service center throughput. If the system is ergodic, we will always have X = LAMBDA

     P0
          Steady-state probability that there are 0 requests in the system

     PM
          Steady-state probability that an arriving request has to wait in the queue

     PK
          Steady-state probability that there are K requests in the system (including the one being served).

     If this function is called with less than four parameters, LAMBDA, MU and M can be vectors of the same size. In this case, the results will be vectors as well.

     REFERENCES

       * G. Bolch, S. Greiner, H. de Meer and K. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998, Section 6.5

     erlangc,qsmm1,qsmminf,qsmmmk

The Erlang-B Formula
====================

 -- Function File: B = erlangb (A, M)

     Compute the steady-state blocking probability in the Erlang loss model.

     The Erlang-B formula E_B(A, m) gives the probability that an open system with m identical servers, arrival rate \lambda, individual service rate \mu and offered load A = \lambda / \mu has all servers busy. This corresponds to the rejection probability of an M/M/m/0 system with m servers and no queue.

     INPUTS

     A
          Offered load, defined as A = \lambda / \mu where \lambda is the mean arrival rate and \mu the mean service rate of each individual server (real, A > 0).

     M
          Number of identical servers (integer, m ≥ 1). Default m = 1

     OUTPUTS

     B
          The value E_B(A, m)

     A or M can be vectors, and in this case, the results will be vectors as well.

     REFERENCES

       * G. Zeng, Two common properties of the Erlang-B function, Erlang-C function, and Engset blocking function, Mathematical and Computer Modelling, Volume 37, Issues 12-13, June 2003, Pages 1287-1296

     erlangc,engset,qsmmm

The Erlang-C Formula
====================

 -- Function File: C = erlangc (A, M)

     Compute the steady-state probability of delay in the Erlang delay model.

     The Erlang-C formula E_C(A, m) gives the probability that an open queueing system with m identical servers, infinite wating space, arrival rate \lambda, individual service rate \mu and offered load A = \lambda / \mu has all the servers busy. This is the waiting probability in an M/M/m/\infty system with m servers and an infinite queue.

     INPUTS

     A
          Offered load. A = \lambda / \mu where \lambda is the mean arrival rate and \mu the mean service rate of each individual server (real, 0 < A < m).

     M
          Number of identical servers (integer, m ≥ 1). Default m = 1

     OUTPUTS

     B
          The value E_C(A, m)

     A or M can be vectors, and in this case, the results will be vectors as well.

     REFERENCES

       * G. Zeng, Two common properties of the Erlang-B function, Erlang-C function, and Engset blocking function, Mathematical and Computer Modelling, Volume 37, Issues 12-13, June 2003, Pages 1287-1296

     erlangb,engset,qsmmm

The Engset Formula
==================

 -- Function File: B = engset (A, M, N)

     Evaluate the Engset loss formula.

     The Engset formula computes the blocking probability P_b(A,m,n) for a system with a finite population of n users, m identical servers, no queue, individual service rate \mu, individual arrival rate \lambda (i.e., the time until a user tries to request service is exponentially distributed with mean 1/\lambda), and offered load A=\lambda/\mu.

     INPUTS

     A
          Offered load, defined as A = \lambda / \mu where \lambda is the mean arrival rate and \mu the mean service rate of each individual server (real, A > 0).

     M
          Number of identical servers (integer, m ≥ 1). Default m = 1

     N
          Number of requests (integer, n ≥ 1). Default n = 1

     OUTPUTS

     B
          The value P_b(A, m, n)

     A, M or n can be vectors, and in this case, the results will be vectors as well.

     REFERENCES

       * G. Zeng, Two common properties of the Erlang-B function, Erlang-C function, and Engset blocking function, Mathematical and Computer Modelling, Volume 37, Issues 12-13, June 2003, Pages 1287-1296

     erlangb, erlangc

The M/M/inf System
==================

The M/M/\infty system is a special case of M/M/m system with infinitely many identical servers (i.e., m = \infty). Each new request is always assigned to a new server, so that queueing never occurs. The M/M/\infty system is always stable.

 -- Function File: [U, R, Q, X, P0] = qsmminf (LAMBDA, MU)
 -- Function File: PK = qsmminf (LAMBDA, MU, K)

     Compute utilization, response time, average number of requests and throughput for an infinite-server queue.

     The M/M/\infty system has an infinite number of identical servers. Such a system is always stable (i.e., the mean queue length is always finite) for any arrival and service rates.

     INPUTS

     LAMBDA
          Arrival rate (LAMBDA>0).

     MU
          Service rate (MU>0).

     K
          Number of requests in the system (K ≥ 0).

     OUTPUTS

     U
          Traffic intensity (defined as \lambda/\mu). Note that this is different from the utilization, which in the case of M/M/\infty centers is always zero.

     R
          Service center response time.

     Q
          Average number of requests in the system (which is equal to the traffic intensity \lambda/\mu).

     X
          Throughput (which is always equal to X = LAMBDA).

     P0
          Steady-state probability that there are no requests in the system

     PK
          Steady-state probability that there are K requests in the system (including the one being served).

     If this function is called with less than three arguments, LAMBDA and MU can be vectors of the same size. In this case, the results will be vectors as well.

     REFERENCES

       * G. Bolch, S. Greiner, H. de Meer and K. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998, Section 6.4

     qsmm1,qsmmm,qsmmmk

The M/M/1/K System
==================

In a M/M/1/K finite capacity system there is a single server, and there can be at most K jobs at any time (including the job currently in service), K > 1. If a new request tries to join the system when there are already K other requests, the request is lost. The queue has K-1 slots. The M/M/1/K system is always stable, regardless of the arrival and service rates.

 -- Function File: [U, R, Q, X, P0, PK] = qsmm1k (LAMBDA, MU, K)
 -- Function File: PN = qsmm1k (LAMBDA, MU, K, N)

     Compute utilization, response time, average number of requests and throughput for a M/M/1/K finite capacity system.

     In a M/M/1/K queue there is a single server and a queue with finite capacity: the maximum number of requests in the system (including the request being served) is K, and the maximum queue length is therefore K-1.

     INPUTS

     LAMBDA
          Arrival rate (LAMBDA>0).

     MU
          Service rate (MU>0).

     K
          Maximum number of requests allowed in the system (K ≥ 1).

     N
          Number of requests in the (0 ≤ N ≤ K).

     OUTPUTS

     U
          Service center utilization, which is defined as U = 1-P0

     R
          Service center response time

     Q
          Average number of requests in the system

     X
          Service center throughput

     P0
          Steady-state probability that there are no requests in the system

     PK
          Steady-state probability that there are K requests in the system (i.e., that the system is full)

     PN
          Steady-state probability that there are n requests in the system (including the one being served).

     If this function is called with less than four arguments, LAMBDA, MU and K can be vectors of the same size. In this case, the results will be vectors as well.

     qsmm1,qsmminf,qsmmm

The M/M/m/K System
==================

The M/M/m/K finite capacity system is similar to the M/M/1/k system except that the number of servers is m, where 1 \leq m \leq K. The queue has K-m slots. The M/M/m/K system is always stable.

 -- Function File: [U, R, Q, X, P0, PK] = qsmmmk (LAMBDA, MU, M, K)
 -- Function File: PN = qsmmmk (LAMBDA, MU, M, K, N)

     Compute utilization, response time, average number of requests and throughput for a M/M/m/K finite capacity system. In a M/M/m/K system there are m \geq 1 identical service centers sharing a fixed-capacity queue. At any time, at most K ≥ m requests can be in the system, including those being served. The maximum queue length is K-m. This function generates and solves the underlying CTMC.

     INPUTS

     LAMBDA
          Arrival rate (LAMBDA>0)

     MU
          Service rate (MU>0)

     M
          Number of servers (M ≥ 1)

     K
          Maximum number of requests allowed in the system, including those being served (K ≥ M)

     N
          Number of requests in the (0 ≤ N ≤ K).

     OUTPUTS

     U
          Service center utilization

     R
          Service center response time

     Q
          Average number of requests in the system

     X
          Service center throughput

     P0
          Steady-state probability that there are no requests in the system.

     PK
          Steady-state probability that there are K requests in the system (i.e., probability that the system is full).

     PN
          Steady-state probability that there are N requests in the system (including those being served).

     If this function is called with less than five arguments, LAMBDA, MU, M and K can be either scalars, or vectors of the  same size. In this case, the results will be vectors as well.

     REFERENCES

       * G. Bolch, S. Greiner, H. de Meer and K. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998, Section 6.6

     qsmm1,qsmminf,qsmmm

The Asymmetric M/M/m System
===========================

The Asymmetric M/M/m system contains m servers connected to a single queue. Differently from the M/M/m system, in the asymmetric M/M/m each server may have a different service time.

 -- Function File: [U, R, Q, X] = qsammm (LAMBDA, MU)

     Compute approximate utilization, response time, average number of requests in service and throughput for an asymmetric M/M/m queue. In this type of system there are m different servers connected to a single queue. Each server has its own (possibly different) service rate. If there is more than one server available, requests are routed to a randomly-chosen one.

     INPUTS

     LAMBDA
          Arrival rate (LAMBDA>0)

     MU
          MU(i) is the service rate of server i, 1 ≤ i ≤ m. The system must be ergodic (LAMBDA < sum(MU)).

     OUTPUTS

     U
          Approximate service center utilization, U = \lambda / ( \sum_i=1^m \mu_i ).

     R
          Approximate service center response time

     Q
          Approximate number of requests in the system

     X
          Approximate system throughput. If the system is ergodic, X = LAMBDA

     REFERENCES

       * G. Bolch, S. Greiner, H. de Meer and K. Trivedi, Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications, Wiley, 1998

     qsmmm

The M/G/1 System
================

 -- Function File: [U, R, Q, X, P0] = qsmg1 (LAMBDA, XAVG, X2ND)

     Compute utilization, response time, average number of requests and throughput for a M/G/1 system. The service time distribution is described by its mean XAVG, and by its second moment X2ND. The computations are based on results from L. Kleinrock, Queuing Systems, Wiley, Vol 2, and Pollaczek-Khinchine formula.

     INPUTS

     LAMBDA
          Arrival rate

     XAVG
          Average service time

     X2ND
          Second moment of service time distribution

     OUTPUTS

     U
          Service center utilization

     R
          Service center response time

     Q
          Average number of requests in the system

     X
          Service center throughput

     P0
          Probability that there is not any request at system

     LAMBDA, XAVG, T2ND can be vectors of the same size. In this case, the results will be vectors as well.

     qsmh1

The M/H_m/1 System
==================

 -- Function File: [U, R, Q, X, P0] = qsmh1 (LAMBDA, MU, ALPHA)

     Compute utilization, response time, average number of requests and throughput for a M/H_m/1 system. In this system, the customer service times have hyper-exponential distribution:

                 ___ m
                 \
          B(x) =  >  alpha(j) * (1-exp(-mu(j)*x))   x>0
                 /__
                     j=1

     where \alpha_j is the probability that the request is served at phase j, in which case the average service rate is \mu_j. After completing service at phase j, for some j, the request exits the system.

     INPUTS

     LAMBDA
          Arrival rate

     MU
          MU(j) is the phase j service rate. The total number of phases m is length(MU).

     ALPHA
          ALPHA(j) is the probability that a request is served at phase j. ALPHA must have the same size as MU.

     OUTPUTS

     U
          Service center utilization

     R
          Service center response time

     Q
          Average number of requests in the system

     X
          Service center throughput