! COMP9334 - Capacity Planning of Computer Systems and Networks

Term 1, 2022

SAMPLE Final Examination

(Note: The following instructions are mostly identical to what you will see in the final exam.)

Instructions:

1. Time allowed – 2 hours, plus 15 minutes.
2. Total number of questions to be answered – 10. Answer all questions.
3. Total marks available – 100 marks, worth 50% of the total marks for the course.
4. Marks available for each question are shown in the exam.
5. Students are advised to read all of the examination questions before attempting to
answer the questions.
6. This exam cannot be copied, forwarded, or shared in any way.
7. Students are reminded of the UNSW rules regarding Academic Integrity and
Plagiarism.
8. Your work will be saved periodically throughout the exam and will be automatically
submitted when the test ends provided you are connected to the internet.
9. DO NOT submit this sample exam. If you submit this exam, you will no longer be able
9. In answering all the questions, it is important for you to show your intermediate steps
and what arguments you have made to obtain the results. You need to note that both
the intermediate steps and the arguments carry marks. Please note that we are not just
interested in whether you can get the final numerical answer right, but we
are more interested to find out whether you understand the subject matter. We do that
by looking at your intermediate steps and the arguments that you have made to obtain
the answer. Thus, if you can show us the perfect intermediate steps and the in-between
arguments but got the numerical values wrong for some reason, we will still award you
marks for having understood the subject matter.
10. You may use these formatting shortcuts in your answers if you want:
Instead of subscript P123 , you may write P_{123} etc.
Instead of superscript 106, you may write 10^6 etc.
Instead of the Greek alphabet λ, you may write lambda etc.
11. This is an open-book and open-web examination.
to access it.
Consider a computer system which is used to support a website. The system,
depicted in the figure below, consists of three devices: one distributor and two
servers. Each device consists of a processor and a buffer.
When an HTTP request arrives at the website, it is first processed by the
distributor. The request is then sent to one of the two servers for processing.
With probability 0.4, the request is sent to Server 1. With probability 0.6, the
request is sent to Server 2. Once a request is processed by either server, the
request is completed and the HTTP response is sent to the user.

During the routine operation of the web site, the following measurements are
collected:
The web site is found to process 72,000 HTTP requests in one hour.
The average number of HTTP requests in the distributor is 0.2.
For Server 1, there is on average 3.2 HTTP requests waiting in the buffer
for processing, and each HTTP request requires a service time of 100
milliseconds.
For Server 2, there is on average 8.1 HTTP requests waiting in the buffer
for processing, and each HTTP request requires a service time of 75
milliseconds.


Question 1
Read the panel on the left and then answer the questions below.

This question consists of 3 parts: Parts (a), (b) and (c).

Part (a)
What is the utilization of Server 1?

Part (b)
What is the average waiting time of Server 1?

Part (c)
What is the average response time of Server 1?

Answer all three parts in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 10
Consider a non-preemptive priority single-server queueing system with 2 classes
of jobs. The two classes of jobs will be referred to as Class A and Class B where
the jobs in Class A have non-preemptive priority over the jobs in Class B. Jobs
from Class A obey Poisson arrival with mean arrival rate and exponential
service time distribution with mean service time . Jobs from Class B obey
Poisson arrival with mean arrival rate and exponential service time
distribution with mean service time . You can assume that the following 4
probability distributions are independent of each other: inter-arrival time
distribution of Class A jobs, inter-arrival time distribution of Class B jobs
and service time distributions of Class B jobs.

The queueing system consists of 2 queues, which will be referred to as Queue A
and Queue B in this question. Each queue consists of 1 buffer space.

Assuming that Queue A is used to buffer jobs from Class A alone and Queue B
is used to buffer jobs from Class B alone. This non-preemptive priority queueing
system can be modelled by a continuous-time Markov chain. The state of the
Markov chain is the three tuple where is the number of jobs in
Queue A, is the number of jobs in Queue B, and is number of jobs in the
server.
2 Question 2
What is the transition rate from state (0,0,0) to (0,0,1)? Explain your answer.
Show your working in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 2
3 Question 3
The state (0,0,1) can transit into three possible states. Write down these states in the box
below. In addition, what are the transition rates of these transitions? Explain your answer.
Show your working in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 6
4 Question 4
For the state (1,1,1), what are the states that can either transit into (1,1,1) or out of (1,1,1)?
Write these states down in the box below and explain your answer.

Furthermore, what are the corresponding transition rates? Explain.
Show your working in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 6
5 Question 5
This system has five possible states, namely (0,0,0), (0,0,1), (0,1,1), (1,0,1) and (1,1,1)

Let P(0,0,0) denote the steady state probability that the state is (0,0,0) etc.

Derive a mathematical expression for the mean waiting time of the jobs in Class A in terms of
P(0,0,0), P(0,0,1) etc.

Show your working in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 6
Question 6
This question has four parts: Parts (a), (b), (c) and (d). Answer these four parts in the box
below.

Part (a)
What is the mean time required to transmit a packet?

Part (b)
What is the second moment of the time required to transmit a packet?

Part (c)
What is the mean waiting time for the packets?

Part (d)
If you would like to reduce the mean waiting time to of the value that you have calculated in
Part (a), what is the minimum transmission rate that you need?

1
6
Consider a transmission link with a transmission rate of 10 Mbps (megabits per
second). Packets arriving at the transmission link obey Poisson distribution with
a mean arrival rate of 1500 packets per second. Measurement at the
transmission link shows that the mean packet size of the packets is 830 bytes
and the second moment of the packet size is 10 bytes .

You may assume that the transmission link has sufficiently large buffer space so
packet loss does not occur in this system.

6 2
Show your working for all the four parts in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 12
7 Question 7
Consider the computer system shown in the figure below which consists of a pre-processor,
n servers and a join point.



When a client request arrives at the system, it will first be processed by the pre-processor.
The pre-processor splits each request into n sub-tasks and sends one sub-task to each
server for further processing. Each server, after it has finished a sub-task, will forward the
result to the join point (shown as a triangle in figure above.). When the join point has
received all the results for a request from all the servers, it will deliver the results to the client.


Given the following:
Each request requires a mean processing time from the pre-processor.
The processing time required by each sub-task is independently and identically
distributed, with an exponentially distributed processing time with mean T
The join point takes negligible amount of time to send the results to the client.
The system is used to serve m interactive users with mean thinking time of T
Using operational analysis, derive the upper bound on the throughput of the system in terms
of m, n, T , T , T .
Tp
s .
t.
p s t
Show your working in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 14
8 Question 8
A computer system consisting of 1 CPU and 1 disk is used for interactive application with 3
terminals. Under the current operating condition, the throughput of the system is 0.4531 jobs
per second. The following table shows the response time, utilisation and device throughput
of the CPU and the disk when there are 3 interactive terminals.

CPU Disk
Response time
(seconds)
0.2196 0.4035
Utilisation 13.59% 43.50%
Device throughput (per
second)
0.6796 1.4499

The average think time of the interactive users is 5 seconds.

The manager in charge of the system would like to add 1 more interactive terminal to the
system, i.e.~to increase the total number of interactive terminals to four (4). What will be the
mean system throughput if the number of interactive terminals is 4?

You can assume that the visit ratio, the service time per visit to each device, as well as the
think time remain unchanged when the number of interactive terminals increases. You can
also assume that the service time required by each interactive user is exponentially
distributed.

Hint: Think about how the Mean Value Analysis is derived.
Show your working in the box below.

Format " $
Σ #
Words: 0
Maximum marks: 14
Question 9
Formulate an integer programming problem which determines:

1. How much new capacity must be added to each existing link; and,
2. How the traffic demands are to be routed,
so that the total expansion cost is minimised.

You will need two sets of decision variables. The first set of decision variables is where
is the amount of capacity that you need to add to the existing link .

The second set of decision variables is where

xuv
xuv euv
yij,uv
yij,uv = { 1 if the traffic from node i to node j uses link euv0 otherwise
A communication carrier has an existing network. We will model this network as
a directed graph where V is the set of nodes in the network and E is the
set of directed links in the network. The network has n nodes (i.e. the size of the
set V is n) and we will denote the nodes as 1,2, ..., n. We will denote the directed
link from node i to node j, if it exists, as . The set E contains all the directed
links that exist in the carrier's network. The current capacity of directed link is
Mbps.

The communication carrier expects that in two years' time, its (directed) traffic
demand from node i to node j will be Mbps, where i, j = 1,...,n and . The
manager of the carrier knows that the existing network capacity will not be able
to deal with this new traffic demand. He decides to increase the capacity of the
existing links in order to deal with the new demand. In order words, no new
links will be added to the network.

In addition, the carrier also has the following restrictions:
For all possible permutations of (i,j) where i, j = 1,..,n and , the
(directed) traffic demand from node i to node j must be routed on only one
path.
The utilisation of each link in the network must be lower than where
is a given constant. Note that the utilisation of a link is defined
as the total amount of traffic on the link divided by the capacity of the link.
Assuming that the cost to add a capacity of x Mbps to an existing link is p times
of x where p is a constant.
The total cost to expand the network capacity is the sum of the cost to expand
each link.
eij
eij
cij
tij i ≠ j
i ≠ j
r
r ∈ (0, 1)

Fill in your answer here

Format " $
Σ #
Words: 0
Maximum marks: 20
Consider the traffic engineering problem that we discussed on pages 26, 28 and
29 of Week 9B's lecture. For that traffic engineering problem, you are given

A directed graph (N,E) where N is the set of nodes and E is the set of
edges
There are m flows (which are indexed by k = 1, 2, ... , m) to be routed
Flow k has a size of , with source node and destination
It costs for a unit of flow to use directed edge
The capacity of directed edge is
In the lecture, we formulated an integer programming (IP) problem to minimise
the total cost while ensuring each flow uses only one path and the total flow on a
directed edge does not exceed its capacity. The IP uses the decision variables
where


The formulation of the IP is as below.






fk sk dk
cij (i, j)
bij
xijk
xijk = { 1 if flow k uses directed edge (i, j)
0 otherwise
Question 10
This question is build on the integer programming problem that was discussed in Week 9B's
lecture. You should first read the panel on the left and then come back here to read the
question.

You are given that the delay of link is . We define the total delay of a path to be the
sum of the delays of the links in the path.

You want to impose the constraints that for each (where = ), the total delay of
the path that flow uses must not exceed a given constant . Explain how these constraints
can be formulated.

Show your working in the box below.

(i, j) tij
k k 1, 2, . . . ,m
k u
Format " $
Σ #
Words: 0
Maximum marks: 10