EEC173A/ECS152A-Computer Networks Winter 2021
Instructor: Chuah
Name: _____________________________
Student ID#: ________________________
24-hour take-home final assessment: March 17
Duration: 24 hours (March 17, 8:00am-March 18, 8:00am)
• This take-home final exam is open book, open notes. Discussing with others in any form is not allowed.
• Each problem may carry different number of points. Try to solve as many as you can.
• Show your reasoning clearly. If your reasoning is correct, but your final answer is wrong, you will receive partial credits. If you just show the answer without reasoning, and your answer is wrong, you may receive no points at all.
• Submit your multiple-choice and numerical answers for all questions on Canvas Quiz. At the end of the Canvas Quiz, there will be a question that allows you to upload a file to show your work. You can use this document to type your response and upload. Alternatively, you write your response on paper, scan it, and upload.
• Be sure to sign the statement of academic integrity on the second page.
• To avoid possible time out from Canvas Quiz or potential network connectivity problem, I highly recommend that you download the word or pdf version of the final so that you have an offline copy to work on either on your computer or with paper & pencil. Once you are confident about your answers, you can login to Canvas Quiz and enter your answers online, as well as upload a copy of your work (see #4 above).
Good luck!
Do not write in this box.
Problem Set
1
2
3
4
5
6
Total
Full Points
20
20
16
12
12
20
100
Points
Statement of academic integrity (please sign below)
As a student at UC Davis, I hold myself to a high standard of integrity, and by signing/accepting the statement below I reaffirm my pledge to act ethically by honoring the UC Davis Code of Academic Conduct. I will also encourage other students to avoid academic misconduct. I acknowledge that the work I submit is my individual effort. I did not consult with or receive any help from any person or other source. I also did not provide help to others. I may work with others only if the instructor gave specific instructions, and only to the extent allowed by the instructor. I understand that suspected misconduct on this assignment/exam will be reported to the Office of Student Support and Judicial Affairs and, if established, will result in disciplinary sanctions up through Dismissal from the University and a grade penalty up to a grade of “F” for the course. I understand that if I fail to acknowledge or sign this statement, an instructor may not grade this work and may assign a grade of “0” of “F”.
Signature (sign/type above this line)
Problem Set 1. Multiple Choice Questions (20 points)
In each of the following questions, select the correct answer.
Q1. (4 pt.) Circuit switching has the advantage of
• Predictable performance
• Not requiring a signaling phase
• Very efficient allocation of shared resources
• None of the above
Q2. (4 pt.) Consider an IEEE 802.11 network that use RTS and CTS frames. Suppose that node A and node B are hidden from each other and both nodes want to transmit to C. Both A and B can hear node C, and node C can hear both A and B. Which of the following statement is FALSE?
• Both node A and node B will send RTS packets, and these RTS packets may collide.
• If the RTS packets from A and B collide, node C will not respond with a CTS.
• After sending an RTS packet, if node A does not hear CTS after time-out, it will attempt to resend RTS.
• Even if node C sends a CTS after receiving RTS from node A (without collision), subsequent data transmission from A can still collide with transmission from node B.
.
Q3. (4 pt.) Consider the following deployment scenario of a network address translation (NAT) box.
Host 128.119.171.186
Host 128.119.171.186
Suppose that the host with IP address 10.0.1.16 sends an IP datagram destined to host 128.119.171.186. The source port is 3394, and the destination port is 80. Consider the datagram at step 2, after it has been transmitted by the router. What is the source and destination IP addresses for this datagram?
• Src: 10.0.1.16; Dest: 128.119.171.186
• Src: 10.0.1.16; Dest: 135.12.197.207
• Src: 135.122.197.207; Dest: 128.119.171.186
• Src: 128.119.171.186; Dest: 135.122.197.207
Q4. (4 pt.) Consider the router and the two attached subnets below (A and B). The number of hosts for each subnet is also shown below. Assume that this organization has been allocated the following address space: 210.85.80.0/23.
Assign subnet addresses to each of the subnets (starting with A, then B) so that the amount of address space assigned is minimal, and at the same time leaving the largest possible contiguous address space available for assignment if a new subnet were to be added. What will be the CIDR entry for subnet A (which has 21 hosts)?
• 210.85.80.0/23
• 210.85.80.0/24
• 210.85.80.0/27
• 210.85.80.0/28
Q5. (4 pt.) Consider the following figure. Assume distant vector routing algorithm is used to find the shortest paths. Which of the following statement is FALSE?
• Each node learns about the global topology through link state packets from other nodes.
• Node u learns about the best paths to other nodes by exchanging distance vectors with v.
• Node u will announce to v that its path costs to w, x, and y is infinity.
• Node x will announce to w that its path costs to v and u is infinity.
Problem Set 2. End-to-end Delay, Web, and File Distribution (20 points)
Q6. (4 pt.) Consider a packet of length 1,000 bytes that begins at end system A and travels over three links to a destination end system. These three links are connected by two packet switches. Assume that the propagation speed on all three links is 2.5 x 108 m/s, the lengths of these links are 5,000km 4,000km, and 1000km, respectively. The transmission rates for the three links are 2Mbps, 10Mbps, and 1Mbps, respectively. The switch processing delay is 3msec. What is the end-to-end delay?
Q7. (4 pt.) Browser Caching. Consider an HTTP server and client as shown in the figure below. Suppose that the RTT delay between the client and server is 20 msecs; the time a server needs to transmit an object into its outgoing link is 0.75 msecs; and any other HTTP message not containing an object has a negligible (zero) transmission time. Suppose the client makes 40 requests, one after the other, waiting for a reply to a request before sending the next request.
Assume the client is using HTTP 1.1 (persistent HTTP) and the IF-MODIFIED-SINCE header line. Assume 60% of the objects requested have NOT changed since the client downloaded them (before these 40 download requests are performed).
How much time elapses (in milliseconds) between the client transmitting the first request, and the completion of the last request (ignoring TCP connection setup time)?
Q8. (4 pt.) Explain how the choice of TTL value affects the performance of DNS cache performance.
Q9. (4 pt.) Suppose that we need to distribute a file of size F =2Gbits to 5 peers. Suppose the server, s, has an upload rate of u=100Mbps.
The 5 peers have upload rates of: u1 = 20 Mbps, u2 = 25 Mbps, u3 = 14 Mbps, u4 = 10 Mbps, and u5 = 15 Mbps
The 5 peers have download rates of: d1 = 29 Mbps, d2 = 33 Mbps, d3 = 15 Mbps, d4 = 20 Mbps, and d5 = 27 Mbps
What is the minimum time needed to distribute this file using client-server model? What is the limiting factor that contributes to the downloading time using client-server model: the ‘server upload rate’, ‘specific client download rate’, or the ‘combined upload of the clients and the server’?
Q10. (4 pt.) Consider the same network connectivity in Question 9. Now assume this file is distributed using peer-to-peer download. What is the minimum time needed to distribute this file? What is the root cause that contributes to the downloading time? The ‘server upload rate’, ‘specific client download rate’, or the ‘combined upload of the clients and the server’?
Problem Set 3. TCP (16 points)
Imagine a TCP session over wireless where the congestion window is fixed at 5 segments (congestion control is turned off and no fast retransmits). Segments may get lost but are not reordered. Assume the sender has a long file (hence continuous byte stream) to send. The receiver has close-to-infinite buffer and it sends an acknowledgment as soon as it receives a segment, i.e., acknowledgments are not deferred. Similarly, sender transmits a segment as soon as it can. Each segment carries 1000 bytes and the time to transmit a segment is 2 ms. Assume that transmission of ACK takes negligible time. Note that the retransmission timer for a segment is started after the last bit of the segment is sent. Assume Go-Back-5, and accumulative ACK are used.
Q11. Suppose two data segments with byte sequence numbers 3000 and 15000 are lost once during the transmission. How many segments get retransmitted under each of the following conditions?
• (4 pt.) Round trip time = 100 ms, Timeout = 102 ms
• (4 pt.) Round trip time = 100 ms, Timeout = 152 ms
Q12. Suppose acknowledgments corresponding to the above data segments are lost instead of the data segments. How many segments get retransmitted under the above conditions?
• (4 pt.) Round trip time = 100 ms, Timeout = 102 ms
• (4 pt.) Round trip time = 100 ms, Timeout = 152 ms
Problem Set 4. Network Layer (12 points)
Please justify your answers by qualitative or quantitative arguments or illustrations.
Q13. (4 pt.) This question explores how to set the (configurable) link weights in link-state routing protocols like OSPF and IS-IS inside a single Autonomous System (AS). How should the network operators set the link weights if their goal is to minimize the number of hops each packet traverses to reach its destination?
Q14. (4 pt.) Similar to the previous question, let us ponder how to assign link weights in link-state routing protocols like OSPF and IS-IS inside a single AS domain. How should the operators set the link weights to minimize the end-to-end delay the traffic experiences? Assume the network is lightly loaded, so queuing delay is insignificant.
Q15. (4 points) In the picture below, the nodes are routers, the edges are links, and the integers correspond to the link weight on each direction of the link. The arrows on the edges to show the shortest path from every node to the destination node D. Dotted lines are links that are not part of the shortest paths to node D.
A
B
C
D
E
F
G
H
I
5
5
5
5
5
5
9
9
10
10
11
11
A
B
C
D
E
F
G
H
I
5
5
5
5
5
5
9
9
10
10
11
11
Suppose the link F-I is overloaded with traffic. Identify a single weight change (on just one link) that would divert traffic from source I to destination D away from the F-I edge without affecting the path between any other source-destination pairs. Avoid any reliance on how routers choose between multiple paths with the same (smallest) cost.
Problem Set 5. Link-State Routing (12 points)
Q16-18. Consider the following network. The link cost represents the probability of failure for that link, e.g., pAC be the probability that link (A,C) fails = 0.01. Assume that failure events on different links are independent of one another. Consider how Dijkstra’s algorithm can be modified to find the most reliable path from node A to every other node on the graph, that is, path for which the probability that all its links stay intact during the connection’s lifetime is maximal.
Let Pk(A,B) be the probability that a path k from A to B = (A, …, B) remains intact (probability that the path does not fail). The goal is to find the best path k with maximum reliability, i.e., highest Pk(A,B).
Q16. (4 pt.) What is the probability for the path from A to E via C (ACE) being intact?
Q17. (4 pt.) What is the probability for the path from A to E via D (ADE) being intact?
Q18. (4 pt.) What is the most reliable path from A to E?
Problem Set 6. Link layer: Error Detection, MAC, & Self-Learning Switch (20 points)
Q19. (6 pt.) Suppose we want to transmit the message 10100101 and protect it from errors using the CRC polynomial x3+1. Encode the data bit sequence using the generator polynomial and give the code word.
Q20. (4 pt.) Interaction between MAC-layer and TCP in Wireless Environment. Wireless link-layer (MAC-layer) relies on local retransmission to recover packets lost due to varying channel conditions (e.g., fading, collisions, etc.). Typically, the MAC-layer will try retransmitting a packet N times before giving up. How does the local MAC-layer retransmission help enhance the throughput performance of the end-to-end TCP connection?
Q21. (4 pt.) If local retransmission at link layer is beneficial as described in Question #20 above, it seems that one should choose a large N to increase the chances of successful repair. Give two reasons or scenarios where it is *not* desirable to have a large N.
Q22. (6 points) Consider the operation of a learning switch in the context of a network in which 6 nodes labeled A through F are star connected into an Ethernet switch.
A
D
B
E
C
F
1
2
3
4
5
6
A
D
B
E
C
F
1
2
3
4
5
6
Suppose that (i) B sends a frame to E, (ii) E replies with a frame to B, (iii) A sends a frame to B, and (iv) B replies with a frame to A. The switch table is initially empty. Show the state of the switch table and after each of these events. For each of these events, identify the interfaces(s) on which the transmitted frame will be forwarded. If nothing happens, leave the table entry blank or enter ‘-‘. Please fill out the blanks of red brackets number. Enter your answers as follow:
(1) XXX
(2) XXX
(3) XXX
…
(10) XXX
Event
Switch Table
Interface(s) on which transmitted frame will be forwarded for each event.
MAC Address
Interface
(i)
B
2
(ii)
(iii)
(iv)