Description

2 NOTE PAGES, CLOSED BOOK, COMPUTERS OFF Your Name:
SUNet ID: @stanford.edu
Signature:
1 /3
2 /2
3 /3
4 /2
5 /2
6 /2
7 /18
8 /14
9 /9
10 /14
11 /12
12 /5
● The exam has 12 questions totaling 86 points.
● You have 120 minutes to complete them.
● Keep your answers concise. ● For multiple-choice questions, circle all true answers. You will be credited points for correctly circled answers and well as for answers correctly left blank. You must circle at least one answer to get credit for the question.
Total /86
● Please box your final answers.
I Multiple Choice Questions
1. [3 points]:
Which of the following statements are true?
A In a network, such as in their B4 network interconnecting their data-center sites, Google can use low and high priorities in the switches to keep the network highly loaded with bulk traffic, while giving low latency to user client traffic.
B When building datacenter networks, cable bundling increases number of fiber runs to decrease number of hops a packet must take.
C Network providers place major content servers like Netflix away from major population areas to even out the load on their servers.
D Some data-center owners use proprietary alternatives to TCP to control congestion for their applications.
E TIMELY is a congestion control algorithm that uses RTT as a signal to decide the rate at which the source host sends data.
2. [2 points]:
Which of the following statements about Manchester coding are true?
A Manchester coding does not negatively affect bandwidth usage.
B Manchester coding was one of the first examples of QAM-16.
C Manchester coding indicates whether a bit is 1 or 0 based on a transition at the end of each period.
D Manchester coding makes clock recovery easier than 4b/5b encoding.
3. [3 points]:
Which of the following is/are true?
A In multicast routing, routers replicate packets on behalf of the sending host.
B In some circumstances, an ISP might select a route with a longer AS-PATH over a route with a shorter AS-PATH.
C Path-vector routing protocols are susceptible to the “counting to infinity” or “bad news travels slowly” problem.
D Both IP multicast and anycast require special support from routers.
E ICMP messages are delivered unreliably.
4. [2 points]:
Which of the following are true about different network applications?
A DHCP is a network protocol that is used to dynamically share a single public IP address between several devices on a network.
C When accessing mail.google.com, the TCP checksum will always guarantee the integrity of the data under all error conditions, while Transport Layer Security (TLS) protocol guarantees confidentiality on top of TCP.
D HTTP/2 addresses the head-of-line blocking issue in HTTP/1.1 by allowing outof-order responses over a single TCP connection, but the issue remains at the transport layer.
5. [2 points]:
Which of the following statements are true about packet switching (compared to circuit switching)?
A Packet switching uses statistical multiplexing.
B Packet switching provides more precise rate guarantees for flows.
C Packet switching requires less per-flow state.
D Packet switching always provides lower per-packet delay guarantees.
6. [2 points]:
A router receives an ARP request whose target hardware address is broadcast, andwhose target IP does not match any of the router’s IPs. The router caches the source IP/hardware address. What else should the router do?
A Send an ICMP error to the frame’s sender, in order to inform the sender that it sent the frame to a host other than the intended target.
B Send an ARP reply to the frame’s sender, in order to inform the sender of the router’s hardware address.
C Forward the frame over all ports except the one on which it was received, in case the intended target of the frame is reachable via one of those ports.
D Nothing.
II Additive Increase, Additive Decrease
7. [18 points]:
In this question we will explore the dynamics of two flows using the AIAD (additive increase, additive decrease) algorithm instead of AIMD. Consider the topology shown in which two hosts A,B are sending packets to D through router R.

The bottleneck link in the path from R to D runs at 10MB/s (i.e. 10 Megabytes per sec ond). The RTTs from A to D and B to D are 100ms. Assume that both A and B can communicate with R instantaneously and with arbitrarily large rate. Assume that each packet has a length of 1250 bytes and the buffer on router R can hold 200 packets.
a. What is the bandwidth-delay product, in Megabytes (MB)? (2 points.)
Answer: MB
b. How many packets can the network hold (on the wire plus in R)? (2 points.)
Answer: packets
Suppose that at time t = 0, host A has a congestion window of 999 packets, B has a congestion window of 0, and R’s buffer is empty.
You should assume that packet drops are always experienced by the flow with more packets in flight. You should assume that each flow updates its congestion window after each RTT, decreasing it if any packet was dropped, and increasing it otherwise.
AIMD: We first consider the evolution of the system when each flow is governed by AIMD, in which the congestion window grows by being incremented and shrinks by being halved (rounding down). In roundtrips 0 through 3, the system evolves as shown in the table below.
t (RTTs) 0 1 2 3
A’s cong. window (packets) 999 1000 500 501
B’s cong. window (packets) 0 1 2 3
c. At which value of t will the number of outstanding packets next exceed the net-
work’s capacity? Give your answer in RTTs, not seconds. (2 points.)
Answer: RTTs
d. What are the congestion windows in the RTT after this? Give your answer in packets. (2 points.)
A: packets B: packets
e. What are the congestion windows of both hosts at t = 300 RTTs? Give your answer in packets. (2 points.)
A: packets B: packets
AIAD: Now, suppose that instead we are using an AIAD protocol. In this case, every drop decreases the congestion window by 5 packets (to a minimum of 1 packet) instead of halving the congestion window.
f. What are the congestion windows of both hosts at t = 300 RTTs? Give your an-
swer in packets. (2 points.)
A: packets B: packets
g. How does the number of dropped packets in AIMD and AIAD compare? (2 points.)
Answer: AIAD results in a (circle one) larger/smaller/equal number of dropped packets.
h. Does AIAD eventually converge to a fair allocation between flows? (2 points.)
Answer (circle one): yes/no
i. On the real internet, the smaller flow can have its packets dropped too. Suppose that the flow to experience the drop was chosen at random with 50/50 probability.
Explain the effect of AIAD on fairness in this new model. (2 points.)
III Elasticity Buffer

8. [14 points]:
Unlike the elasticity buffer we saw in class, when a new packet starts arriving the router waits until the elasticity buffer is only 1/3 full (i.e. it reaches a threshold B/3) before it starts reading from the elasticity buffer. Your job is to determine how big the buffer should be (B) in order to prevent the buffer overflowing or underflowing.
a. On the two sets of axes below, sketch the cumulative arrivals and departures from the elasticity buffer on the router for the two cases: (1) When the end host is at the highest clock rate and the router is at the slowest, and (2) When the router is at the highest clock rate and the end host is at the slowest. (2 points.)

b. Write down an expression for the conditions required so that the buffer does not overflow. Your answer should be an inequality for the buffer size, B, in terms of
Rmax, Rmin, and Pmax. (2 points.)
c. Simplify your expression above, to prove that . (2 points.)
d. Write down an expression for the conditions required so that the buffer does not underflow. Your answer should be an inequality for the buffer size, B, in terms of
Rmax, Rmin, and Pmax. (2 points.)
e. Simplify your expression above, to prove that . (2 points.)
f. Write down an expression for the minimum size of the gap we need between packets (i.e. the interpacket gap) to prevent the elasticity buffer from overflowing. Explain briefly why we need an interpacket gap. (2 points.)
g. The end host and the router each have an internal clock that runs at nominally 1GHz, but can vary from 999.9 MHz to 1000.2 MHz. i.e. in the worst case, the clock might be 0.1 MHz slower (100 parts per million) or 0.2 MHz faster (200 parts per million). Note that unlike the examples we used in class the clock range is asymmetric around the center frequency of 1GHz. Explain why it might make sense to use the expressions above to design an elasticity buffer for this system.
(2 points.)
IV Are you still watching?
9. [9 points]:
Consider an adaptive bitrate (ABR) video streaming system, where the video is delivered in 2-second chunks (the playback cannot start until the whole chunk is downloaded). At T = 0, a client that has a link speed of 4Mb/s starts streaming a movie with an encoded bitrate of 2Mb/s.
a. How long does it take the video to start playing (startup time)? (3 points.)
Answer: s
b. Let’s say that at T = 10s, the link speed suddenly drops to 0. At what time T will the video stop playing? (Hint: See (a) for when video starts playing) (3 points.)
Answer: s
c. New scenario. The link runs at its original speed of 4Mb/s between T = 0s until T = 15s. Then, at T = 15s, the link speed drops to 400kb/s, but the client continues streaming video that was encoded at a bitrate of 2Mb/s. The video will eventually stall. At what time will it resume playing (even if only for a short time)? (3 points.)
Answer: s
V Web page on a cold start
10. [14 points]:
Message Laptop First Hop Router Wikipedia Server
DHCP Request ◻ ◻ ◻
DHCP Response ◻ ◻ ◻
ARP Request ◻ ◻ ◻
ARP Response ◻ ◻ ◻
DNS Request ◻ ◻ ◻
DNS Response ◻ ◻ ◻
TCP Segment(s) ◻ ◻ ◻
VI Ethernet and CSMA/CD
11. [12 points]:

a. A 1000m long 1Gb/s Ethernet network uses CSMA/CD to control access to a shared copper cable as shown in the figure. The Ethernet specification requires that if a collision occurs, it must detect the collision before it finishes transmitting a packet. What is the size of the minimum packet in this network? Express your answer in bits or bytes. (Assume the speed of propagation is 2×108m/s.) (3 points.)
Answer: bits or bytes
b. If the Ethernet network is upgraded to 10Gb/s, how does this affect the minimum size packet we can use? Explain why this might be a problem. (3 points.)
c. If we replace the long shared copper cable with a “broadcast star” in which no two hosts are now more than 500m apart, what is the new minimum packet size for the 1Gb/s Ethernet network? (3 points.)

Answer: bits or bytes
d. Today, CSMA/CD is not commonly used in wired Ethernet networks. Intead, end hosts are typically connected to their nearest Ethernet switch using a full duplex cable (which means there is a separate, independent channel for transmit and receive). Explain why this kind of network does not require CSMA/CD. (3 points.)
VII Manchester Encoding
12. [5 points]:
Encode the bitstream “011001” using Manchester encoding. The first bit has been encoded for you.