COMP9334
Capacity Planning for Computer Systems and Networks
Week 2A: Operational Analysis (2). Workload Characterisation
COMP9334
1
Last lecture
• Modellingacomputersystemasaqueueingnetwork • Operationalanalysisonqueueingnetworks
• Wehavederivedtheseoperationallaws • UtilisationlawU(j)=X(j)S(j)
• ForcedflowlawX(j)=V(j)X(0)
• ServicedemandlawD(j)=V(j)S(j)=U(j)/X(0) • Little’slawN=XR
T1,2021 COMP9334 2
This lecture
• Operational analysis (Continued)
• Usingoperationallawfor
• Performance analysis
• Bottleneck analysis
• Workload characterisation
• Poissonprocessanditsproperties
T1,2021 COMP9334 3
Interactive systems
M users
• An interactive system is used to model the interaction between humans (users) and computers
• The system consists of • A number of users
• A computer system
results
jobs
T1,2021
COMP9334
4
Interactive systems (Cont’d)
M users
• Interactions
• Users send jobs to
computer systems
• After finishing processing a job, the computer system returns the result to the user
• A user, after inspecting the results from the computer system, will send another job to the system
results
jobs
T1,2021
COMP9334
5
Interactive systems: Modelling assumptions
M users
• Analyze interactive systems with specific assumptions
• Fixed number of users denoted by M
• Each user can have at most 1 job at the computer system
• Each user goes through a cycle consisting of
• Thinkingtime
• Waitingforresulttime
results
jobs
T1,2021
COMP9334
6
Interactive cycle
User 1
User 1 has no jobs at the system. They send a job to the computer system at this time.
time
• The time the job from User 1 spends in the computer system
• User 1 waiting for the results
results
jobs
T1,2021 COMP9334
7
Results are returned to the user
Thinking time
system
User 1 sends a job to the computer
Interactive cycle
• User 1’s perspective: waiting for the result of their job
• Computer system’s perspective: Response time of the job from User 1
results
jobs
User 1
User 1 has no jobs at the system. They send a job to the computer system at this time.
Results are returned to the user
time
User 1 sends a job to the computer system
T1,2021 COMP9334
Thinking time
= Processing time of the user. That’s why a user is depicted as a circle
8
Quiz
• Question: At any time, what is the sum of the number of busy users and the number of jobs at the computer system? M
Job at computer system
Busy user (= thinking)
results
jobs
User 1 User 2
User 3
time time
time
T1,2021 COMP9334
9
Interactive system: Parameters
• M interactive users
• Z = mean thinking time
• R = mean response time of the computer system
• X0 = throughput
T1,2021 COMP9334
10
Analyzing interactive system: Quiz 1
• Mavg = mean # busy users
• Z = mean thinking time
• X0 = throughput
• Apply Little’s Law to the red box. What do you get?
• Mavg=Z*X0
T1,2021 COMP9334
11
Analyzing interactive system: Quiz 2
• Navg=average#jobsin the computer system
• R=meanresponsetime at the computer system
• X0=throughput
• ApplyLittle’sLawtothe computer system (i.e. the blue box), what do you get?
• Navg=R*X0
T1,2021 COMP9334
12
Analyzing interactive system: Quiz 3
• Quiz1: • Quiz2:
• WhatisMavg+Navg? • M=Mavg+Navg
• Interactiveresponsetime law
• M=X0*(Z+R)
T1,2021 COMP9334
13
Mavg = X0 * Z
Navg = X0 * R
The operational laws
• Thesearetheoperationallaws
• UtilisationlawU(j)=X(j)S(j)
• ForcedflowlawX(j)=V(j)X(0)
• ServicedemandlawD(j)=V(j)S(j)=U(j)/X(0) • Little’slawN=XR
• InteractiveresponsetimeM=X(0)(R+Z)
• Applications
• Meanvalueanalysis(laterinthecourse) • Bottleneckanalysis
• Modificationanalysis
T1,2021 COMP9334 14
Bottleneck analysis – motivation
Disk 1
Disk 2
Disk 3
CPU
D(j)
79ms
108ms
142ms
92ms
Utilisation
0.30
0.41
0.54
0.35
Service demand law: D(j) = U(j) / X(0) ==> U(j) = D(j) X(0)
Utilisation increases with increasing throughput and service demand
T1,2021 COMP9334 15
Utilisation vs. throughput plot U(j) = D(j) X(0)
Disk 3
Disk 2
CPU
Disk 1
What determines this order?
Observation: For all system throughput:
Utilisation of Disk 3 > Utilisation of Disk 2 >
Utilisation of CPU > Utilisation of Disk 1
T1,2021 COMP9334 16
Bottleneck analysis
• Recall that utilisation is the busy time of a device divided by measurement time
• Whatisthemaximumvalueofutilisation?
• Based on the example on the previous slide, which device
will reach the maximum utilisation first?
T1,2021 COMP9334 17
Bottleneck (1)
• Disk3hasthehighestservicedemand • Itisthebottleneckofthewholesystem
Operational law: } Utilisation limit:
T1,2021 COMP9334
18
Bottleneck (2)
Should hold for all K devices in the system
Bottleneck throughput is limited by the maximum service demand
T1,2021 COMP9334
19
Bottleneck exercise
Disk 1
Disk 2
Disk 3
CPU
The system throughput is upper bounded by ! = 7.04 jobs/s “.!$%
If we upgrade Disk 3 by a new disk which is 2 times faster, which device will be the bottleneck after the upgrade? You can assume that service time is inversely proportional to disk
speed.
T1,2021 COMP9334 20
D(j)
79ms
108ms
142ms
92ms
Utilisation
0.30
0.41
0.54
0.35
Another throughput bound
• Little’s law
Previously, we have
Therefore:
T1,2021 COMP9334 21
Throughput bounds
Throughput
Bound 2. Slope =
Bound 1
Actual throughput
N
T1,2021 COMP9334
22
Bottleneck analysis
• Simple to use
• Needsonlyutilisationofvariouscomponents
• Assumes service demand is load independent
T1,2021 COMP9334 23
Modification analysis (1)
• •
(Reference:LazowskaSection5.3.1)
Acompanycurrentlyhasasystem(3790)andisconsideringswitching to a new system (8130). The service demands for these two systems are given below:
CPU
4.6
System
Service demand (seconds) Disk
• • •
3790 4.0
8130 5.1 1.9
Thecompanyusesthesystemforinteractiveapplicationwithathink time of 60s.
Giventhesameworkload,shouldthecompanyswitchtothenew system?
Exercise:Answerthisquestionbyusingbottleneckanalysis.Foreach system, plot the upper bound of throughput as a function of the number of interactive users.
T1,2021 COMP9334 24
Modification analysis (2)
Slope = 1/68.6
Slope = 1/67
1/4.6
1/5.1
T1,2021 COMP9334 25
Operational analysis
• Operational analysis allows you to bound the system performance but it does NOT allow you to find the throughput and response time of a system
• To order to find the throughput and response time, we need to use queueing analysis
• To order to use queueing analysis, we need to specify the workload
T1,2021 COMP9334 26
Workload analysis
• Performancedependsonworkload
• Whenwelookattheperformanceboundearlier,thebounds
depend on number of users and service demand
• Queueresponsetimedependsonthejobarrivalprobability distribution and job service time distribution
• Recall from Lecture 1A:
• Uniform arrival times and uniform processing times result in zero waiting
time
• But non-uniform distributions give non-zero waiting time
• Needtospecifyworkloadbyusingprobabilitydistribution. • Wewilllookatawell-knownarrivalprocesscalledPoisson
process today.
T1,2021 COMP9334 27
Arrival process
• Each vertical arrow in the time line below depicts the arrival
of a customer
Inter-arrival time
time t5
t1
t2 t3 t4
• Anarrivalcanmean
• A telephone call arriving at a call centre
• A transaction arriving at a computer system
• A customer arriving at a checkout counter
• An HTTP request arriving at a web server
• Theinter-arrivaltimedistributionwillimpactontheresponsetime.
• Wewillstudyaninter-arrivaldistributionthatresultsfromalargenumber
of independent customers.
T1,2021 COMP9334 28
Describing arrivals probabilistically
• Assumeacustomerarrivesattime0
0
t
At least one arrival in (0,t]
time
0
t
No arrivals in (0,t]
time
• Quiz:Whatistherelationbetweenthefollowingtwoprobabilities?
• Prob[at least one arrival in (0,t] ]
• Prob[no arrivals in (0,t] ]
• Answer:Theyaddupto1
• Moral:”Noarrivals”isnotboring,ittellsyousomething
T1,2021 COMP9334 29
Inter-arrival probability
• Assumeacustomerarrivesattime0
0
Inter-arrival time
t
Next arrival is after time t
time
0
t
No arrivals in (0,t]
time
• Quiz:Whatistherelationbetweenthefollowingtwoprobabilities?
• Prob[Inter-arrival time is >= t]
• Prob[no arrivals in (0,t] ] • Answer:Equal
• Nextstep:FindProb[noarrivalsin(0,t]]forindependentcustomers
T1,2021 COMP9334 30
Many independent arrivals (1)
• Problemsetup:
• An arrival at time 0
• A large pool of N independent customers
• Behaviour of each customer: Within a small time interval of d, a customer sends a request (or arrives) with a probability of pd
• p is a constant
• Quiz:Ifthereare2(=N)customers,whatistheprobabilitythatboth of them do not send any request in the time interval d
• Answer: (1 – p d)2
Customer 1
Customer 2
Prob[Send] = pd Prob[Not send] = 1 – pd
Prob[Send] = pd Prob[Not send] = 1 – pd
0
d
time
T1,2021
COMP9334
Picture credit: openclipart.org 31
Many independent arrivals (2)
• Aim: Want to find the probability of no arrivals in (0,t] • Divide the time t into intervals of width d
d
0
time t
• No arrival in (0,t] = no arrival in each interval d from N users • Probability of no arrival in d =
• There are t / d intervals
• Probability of no arrival in (0,t] is
(1 – p d)N
≈ 1 – Npd
T1,2021 COMP9334 32
Exponential inter-arrival time
• We have showed
Probability( no arrival in (0,t]) =
• Probability(inter-arrival time > t) =
• This means
Probability(inter-arrival time £ t) =
• What this shows is the inter-arrival time distribution for
independent arrival is exponentially distributed
• Define: l = Np
• l is the mean arrival rate of customers
T1,2021 COMP9334 33
Exponential distribution – cumulative distribution
• Cumulative distribution of inter-arrival time with customer arrival rate l
• Prob(inter-arrivaltime£t)=1-exp(-lt)
Prob that at least a customer will arrive before t = 1 for l = 1
Prob that at least a customer will arrive before t = 1 for l = 3
t
T1,2021 COMP9334
34
>
Exponential distribution
• A continuous random variable is exponentially distributed with rate l if it has probability density function
Reminder:
Probability density function
integration Cumulative differentiation probability
t
T1,2021 COMP9334 35
Probability density function (PDF)
Reminder: PDF f(t) Probability(t £ T £ t + dt) = f(t) dt
Red area = probability that inter-arrival time is in the interval [0,0.2]
Blue area = probability that the inter-arrival is in the interval [1,1.2]
T1,2021
COMP9334
36
Two different methods to describe arrivals
Method 1: Continuous probability distribution of inter-arrival time
Inter-arrival time
time
T1,2021 COMP9334
37
Two different methods to describe arrivals
Method 2: Use a fixed time interval (say t), and count the number of arrivals within t.
time
5 arrivals in t 8 arrivals in t
6 arrivals in t
• The number of arrivals in t is random
• The number of arrivals must be a non-negative integer
• We need a discrete probability distribution:
• Prob[#arrivals in t = 0]
• Prob[#arrivals in t = 1] • etc.
T1,2021 COMP9334 38
Poisson process (1)
• Definition: An arrival process is Poisson with parameter l if the probability that n customer arrive in any time interval t is
Example:
Example:
l= 5 and t = 1
Note: Poisson is a discrete probability distribution.
T1,2021 COMP9334
39
Poisson process (2)
• Theorem: An exponential inter-arrival time distribution with parameter l gives rise to a Poisson arrival process with parameter l
• How can you prove this theorem?
• Apossiblemethodistodivideanintervaltintosmalltimeintervals of width d. A finite d will give a binomial distribution and with d ! 0, we get a Poisson distribution.
T1,2021 COMP9334 40
Customer arriving rate
• Given a Poisson process with parameter l, we know that the probability of n customers arriving in a time interval of t is given by:
• What is the mean number of customers arriving in a time interval of t?
• That’s why l is called the arrival rate.
T1,2021 COMP9334 41
Customer inter-arrival time
• You can also show that if the inter-arrival time distribution is exponential with parameter l, then the mean inter-arrival time is 1/l
• Quite nicely, we have
Mean arrival rate = 1 / mean inter-arrival time
T1,2021 COMP9334 42
Application of Poisson process
• Poisson process has been used to model the arrival of telephone calls to a telephone exchange successfully
• Queueing networks with Poisson arrival is tractable • Wewillseethatinthenextfewweeks.
• Beware that not all arrival processes are Poisson! Many arrival processes we see in the Internet today are not Poisson. We will see that later.
T1,2021 COMP9334 43
References
• Operationalanalysis
• Lazowska et al, Quantitative System Performance, Prentice Hall, 1984. (Classic text on performance analysis. Now out of print but can be download from http://www.cs.washington.edu/homes/lazowska/qsp/
• Chapters 3 and 5 (For Chapter 5, up to Section 5.3 only)
• Alternative 1: You can read Menasce et al, “Performance by design”, Chapter 3. Note that Menasce doesn’t cover certain aspects of performance bounds. So, you will also need to read Sections 5.1-5.3 of Lazowska.
• Alternative 2: You can read Harcol-Balter, Chapters 6 and 7. The treatment is more rigorous. You can gross over the discussion mentioning ergodicity.
• Poisson process: Harcol-Balter Chapter 11
T1,2021 COMP9334 44