Lecture outline
• Capacity planning • Why?
• What?
• Quality of service metrics
• Quantitative performance analysisçèCapacity Planning • What techniques you will learn
• More quality of service metrics
• Single server queues
T1, 2021 COMP9334 10
Why capacity planning?
T1, 2021 COMP9334 11
Why capacity planning?
• The aim of capacity planning is to improve performance of computer systems by adding “capacity”.
• What is performance? • What is capacity?
T1, 2021 COMP9334 12
Design of an e-Commerce systems
• Functionalrequirements
• Productsearch,databasemanagementfunctionsetc
• Search correctness, algorithmic efficiency
• Computerandnetworksecurity
• Systemperformance
• E.g.Canthecomputersystemreturndatabasesearchwithin20msif there are 500 search queries per second?
Workload
• If not, should we buy more servers? How many?
capacity
performance
• Canyouthinkofothersystemperformancerequirements? T1, 2021 COMP9334 13
Web search engine
• Sayyouareplanningacomputersystemwhichwillhosta search engine that rivals Google
• Currentexpectedworkload • 1000searchespersecond
• Performancespecification • Returnresultswithin10ms
performance
• Whathardwareandnetworkshouldyouuse? • Howmanyservers?Howmuchdiskspace?Etc.
• Whatifworkloadisexpectedtoincreaseby50%inone year, can the system still maintain its performance?
capacity
• Question:Canyouthinkofothercapacityparameters?
T1, 2021 COMP9334 14
Capacity planning problems
• Focused on capacity planning of computer systems and networks
• Elements of a capacity planning problems • Given:
• Workload specifications
• Performance specifications
• Find:
• Capacity e.g. hardware or network requirements, personnel
requirements etc.
• Capacity planning problems are everywhere in life. Can you come out with some capacity planning problems in real life? For each problem, you must identify the workload, performance and capacity parameters.
T1, 2021 COMP9334 15
Capacity planning motivations
• Importanceofperformance
• Canbelifeanddeath
• Availability of critical infrastructure e.g. emergency services
• Customersatisfaction • Availability
• Response time
• Theitalicisedtermsareexamplesofcomputersystem related performance metrics
• AlsoknownasQualityofservice(QoS)metrics
T1, 2021 COMP9334 16
Response time
• Response time
• What is it? (Next slide)
• Possible performance specifications
• Meanresponsetimeislessthan1swhennomorethan5000
requests arrive per second
• 95%oftherequestsarecompletedwithin1swhennomore than 5000 requests arrive / s
• Note: Workload characteristics are also part of the performance specification
T1, 2021
COMP9334 17
Response time of a system
Request arrives at time t1
Request completes and leaves at time t2
Response time = t2 – t1.
Measured in seconds. Can be expressed as mean, standard deviation, probability distribution etc.
T1, 2021 COMP9334 18
Availability
• Fractionoftimethesystemisupanduseablebyusers
• Ex:ItiscommonforInternetServiceProviders(ISP)tosign Service Level Agreement (SLA) with their commercial customers. One ISP guarantees that its network outage is less than 6 hours per 30 days. The network availability is 1 – 6/(30*24) = 99.17%
T1, 2021 COMP9334 19
Lecture outline
• Capacity planning • Why?
• What?
• Quality of service metrics
• Quantitative performance analysisçèCapacity Planning • What techniques you will learn
• More quality of service metrics
• Single-server queues
T1, 2021 COMP9334 20
Capacity PlanningèPerformance analysis
• Capacity planning question:
• AwebserverneedstocompleteanHTTPrequestwithin20ms when there are 500 HTTP requests per second, what CPU speed do you need?
• Let us turn the capacity planning question into a performance analysis question
• Performance analysis question:
• IfthewebserverhasaCPUwithxMIPS,whatistheresponse
time when there are 500 HTTP requests per second?
• If you can solve the performance analysis question for any value of x, you can also solve the capacity planning question
T1, 2021 COMP9334 21
Exercise:
• As a capacity planner, your task is to choose the CPU speed (in MIPS) of a web server so that the mean response time to a specific workload is no more than 25ms.
• You talk to a performance analyst about your problem. The analyst knows an algorithm that predicts the mean response time for any CPU speed.
• You take the algorithm and plug in a number of different CPU speeds. The results are recorded below.
• Can you solve your capacity planning problem?
CPU Speed (MIPS)
2000
2500
3000
3500
4000 T1, 2021 C
Predicted mean response time (ms)
40
32
26
22
18
MP9334
22
O
Three performance analysis strategies
• Build the system and perform measurement • Simulation
• Mathematical modelling
• This course will look at
• QuantitativemethodstodeterminetheQoSmetricsofcomputer
systems using
• Queueing networks
• Markov chains
• Usingsimulationtostudyperformance
• Optimisationmethodssuchaslinearandintegerprogramming
T1, 2021 COMP9334 23
Ex. 1: Server farm power allocation
• Aserverfarmconsistsofmultipleservers
• Theserverscanrunat
• Higher clock speed with higher power
• Lower clock speed with lower power
• Ex:Given
• Higher power = 250W, lower power = 150W
• Power budget = 3000W
• You can have
• 12 servers at highest clock speed
• 20 servers at lowest clock speed
• Other combinations
• Which combination is best? • Queueingtheory
T1, 2021 COMP9334 24
Ex 2: Internet data centre availability
• Distributed data centres • Availability problem:
• Eachdatacentremaygodown
• Mean time between going down is 90 days
• Meanrepairtimeis6hours
• CanImaintain99.9999%availabilityfor3outof4centres
• Technique: Markov Chain
T1, 2021 COMP9334 25
Ex 3: Network expansion
• You would like to add communication links to a network. The design questions are: Where to add? How much capacity?
• Technique: Integer programming
T1, 2021 COMP9334 26
Why probability?
• The mathematical methods that we are going to study are based on probability theory. Why probability?
• Let us say 500 HTTP requests arrive at the web server in one second
• A deterministic world will mean
• AnHTTPrequestarrivesevery2ms
2ms
time
• But the arrival pattern is not deterministic, it’s random time
T1, 2021 COMP9334
27
Lecture outline
• Capacity planning • Why?
• What?
• Quality of service metrics
• Quantitative performance analysisçèCapacity Planning • What techniques you will learn
• More quality of service metrics
• Single-server queues
T1, 2021 COMP9334 28
QoS metrics
• We have seen 2 QoS metrics • Responsetime
• Availability
• More QoS metrics • Throughput
• Reliability(Willdiscusslaterinthecourse) • Scalability(Notdiscussed)
T1, 2021 COMP9334 29
Throughput (1)
• Therateatwhichrequestsarecompleted
• Ex:Fornetworkrouters,throughputcanbemeasuredin
• Packetspersecond(pps)
• Ex: 10 Mpps for 40-byte packets • Note: Should specify packet size
• Mb/s
• Otherthroughputmeasures
• Website:HTTPrequests/s,bytes/s • CPU:MIPS,FLOPS
T1, 2021 COMP9334 30
Throughput (2)
• Throughput is a function of the load
• Adisktakes0.01stoperformanI/Ooperation
• MaximumnumberofI/Ooperationpers=100
• If50I/Ooperationsarrivepersecond,thethroughput=50I/O operations/s
• If110I/Ooperationsarrivepersecond,thethroughput=100I/O operations
• Canyoufindaformularelatingthroughout,offeredloadandmax capacity?
• Throughput=min(offeredload,maxcapacity)
T1, 2021 COMP9334 31
Throughput (2*)
• If you find it difficult to do the previous page, you can try this real-life analogy.
• Throughput is a function of the load
• Abaristercanmakeacupofcoffeeevery30seconds
• Maximumnumberofcupsofcoffeethebaristercanmakeinan hour = 120
• If50customersarriveinanhourandeachcustomerordersa coffee, the barister’s throughput = 50 coffees / hour
• If150customersarriveinanhourandeachcustomerordersa coffee, the barister’s throughput = 120 coffees / hour
T1, 2021 COMP9334
32
Throughput (cont.)
Throughput (3)
Thrasing = congestion collapse
Thrashing = congestion collapse
T1, 2021 COMP9334 33
Throughput (4)
• Performance evaluation can be used to determine the maximum throughput of computer systems
• Example:bottleneckanalysis • Topic for next week
T1, 2021
COMP9334 34
Lecture outline
• Capacity planning • Why?
• What?
• Quality of service metrics
• Quantitative performance analysisçèCapacity Planning • What techniques you will learn
• More quality of service metrics
• Single-server queues
T1, 2021 COMP9334 35
Quantitative performance analysis (3)
• Sample performance analysis question:
• IfthewebserverhasaCPUwithxMIPS,whatistheresponse
time when there are 500 HTTP requests per second? • Performanceanalysisquestion:
• Given:
• A computer system with a certain capacity
• The workload
• Find
• The performance (response time, throughput etc) of the system
• Ourmethodis:
• Build analytical models of computer systems
• Animportantpartoftheanalyticalmodelis“queue” • You can surely relate “queues” to “waiting time”
T1, 2021 COMP9334 36
Single server FIFO queue
• QueueingTheoryterminologies • Server:Processingunit
• FIFO:First-infirst-out
• Workconservingserver
• The server cannot be idle when there are jobs waiting to be processed in the queue
• Ex:Shopwithonlyonecheckoutcounter • Theserverisaresource
• Queuesresultfromresourcecontention • Mainconcern:responsetime
T1, 2021 COMP9334 37
Job index
Arrival time
Processing time required
1
2
2
2
6
4
3
8
4
4
9
3
Assumption: server is idle when job #1 arrives
1
24
time
Job #1 is admitted into the server immediately since the server is idle.
Job #1 is completed and leaves the system at time 4.
T1, 2021 COMP9334 38
Job index
Arrival time
Processing time required
1
2
2
2
6
4
3
8
4
4
9
3
12
246 10
time
Job #2 arrives when the server is idle. It gets admitted immediately.
Job #2 will be completed at time 10.
T1, 2021 COMP9334 39
Job index
Arrival time
Processing time required
1
2
2
2
6
4
3
8
4
4
9
3
2
3
1
246 10 14
time
Job #3 arrives when Job #2 is being served i.e. the server is busy. Job #3 has to wait in the queue.
Server starts processing Job #3 immediately after finishing Job #2.
T1, 2021 COMP9334 40
Job index
1
2
3
4
Arrival time
2
6
8
9
Processing time required
2
4
4
3
2
3
4
1
246 10 1417
time
Job #4 arrives when the server is processing Job#2 and Job#3 is in the queue. Job #4 joins the queue. It gets served at time 14, immediately after Job#3 is completed.
T1, 2021 COMP9334 41
Job index
Arrival time
Processing time required
1
2
2
2
6
4
3
8
4
4
9
3
2
3
4
1
246 10 1417
time
• Definition: Response time = Departure time – arrival time Ex: Response time for Job#4 = 17 – 9 = 8 (= 5 + 3)
• Response time = Waiting time + Processing time
T1, 2021 COMP9334 42
Job index
Arrival time
Processing time required
1
2
2
2
6
4
3
8
4
4
9
3
2
3
4
1
246 10 1417
time
• Definition: Utilisation = Percentage of time over which the server is busy
•What is the utilisation of the server over the first 12s? • 8/12 = 66.7%
T1, 2021 COMP9334 43
Single server FIFO queues
• Can be used to model
• Shopwithonlyonecheckoutcounter
• AsingleprocessorprocessingjobsinFIFOorder • AdiskprocessingjobinFIFOorder
• Model
• Anabstractionoftherealsystem
• Needtocaptureenoughdetailstomeetouranalysisrequirements
T1, 2021 COMP9334 44
What if both inter-arrival time and processing time are determinisitic?
Job index
Arrival time
Processing time required
1
2
1
2
4
1
3
6
1
4
8
1
1
23
What is the waiting time for each job? What is the response time for each job?
time
T1, 2021 COMP9334 45
Determining response time
• Generallyweneedtoknow
• Thearrivalpattern
• Ex: The arrival rate
• Ex: The inter-arrival time probability distribution
• Theservicetimeprobabilitydistribution • The time required to process the job
• Sinceweareinterestedinresponsetime,ourmodels capture the time related aspects of the real systems e.g. queueing, processing units
• Wewilllearndifferentmethodstodetermineresponse time in this course
T1, 2021 COMP9334 46
Service time
• Time require to process a request at a resource
• Ex:Theservicetimetosenda1000bytepacketovera10kbpslink
is 0.8s. In this case,
• Service time = packet size / transmission rate
• Ex:TheservicetimetofetchaXbytelargefilefromadiskis • Seek time + X / transfer rate
• Foraclassofresources,wehave
• Service time = Overhead + Job size / Processing rate
T1, 2021 COMP9334 47
Summary
• What capacity planning is
• Very important: A capacity planning problem can be solved
by solving a series of performance analysis problems
• Performance metrics
• Responsetime,waitingtime,throughput
• Modelling of single server queues
T1, 2021 COMP9334 48
References
• Reading:
• Menasceetal,Chapters1&2
• OR
• Harcol-Balter.Chapters1&2.
• Exercises:
• Revisionproblems:
• See course web site
• Youareexpectedtotrytheseexercises.Solutionswillbeavailable
on the web.
T1, 2021 COMP9334 49