COMP5416代做、代写Java，c/c++程序设计

日期：2023-09-09 09:40

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).