From:
http://www.perfdynamics.com/Tools/PDQpython.html
http://simpy.sourceforge.net/examples/Jackson%20network.htm
Messages arrive randomly at rate 0.5 per unit time at a communication network with 3 nodes (computers). Each computer can queue messages and service-times are exponential with mean m[i] at node i. These values are given in the column headed m[i] in the table below. On service at a node a message transfers to one of the other nodes or leaves the system. The probability of a transfer from node i to node j is p[i,j]. Node 4 means "outside the system" so a message will transfer out of the system from node i with probability p[i,4].
Your task is to estimate the average time taken for jobs going through the system and the average number of jobs in the system.
The transition probabilities are given in the following table:
| Node | m[i] | p[i,1] | p[i,2] | p[i,3] | p[i,4] |
| i | (leave) | ||||
| 1 | 1.0 | 0 | 0.5 | 0.5 | 0 |
| 2 | 2.0 | 0 | 0 | 0.8 | 0.2 |
| 3 | 1.0 | 0.2 | 0 | 0 | 0.8 |
The graph is:
Note: i have corrected an error in the graph, look at the third queue, the service rate is 0.5*lambda1 + 0.8*lambda2, it is not 0.8*lambda2.
The specific steps involved are:
1.Use the routing probabilities in the diagram to write down the traffic equations
2. Use my Parallel Gauss-Seidel with relaxation solver to calculate the internal workflows: L1, L2, L3
3. Use the algebric equations to calculate the average queue length and average response time etc.
From the queuing network diagram, we have:
L1 = 0.5 + 0.2 L3
L2 = 0.5 L1
L3 = 0.5 L1 + 0.8 L2
Note: L1,L2,L3 are the arrival rates ...
Rearrange the terms into matrix form:
1.0 L1 + 0.0 L2 - 0.2 L3 = 0.5
- 0.5 L1 + 1.0 L2 + 0.0 L3 = 0.0
- 0.5 L1 - 0.8 L2 + 1.0 L3 = 0.0
You can resolve the system of equations with my Parallel Gauss-Seidel with relaxation (see GSRP ) just by passing the following parameters in gsp.pas:
matrows[0,0]:=1.0;matrows[0,1]:=0.0;matrows[0,2]:=-0.2;
matrows[1,0]:=-0.5;matrows[1,1]:=1.0;matrows[1,2]:=0.0;
matrows[2,0]:=-0.5;matrows[2,1]:=-0.8;matrows[2,2]:=1.0;
vecb[0]:=0.5;vecb[1]:=0.0;vecb[2]:=0.0;
vecx[0]:=1;vecx[1]:=0;vecx[2]:=1;
The solution of the system gives: L1:= 0.609 , L2 = 0.304 and L3 = 0.548
And we are told the routers service times: S1 = 1.0, S2 = 2.0, S3 = 1.0,
So, the service rates are: M1 = 1.0 , M2 = 0.5 and M3 = 1.0
We know from queuing theory that an M/M/c model gives:
C(c, U) = Erlang formula = P(c) / (1 - Utilization)
note: c the number of servers..
P(c): means the probability that all the servers are busy.
P(0): means the probability that there is no waiting time in the queue, that means also: AT LEAST one server among the C servers are not busy...
The average waiting time in the 'queue' = C(c,U) / (service rate * c * (1 - Utilization)) (10)
It's approximatly equal to: Utilization^C/(service rate * (1 - Utilization^C)
Note: ^ means power
and C means the number of servers.
This approximation is exact for the M/M/1 and M/M/2 models, but 'slightly' lower than the result in (10) if c > 2
and Utilization = Density of circulation / C (number of servers)
Response time = The average waiting time in the 'queue' + (1 / service rate)
average numbers of users in the system = service rate x response time
average number of users in queue = service rate * average waiting time in the 'queue'.
and we know that R (response time) = D(average waiting time in the queue) + 1 /Service rate (1)
and Pt (the perceived throuput) = 1 / R (2)
and Ns (average number of jobs in the system) = arrival rate * R (3)
and and Nq (average number of jobs in the queue) = arrival rate * D (4)
Now we can start our calculations , so we have that:
The average waiting time in the 'queue' = C(c,U) / (service rate * c * (1 - Utilization)) (5)
C(c, U) = Erlang formula = P(c) / (1 - Utilization)
Note: c the number of servers..
And (5) is approximatly equal to:
Utilization^C/(service rate * (1 - Utilization^C) )
So, for the first queue in our Jackson network we have that:
A1 (the arrival rate) equal L1 = 0.609
M1 (the service rate is) equal S1 = 1.0
We substitute in Eq. (5) this will give: (0.605/1)^1/ 1 *(1-(0.609/1)^1)
So, D1(average waiting time in the queue) for the first queue = 1.547
and from (1) , R1(response time in the queue 1) for the first queue = 1.547 + 1/1 = 2.547
and from (3) => Ns1(average number of jobs in the system queue 1) = 0.609 * 2.547 = 1.551
the same for the second queue we have
A2 (the arrival rate) equal 0.5*L1 = 0.304
M2 (the service rate is) = 0.5
We substitute in Eq. (5) this will give: (0.304/0.5)^1/ 0.5 *(1-(0.304/0.5)^1)
So , D2(average waiting time in the queue) for the second queue = 3.102
and from (1) , R2(response time in the queue 2) for the second queue = 3.102+ 1/0.5 = 5.102
and from (3) => Ns2(average number of jobs in the queue system 2) = 0.304 * 5.102 = 1.551
The same for the third queue we have
A3 (the arrival rate) equal 0.5 *L1 + 0.8 * L2 = 0.304 + 0.243 = 0.547
M3 (the service rate is) = 1.0
We substitute in Eq. (5) this will give: (0.547/1)^1/ 1 *(1-(0.547/1)^1) = 0.547/0.453 = 1.207
so the D3(average waiting time in the queue) for the third queue = 1.207
and from (1) , R3(response time in the queue 3) for the third queue = 1.207 + 1/1 = 2.207
and from (3) => Ns3(average number of jobs in the queue system 3) = 0.547 * 2.207 = 1.207
The total average number of jobs in the system is: Ns1 + Ns2 + Ns3 = 4.309
To obtain D (average waiting time in the system) , you can not simply add the expected waiting times at the respected queues , because jobs does not necessarily visit each queue exactly once. However, in the Jackson network the Little formula can still be used, so from Eq. (3) we have that:
and Ns (average number of jobs in the system) = arrival rate * R (3)
that means that R = Ns / L(arrival rate from outside to the system)
Hence, R is equal to : Ns / L = 4.309 / 0.5 = 8.618.
So, Ns = 4.309 and R = 8.618, and this is the same results that we get in the following simulations:
http://www.perfdynamics.com/Tools/PDQpython.html
You can also do a simulation in Object Pascal if you want, like i have showed you , look at 'An M/M/n queuing model simulation' here: homepage.
Please click here to return to my homepage: homepage.
Regards,
Amine Moulay Ramdane.
http://pages.videotron.com/aminer/