COMP5416/4416 Assignment 2 2023 S2
Due: 29/Oct/2023 23:59
8 questions. Q1-Q4, 10 points each. Q5-Q7, 20 points each.
1. M/M Queue. 10%. Given arrival rate λ = 6 unit/s and service rate μ = 3 unit/s. Analyse
M/M/3/6 queue. Calculate (1) the stationary distribution of the queueing system, and (2) the
probability that a new arrival is dropped. (3) In an M/M/1 queue, λ > μ is not allowed. Why is
λ > μ allowed in an M/M/3/6 queue?
2. Packet scheduling. 10%. Consider a queueing system below. It takes one second to process
one packet.
(1) Assuming FIFO service, indicate the time at which packets 2 through 12 each leave the
queue. What is the average of this delay over all 12 packets?
(2) Now assume a priority service and assume that odd-numbered packets are high priority,
and even-numbered packets are low priority. Indicate the time at which packets 2 through 12
each leave the queue. For each packet, what is the delay between its arrival and the beginning
of the slot in which it is transmitted? What is the average of this delay over all 12 packets?
(3) Now assume weighted fair queueing (WFQ) service. Assume that odd-numbered packets
are from class 1, and even-numbered packets are from class 2. Class 1 has a WFQ weight of 2,
while class 2 has a WFQ weight of 1. For each packet what is the delay between its arrival and
its departure? What is the average delay over all 12 packets?
(4) What do you notice about the average delay in all cases? Why?
3. Weighted fair queue. 10%. Alice, Bob, and Chris are three users sharing one bottleneck
link with 100 Mbps. We use a weighted fair queue to guarantee that Alice, Bob, and Chirs
should get 40 Mbps, 35Mbps, and 25Mbps respectively. What are the weights of the weighted
fair queue for the three users? Then, Bob does not have anything to transmit, but Alice and
Chris have many packets to transmit. What are the transmission rates of them using the same
weighted fair queue in the system?
4. Token bucket. 10%. The following figure shows a token bucket scheduler. It consists of a
bucket which can accommodate 3 tokens and a queue which can accommodate infinite
packets. The arrival of packets follows Poisson process with rate 𝜆𝜆 > 0. The arrival of tokens
follows Poisson process with rate 𝜇𝜇 > 0, which is independent of the arrival of packets. As
discussed in the class, each packet consumes exactly one token and the packets are served by
the first-in-first-out principle. If there is no token in the bucket, packets will wait at the queue.
Otherwise, each packet consumes one token and leaves the system immediately. If the bucket
is full, new token arrivals will be dropped. The system reaches the steady state after a
sufficiently long time.
Let 1, 2, 3, 4, … denote the states where there are 1, 2, 3, 4… packets in the buffer. Let -1, -2,
-3 denote the states where there are 1, 2, 3 tokens in the bucket. Let 0 denote the state where
there are 0 packet and 0 token. Draw the state transition diagram of the system. Compute the
stationary probability that there are at least 1 token in the bucket. (Hint: it is very similar to an
M/M/1 queue, but the states are left-shifted by 3.)
5. BER vs SNR. 20%. We aim to plot BER vs SNR curves of two modulation schemes in this
question.
(1) BPSK. In wireless communication, we can transmit 0 and 1 through signals –1 and 1
respectively. Both –1and 1 signals have power of 1, so that the mean signal power is 1. This is
called Binary Phase Shift Keying (BPSK). Due to the existence of noise, the received signal is
–1+n or 1+n respectively, where n is the noise term. n follows Gaussian distribution
n~N(0, σ2). σ2 is the power of the noise, and thus 1
σ2 is SNR. If the received signal is ≥ 0, it
is decoded as 1; if the received signal is < 0, it is decoded as 0. We assume that 0 and 1 are sent
with equal probabilities. Compute average BER vs SNR of BPSK when SNR =
[0,5,10,15,20,25] dB. Hint: What is dB?
(2) 4PAM. Now we consider another modulation scheme, where each signal can represent two
bits. We can transmit 00, 01, 11, 10 through signals –3, –1, 1, and 3 respectively. The mean
signal power of the signal is32+12+12+32
4 = 5. This is called 4 pulse-amplitude modulation
(4PAM). Still, due to the existence of noise, the received signal is –3+n, –1+n, 1+n, or 3+n
respectively, where n is the noise term. Still, n follows Gaussian distribution n~N(0, σ2). σ2
is the power of the noise, and thus 5
σ2 is SNR. If the received signal is in (−∞, –2], (–2, 0], (0,
2], and (2, ∞), it is decoded as 00, 01, 11, and 10 respectively. We assume that 00, 01, 11, and
10 are sent with equal probabilities. Compute average BER vs SNR of 4PAM when SNR =
[0,5,10,15,20,25] dB. Note that if 00 is decoded as 01, it is regarded as one-bit error; if 00 is
decoded as 11, it is regarded as two-bit error. To compute Q function, you can use Python
math.erfc() function. math.erfc() returns result of erfc function, and Q(x) = 1
2
erfc x
√2
(3) Plot the BER vs SNR curves of BPSK and 4PAM. Discuss why improved data rate can
cause higher BER.
If you use any form of programming to complete this task, you need to submit your code as
LastnameFirstBER.py.
6. Erlang. 20%. Erlang B Figure Establishment. In this task, you will need to establish Erlang
B Figure through two ways, by simulation and by calculation. Show your plotted figures as
your final answers. Your plotted figures should match one of the figures in the lecture slides.
The ranges of the figures: x-axis, λ
μ is from 0.1 to 100; y-axis, probability of blocking is from
0.001 to 0.1.
By simulation: You will need to build simulation on an M/M/m/m queue with arbitrary m.
You can reuse the codes in Week 6 Lab to simulate an M/M/m/m queue. Your Python code
must be submitted as supplementary material.
Let m = 1,2,3, … , 9; 10, 20,30, … ,90, 100. Let λ
μ = 0.1,0.2, … , 0.9; 1, 2,3, … ,9; 10, 20,30, …,
90, 100. You will need to find the simulated the probability of blocking under all m and λ
μ
values, and plot the Erlang B Chart (using log-log chart). You need to submit your Python
code as LastnameFirstSimulation.py.
By calculation: You will need to use Erlang B formulation to plot the chart. Still, let m =
1,2,3, … , 9, 10, 20,30, … ,90, 100. Let λ
μ = 0.1,0.2, … , 0.9, 1, 2,3, … ,9,10, 20,30, … , 90, 100.
You will need to find the calculated the probability of blocking under all m and λ
μ values, and
plot the Erlang B Chart (using log-log chart). You need to submit your Python code as
LastnameFirstCalculation.py.
7. Socket Programming. 20%. In this task, you will need to build a multicasting server for a
chatroom. Each client will first connect to the server. Then, if the client sends a message to the
server, all connected clients will receive the message. The client side is provided in Q7client.py.
An exemplary server side is running at “wbserver.cs.usyd.edu.au” and port number 34000. You
can use Q7client.py and change the serverName as “wbserver.cs.usyd.edu.au” to connect to the
exemplary server. (Need to use VPN if you are not at the University.) We do not provide the
code of the server, and your task is to re-build the server by yourself. Please note, only the
serverName and serverPort can be changed; anything else in the Q7client.py cannot be changed!
When you start the client, you will first input your name (e.g., “TestName”), and then you can
send your message (e.g., “Hello World!”). Then, all the connected clients will receive
“TestName: Hello World!”.
(1) Read the code of Q7client.py, and use it to connect to the exemplary server to understand
what functions it can provide. An example of results are shown below.
(2) Write the code of server by yourself. (Hint: your server should support multiple clients at
the same time, so that you need to establish multiple threads for each new client.)
(3) Run your server and at least three clients in your own computer and test if they can work
correctly. In this step, the server is run on your local machine so that the server’s IP address
should be 127.0.0.1. Also, the server socket should bind with port number 34000.
(4) After (3) Use one of the clients to send a message “Hello World!”. Use Wireshark to capture
what packets are sent from this client to the server and what packets are sent from the server to
all clients. Use screenshot to show that all clients receive the message.
You need to submit your server code in Python 3. You should name it as
LastnameFirstNameServer.py. You need to submit your Wireshark trace. You should name it
as LastnameFirstNameCapture.pcapng
We will test your server code by the following approach. We will run three Q7client.py
(without any change, i.e., with 127.0.0.1 and 34000) and your server code (without any change)
in one computer. You will get significant penalty if your submitted code does not work (e.g.,
we need to modify your code).
Submission instructions. In the “main file submission”, you can only upload your answers
in a single pdf file. In the “supplementary file submission”, zip all your codes and captures
in one file and upload.