COMP9334 Project, Session 1, 2018:
Updates to the project, including any corrections and clari cations, will be posted on the
subject website. Make sure that you check the course website regularly for updates.
Change log
Note: New text is shown in red coloured font. Deleted text is retained and shown as strikethrough,
e.g. this is deleted text.
Version 1.1. (22 April 2018) Changes in: Table 4, Section 3.1.2, Section 5.2.3.
Version 1.2. (3 May 2018) Changes in: Section 3.1.4, Table 1
1 Introduction and learning objectives
This project is inspired by the research work reported in the article Exact analysis of the M/M/k/setup
class of Markov chains via recursive renewal reward [1]. The paper studies a dilemma faced by
data centre operators on trading o energy consumption and latency. The key question that the
paper asks is whether one should turn an idling server o . The advantage of turning o an idling
server is that it can save a lot of energy. However, if an o server is needed again, it has to be
setup and this adds latency to job processing. In this project, you will use simulation to try to
answer a similar research question.
In this project, you will learn:
1. To apply discrete event simulation to a performance analysis problem
2. To use statistically sound methods to analyse simulation outputs
2 Support provided
If you have problems doing this assignment, you can post your question on the message board
on the subject website. We strongly encourage you to do this as asking questions and
trying to answer them is a great way to learn. Do not be afraid that your question
may appear to be silly, the other students may very well have the same question!
3 Description of the computer system
Figure 1 depicts the computer system to be considered in this project. The system consists of a
dispatcher as its front-end and m servers at its back-end. There is only one queue and it is located
at the dispatcher; there are no queues at the computer servers. You can assume that:
Figure 1: Architecture of a computer system. The front-end consists of a dispatcher and the
back-end has a number of computer servers. There is a queue at the dispatcher. There are no
queues at the servers.
The dispatcher has su cient memory so the number of waiting room for queueing can be
considered to be in nite.
The communication between the dispatcher and the server is fast. This means that once a
server has nished working on a job, it can inform. the dispatcher immediately. It also means
that it takes the dispatcher negligible time to send a job to a server.
The dispatcher takes negligible time to make a decision.
We discussed the multi-server queue in Week 3’s lecture. In the setup in Week 3, all servers
remain on at all times. A server can only have two states: busy or idle. An arriving job will be
served immediately if there is an idling server, otherwise it will join the queue at the dispatcher.
Once a server has nished processing a job, it will serve the job at the front of the queue if there
is one. In particular, if the inter-arrival time and service time probability distributions are expo-
nential, then we learnt in Week 3 that this type of multi-server queue could be modelled as an
M/M/m queue.
Energy consumption is a major issue faced by data centres. A drawback of the multi-server
queue described in the last paragraph is that the idling servers consume power but are not doing
useful work. There have been various proposals to reduce the power consumption and they are
discussed in Section 3 of [1]. We recommend that you go through Sections 1 and 3 of [1] to get a
better understanding of the various proposals because reading those sections will help you to put
the project work into context. For this project, you will focus on the setup/delayedo mode of
operation which is similar (but not identical) to that discussed in Section 3.2 of [1].
3.1 The setup/delayed system
We will now explain the setup/delayedo mode of operation that is used in this project.
2
3.1.1 Server state
In this project, a server can have four states:
The OFF state means the server is powered o . A server in the OFF state cannot process
a job.
If a server in the OFF state is powered on, then it enters the SETUP state. In this state,
the server is in the process of booting up. A server in the SETUP state cannot process a
job. We will use the term setup time to refer to the time needed to boot up the server; this
is the time from the moment the server is switched on to the moment the setup is nished.
Once the setup is nished, the server can start to process jobs. We assume in this project
that the setup time is deterministic.
The BUSY state means the server is processing a job.
After a server in the BUSY state has nished processing a job, it will check whether there
is a job waiting at the dispatcher. If the dispatcher queue is empty, the server will enter
the DELAYEDOFF state. When a server enters the DELAYEDOFF state, it will start
a countdown timer. The initial value of the countdown timer is denoted by Tc which is
a positive value. During the DELAYEDOFF state, the server is still powered on and the
dispatcher may send a job to a server in the DELAYEDOFF state to process. There are
two possibilities to consider, depending on whether the dispatcher sends a job to the sever
in the DELAYEDOFF state. Let us discuss these two possibilities separately:
{ If the dispatcher does not send any jobs to a server in the DELAYEDOFF state before
the countdown timer expires (i.e. reaches the value of zero), then the server will power
o itself when the countdown timer expires. In other words, at the time when the
countdown timer expires, the server will go from DELAYEDOFF state to OFF state.
{ If the dispatcher sends a job to a server in the DELAYEDOFF state before the count-
down timer expires, the server will change its state to BUSY and process the job. The
countdown timer will be removed. Note that a server may cycle between the BUSY
and DELAYEDOFF states many times; each time when the server goes from BUSY to
DELAYEDOFF state, the countdown timer is initialised to Tc.
3.1.2 Handling arrivals
Having described the four possible server states, we will now explain what happens when a job
arrives at the dispatcher. It is important to remember that the dispatcher cannot send a job to
a server in OFF, SETUP or BUSY state. However, the dispatcher can send a job to a server in
the DELAYEDOFF state for processing. It can also send a job to a server that has just nished
setting up (i.e. the end of SETUP) or nished processing a job; these two possibilities will be
discussed later on.
When a job arrives at the system, the dispatcher will use the following rules:
1. If there is at least a server in the DELAYEDOFF state, then the dispatcher will send the
arriving job to a particular server in the DELAYEDOFF state. The choice of the server
depends on the value of the countdown timer of the servers at the time when the job arrives
at the dispatcher. The dispatcher will send the job to the server with the highest value in
the countdown timer. The selected server will cancel its countdown timer and change its
state to BUSY.
2. If there are no servers in the DELAYEDOFF state, then the dispatcher will check whether
there are servers in the OFF state. If there is at least a server in the OFF state, then the
dispatcher will select one of them and turn it on. There are no speci c criteria to choose an
OFF server, so any one of them can be chosen. The state of the selected server will change
3
from OFF to SETUP. The dispatcher will put the job in at the end of the queue and mark
the job. The jobs in the queue can be either MARKED or UNMARKED. A job in the queue
is MARKED if it is waiting for a server to be setup. Hence, a simple consistency check is
that the number of MARKED jobs in the queue should equal to the number of servers in
the SETUP state.
3. If there are no servers in the DELAYEDOFF state and there are no servers in the OFF
state, then it means all the servers are either in BUSY or SETUP state. In this case, the
job is put in at the end of the queue and is UNMARKED.
3.1.3 Handling departures
We now describe what happens when a job departs from a server. There are two cases to consider
depending on whether there is a job in the queue in the dispatcher. In the following description,
the server is referring to the server that has just completed processing of a job.
1. If the dispatcher queue is empty, then the server will change its state from BUSY to DE-
LAYEDOFF. It will also start the countdown timer. The initial value of the countdown
timer is Tc. In this project, you can assume that Tc is deterministic.
2. If there is at least one job at the queue, the server will take the job from the head of
the queue. The state of the server remains BUSY. The other actions of the dispatcher
depends on whether the job that has been sent to the server for processing is MARKED or
UNMARKED.
(a) If the job is UNMARKED, then it means this job is not waiting for a server to be setup.
There is no further action to be taken.
(b) If the job is MARKED, then it means this job is waiting for a server which is still in
the process of setting up. Since the dispatcher is sending this job to a server which is
di erent from the one that the job is waiting for, the dispatcher has to decide whether
the set up process should continue. The rationale is that we do not wish to complete
the setup and nd that the newly setup server has no job to process. In this case, the
dispatcher will check whether there is an UMARKED job in its queue. If there is one,
it means there is a job in the queue which is not associated with a server in the SETUP
state. The dispatcher’s actions are:
i. If there is at least a UNMARKED job, then the dispatcher will choose the rst
UMARKED job and change it to a MARKED job.
ii. If there are no UNMARKED jobs, then the dispatcher will need to turn o a server
that is in the SETUP state. In this case, the dispatcher will look at how much
time the servers in the SETUP state still need to complete setting up and it will
choose to turn o the server with the longest remaining setup time. The state of
the selected server will change from SETUP to OFF and you can assume that this
change of state is immediate. You may ask how the dispatcher knows what the
remaining setup time is. Note that setup starts when a job arrives at the dispatcher
and there is an OFF server, so the dispatcher knows the time setup begins. It also
knows the time when setup nishes because we assume setup time is deterministic.