Function File: [U, R, Q, X] = qnmarkov (lambda, S, C, P)

Function File: [U, R, Q, X] = qnmarkov (lambda, S, C, P, m)

Function File: [U, R, Q, X] = qnmarkov (N, S, C, P)

Function File: [U, R, Q, X] = qnmarkov (N, S, C, P, m)

Compute utilization, response time, average queue length and throughput for open or closed queueing networks with finite capacity and a single class of requests. Blocking type is Repetitive-Service (RS). This function explicitly generates and solve the underlying Markov chain, and thus might require a large amount of memory.

More specifically, networks which can me analyzed by this function have the following properties:

• There exists only a single class of customers.
• The network has K service centers. Center k \in {1, …, K} has m_k > 0 servers, and has a total (finite) capacity of C_k \geq m_k which includes both buffer space and servers. The buffer space at service center k is therefore C_k - m_k.
• The network can be open, with external arrival rate to center k equal to \lambda_k, or closed with fixed population size N. For closed networks, the population size N must be strictly less than the network capacity: N < \sum_{k=1}^K C_k.
• Average service times are load-independent.
• P_{i, j} is the probability that requests completing execution at center i are transferred to center j, i \neq j. For open networks, a request may leave the system from any node i with probability 1-\sum_{j=1}^K P_{i, j}.
• Blocking type is Repetitive-Service (RS). Service center j is saturated if the number of requests is equal to its capacity C_j. Under the RS blocking discipline, a request completing service at center i which is being transferred to a saturated server j is put back at the end of the queue of i and will receive service again. Center i then processes the next request in queue. External arrivals to a saturated servers are dropped.

INPUTS

lambda(k)

N

If the first argument is a vector lambda, it is considered to be the external arrival rate lambda(k) ≥ 0 to service center k of an open network. If the first argument is a scalar, it is considered as the population size N of a closed network; in this case N must be strictly less than the network capacity: N < sum(C).

S(k)

average service time at service center k

C(k)

capacity of service center k. The capacity includes both the buffer and server space m(k). Thus the buffer space is C(k)-m(k).

P(i,j)

transition probability from service center i to service center j.

m(k)

number of servers at service center k. Note that m(k) ≥ C(k) for each k. If m is omitted, all service centers are assumed to have a single server (m(k) = 1 for all k).

OUTPUTS

U(k)

center k utilization.

R(k)

response time on service center k.

Q(k)

average number of customers in the service center k, including the request in service.

X(k)

throughput of service center k.

NOTES

The space complexity of this implementation is O(\prod_{k=1}^K (C_k + 1)^2). The time complexity is dominated by the time needed to solve a linear system with \prod_{k=1}^K (C_k + 1) unknowns.

Package: queueing