COMP5416: Advanced Network Technologies - Assignment 1: Equilibrium of Three Competing Transmissions
COMP 5416 Assignment 1 (2022)
Due: 10/September/2022, 23:59
Question 1 (Equilibrium of Three Competing Transmissions, 17%). Consider the following scenario where three mobile phones are competing to use the same channel. Each user independently decides either to transmit or not. There are 8 situations, and each user’s utility in each situation is listed below. If a user is the only one transmitting, she will get a utility of 10. If 2 or more users are transmitting simultaneously, no one is successful and all of them will get −5 utility. If a user is off, she will always get 0 utility. We aim to investigate the Nash equilibrium in this setting. Please note that in the presence of more than two users, Nash equilibrium is satisfied when no user can do better by unilaterally changing her own strategy. In this question, Nash equilibrium is reached when the following conditions are all satisfied.
- If Users 2 and 3 do not change their strategies, User 1 cannot achieve a better utility by changing her strategy.
- If Users 1 and 3 do not change their strategies, User 2 cannot achieve a better utility by changing her strategy.
- If Users 1 and 2 do not change their strategies, User 3 cannot achieve a better utility by changing her strategy.
Situation User 1 User 2 User 1 Off Off Off 2OffOffOn 3OffOnOff 4OffOnOn 5 On Off Off 6OnOffOn 7OnOnOff 8 OnOnOn
Consider the mix strategy, where p1, p2, and p3 denote the probabilities that Users 1, 2, and 3 are “on”. Calculate all possible values of (p1, p2, p3) when Nash Equilibrium is reached.
Hint: p1(1 − p2)(1 − p3) is the probability that User 1 is on and Users 2 and 3 are off.
Question 2 (Web Cache, 17%). Consider the following scenario where two schools of one university are installing web caches for users. (You only need to review the contents discussed in lectures in weeks 1–3 to complete this question.)
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 2ms. 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 8ms.
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). 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 10×106 = 1250 packets per second. The waiting time at the queue can be calculated 8000
(1) Without cache, what is the average overall delay for each user to derive its requested webpage? (Only the propagation delays and the waiting delays at the queues are considered. All other delays are ignored.)
(2) Now, caches can be installed at the school’s gateway, so that 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?
(3) Now, cache can be installed at the university’s gateway, so that 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?
(4) Now, 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. (Note, a% and b% are defined with respect to the original requests, do not use (1−a%)(1−b%), but to use (1−a%−b%) to calculate the rest of the requests served by the original Internet servers).
Question 3 (Delay and Loss, 17%). 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 at the beginning. The nodes use the store-and-forward scheme. (Ignore processing delays at each node.)
(A) What is your student number? Warning: If you use another student’s number as S value to answer the question, the following sub-questions will not be marked and you will get 0 in this question.
(B) How long does it take to transmit the file if the whole file is transmitted as a single packet. No packet is lost and there is no bit error in the transmission.
(C) Now assume that the bandwidth of link B − C and C − D become 0.5 Mbps. No packet is lost and there is no bit error in the transmission. Answer (C1)–(C3).
(C1) How long does it take to transmit the file if the whole file is transmitted as a single packet.
(C2) We would like to break the file into smaller packets to decrease the overall delay 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. Repeat (C1) when we break the file into N = 4 packets.
(C3) What should be the optimal size of the packets to have the minimum overall delay to deliver the whole file? Find the overall delay.
Hint: Since the link B − C has a smaller bandwidth compared with A − B, packets could be queued for some time!
(D) Still, the bandwidth of link B − C and C − D is still 0.5 Mbps. No packet is lost and but the error probability of each bit through the end-to-end transmission is 10 (D1)–(D3).
. Each bit (including the header) is flipped in each link independently. Answer
(D1) We still 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. The receiver will check the integrity of each received packet. If there is at least one bit error, the packet is discarded and all the information bits carried by the packet is lost. If there is no bit error, the packet is delivered to the application and all the information bits are delivered successfully. What is the expected number of information bits successfully delivered when we break the file into N = 4 packets.
(D2) What should be the optimal size of the packets to have the maximum expected number of information bits successfully delivered? Is this solution realistic?
Question 4 (P2P Tit-for-Tat, 16%). In this question, we consider a slightly modified Tit-for-Tat algorithm in a P2P system. As shown in the figure below, A and B are communicating with their top-6 partners in a P2P system. In this scenario, each peer sends chunks to those six (instead of four) peers currently sending her chunks at highest rate. A’s uploading and downloading data rates of the ith partner are ui and di respectively; B’s uploading and downloading data rates of the ith partner are u′i and d′i respective.Fori=1,2,...,6,ui,u′i,di,d′i arerandomlydistributed.Theyareindependentrandomvariables,followinguniform distribution in [0, 1] Mbps.
Now A optimistically unchoked B, with a sending data rate of rab. rab is a random variable, independent of ui,ui,di,di. It follows uniform distribution in [0,1] Mbps. If A becomes a top-6 sender of B, B will start to serve A with a sending data rate of rba = rab.
What is the probability that both A and B find each other a top-6 sender? Show your mathematical derivations.
Question 5 (TCP and max-min fairness,16%). In this task, you will investigate the performance of TCP and discuss if max-min fairness can be achieved. (In the lecture, we have already discussed the simple case where two TCP sessions are sharing one link.)
The network topology is shown above. Three TCP sessions (1, 2, and 3) are sharing the A − B and B − C links. TCP session 1 passes A−B; TCP session 2 passes B−C; and TCP session 3 passes A−B−C. TCP Reno is employed for each TCP session. The link capacity of A − B and B − C are 3.2 Mbps and 6.4 Mbps respectively. Each TCP packet size (MSS) is 500 bytes. We assume that the RTTs of TCP sessions 1, 2, and 3 are 100 ms, 100 ms, and 100 ms respectively. As discussed in the lecture, if the sum data rate of TCP sessions passing a link exceeds the link bandwidth, the link is congested and all TCP sessions passing the link will be “multiplicatively decreased”. If a TCP session does not pass any congested link, then it will be “additively increased”. Hint: you may use RTT . cwnd may not be an integer in MSS.
(1) At the beginning, the windows sizes (cwnd) of TCP sessions 1, 2, and 3 are 10MSS, 5MSS, and 1MSS respectively. Draw a figure to show cwnd vs time of the three TCP sessions. After a sufficient amount of time, can the average data rates of the TCP sessions realise max-min fairness? You may use Python/excel to plot the figure. Repeat the the above steps if the initial windows sizes (cwnd) of TCP sessions 1, 2, and 3 are 1MSS, 5MSS, and 10MSS respectively.
(2) Repeat (1) if the RTTs of TCP seasons 1, 2, and 3 are 100 ms, 100 ms, and 200 ms respectively.
Question 6 (DNS, 17%). Consider the network shown below. In the figure, DNSA is School A’s local and authoritative DNS server and DNSB is server B and B’s authoritative DNS server. Server B is Server B’s duplicated server (mirror) so that it is fine for a client to visit B instead of B. TLD is the TLD DNS server. Root is the Root DNS server. Assume that the one-way propagation delay through each network (shown as clouds in the figure) is labeled in the figure. Suppose a computer in school A requests a webpage from server B. The webpage fits into exactly one TCP packet (and there is no object in the webpage). The computer does not know the IP address of B or B so that it should request for the DNS service. The DNS request should visit all the Root, TLD, and authoritative servers for sub-questions (1) and (2).
(1) Using the iterative DNS resolution, and the IP address is translated as the IP address of B. What is the overall delay for the computer to get the webpage (including the DNS resolution delay and the delay to get the webpage by HTTP).
(2) Using the iterative DNS resolution, and the IP address is translated as the IP address of B. What is the overall delay for the computer to get the webpage (including the DNS resolution delay and the delay to get the webpage by HTTP).
(3) Now suppose that DNSA has already cached the IP addresses of B and B, so that the DNS request from any computer can be directly addressed by DNSA. In school A, there are 5000 requests per second to get the webpage from either B or B, and each request must follow a DNS resolution, i.e., no requesting computer knows the IP address of B or B. (We assume there is no other traffic in the network.) At servers B and B. An additional waiting delay is added as follows. If the request rate at B or B is λ requests per second, it will cause an additional delay of λ/200 (in ms). For load balancing purpose, for x% of the requests, DNSA can return the IP address of B; for the rest of 1 − x% of the requests, DNSA can return the IP address of B. Find the optimal x% so that the average overall delay (including the DNS resolution delay and the delay to get the webpage by HTTP) of clients in school A is minimised.
