COMP5416/4416 Assignment 1: DNS, Tit-for-Tat algorithm, Nash Equilibrium and Wireshark Experiment
COMP5416/4416 Assignment 1
8 questions. Q1-Q5, 8 points each. Q6-Q8, 20 points each.
-
(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? -
(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. -
(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 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”. If 𝑟%&=𝑑#"=𝑑'"=𝑑("=𝑑$", then it is not regarded as top 4. 𝑟%& must be strictly greater than one of the 𝑑!" values.
-
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?
-
(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 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.
-
(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)
- (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. 4) Your browser should display text and two images. 5) When the images are completely loaded, enter the following URL into your browser 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.
- (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).
