!
Cover page
COMP9334 – Capacity Planning of Computer Systems and Networks
Term 1, 2021
SAMPLE Final Examination
(Note: The following instructions are identical to what you will see in the final exam.) Instructions:
1. Time allowed: 2 hours and 15 minutes.
2. Answer all questions.
3. Marks available for each question are shown in the exam.
4. Total marks for this exam: 100 marks.
5. This exam is worth 50% of the overall assessment for this course.
6. Students are advised to read the examination questions before attempting to answer
the questions.
7. This exam cannot be copied, forwarded, or shared in any way.
8. Students are reminded of the UNSW rules regarding ACADEMIC INTEGRITY AND
PLAGIARISM.
9. Your work will be saved periodically throughout the exam and will be automatically
submitted provided you are connected to the Internet.
10. 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.
11. You may use these formatting shortcuts in your answers if you want:
Instead of subscript P123 , you may write P_{123} etc. Instead of exponent 106, you may write 10^6 etc. Instead of Greek alphabet , you may write lambda etc.
12. This is an open-book and open-web examination.
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 A and exponential service time distribution with mean service time . Jobs from Class B obey Poisson arrival with mean arrival rate B and exponential service time distribution with mean service time .
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 (nA,nB,nS) where nAis the number of jobs in Queue A, nB is the number of jobs in Queue B, and nSis 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
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 106 bytes2.
You may assume that the transmission link has sufficiently large buffer space so packet loss does not occur in this system.
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 16 of the value that you have calculated in Part (a), what is the minimum transmission rate that you need?
Show your working for all the four parts in the box below.
Format
“$
Σ#
Words: 0
7
Question 7
Consider the computer system shown in the figure below which consists of a pre-processor, n servers and a join point.
Maximum marks: 12
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 Tp 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 Ts . 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 Tt.
Using operational analysis, derive the upper bound on the throughput of the system in terms of m,n,Tp,Ts,Tt.
8
Question 8
Show your working in the box below.
Format
“$
Σ#
Words: 0
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.
Maximum marks: 14
Response time (seconds)
Utilisation
Device throughput (per second)
CPU Disk 0.2196 0.4035
13.59% 43.50% 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
A communication carrier has an existing network. We will model this network as a directed graph
The communication carrier expects that in two years’ time, its (directed) traffic demand from node i to node j will be tij Mbps, where i, j = 1,…,n and i ! j. 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 i ! j, 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 r where
r (0, 1) 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.
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 xuv where
xuv is the amount of capacity that you need to add to the existing link euv.
The second set of decision variables is yij,uv where
y
ij,uv
= {1 if the traffic from node i to node j uses link euv 0 otherwise
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 fk, with source node sk and destination dk
It costs cij for a unit of flow to use directed edge (i, j) The capacity of directed edge is bij
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 xijk where
xijk = { 1 if flow k uses directed edge (i, j) 0 otherwise
The formulation of the IP is as below.
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 (i, j) is tij. 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 k (where k = 1, 2, . . . , m), the total delay of the path that flow k uses must not exceed a given constant u. Explain how these constraints can be formulated.
Show your working in the box below.
Format
Σ#
“$
Words: 0
Maximum marks: 10