COMP9334
Capacity Planning of Computer Systems and Networks
Week 1B: Queuing networks. Operational analysis
COMP9334
1
Last lecture
• Solve capacity planning by solving a number of performance analysis problems
• Performancemetrics
• Response time, waiting time • Throughput
• SingleserverFIFOqueue • A server = A processing unit
T1,2021 COMP9334 2
This lecture
• Queueing networks • Operational analysis
• Fundamentallawsrelatingthebasicperformancemetrics
T1,2021 COMP9334 3
Modelling computer systems
• Single server queue considers only a component within a computer system
• AcomponentcanbeaCPU,adisk,atransmissionchannel
• A request may require multiple resources
• E.g.CPU,disk,networktransmission
• We model a computer systems with multiple resources
by a Queueing Networks (QNs)
T1,2021 COMP9334 4
Pictorial representation of single server queues
Waiting line
Queue
server
Arriving customers
Arriving requests
Finished
Requests waiting to be processed
CPU
requests
T1,2021 COMP9334 5
Pictorial representation of queues
Systems with m servers
1 2
m
Waiting line
T1,2021 COMP9334 6
A simple database server
The server has a CPU and a disk.
pen queueing network
xternal arrivals
orkload intensity specified by arrival rate
A transaction may visit the CPU and disk multiple times. nbouT1n,2d02e1dnumCbOeMPr93o34fcustomersinthesystem 7
O
E W U
Database servers for batch jobs
• Example:Batchprocessingsystem
• E.g.Forsummarizationdatafromdatabases
• Noon-linetransactions
atabase server for batch jobs
unning batch jobs overnight
E.g. producing managerial reports
T1,2021 COMP9334 8
D
R
Open vs. closed queueing networks (1)
pen queueing network
Open queueing network
• External arrivals
• Workload intensity
specified by arrival rate
xternal arrivals
abase server for batch jobs
orkload intensity specified by arrival rate nbounded number of customers in the system
equilibrium, flow in = flow out throughput = arrival rate
ning batch jobs overnight
T1,2021 COMP9334 9
Closed queueing network • No external arrivals
• Workload intensity
specified by customer
population
Page 26
O
E
at
W
U
In
)
un
E.g. producing managerial reports
D
R
Open vs. closed queueing networks (2)
en queueing network
Open queueing network • Possibly unbouned #customers
• For stable equilibrium
Throughput = arrival rate
ernal arrivals
abase server for batch jobs
rkload intensity specified by arrival rate bounded number of customers in the system
quilibrium, flow in = flow out throughput = arrival rate
ning batch jobs overnight
Page 26
T1,2021 COMP9334
10
Closed queueing network • Known #customers
• Throughput depends on
#customers etc.
Op
Ext
at
Wo
Un
In e
)
un
E.g. producing managerial reports
D
R
Open vs. closed queueing networks – Terminology
en queueing network
ernal arrivals
abase server for batch jobs
rkload intensity specified by arrival rate bounded number of customers in the system
quilibrium, flow in = flow out throughput = arrival rate
ning batch jobs overnight
Page 26
Work in a closed queueing network is called jobs
T1,2021 COMP9334
11
Work in an open queueing network is called transaction
Op
Ext
at
Wo
Un
In e
)
un
E.g. producing managerial reports
D
R
DB server – mixed model
• Theserverhasboth
• Externaltransactions
• Batchjobs
Mixed queueing network
T1,2021 COMP9334 12
Different techniques are needed to analyse open and closed TqruaensuaecitniognnetwoMrkasximum Average Minimum
Service Level Agreements
Group Response Time (sec) Throughput
owed into the database. If the MPL is too
e
n h
m i
a o
y
a t
o
a a
N g
suffer, since not all DBMS resources he other hand, if the MPL is too high,
up in an external queue. The application can then control the order in which transactions are executed by scheduling
DB server – Multi-programming level
ontrol on scheduling. The question of L to achieve both goals simultaneously
incoming transactions
• Somedatabaseserver
ot just for databases but in system de-
the external queue.
management systems (DBMS)
in we study this problem in the context
set an upper limit on the number
loads, both via extensive experimenta- oretic analysis.
MPL=4 DBMS
of active transactions within the
external queue
o most critical factors in adjusting the
system
of resources that the workload utilizes
• Thisupperlimitiscalledmulti- the transactions’ service demands. We
programming level (MPL)
ased controller, augmented by queue- for automatically adjusting the MPL. methods to the specific problem of ex- of transactions. We find that external nearly as effective as internal prioriti- egative consequences, when the MPL
Figure 1. Simplified view of the mechanism used in external scheduling. A fixed limited number of trans- actions (MPL=4) are allowed into the DBMS simul- taneously. The remaining transactions are held back in an external queue. Response time is the time from when a transaction arrives until it completes, includ- ing time spent queueing externally to the DBMS.
• AhelppagefromSAPexplainingMPL
Examples of recent work on external scheduling come
• http://dcx.sap.com/1200/en/dbadmin_en12/running-s-3713576.html
• PicturefromSchroderetal.“Howtodetermineagoodmulti-
eb applications are largely dependent
se, whperoe gthreamamjoirnitgy loefvtehel froeqruexstternal scheduling”
from many areas including storage servers, web servers, and
database servers. For example, Jin et al. [9] develop an ex-
rants CCR-0133077, CCR-0311383, 0313148,
ternal scheduling front-end to provide proportional sharing
among the requests at a storage service utility. Blanquer et
T1,2021 COMP9334 13
will On t ent c MP em, n Here work
g the e tw ber
ty of ck b
dels our
tion n be
ny n ely.
n
ys w taba
SF g
h Digital Greenhouse Grant.
MPL is already met, all remaining transactions are queued
al. [4] study external scheduling for quality of service pro-
Operational analysis (OA)
• “Operational”
• Collectperformancedataduringday-to-dayoperation
• Operation laws
• Applications:
• Usethedataforbuildingqueueingnetworkmodels • Performbottleneckanalysis
• Performmodificationanalysis
T1,2021 COMP9334 14
Single-queue example (1)
#requests = A
server
#requests = C
B
In an observational period of T, server busy for time B A requests arrived, C requests completed
A, B and C are basic measurements
Deductions: Arrival rate l = A/T Output rate X = C/T
Utilisation U = B/T
Mean service time per completed request = B/C
T1,2021 COMP9334 15
Motivating example
• Given
• Observationperiod=1minute
• CPU
• Busy for 36s.
• 1790 requests arrived
• 1800 requests completed • Find
• Mean service time per completion = 36/1800 = 0.02s
• Utilisation = 36/60 = 60%
• Arrival rate =
• Output rate =
1790/60 = 29.83 requests /s
1800/60 = 30 requests/s
T1,2021 COMP9334 16
Utilisation law
• The operational quantities are inter-related
• Consider
• UtilisationU=B/T
• MeanservicetimepercompletionS=B/C • OutputrateX=C/T
• Utilisation law – Can you relate U, S and X? • U=SX
• Utilisation law is an example of operational law.
T1,2021 COMP9334 17
Application of OA
• Don’thavetomeasureeveryoperationalquantities • MeasureBtodeduceU-don’thavetomeasureU
• Consistencychecks
• IfU1SX,somethingiswrong
• Operationallawscanbeusedforperformanceanalysis • Bottleneckanalysis(Lecture2A)
• Meanvalueanalysis(Laterinthecourse)
T1,2021 COMP9334 18
Equilibrium assumption
• OA makes the assumption that • C=A
• OratleastC»A
• This means that
• Thedevicesandsystemareinequilibrium
• •
Arrival rate of requests to a device = Output rate of requests for that device = Throughput of the device
The above statement also applies to the system, i.e. replace the word “device” by “system”
T1,2021
COMP9334 19
OA for Queueing Networks (QNs)
The computer system has K devices, labelled as 1,…,K.
The convention is to add an additional device 0 to represent the outside world.
T1,2021 COMP9334
20
OA for QNs (cont’d)
• Wemeasurethebasicoperationalquantitiesforeach device (or other equivalent quantities) over a time of T
• A(j)=Numberofrequestarrivingatdevicej
• B(j)=Busytimefordevicej
• C(j)=Numberofcompletedrequestsfordevicej
• Inaddition,wehave
• A(0)=Numberofarrivalsatthesystem
• C(0)=Numberofcompletionsforthesystem
• Question: What is the relationship between A(0) and C(0) for a closed QNs?
T1,2021 COMP9334 21
Visit ratios
• A job arriving at the system may require multiple visits to a device in the system
• Example:Ifeveryjob(ortransaction)arrivingatthesystemwill require 3 visits to the disk (= device j), what is the ratio of C(j) to C(0)?
• WeexpectC(j)/C(0)=3. • V(j)=Visitratioofdevicej
= Number of times a job (transaction) visits device j • We have V(j) = C(j) / C(0)
T1,2021
COMP9334 22
Forced Flow Law
Since
The forced flow law is
T1,2021 COMP9334 23
Service time versus service demand
• Ex: A job requires two disk accesses to be completed. One disk access takes 20ms and the other takes 30ms.
• Service time = the amount of processing time required per visit to the device
• Thequantities“20ms”and“30ms”aretheindividualservicetimes.
• D(j) = Service demand of a job at device j is the total service time required by that job
• Theservicedemandforthisjob=20ms+30ms=50ms
T1,2021 COMP9334 24
Service demand
• Service demand can be expressed in two different ways
• Ex:Ajobrequiresthreediskaccessestobecompleted.One disk access takes 20ms and the others take 30ms and 28ms.
• What is D(j)? 78ms.
• What are V(j) and S(j)?
• Recall that S(j) = mean service time of device j
• V(j) = 3. S(j) = 26ms.
• Service demand D(j) = V(j) S(j)
T1,2021 COMP9334 25
Service demand law (1)
Given D(j) = V(j) S(j) Since
• What is X(j) S(j)?
• It is U(j)
Service demand law
T1,2021 COMP9334
26
Service demand law (2)
• Service demand law D(j) = U(j) / X(0)
• Youcandetermineservicedemandwithoutknowingthevisitratio
• OvermeasurementperiodT,ifyoufind
• B(j) = Busy time of device j
• C(0) = Number of requests completed
• You’veenoughinformationtofindD(j) • The importance of service demand
• Youwillseethatservicedemandisafundamentalquantityyou need to determine the performance of a queueing network
• Youwilluseservicedemandtodeterminesystembottleneckin Lecture 2A
T1,2021 COMP9334 27
Server example exercise
Disk 1
Disk 2
Disk 3
CPU
# I/O per second
32
36
50
Utilisation
0.30
0.41
0.54
0.35
Total # jobs=13680
What is the service time of Disk 2? What is the service demand of Disk 2? What is its visit ratio?
Measurement time = 1 hr
T1,2021 COMP9334 28
Server example solution
Service time System throughput Service demand Visit ratio
= U2/X2 = 0.41/36 = 11.4ms = 13680/3600 = 3.8 jobs/s
= 0.41/3.8 = 108ms
T1,2021 COMP9334
29
Measurement time = 1 hr
Disk 1
Disk 2
Disk 3
CPU
# I/O per second
32
36
50
Utilisation
0.30
0.41
0.54
0.35
Total # jobs=13680
= 36/3.8 = 108 / 11.4 = 9.47
Little’s law (1)
• Due to J.C. Little in 1961
• Afewdifferentforms
• The original form is based on stochastic models
• Animportantresultwhichisnon-trivial
• All the other operational laws are easy to derive, but Little’s
Law’s derivation is more elaborate. • Consider a single-server device
• Navg=Averagenumberofrequestsinthedevice
• When we count the number of requests in a device, we include
the one being served and those in the queue waiting for service
T1,2021 COMP9334 30
Little’s Law (2)
• X = Throughput of the device
• Ravg = Average response time of the requests
• Navg = Average number of requests in the device • Little’s Law (for OA) says that
Navg = X * Ravg
We will argue the validity of Little’s Law using a simple example.
T1,2021 COMP9334 31
Consider the single sever queue example from Week 1
Request index
1
2
3
4
Arrival time
2
6
8
9
Service time
2
4
4
3
Departure time
4
10
14
17
Let us use blocks of height 1 to show the time span of the requests, i.e. width of each block = response time of the request
3 2
1
1
246 10 1417
time
4
3
2
T1,2021 COMP9334 32
3 2
1
1
2 4 6 10 14 17
time
4
3
2
Assuming that in the measurement time interval [0,20]
these 4 requests arrive and depart from this device, i.e. the device is in equilibrium.
Total area of the blocks
= Response time of request 1 + Response time of request 2 +
Response time of request 3 + Response time of request 4 = Average response time over the measurement interval *
Number of requests completed over the measurement interval
This is one interpretation. Let us look at another.
T1,2021 COMP9334 33
3 2
1
1
246 10 1417
time
4
3
2
Let us assume these blocks are “plasticine” and let them fall to the ground. Like this.
3 2
1
1
246 10 1417
time
4
3
4
2
3
4
There is an interpretation of the height of the graph.
T1,2021 COMP9334 34
Request index
Arrival time
Service time
1
2
2
2
6
4
3
8
4
4
9
3
3 2
Requests waiting
to be processed
1
246 10 1417 time
Request being processed
4
3
4
2
3
4
1
Interpretation: Height of the graph = #requests in the device E.g. Number of requests in [9,10] = 3
E.g. Number of requests in [11,12] = 2 etc.
T1,2021 COMP9334 35
3 2
1 1
246 10 1417 time
waiting requests
Request being processed
4
3
4
2
3
4
Again, consider the measurement time interval of [0,20].
Area under the graph in [0,20]
= Height of the graph in [0,1] + Height of the graph in [1,2] + …
Height of the graph in [19,20]
= #reqs in [0,1] + #reqs in [1,2] + … + #reqs in [19,20]
= Average number of requests in [0,20] in the device * 20
T1,2021 COMP9334 36
3 2
1
1
246 10 1417
Area = Average response time over [0,T] * Number of requests completed in [0,T]
time
4
3
2
waiting requests
3 2
1
246 10 1417 time
Area = Average number of requests in [0,T] * T
4
3
4
2
3
4
1
Request
being processed
T1,2021 COMP9334 37
Deriving Little’s Law
Area = Average response time of all jobs *
Number of requests completed in [0,T] (Interpretation #1)
= Average #requests in [0,T] * T (Interpretation #2) Since Number of requests completed in [0,T] / T
= Device throughput in [0,T] We have Little’s Law.
Average number of requests in [0,T]
= Average response time of all reqs * Device throughput in [0,T]
T1,2021 COMP9334 38
Using Little’s Law (1)
queue
server
• A device consists of a server and a queue
• The device completes on average 8 requests per second • On average, there are 3.2 requests in the device
• What is the response time of the device?
• Mean throughput X = 8 requests/s
• Mean number of requests Navg = 3.2 requests
• By Little’s Law, average response time = Navg/X = 3.2 / 8 = 0.4 s
T1,2021 COMP9334 39
Intuition of Little’s Law
• Little’s Law
• Mean#requests=Meanresponsetime*Meanthroughput
• If #requests in the device ⬆ , then response time ⬆ • Andviceversa
T1,2021 COMP9334 40
Applicability of Little’s Law
• Little’sLawcanbeappliedatmanydifferentlevels
• Little’slawcanbeappliedtoadevice • Navg(j)=Ravg(j)*X(j)
• AsystemwithKdevices
• Navg(j)=#requestsindevicej
• AveragenumberofrequestsinthesystemNavg=Navg(1)+….+ Navg(K)
• Averageresponsetimeofthesystem=Ravg • Wecanalsoapplyittoanentiresystem
• Navg=Ravg*X(0)
T1,2021 COMP9334 41
T1,2021 COMP9334 42
Using Little’s Law (2)
queue server
• The device completes on average 8 requests per second
• On average, there are
• 3.2requestsinthedevice • 2.4requestsinthequeue • 0.8requestsintheserver
• What is the mean waiting time and mean service time?
• Hint: You need to draw “boxes” around certain parts of the device and interpret the meaning of response time for that box.
T1,2021 COMP9334 43
Using Little’s Law (2)
queue server
• The device completes on average 8 requests per second • On average, there are
• 3.2requestsinthedevice • 2.4requestsinthequeue • 0.8requestsintheserver
• What is the mean waiting time and mean service time?
T1,2021 COMP9334 44
• MeanthroughputX=8requests/s • Meanwaitingtime=2.4/8=0.3s • Meanservicetime=0.8/8=0.1s
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. From beginning of Chapter 3 to Section 3.2.4.
• Alternative 2: You can read Harcol-Balter, Chapter 6. The treatment is more rigorous. You can gross over the discussion mentioning ergodicity.
• Little’sLaw(Optional)
• I presented an intuitive “proof”. A more formal proof of this well known Law is
in Bertsekas and Gallager, “Data Networks”, Section 3.2
• Revisionquestionsbasedonthisweek’slectureareavailablefromcourse
web site
T1,2021 COMP9334 45