Basic definitions for
performance predictions
The performance of a system that gives services could be see from the point of view of the users or of the system itself. In the first case quantities of interest could be the time to obtain a service or the waiting time before get a service; in the second case the number of users served in the unit time or the level of utilization of the resourses.
The model can be built starting by the observation of the behavior of the system.
SYSTEM
ARRIVALS COMPLETIONS
users servers or resourses
measures:
T: the system observation lenght of time;
A: the number of arrivals in the period T;
C: the number of completions in the period T.
Derived quantities:
: arrival rate, = A/T;
X: throughput, X= C/T.
In case of single server another measure of interest is the lenght of time the server is busy (B). Then we can derive:
: utilization of the server, =B/T;
S: average service completion per request, B/C.
From which it is possible to derive the utilization law:
= X S
The utilization form is a special case of the
Little’s law
. In particular denoting with:W : the accumulated time in system of the requests and defining with:
N: the average number of requests in the system, N = W/T
R: the average system residence time per request, R=W/C
the Little’s law is equal to:
N=X R
Little’s law is very important in the performance evaluation of system consisting of a set of servers because it is widely applicable and does not requery strong assumptions.
Queueing systems
Normally a system can be modeled a set of interconnected queues, in which the servers and the users have different characteristics for each queue. If each queue has a behavior that is independent of the other queues then each queue can be analysed separately. In particular conditions each queue can be modeled as a Markov chain.
For example the birth/dead process analysed before can be used to represent a particular queue in which:
the inter arrival time of the users is distributed in accordance to the exponential distribution, with arrival rate equal to ;
the presence of only one server;
the service time is distributed in accordance to the exponential distribution, with service time equal to 1/.
This kind of queue is denoted as M/M/1 and could model the queue see in the previous slides.
M/M/1 queue analysis
Infinite queue
State transition diagram – infinite population
State transition diagram with boundaries
0 1 2 3
. . . .
0 1 2 3
. . . .
Flow In = Flow Out principle: the flow into a set of states is equal to the flow out of this set of states in equilibrium.
1 1 2
0 1
. . .
k
k p
p p p
p p
out flow in
flow
Combining,
,...
2 , 1 , ... 0
2
1
p p p k
p
k k
k
k
Since the sum of the fractions of time that the system is at any possible state, from 0 to ∞, equals one
1 ...
...
0 0 0
2 1
0
k
k k
k
k p p
p p
p
p
This leads to
1
1
0 0
k
k
p
It is now possible to derive the following quantities:
Probability to stay in state i (fraction of time server has k request):
k
k p
p 0
where
U p
k
k
1 1
1
0
0
The utilization factor:
1 0
p
U
The expected number of users in the system
Using the definition of average,
0 0
0
1 1
k
k k
k k
k k U U U k U
p k N
Since the last summation equals U/(1-U)2 for U<1,
) 1 /( U U
N
The average response time
Using the Little’s Law, since the average throughput equals
,
) 1 /(
) 1 )(
/ 1 ( ) 1 )(
/ (
/X U U U S U
N
R
where S =1/ is the average service time of request at the server.
The expected number of users in queue
1
2
1 1
k k pk
L
E
The average time in queue and in the system
E[W] E[L]
(1 )
E[T] E[ N]
1
(1 )
Example
Requests arrival rate at the Web server: =30 requests/sec Average service time: 0.02 seconds
Average service rate => = 1/0.002 = 50 request/sec p0=1-0.6=40%
_
Average number of requests at the server: N=0.6/(1-0.6)=1.5 Average response time: R=(1/50)/(1-0.6)=0.05sec
Should the server be twice as fast => = 100 request/sec U=0.3
R=0.014 sec
Finite queue
State transition diagram –infinite population/finite queue
Using the flow-in=flow-out equations,
W k
p p
k
k 0 , 1,....
Since we have a finite number of states,
/ 1 1
) / ( 1
...
1 0
0 0 0 1
0
W
W k k W
p
p p p p
p
Hence,
0 1
) / ( 1
/ 1
W
p
Since U=1-p0,
0 1 2 3
. . .
K
. . .
.
W
The utilization factor:
1
0 1 /
) / ( 1 ) / (
p W W
U
The expected number of users in the system Using the definition of average.
W
k W k
k k pk p k N
0 0 0
) / (
Hence
1 /
(1 / )1 ) / )(
1 ( ) / ( ) /
( 1
W WW W W
N
The average response time Using the Little’s Law,
1/ ) / (
(1 1)(//)) 1/ (
1
SW W WW W
X N R
Example
Requests arrival rate at the Web server: =30 requests/sec Average service time: 0.02 seconds
Average service rate: = 1/0.002 = 50 request/sec
p0=0.4/(1-0.6W+1)
Minimum value for the maximim number of accepted requests so that less than 1% of the request are rejected
=> pW=p0(/)W<0.01
0.4* 0.6W/(1-0.6W+1)<0.01 => W≥8
Generalized System-Level Models
Using the flow-in=flow-out equations,
,...
2 , 1
1 ,
1
pk kpk k
k
By applying recursively,
. . .
0 1 0 2 1 1 2 1 2
0 1 0 1
p p
p
p p
0 1 0 2 1 1 1
1 p ... p
p
k k k
k k
k
So
1
k
0 1 2
. . . .
Since
1
0 1
0 1
0
k k
i i
p i
this implies that
0 1
0 1
0 k
k
i i
p i
