[SOLVED] COMP9334 2

Capacity Planning of Computer Systems and Networks
Week 1B: Queuing networks. Operational analysis

Last lecture

Copyright By Assignmentchef assignmentchef

Solve capacity planning by solving a number of performance analysis problems
Performancemetrics
Response time, waiting time Throughput
SingleserverFIFOqueue A server = A processing unit
T1,2022 COMP9334 2

This lecture
Queueing networks Operational analysis
Fundamentallawsrelatingthebasicperformancemetrics
T1,2022 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,2022 COMP9334 4

Pictorial representation of single server queues
Waiting line
Arriving customers
Arriving requests
Requests waiting to be processed
T1,2022 COMP9334 5

Pictorial representation of queues
Systems with m servers
Waiting line
T1,2022 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,2d02e2dnumCbOeMPr93o34fcustomersinthesystem 7

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,2022 COMP9334 8

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 nboundednumberostomersinthesystem
equilibrium, flow in = flow out throughput = arrival a
ning batch jobs overnight
T1,2022 COMP9334 9
Closed queueing network No external arrivals
Workload intensity
specified by customer
population
E.g. producing managerial reports

Open vs. closed queueing networks (2)
en queueing network
Open queueing network Possibly unbounded #customers
For stable equilibrium
Throughput = arrival rate
ernal arrivals
abase server for batch jobs
rkload intensity specified by arrival rate boundednumberofomersinthesystem
quilibrium, flow in = flow out throughput = arrival ra
ning batch jobs overnight
T1,2022 COMP9334
Closed queueing network Known #customers
Throughput depends on
#customers etc.

E.g. producing managerial reports

Open vs. closed queueing networks Terminology
en queueing network
ernal arrivals
abase server for batch jobs
rkload intensity specified by arrival rate boundednumberofomersinthesystem
quilibrium, flow in = flow out throughput = arrival ra
ning batch jobs overnight
Work in a closed queueing network is called jobs
T1,2022 COMP9334
Work in an open queueing network is called transaction

E.g. producing managerial reports

DB server mixed model
Theserverhasboth
Externaltransactions
Batchjobs
Mixed queueing network
T1,2022 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
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
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,2022 COMP9334 13
will On t ent c MP em, n Here work
g the e tw ber
ty of ck b
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,2022 COMP9334 14

Single-queue example (1)
#requests = A
#requests = C
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,2022 COMP9334 15

Motivating example
Observationperiod=1minute
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,2022 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,2022 COMP9334 17

Application of OA
Donthavetomeasureeveryoperationalquantities MeasureBtodeduceU-donthavetomeasureU
Consistencychecks
IfU1SX,somethingiswrong
Operationallawscanbeusedforperformanceanalysis Bottleneckanalysis(Lecture2A)
Meanvalueanalysis(Laterinthecourse)
T1,2022 COMP9334 18

Equilibrium assumption
OA makes the assumption that C=A
OratleastCA
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
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,2022 COMP9334

OA for QNs (contd)
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,2022 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)
COMP9334 22

Forced Flow Law
The forced flow law is
T1,2022 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
Thequantities20msand30msaretheindividualservicetimes.
D(j) = Service demand of a job at device j is the total service time required by that job
Theservicedemandforthisjob=20ms+30ms=50ms
T1,2022 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,2022 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,2022 COMP9334

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
YouveenoughinformationtofindD(j) The importance of service demand
Youwillseethatservicedemandisafundamentalquantityyou need to determine the performance of a queueing network
Youwilluseservicedemandtodeterminesystembottleneckin Lecture 2A
T1,2022 COMP9334 27

Server example exercise
# I/O per second
Utilisation
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,2022 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,2022 COMP9334
Measurement time = 1 hr
# I/O per second
Utilisation
Total # jobs=13680
= 36/3.8 = 108 / 11.4 = 9.47

Littles 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 Littles
Laws 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,2022 COMP9334 30

Littles Law (2)
X = Throughput of the device
Ravg = Average response time of the requests
Navg = Average number of requests in the device Littles Law (for OA) says that
Navg = X * Ravg
We will argue the validity of Littles Law using a simple example.
T1,2022 COMP9334 31

Consider the single sever queue example from Week 1
Request index
Arrival time
Service time
Departure time
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
246 10 1417
T1,2022 COMP9334 32

2 4 6 10 14 17
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,2022 COMP9334 33

246 10 1417
Let us assume these blocks are plasticine and let them fall to the ground. Like this.
246 10 1417
There is an interpretation of the height of the graph.
T1,2022 COMP9334 34

Request index
Arrival time
Service time
Requests waiting
to be processed
246 10 1417 time
Request being processed
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,2022 COMP9334 35

246 10 1417 time
waiting requests
Request being processed
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,2022 COMP9334 36

246 10 1417
Area = Average response time over [0,T] * Number of requests completed in [0,T]
waiting requests
246 10 1417 time
Area = Average number of requests in [0,T] * T
being processed
T1,2022 COMP9334 37

Deriving Littles 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 Littles Law.
Average number of requests in [0,T]
= Average response time of all reqs * Device throughput in [0,T]
T1,2022 COMP9334 38

Using Littles Law (1)
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 Littles Law, average response time = Navg/X = 3.2 / 8 = 0.4 s
T1,2022 COMP9334 39

Intuition of Littles Law
Littles Law
Mean#requests=Meanresponsetime*Meanthroughput
If #requests in the device , then response time Andviceversa
T1,2022 COMP9334 40

Applicability of Littles Law
LittlesLawcanbeappliedatmanydifferentlevels
Littleslawcanbeappliedtoadevice Navg(j)=Ravg(j)*X(j)
AboxwithKdevices
Box3inthenextslidehas4devices
Navg(j)=#requestsindevicej
AveragenumberofrequestsintheboxNavg=Navg(1)+.+ Navg(K)
Averageresponsetimeofthebox=Ravg
Response time of a box = Departure time from the box Arrival time
to the box
Wecanalsoapplyittoanentiresystem
Navg=Ravg*X(0)
T1,2022 COMP9334 41

T1,2022 COMP9334 42

Using Littles 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,2022 COMP9334 43

Using Littles 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,2022 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,, 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.
LittlesLaw(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
Revisionquestionsbasedonthisweekslectureareavailablefromcourse
T1,2022 COMP9334 45

CS: assignmentchef QQ: 1823890830 Email: [email protected]