2d:null 2e:["$","title",null,{"children":"Performance Evaluation of Closed Queueing Systems with Exponential Servers | Rob | Labs | Observable"}] 33:T4ba,md` # Performance Evaluation of Closed Queueing Systems with Exponential Servers ## Rob Chohan
### Statistics 601, Research, Spring 1995 ##### Originally written in ${tex`\LaTeX`}, ported to ${html``} and ${tex`\KaTeX`} in 2018 `34:T68b,md` Closed queueing systems are systems where new customers never enter and existing customers never depart. Customers move throughout the system in a cyclic manner. Potential applications for these types of systems are to computer systems with several processors, disk drives and input/output devices. The goal here is to investigate derivation of performance measures for a specific type of system and to implement the algorithms presented. Possible future research topics include simulation of a system more general than discussed here, a survey of queueing software, and performance evaluation through techniques not discussed here. One example of this type of system is four terminals connected to a time shared computer. Each terminal is modeled by a single server that holds at most one customer. A "customer" that circulates in this queueing network represents control of the terminal. The presence of a customer at a terminal server indicates that the person at the terminal is thinking or typing and the presence of a customer at the computer server indicates that the person has hit "return" and is waiting for the prompt (i.e., exit from the computer queue). In this specific model a customer leaving a terminal server must eventually return to the same server. The queueing models studied here are commonly called Gordon and Newell networks. In general our fixed number of customers ${tex`N`} will pass repeatedly through ${tex`M`} stages of service. At the ${tex`i`}th stage of service there are ${tex`r_i`} parallel servers each with a service time for a customer given by a exponentially distributed random variable with mean ${tex`1/\mu_i`}. `35:T447,md` The algorithm can be stated in psuedocode,

   Set N = 0
   init n(i,0) = 0   i = 1,...,M

step 1  t(i,N) = 1/mu(i) + 1/mu(i)*(n(i,N-1))   i = 1,...,M
	Upsilon(N) = N / sum(t(i,N))            sum over i
	n(i,N) = Upsilon(N) * t(i,N)
	let N = N + 1
	goto step 1

This algorithm is implemented into MATLAB in the m-file MEANVALU.M ### Example This example considers a cyclic queueing system of four queues. The service rates in ${tex`msec^{-1}`} are ${tex`\mu_1=2`}, ${tex`\mu_2=3`}, ${tex`\mu_3=6`}, ${tex`\mu_4=4`}. The mean throughput of each queue is equal, ${tex`\theta_1 = \theta_2 = \theta_3 = \theta_4 = 1.0`}. The normalization constants were computed using the MATLAB routines BUZEN.M and HARRISON.M, and performance measures were computed using BUZEN.M and MEANVALU.M, for customer loads from 1 to 10. A summary of the mean queue length is given graphically in figure 1. Since the mean throughputs were identical the plot for mean waiting time is identical to that for mean queue length except for a scaling factor. Results for ${tex`N=4`} are summarized below. `36:T4a4,md` ### Remarks The ideas presented here represent the tractable case of closed Markovian queueing systems. Being the most tractable possibly means that these methods aren't the most efficient, but these methods are important for others to study, learn, and build upon. Efficient algorithms will develop from these. I would guess that these methods are rarely used in practice, but surely studied for their properties. Having this gentle introduction subject was made easier by the underlying assumptions. The next step would be to generalize to multiple class stages, mixed service with load dependent and independent servers, and varying service disciplines which fall into the area of systems called BCMP networks. There are several other methods and algorithms used to solve these systems. RECAL is used for models with large numbers of routing chains. PANACEA is also a technique for large Markovian queueing systems. The problem of calculating the normalization constant is transformed into a problem in integration whose solution takes the form of an asymptotic power series. The isolation method subdivides the global system into subsystems and studies them separately. `37:T5ac,md` ### Appendix #### BUZEN.M

  function y = normal(rate, tput, N)
% buzen.m
% This assumes that rate & tput are input as row vectors
% Computes normalization constants and performance measures
% This routine is the main engine for this paper
`
// M = length(rate);
// x = tput ./ rate;               % x is the notation from Gordon & Newell

// % computation of the normalization constants
// G = zeros(1, N+1);
// G(1) = 1;

// for m = 1:M,
// 	for n = 2:N+1,
// 		G(n) = G(n) + x(m)*G(n-1);
// 	end
// end
// Normalization = G;

// % calculation of the mean Throughput, Upsilon

// Mean_throughput = tput' *( G(N) ./ G(N+1) )


// % Mean queue length
// f = flops;
// for m = 1:M,
// 	tmp = 0;
// 	for n = 1:N,
// 		tmp = tmp + (x(m).^n * G(N+1 -n) / G(N+1) );
// 	end
// 	nbar(m) = tmp;
// end
// f=flops - f;
// Mean_queue_length = nbar'


// % Mean waiting time

// Mean_waiting_time = Mean_queue_length ./ Mean_throughput

// % Utilization

// Utilization = [x * G(N)/G(N+1)]'


// % marginal distributions, Pr(exactly k customers at the ith queue)
// marginal = zeros(M, N+1);
// for m = 1:M,
// 	for k = 0:N;
// 	if k ~= N, 
//  marginal(m, k+1) = x(m).^k *( G(N+1 - k)  - x(m)*G(N+1 -k -1) )/G(N+1);
// 	else,
// 		marginal(m, k+1) = x(m).^k *( G(1))/G(N+1);
// 	   end
// 	end
// end
// Marginal_probabilities = marginal

// % compute the mean queue length more efficiently
// f = flops;
// marginal*[0:N]';
// f=flops - f;

//

38:[] 31:{"id":"a2eb00c66d391d8f","slug":"performance-evaluation-of-closed-queueing-systems-with-ex","title":"Performance Evaluation of Closed Queueing Systems with Exponential Servers","thumbnail":"4e9ea396e5a91050c719e0c7428994cccdf6c2be981c3addb43c96d2480eef74","access_level":"public","create_time":"$D2018-07-28T19:39:25.661Z","update_time":"$D2018-07-28T21:37:52.418Z","view_time":null,"first_public_time":"$D2018-07-28T21:21:42.677Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"4fb28e57b1ee7ad7","login":"roblabs","name":"Rob | Labs","avatar_url":"https://avatars-next.observableusercontent.com/a46c63fe02259f75113a4e65721ca91dcd78e54ad768500cc6c0975a9fe307a2","tier":"starter_2024"},"version":385,"publish_version":385,"role":null,"authored":false,"authors":[{"type":"individual","id":"979e07e6bb09b05a","login":"roblabs","name":"Rob | Labs","avatar_url":"https://avatars-next.observableusercontent.com/a46c63fe02259f75113a4e65721ca91dcd78e54ad768500cc6c0975a9fe307a2","tier":null}],"members":[{"type":"individual","id":"979e07e6bb09b05a","login":"roblabs","name":"Rob | Labs","avatar_url":"https://avatars-next.observableusercontent.com/a46c63fe02259f75113a4e65721ca91dcd78e54ad768500cc6c0975a9fe307a2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"83f926e43e17d2fb","slug":"latex-with-katex","title":"LaTex with KaTex","owner":{"id":"4fb28e57b1ee7ad7","login":"roblabs","name":"Rob | Labs"}},"type":"notebook","body":{"titling":"auto","title":"Performance Evaluation of Closed Queueing Systems with Exponential Servers","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md`\nThe probability that a \ncustomer moves to the ${tex`j`}th stage after completing service at the ${tex`i`}th stage\nis ${tex`p_{ij}, \\; i,j=1,\\ldots,M`}. In this discussion we will consider ${tex`r_i = 1`},\na single class system. Another assumption is that the ${tex`j`}th stage's mean service time is \nindependent of the number of customers present, this is called state or load\nindependent service. The service discipline is first come first served.\n\nThe state of the system can be described by a vector ${tex`\\underline{n} =(n_1, \\ldots, n_M)`} \n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"md`\nwhere ${tex`n_i`} is the number of customers\npresent at the ${tex`i`}th queue. The state space is \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"\ntex.block`S(N,M)=\\left\\{ \\underline{n} : \\sum_{i=1}^{M} n_i =N, \\;n_i \\geq 0 \\; \\forall i \\right\\} `\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"\nmd`\nThe number of distinct state in this system is equal to the number of customers\nthat must be placed among M queues, ${tex`C^{N+M-1}_{M-1}`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"md`\nThe equilibrium distribution of customers in the closed system will be \nimportant in forumlating performance measures. Let ${tex`P(\\underline{n})`} be\nthe equilibrium probability that the system is in state ${tex`\\underline{n}`}.\nThe net flow out of state ${tex`\\underline{n}`} equals the net flow into state\n${tex`\\underline{n}`}, this is called the global balance equation:\n`\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"\ntex.block`\\sum_{i=1}^{M} \\mu_i P(\\underline{n}) = \\sum_{i=1}^{M} \\sum_{j=1}^{M} \\mu_j p_{ji} P(n_1, \\ldots, n_j+1,\\ldots, n_i-1, \\ldots, n_M)`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"\nmd`\nThe left hand side corresponds to customers leaving state ${tex`\\underline{n}`}\nthrough departures while the right hand side corresponds to entering \n${tex`\\underline{n}`} from \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"\ntex.block`(n_1, \\ldots, n_j+1,\\ldots, n_i-1, \\ldots, n_M)`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"\nmd`\nthrough a transfer of customers from queue ${tex`i`} to queue ${tex`j`}. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"md`\nDefine throughput\nas the rate at which customers leave a queue. Let the average\nthroughput through queue ${tex`i`} be ${tex`\\theta_i`}. The set\nof simultaneous equations \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"tex.block` \\theta_i = \\sum_{j=1}^{M} p_{ji} \\theta_j \\;\\; i=1,\\dots,M `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"md`\nare known as the \"traffic equations\". These equations say that the average\nthroughput through queue ${tex`i`} is equal to the flows from all other queues \nincluding ${tex`i`}. \n\nTo solve the global balance equation rewrite the traffic equations as\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"tex.block` \\sum_{j=1}^{M} \\frac{p_{ji} \\theta_j }{\\theta_i} = 1, \\; i=1,\\ldots,M`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"md`Inserting this identity into the global equation yields`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"tex.block` \\sum_{i=1}^{M} \\sum_{j=1}^{M} \\frac{p_{ji} \\theta_j }{\\theta_i} \\mu_i P(\\underline{n}) = \n\\sum_{i=1}^{M} \\sum_{j=1}^{M} \\mu_j p_{ji} P(n_1, \\ldots, n_j+1,\\ldots, n_i-1, \\ldots, n_M) `\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"md`This holds if the local balance equations hold`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"tex.block`\n\\begin{aligned}\n\\frac{\\theta_j}{\\theta_i} \\mu_i P(\\underline{n}) &= \\mu_j P(n_1, \\ldots, n_j+1,\\ldots, n_i-1, \\ldots, n_M) \\\\ \\mu_i P(\\underline{n}) &= \\theta_i P(n_1,\\ldots, n_i-1, \\ldots, n_M) \\\\\nP(\\underline{n}) &= \\left(\\frac{\\theta_i}{\\mu_i}\\right) P(n_1,\\ldots, n_i-1, \\ldots, n_M)\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"md`Continuing this recursion until the ${tex`i`}th term is zero `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"tex.block`P(\\underline{n}) = \\left(\\frac{\\theta_i}{\\mu_i} \\right)^{n_i} P(n_1, \\ldots, 0, \\ldots, n_M) `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":73,"value":"md`Doing this for each queue yields`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"tex.block` P(\\underline{n}) = \\prod_{i=1}^{M}\\left(\\frac{\\theta_i}{\\mu_i} \\right)^{n_i} P(\\underline{0})`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"md`Summing over the state space ${tex`S(N,M)`} and letting ${tex`x_i= \\frac{\\theta_i}{\\mu_i}`} gives`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"tex.block`\n\\begin{aligned}\n\\sum_{\\underline{n}\\in S(N,M)} P(\\underline{n}) &=& \\sum_{\\underline{n}\\in S(N,M)} \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i} P(\\underline{0}) \\\\\n1 &=& \\sum_{\\underline{n}\\in S(N,M)} \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i} P(\\underline{0}) \\\\\nP(\\underline{0}) &=& \\frac{1}{\\sum_{\\underline{n}\\in S(N,M)} \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i}} \n\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"md`\nComputing ${tex`P(\\underline{0})`} becomes computationally large, ${tex`C^{N+M-1}_{M-1}`} \nstates, so the idea of a normalizing constant is introduced.\n\nLet ${tex`G(N) =\\sum_{\\underline{n}\\in S(N,M)} \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i}`},\na normalizing constant so that all the ${tex`P(\\underline{n})`} sum to one. This gives`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"tex.block` P(\\underline{n}) = \\frac{\\prod_{i=1}^{M}\\left( x_i \\right)^{n_i}}{G(N)} `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"md`the joint probability distribution of customers in the closed queueing system.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"md`\nWe will now look at algorithms used to compute performance measures for the system\nbased on the previous results for ${tex`N-1`} customers. One approach is called the\n*convolution algorithm* [Buzen]. It is a recursion method for computing the\nnormalization constants for increasing populations of customers. Its usefullness\nis that a variety of performance measures can be written as functions of \nthe normalization constants.\n\nTo derive the convolution algorithm we need to first define the auxiliary\nfunction\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"tex.block` g(n,m) =\\sum_{\\underline{n}\\in S(N,M)} \\prod_{i=1}^{m}\\left( x_i \\right)^{n_i} `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"md`\nThen for ${tex`m>1`} and ${tex`n>0`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":"tex.block`\n\\begin{aligned}\n\n\ng(n,m) &= \\sum_{\\stackrel{\\underline{n}\\in S(N,M)}{n_m=0} } \\prod_{i=1}^{m-1}\\left( x_i \\right)^{n_i} + \\sum_{\\stackrel{\\underline{n}\\in S(N,M)}{n_m>0} } \\prod_{i=1}^{m}\\left( x_i \\right)^{n_i} \\\\\n&= g(n,m-1)\\cdot1 + x_m\\cdot g(n-1,m)\n\\end{aligned}\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":108,"value":"md`\nWith the initial conditions `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":112,"value":"tex.block`g(n,1) = x_{1}^{n}, \\;n=0,\\ldots, N`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"tex.block`g(0,m)=1, \\; m=1,\\ldots,M`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"md`\nThe first term on the right hand side is the normalization constant\nwithout the ${tex`m`}th queue and the second term is the normalization constant\nfor ${tex`m`} queues with ${tex`n-1`} customers. Note that ${tex`G(N)`} is equal to\n${tex`g(N,M)`} and ${tex`g(n,M)=G(n)`}, for ${tex`n=0,\\ldots,N`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"md`\nThis algorithm can be implemented with the following psuedocode\n\n

\ninitialize G(0) = 1\n\t   G(n) = 0, n = 1,...,N\n\t   x(m)      m = 1,...,M\nfor m = 1 to M\n  for n = 1 to N\n    G(n) = G(n) + x(m)*G(n-1)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":124,"value":"md`\nThis algorithm requires one addition and one multiplication at each\nevaluation of ${tex`G(n)`}.  This is done ${tex`NM`} times so ${tex`NM`} additions and\n${tex`NM`} multiplications are required.\n\nHarrison presented a method for deriving these normalization constants in a\nclosed system with load independent service.  The method stated here is an\nexplicit, closed form expression for ${tex`G(N)`} for the case when all \n${tex`x_i`}'s are distinct.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":288,"value":"tex.block`\n\\begin{aligned}\n\tG(N) &= \\sum_{\\underline{n}\\in S(N,M)} \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i} \\\\\n &= \\sum_{j=1}^{M} \\frac{ x_{j}^{N+M-1}}{\\prod_{i\\neq j}(x_j- x_i)} \n\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"md`\nThis is implemented into MATLAB in the m-file HARRISON.M.\n\n### Performance Measures from the Normalization Constants\n\n#### Marginal distribution of queue length\n\nOf interest is the probability that there are exactly ${tex`k`} customers present\nat the ${tex`i`}th queue.  This probability can be expressed as\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"tex.block`P(n_i = k) = \\sum_{\\stackrel{\\underline{n}\\in S(N,M)}{n_i=k} }P(\\underline{n}) `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"md`\nIt is easier to first calculate\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":259,"value":"tex.block`\n\\begin{aligned}\nP(n_i \\geq k) &= \\sum_{\\stackrel{\\underline{n}\\in S(N,M)}{n_i\\geq k} }P(\\underline{n}) \\\\\n &= \\sum_{\\stackrel{\\underline{n}\\in S(N,M)}{n_i\\geq k} } \\frac{ \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i} }{G(N)} \\\\\n &= x_{i}^{k} \\sum_{\\underline{n}\\in S(N-k,M)} \\frac{ \\prod_{i=1}^{M}\\left( x_i \\right)^{n_i} }{G(N)} \\\\\n &= x_{i}^{k} \\frac{G(N-k)}{G(N)} \n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":155,"value":"md`\nIt then follows from\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":266,"value":"tex.block`\n\\begin{aligned}\nP(n_i=k) &= P(n_i \\geq k) - P(n_i\\geq k+1) \\\\\n&= \\left\\{ \\begin{array}{ll}\n\t       x_{i}^{k} \\frac{G(N-k) - G(N-k-1)}{G(N)} & k=0,\\ldots,N \\\\\n\t\t0 & else\n\t\t\t\\end{array}\n\t      \\right. \n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":161,"value":"md`\n#### Mean queue length\n\nThe expected number of customers at the ${tex`i`}th queue is given by\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":270,"value":"tex.block`\n\\begin{aligned}\n\\bar{n}_i(N) &= \\sum_{k=1}^{N} kP(n_i=k) \\\\\n &= \\sum_{k=1}^{N} kx_{i}^{k} \\frac{G(N-k) - G(N-k-1)}{G(N)} \\\\\n &= \\sum_{k=1}^{N} kx_{i}^{k} \\frac{G(N-k) }{G(N)} \n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"md`\nUtilization and Mean Throughput\n\nThe utilization and mean throughput of the ${tex`i`}th queue are related by \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":171,"value":"tex.block`\n\\begin{aligned}\nU_i(N) &= 1 - P(n_i=0) = P(n_i \\geq 1) \\\\\n &= x_i\\frac{G(N-1) }{G(N)} \\\\\n\\bar{\\Upsilon}_i(N) &= \\mu_i U_i(N) \\\\\n     &= \\theta_i \\frac{G(N-1) }{G(N)}\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":178,"value":"md`\n#### Mean Waiting time\n\nOnce the throughput and mean queue length of a queue are computed, the mean\nwaiting time at the queue follows directly from Little's Law.  This formula\nstates that the average number of customers in a system is equal to the \naverage arrival rate of customers times the average time spent in that \nsystem.  Rearranging gives,\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"tex.block` \\bar{\\tau}_i(N) = \\frac{\\bar{n}_i(N) }{ \\bar{\\Upsilon}_i(N)} `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"md`\nThese four measures, mean queue length, utilization, throughput, and \nmean wait time are implemented into MATLAB in the m-file BUZEN.M.\n\n### Computation of Performance Measures without Computing Normalization Constants\n\n*Mean-value Analysis* uses basic queueing relationships to determine the\nperformance measures [Reiser].  The derivation is fairly simple.\n\nThe mean waiting time, ${tex`\\bar{\\tau}_i`}, has two terms, the service time of \nthat customer and the service time for all customers before it.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":186,"value":"tex.block` \\bar{\\tau}_i = \\frac{1}{\\mu_i} + \\frac{1}{\\mu_i}(avg \\; \\# \\; customers \\; at \\; arrival) `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":188,"value":"md`\nAccording to the *Arrival Theorem* for closed Markov systems the number\nof customers present upon arrival has the same distribution as the equilibrium\ndistribution for the system with one customer less [Ross].\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":189,"value":"tex.block`  \\bar{\\tau}_i = \\frac{1}{\\mu_i} + \\frac{1}{\\mu_i}( \\bar{n}_i(N-1)) `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"md`\nThe mean-value analysis algorithm also makes use of Little's Law first\napplied to the entire system and then to the ${tex`i`}th queue.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"tex.block` \n\\begin{aligned}\n\\bar{\\Upsilon}(N) \\sum_{i=1}^{M} \\bar{\\tau}_i(N) &= N \\\\\n\\bar{\\Upsilon}(N) \\bar{\\tau}_i(N) &= \\bar{n}_i(N)\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"tex.block` \\bar{\\Upsilon}(N) \\bar{\\tau}_i(N) = \\bar{n}_i(N) `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":199,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":294,"value":"elements = [\n  {Queue: 1, meanQueueLength: 2.0150, meanWait: 1.2039, Utilization: 0.8369, throughput: 1.6737},\n  {Queue: 2, meanQueueLength: 0.9849, meanWait: 0.5885, Utilization: 0.5579, throughput: 1.6737},\n  {Queue: 3, meanQueueLength: 0.3654, meanWait: 0.2183, Utilization: 0.2790, throughput: 1.6737},\n  {Queue: 4, meanQueueLength: 0.6347, meanWait: 0.3792, Utilization: 0.4184, throughput: 1.6737}\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"md`\n#### Data\n\n| Queue ${tex`i`} | Mean queue length | Mean wait (${tex`msec`}) | Utilization ${tex`P(\\cdot)`} | throughput ${tex`(msec^{-1})`}\n|-----------|----------------|----------------------|------------|-------|${elements.map(e => `\n| ${e.Queue} | ${e.meanQueueLength} | ${e.meanWait} | ${e.Utilization}  | ${e.throughput}`)}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":323,"value":"elements2 = [\n  {Queue: 1, k0: 0.1631, k1: 0.2065, k2: 0.2391, k3: 0.2348, k4: 0.1565},\n  {Queue: 2, k0: 0.4421, k1: 0.2777, k2: 0.1642, k3: 0.0850, k4: 0.0309},\n  {Queue: 3, k0: 0.7210, k1: 0.2089, k2: 0.0555, k3: 0.0126, k4: 0.0019},\n  {Queue: 4, k0: 0.5816, k1: 0.2608, k2: 0.1087, k3: 0.0391, k4: 0.0098}\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":328,"value":"md`\n#### ${tex`P(n_i = k)`}\n   \n| Queue ${tex`i`} | ${tex`k=0`} | ${tex`k=1`} | ${tex`k=2`} | ${tex`k=3`} | ${tex`k=4`} \n|-----------|----------------|----------------------|------------|---|----|${elements2.map(e => `\n| ${e.Queue} | ${e.k0} | ${e.k1} | ${e.k2}  | ${e.k3} | ${e.k4}`)}\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"md`\n### Bibliography\n**[Arthur]** J. L. Arthur 1995 *Notes on Queueing Theory*.\n\n**[Bruell]** S. C. Bruell \\& G. Balbo 1980 Computational Algorithms for\nClosed Queueing Networks, North-Holland, N.Y.\n\n**[Buzen]** J. P. Buzen 1973 Computational Algorithms for Closed Queueing \nNetworks with Exponential Servers, *Comm. of the ACM* **16** (9).\n\n**[Gordon]** W. J. Gordon \\& G. F. Newell 1967 Closed Queuing Systems\nwith Exponential Servers, *Opns. Res.* **15** 254-265.\n\n**[Harrison]** P. G. Harrison 1985 On Normalizing Constants in\nQueueing Networks, *Opns. Res.* **3** (2) 464-468.\n\n**[Reiser]** M. Reiser \\& S. S. Lavenberg 1980 Mean-value Analysis of \nClosed Multichain Queueing Networks, *J. of the ACM* **27** (2) 313-322.\n\n**[Robertazzi]** T. G. Robertazzi 1990 Computer Networks and Systems:\nQueueing Theory and Performance Evaluation, Springer-Verlag.\n\n**[Ross]**  S. M. Ross 1993 Introduction to Probability Models,\nAcademic Press 5th edition.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":211,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":215,"value":"md`\n#### HARRISON.M\n\n% Implements the Harrison Algorithm for computing Normalizing Constants\n% in Queueing Networks.  The varible x must each be distinct.\n% This routine should stop it it's not as it will divide by zero.\n\n% Varible List\n% N is the number of customers, or load\n% M is the number of servers\n% rate is the exponential service rate of the ith server\n% tput is the throughput calculated from the traffic equations\n`\n// % By Rob Chohan, last update:  23 May 95\n\n// M = length(rate);\n// z = zeros(size(rate));\n// out = zeros(1,N);\n\n// x = tput ./ rate;               % x is the notation from Gordon & Newell\n\n// for i = 1:M,\n// \ttmp = x ~= x(i);\n// \ttmp = tmp .*x;\n// \ttmp2 = x(i) - tmp(tmp~=0);\n// \tz(i) = prod(tmp2);\n// end\n\n// for i = 1:N\n// \tout(i) = sum(x.^(i +M-1) ./ z);\n// end;\n\n// y = out';\n\n// 
","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"md`\n#### MEANVALU.M\n\nfunction y = meanvalue(rate, tput, N)\n\n% Computes performance measures via the mean value analysis algorithm\n\n`\n// M = length(rate);\n\n// nbar = zeros(1, M);\n// one = ones(size(nbar));\n\n// for n = 2:N+1,\n// \t(n-1);\n// \ttau = 1./rate .* (one + nbar );\n// \tupsilon = (n-1) / sum(tau);\n// \tnbar = upsilon * tau;\n// end\n// disp(' ')\n// disp('mean queue    mean wait')\n// disp ([nbar' tau'])\n// mean_throughput = upsilon\n\n// y = [nbar' tau'];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W38","stdlib":"1"}}
32:"$31:body"