COMP5416 Advanced Network Technologies - Assignment 2 (2022) : TCP, BER vs SNR, Network Policing, Queue and Erlang, Multi-thread Server and Viterbi Decoder
COMP 5416 Assignment 2 (2022)
Question 1 (TCP, 20%). In the following network, node A transmits packets that pass through B–D, and arrive at the destination E. The bit rate of all links is R = 1 Mbit/sec. The maximum packet size in the network is 1500 Bytes. Ignore the header size. The one-way propagation delay on each link is 20 msec.
(1) How long does it take to transmit N = 50 packets if TCP Reno is used. At the beginning, ssthresh is 6 segment size (9000 bytes). B–D use Store-and-Forward. No packet is lost. TCP timer does not expire. There is no bit-error in transmission. The size of ACK packets is negligible. The size of TCP header is negligible. Please also ignore TCP handshake delay and TCP termination delay.
(2) Repeat (1) when the sender transmits N = 250 packets.
Question 2 (BER vs SNR with different modulation schemes, 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 −1 and 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 is SNR. If the received signal is ≥ 0, it is decoded as 1; if the received signal is < 0, σ2
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 is 32+12+12+32 = 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 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. σ2
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 errors.
To compute Q function, you can use Python math.erfc() function. math.erfc() returns result of erfc function, and Q(x) = 1erfc(√x ).
(3) Plot the BER vs SNR curves of BPSK and 4PAM. You should derive a figure like Page 45 in the slides of Week 8. Discuss why improved data rate can cause higher BER. Discuss why the transmitted signal should be 00, 01, 11, and 10 at −3, −1, 1, and 3 respectively for 4PAM. Why not 00, 01, 10, and 11?
Question 3 (Network Policing, 20%). Alice, Bob, and Chris are three users sharing one bottleneck link. We utilise token buckets and queues to mark, schedule, and police their traffic. The bottleneck link has a bandwith of 4Mbps and it can buffer at most 3 Mbit data. Alice’s traffic is a VoIP session and Alice has declared 1 Mbps data rate and 1 Mbit burst size. Bob’s traffic is a VoIP session and Bob has declared 2 Mbps data rate and 1 Mbit burst size. Chris’s traffic is an HTTP session without declared data rate or burst size. Each packet has a size of 1000 byte. We prioritise the traffic as follows: Alice’s conforming traffic = Bob’s conforming traffic > Chris’s traffic > Alice’s non-conforming traffic = Bob’s non-conforming traffic.
Queue
(1) Design the policies at the two token buckets and the rule at the queue to satisfy the above requirements.
(2) The above design in (1) has one disadvantage: When both Alice and Bob are non-conforming, and the system has enough capability to handle some of the non-conforming traffic, it cannot handle the non-conforming traffic in a fair way. Discuss the following scenario: In a long period of time, Alice is transmitting with a constant rate of 2 Mbps; Bob is transmitting with a constant rate of 100 Mbps; Chris is inactive. There is no burst traffic. Discuss what will happen.
(3) Modify the design in (1) to address the issues in (2). If the system has capability to handle a partial or all non-conforming traffic, non-conforming traffic will be handled in a fair way. Please note that this is an open question. You can add token bucket, queue, or other modules at any place in the system. Your will get full mark as long as your design works correctly. Bonus marks may be granted if your design is smart.
Question 4 (Queue and Erlang B: Simulation, Analysis, and Application, 20%). In this task, you need to simulate and analyze an M/M/m/n queue with arbitrary m and n. You can reuse the codes in Week 6 Lab to simulate an M/M/m/n queue. You Python code must be submitted as supplementary material. You also need to theoretically compute the stationary distribution to verify your simulation or table-lookup.
Throughout this question, let the arrival rate be λ. Let the service rate of each server be μ.
(1) Let λ = 2 and μ = 3. What is the stationary distribution of an M/M/1/10 queue. Please figure out this result by both simulation and analysis.
(2) Let λ = 5 and μ = 1. What is the stationary distribution of an M/M/5/10 queue. Please figure out this result by both simulation and analysis.
(3) Use theoretical analysis only. What is the stationary distribution of an M/M/m/m queue (now n = m). What is the probability that a new arrival is blocked (dropped) by the system? This probability is defined as pb.
(4) Follow (3). Let μ = 1 and m = 10. If the blocking probability pb must be limited to 0.001, what is the maximum value of λ?
(5) Follow (3). Let λ = 10 and μ = 1. If the blocking probability pb must be limited to 0.001, what is the minimum value of m, i.e., the number of servers?
(6) Use the Erlang B table provided to verify your solution in (4) and (5). Which row and column shows the solution to (4) and (5)? Why?
Question 5 (Multi-thread Server: Implementation, 20%). You are given the complete code for the client in Lab in Week 8. Your task is to write the TCP server. The client code is in client.py. You must not modify this code. (However, you are allowed to change ServerName and ServerPort). Only Python 3 is allowed.
Different from the server in the lab, the new server must be able to serve multiple clients simultaneously. Please note that the server code in Week 8 can only accept one client! In order to serve multiple clients simultaneously. The server should run multiple threads. The server will establish a new connection socket to communicate with one new client, and each new connection socket will be managed by a new thread. You should self-study the following function: _thread.start_new_thread().
The following figure shows an example of server when two clients are sending images at the same time. The two connections are closed in the end, demonstrating that there are two concurrent transmissions before the first “Connection closed”.
You also need to capture the concurrent data transmission by Wireshark. In the example in the next page, we can see that the two clients are running at 192.168.0.3, with port numbers 60458 and 60462. The server is running at 192.168.0.4, with port number 12011. The throughputs of the two connections are both positive at around the 4th second.
Tasks and submissions:
(1) Build up a multi-thread server which can serve multiple clients at the same time. Submit your server-side Python code.
Submit your server code as Lastname_Firstname_Server.py. We will use the client in Week 8 to test against your server.
(2) Test your server with three clients sending images at the same time. Capture the packets by Wireshark at the server side. You are allowed to run the server and clients in one computer using localhost. Submit your Wireshark capture. Your capture file must be smaller than 10MB. Your capture will be ignored and will not be marked if it is greater than 10MB. Submit your capture as Lastname_Firstname_Capture.pcapng (or .pcap).
(3) In the main submission file, based on your capture in (2), plot the throughput vs. time of the three connections (similar to the figures in the next page). Show that they are operated in parallel. In the main file, you also need to give the three clients’ IP addresses, clients’ port numbers, server’s IP address, and server’s port number.
You overall mark will be zero if you do not submit code in (1), no matter if you submit (2) or (3).
You submission in (2) and (3) will be ignored and will not be marked if your submission in (1) does not work. You overall mark will be zero if your Wireshark capture in (2) does not match the throughput plots in (3).
Question 6 (Viterbi decoder and performance of convolutional code, bonus 10%. ). Consider the convolutional code with generators 111 and 101. The number of message bits is k = 20 and the number of coded bits is n = 40.
(1, 5%) Use Python to build a Viterbi decoder. The received bits (40 bits) should be in the following format in the first line of your code Receive=[0,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,1,0,1,1,1,0,0,1,1,1,0,0,0,1,0,0,0]. Your decoder should print the decoded bits, for example, [0,0,1,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,1]. Note that we will change “Receive” to test your decoder. You will get at most 3% if your decoder fails in any test case. Please only print out the decoded bits.
(2, 5%) The transmitted bits may be flipped due to channel bit errors. Under different bit error rate (BER), use simulation method to figure out the following probabilities: (1) pa (no error): the received bits (40 bits) are the same as transmitted bits. (2) pb (error correction): the received bits are different from transmitted bits but the decoded bits are the same as the original message bits. (3) pc (error correction failure): the received bits are different from transmitted bits and the decoded bits are different from the original message bits. Use a table to show pa , pb , and pc under different BER, where BER= 0.01, 0.02, . . . , 0.2. You need to submit your Python simulator. Note that if (1) fails, you will get zero in this subquestion.
