COMP5416/4416 Assignment 1 2023 S2
Due: 10/Sep/2023 23:59
8 questions. Q1-Q5, 8 points each. Q6-Q8, 20 points each.
1. (8%) As shown in the figure below, a file of size F = 1000 + S bytes is transmitted on an end-to-end
connection over three links, where S is the last three digits of your student number. For example, if your
student number is 490123456, then S = 456 and F = 1456 bytes. Each link is 100 km. The signal
prorogation speed is 2×108 m/s. Assume that a header of 28 bytes (UDP header and IP header) is added
to each packet. The bandwidth of all links is R = 1 Mbps. The nodes use the store-and-forward scheme.
No packet is lost and there is no bit error in the transmission.
(1) How long does it take to transmit the file if the whole file is transmitted as a single packet.
(2) We break the file into smaller packets in the store-and-forward scheme. Assume that each time you
break the file to make a new packet, you have to add 28 bytes as the header of the new packet. What
should be the optimal number of the packets? What is the overall time to transmit the file with the
optimal number of packets?
2. (8%) Consider that you want to establish a new network in domain myuni.edu. You have two hosts
www.welcome.myuni.edu and www.home.myuni.edu with IP addresses labelled in the figure. Also,
you have the authoritative DNS server.
(1) What resource records (RRs) do you need to add in the DNS hierarchy? Where do you need to add
these RRs?
(2) Now that host 1 requests the IP address of www.welcome.myuni.edu. How is the IP address
addressed? How are the RRs in (1) used? Assume that the local DNS server dns.mypoly.com only
knows the root DNS server. Use iterative approach.
(3) Now that another host 2 requests the IP address of www.home.myuni.edu. How is this addressed.
This time the local DNS server dns.mypoly.com has known the IP addresses of TLD DNS server and
authoritative DNS server. Use iterative approach.
3. (8%). In this question, we consider the Tit-for-Tat algorithm in a P2P system. As shown in the figure
below, A and B are communicating with their top-4 partners in a P2P system. In this scenario, each peer
sends chunks to those four peers currently sending her chunks at highest rate. A’s uploading and
downloading data rates of the th partner are ! and ! respectively; B’s uploading and downloading
www.welcome.myuni.edu
111.111.111.15
root DNS server
authoritative DNS server
dns.myuni.edu
111.111.111.1
TLD DNS server
.edu DNS server
www.home.myuni.edu
111.111.111.16
requesting host 1
Local DNS server
dns.mypoly.com
requesting host 2
data rates of the th partner are !
" and !
" respective. For = 1,2,3,4, !, !
"
, !, !
" are randomly
distributed. They are independent random variables. Their distribution follows {1,2,3,4} Mbps with
probabilities ,
-. Now A optimistically unchoked B, with a sending data rate of %&. %& is a
random variable, independent of !, !
"
, !, !
"
. It also follows the distribution {1,2,3,4} Mbps with
probabilities ,
-. If A becomes a top-4 sender of B, B will start to serve A with a sending data
rate &% = %&. What is the probability that both A and B find each other a top-4 sender? Show your
mathematical derivations. Please note that top means “strictly greater than”.
" , then it is not regarded as top 4. %& must be strictly greater than one of the !
" values.
4. In the figure below, TCP Reno transmits packets with the given sequence numbers on channel. Each
packet is with the same size. At time T1, EstimatedRTT = 16 ms, and DevRTT = 8 ms. We use the
following update functions.
EstimatedRTT = 0.875 EstimatedRTT + 0.125 SampleRTT
DevRTT = 0.75 DevRTT + 0.25 |SampleRTT-EstimatedRTT|
TimeoutInterval = EstimatedRTT + 4 DevRTT
(1) Compute the value of X in ms.
(2) What ACK number does the receiver send at “ACK ?”?
(3) Suppose ssthresh=16 (segment) and cwnd=5 (segment) at T1. What is cwnd at the sender at T3,
T4, and T5?
5. (8%) Consider the following DHT networks. Transmission over each link takes 10 ms. The links are
directional as noted in the figures. When a key is found, the key holder creates a direct connection to
the query-originating node and transmits the key. The delay on that link can be ignored. For example,
if 1 is the query node and 5 is the key holder, then the delay is 40 ms. What is the average time to search
m
ACK(m+1)
m+1
10 ms 5 ms X 10 ms 10 ms 5 ms
m+2
ACK(m+2) ACK(m+3)
m+1
ACK ?
T1 T2 T3 T4 T5
for a key in the following network if the query node and key are distributed uniformly among the nodes?
Please note, the query node and the key holder may be the same and the delay is 0 in this situation.
6. (20%) In the Tutorial 1, question 1, we consider a system where two users are sharing the same
channel with utility as follows.
We have successfully derived three Nash Equilibria for this problem. We now want to investigate the
question one step further through a learning algorithm. The two users do not directly set their
transmission probability ( #, '), but to gradually “learn” the transmission probabilities iteratively. We
use ( #( ), '( )) to denote their learnt values after the th iteration.
Suppose at very beginning, ( #( ), '( )) = (0.3,0.7), where = 0. Then, the two users will update
their transmission probability as follows. For user 1, its utility is
#( ) = #( )(10 − 15 '( ))
Then, it will check that '( ) = 0.7 so that #( ) = #( )910 − 15 '( ): = −0.5 #( ). In order to
maximize #( ), #( ) should be as small as possible, and the optimal solution is #
∗
( ) = 0.
However, instead of directly setting #( + 1) to 0, #( + 1) can be updated as follows
#( + 1): = (1 − ) #( ) + #
∗
( )
where : = is the assignment operation. is a small value, called learning rate.
Similarly, user 2 will update accordingly
'( + 1): = (1 − ) '( ) + '
∗( )
The progress is repeated for iterations and we want to check how ( #( ), '( )) will change.
(1) Let =0.001, ( #(0), '(0)) = (0.3,0.7). Plot ( #( ), '( )) vs. where is from 1 to 10000. Does
the learning algorithm approach to a Nash Equilibrium after a large number of iterations?
(2) Now you can choose arbitrary valid ( #(0), '(0)) values. Does the learning algorithm approach to
a Nash Equilibrium after a number of iterations? Which Nash Equilibrium does it approach to? Discuss
how the initial values ( #(0), '(0)) will influence the final results.
[User 2 is a jammer] Now we consider another scenario that user 1 is a normal user but user 2 is a
jammer. That means, user 2’s target is to fail user 1’s transmission. If both are transmitting, user 2 will
gain a positive utility. However, if user 1 is not transmitting but user 2 is transmitting, user 2 will lose
its energy. The Utility table is as follows:
(3) Use a similar approach in the tutorial 1; calculate the transmission probabilities of ( #, ') of the
two users in the new case when a Nash Equilibrium is reached.
(4) Repeat the progress of (1) and (2) for the new case.
(5) Discuss how Nash Equilibrium in the new case (user 2 is a jammer) is different from Nash
Equilibrium in the original case (both users are normal users). (bonus point)
7. (20%) In this task, you will run a Wireshark experiment. Please follow the following procedure and
answer questions.
Please note that you will need to connect to VPN if you are not on campus. You will need to use Cisco
AnyConnect. You need to choose the correct interface in Wireshark indicating the VPN you are using.
Otherwise, you cannot see the correct packets captured.
You are only allowed to use one of the following web browsers: Google Chrome, Firefox, Safari, or
Microsoft Edge. Please update it to the latest version.
1) Open a web browser. Clear the cache of the browser.
2) Start up the capture of Wireshark packet sniffer.
3) Enter the following URL into your browser.
http://wbserver.cs.usyd.edu.au/A1.html
4) Your browser should display text and two images.
5) When the images are completely loaded, enter the following URL into your browser
http://wbserver.cs.usyd.edu.au/A2.html
6) When the images are completely loaded, refresh your browser (e.g., press F5).
7) When the images are completely loaded, stop Wireshark packet capture.
Questions
(0) What is the time (date, hour, and minute) that you capture the packets? What is the web browser
you use to complete this question? You will get 0 mark if you do not provide the time and browser.
(1) What is the IP address of the server that sends you the base web page?
(2) What is the IP address of the server that sends you the images?
(3) Is non-persistent HTTP or persistent HTTP employed? Why?
(4) What are the sizes of the images? How do you know that? You can only use the information provided
by Wireshark capture.
(5) In step 3), your browser has downloaded the images for the first time. These images may or may
not be re-downloaded again in the following steps. In step 5), did your browser send the request for the
images? If so, did the server send back the images to your browser again? In step 6), did your browser
send the request for the images? If so, did the server send back the images to your browser again? (You
should give screenshots.)
(6) Now you need to have a close investigation of the first image you have downloaded (when you
download the image USYD.jpg for the first time). Locate the first four bytes of the image in Wireshark.
Screenshot the packet and location of the first four bytes shown by Wireshark. Locate the last four bytes
of the image in Wireshark. Screenshot the packet and location of the last four bytes shown in Wireshark.
To help you locate the bytes, you may consider to convert the original image file into a byte-stream
format. You may use the following website https://www.onlinehexeditor.com/ to do so. (This step is
optional)
(7) Following (6), which one of the following statements is correct when you download USYD.jpg for
the first time. Give your screenshots to justify your answer.
(a) The image is downloaded by a single packet.
(b) The image is downloaded by multiple packets and the last packet includes HTTP response (200 OK)
and the last portion of the image.
(c) The image is downloaded by multiple packets. The last packet includes the last portion of the image.
Then, an HTTP response (200 OK) is received in a separate packet.
8. (20%) Consider the following scenario where two schools of one university are installing web caches
for users.
Inside each school, the one-way propagation delay from each host to the school’s gateway is 2ms. The
link bandwidth is assumed to be infinity (sufficient large). The link bandwidth from each school’s
gateway to the university’s gateway is 10Mbps, and one-way propagation delay is 4ms. The access link
bandwidth from the university’s gateway to the Internet is 20Mbps, and assume that the one-way
propagation delay from the gateway to any server in the public Internet is 6ms.
On average, the requests from each school to view the webpage (of the public Internet) arrive at the rate
of 1000 requests per second and the webpage is 1000 bytes (which fits exactly one packet). Ignore the
header size. The requests themselves are very small and we assume that they do not take any bandwidth.
To analyse the delay, we model the system as there are three queues in the system: the downlink from
the public Internet to the university’s gateway (Queue 1); the downlink from the university’s gateway
to school A’s gateway (Queue 2); the downlink from the university’s gateway to school B’s gateway
(Queue 3). The queues are modelled as M/M/1 queues. In this question, we only consider the
propagation delay (uplink and downlink) and the waiting time at the three queues (downlink only). For
example, in Queue 2, the arrival rate is 1000 packets per second, and the service rate is #*×#*!
,*** = 1250
packets per second. The waiting time at the queue can be calculated #
#'-*.#*** = 0.004 s = 4 ms. For
simplicity, we also ignore the TCP setup delay. The propagation delays (uplink and downlink) are only
counted once.
(1) Without cache, what is the average overall delay for each user to derive its requested webpage?
Only the propagation delays (once) and the waiting delays at the queues are considered. All other delays
are ignored.
(2) After step (1), conditional GET can be used. 10% of the original requests can be addressed by 304.
We assume that these response messages do not take any bandwidth. Only propagation delay is counted
for these response messages. (We assume that these messages are with small size and they do not
experience waiting delays at the queues.)
(3) After step (2), caches can be installed at the school’s gateway, so that another 10% of the original
requests can be served by the schools’ proxies (proxies A and B). What is the average overall delay for
each user to derive its requested webpage? (In this question, 10% goes to the original server with 304,
10% goes to the proxy with 200, and 80% goes to the original server with 200).
(3) After step (2), cache can be installed at the university’s gateway, so that another 20% of the original
requests can be served by the university’s proxy (proxy U). (There are no schools’ proxies.) What is the
average overall delay for each user to derive its requested webpage? (In this question, 10% goes to the
original server with 304, 20% goes to the proxy with 200, and 70% goes to the original server with 200).
(4) After step (2), caches can be installed at all gateways (proxies A, B, and U). a% of the original
requests can be served by the schools’ proxies, and b% of the original requests can be served by the
university’s proxy. However, due to the limited storage owned by the university’s ICT department, we
have 2a%+b% ≤ 20%. Calculate the average overall delay for each user to derive its requested webpage
as a function of a and b and find the optimal a and b. (In this question, 10% goes to the original server
with 304, a% goes to the school’s proxy with 200, b% goes to the university’s proxy with 200, and
90%−a%−b% goes to the original server with 200).