Study Guide

Question 1

1. What causes congestion collapse to occur?

Answer 1

Congestion collapse occurs when dropped packets and excessive queuing delays that result from congestion in turn further exacerbate the problem, which causes more drops and delays, and so on. Dropped packets cause retransmissions that add additional traffic to the congested path, while excessive delays can cause spurious retransmissions (i.e., a timeout occurs when the packet was merely delayed, not lost). Note that normal traffic that contributes to congestion is not the cause of collapse, it is the extra traffic that is caused by congestion that leads to collapse.

Question 2

2. What is the difference b​etween ​fairne​ss and ​efficiency in a congestion control scheme?

Answer 2

Efficiency is how much of the available bandwidth is used, i.e., efficient congestion control leaves little or no bandwidth wasted. (Some definitions of efficiency may refer specifically to bandwidth used to do “productive work”, thus excluding overhead traffic.) Fairness is how bandwidth allocated between the different flows. Two common definitions of fair are that all flows get equal throughput, or that all flows get throughput proportionate to their demand (i.e., how much they want to send).

Question 3

3. Assuming traditional TCP Reno with AIMD behavior (i.e., the version presented in the lecture videos), suppose a TCP flow’s bottleneck link has 1 Gbps capacity, and that link is not being shared with any other flow​ s. What will the ​average throughput of that flow be, in megabits per second (Mbps)?

Answer 3

Additive increase will increase the throughput until it equals the bandwidth, at which point a packet loss will occur and trigger multiplicative decrease. At that point, throughput immediately drops to 1⁄2 the bandwidth. Additive increase then resumes, raising throughput linearly until it reaches the total bandwidth again. Thus the average throughput is the average of 1⁄2 bandwidth and 1x bandwidth = 3⁄4 bandwidth. Therefore, the average throughput on a 1 Gbps link will be 3⁄4 x 1 Gbps = 750 Mbps. (A more detailed approach may look at the area beneath the throughput curve, but this results in the same math since the additive increase is linear.)

Question 4

4. What circumstances lead to the incast problem? (In other words, what factors must be present for incast to occur?)

Answer 4

The incast problem occurs when collective communication (i.e., many-to-one or many-to-many patterns) occurs on high fan-in switches. This results in many small packets arrive at the switch at the same time, thus causing some of the packets to be lost. The last necessary factor is a low-latency network, which means the timeout delay will be much more than the round-trip-time of the network. Consequently, large delays occur in which the system is simply waiting for the timeouts to occur. This slows the whole application, since hearing from all the senders in collective communication is usually necessary before the application can proceed. As a real-world example, suppose a web app has to query a back-end database and needs to check with 100 database nodes to do this. It needs to hear back from all 100 nodes before proceeding, or else it risks missing some of the results. (This is the implicit “barrier” that occurs in some data center applications that are not explicitly using barrier synchronization.) Because they are all responding to the same query, all the nodes will reply at roughly the same time. This means a high fan-in switch will have to handle many of these database replies at the same time. Such traffic bursts may cause only a few of these packets to be lost, while the rest are delivered. However, the application still cannot proceed until it receives replies from these few, so it waits. After a significant delay, retransmissions finally occur and may be delivered, allowing the application to proceed.

Question 5

5. Suppose you are working on some live video call software (think Skype or Google Hangouts) and decide to build your application protocol on top of UDP (rather than TCP). Give as many different points as you can (minimum two) to help justify that decision.

Answer 5

● Latency is critical – retransmissions are pointless since they will arrive too late anyway
● Dropped frames aren’t a big deal – the next frame will advance the video state before a retransmitted frame could arrive anyway
● Congestion control and flow control could cause unacceptable delays, as video frames get backed up in the sender host’s local buffer (what is needed instead is for the application itself to reduce the frame rate that it tries to send)

Question 6

6. Why does the linear growth rate of TCP-RENO (1/RTT) perform poorly for short lived flows in networks with large bandwidth and delay products?

Answer 6

The time period required for the congestion window to reach its maximum value is very large (on the order of minutes and hours) for TCP-RENO in paths with large bandwidth delay products. Short lived flows may never reach a congestion event, meaning the flow unnecessarily transmitted slower than necessary over its entire lifetime to avoid congestion.

Question 7

7. Describe the operation of BIC-TCP’s binary search algorithm for setting the congestion window. Once stable, how does BIC-TCP react to changes in available bandwidth, i.e. what happens when there is a sudden increase or decrease in available bandwidth?

Answer 7

At a high level, when BIC-TCP experiences a packet loss event, the congestion window value is set to the midpoint between last window value that did not suffer from loss (WMAX) and the previous window size that was loss free for at least one RTT (WMIN). This is often referred to as a binary search, as it follows intuitively that the maximum possible stable window value is somewhere between a value that was known to be stable and the value achieved just prior to the loss event. This algorithm “searches” for this maximum stable window value by effectively reducing the range of possible value by half per packet loss event.

Once this maximum stable window size has been achieved, if there is a sudden increase in available bandwidth, then max probing phase of BIC-TCP will rapidly increase the window beyond the value of WMAX until another loss event occurs, which resets the value of WMAX. If a sudden decrease in available bandwidth occurs, and this loss is below the value of WMAX, then the window size is reduced by a multiplicative value (β), enabling a safe reaction to a lower saturation point.

Question 8

8. How does the replacement of this congestion control algorithm with a cubic growth function in CUBIC-TCP improve on BIC-TCP? Discuss.

Answer 8

CUBIC retains the strengths of BIC-TCP, but makes many improvements. First, BIC-TCP is a rather complex algorithm that approximates a cubic function. It’s growth function has both linear and logarithmic elements, and many different phases (additive increase, binary search, max probing). Additionally, on short RTT and low speed networks, BIC-TCP’s growth function can be too aggressive (recall it was designed to achieve high utilization on large bandwidth, long RTT networks), making it fairly unfriendly to other TCP flows competing for bandwidth.

CUBIC replaces the growth function in BIC-TCP with a cubic growth function, based on the elapsed time between congestion events. This function maintains the multiplicative decrease utilized by many TCP variants, but records the window size at a congestion event as WMAX. Using this value of WMAX , the cubic growth function can be restarted, with the plateau occurring at WMAX. This eliminates the need for multiple growth phases and maintaining
values like SMAX/MIN. The plateau of the cubic growth function retains BIC-TCP’s stability and utilization strengths.

Question 9

9. What is the purpose of the following regions of the CUBIC growth function: a. Concave b. Plateau c. Convex

Answer 9

a. Concave

The concave region of CUBIC’s growth function rapidly increases the congestion window to the previous value where a congestion event occurred, allowing for a quick recovery and high utilization of available bandwidth following a congestion event.

b. Plateau

The plateau is also known as the TCP friendly region. In this region of the growth curve, the congestion window is nearly constant as it approaches and potentially exceeds WMAX. This achieves stability, as WMAX represents the point where network utilization is at its highest under steady state conditions.

c. Convex

The convex region of CUBIC’s growth function exists to rapidly converge on a new value of WMAX following a change in available bandwidth. When the congestion window exceeds WMAX, and continues to increase throughout the end of the plateau, it likely indicates some competing flows have terminated and more bandwidth is available. This is considered a max probing phase, as the congestion window will grow exponentially in this region until another congestion event occurs and WMAX is reset.

Question 10

10. How does CUBIC’s fast convergence mechanism detect a reduction in available bandwidth (i.e. a new flow competing for bandwidth)?

Answer 10

When new flows start competing for bandwidth, other flows must release some bandwidth to maintain fairness. CUBIC employs the fast convergence mechanism to accomplish this. When two successive congestion events indicate a reduction in available bandwidth (i.e. a reduced value of WMAX), the new value of WMAX further reduced (based on the multiplicative decrease factor used for resetting the congestion window) to free up additional bandwidth and reduce the number of congestion events required for all flows to converge on a fair distribution of bandwidth.

Question 11

11. What kinds of web traffic stand to benefit most from utilizing the TFO option? How does TFO improve the performance of these flows?

Answer 11

Short lived TCP connections (small data sizes) on links with large propagation delays. The performance of these flows are dominated by the return trip time (RTT), and as such, the 3 way handshake used in standard TCP constitutes a large amount of overhead. By enabling the client and server to communicate some of the payload (data) during the 3WHS, it is possible to reduce the number of required RTTs for the flow to complete, reducing the RTT penalty incurred by the 3WHS.

Question 12

12. Describe how a trivial implementation of TCP Fast Open (in which the server replies to a all HTTP GET requests with a TCP SYN-ACK packet with data attached) can be exploited to mount a source address spoof attack. How does TFO prevent this?

Answer 12

An attacker can send many HTTP GET requests for large resources to a victim server, spoofing a victim host address as the requestor. The victim server would then perform the expensive data fetch operations and transmit large volumes of data to a victim host. The result is a Denial of Service attack on both victims.

TFO prevents this by using an encrypted cookie that must be requested by the requestor before initiating requests. The server uses this cookie to verify that the requester address is not a forgery.

Question 13

13. What threat do network middleboxes pose to negotiating MPTCP connections? How does the design of MPTCP mitigate this?

Answer 13

Network middleboxes may strip out unrecognized TCP options (flags) used during the 3-way handshake used to negotiate a MPTCP connection. This means that while the sender and receiver may both be MPTCP capable with multiple viable interfaces, a middlebox along the route may ultimately prevent a MPTCP connection.

MPTCP is designed to resort to a single path TCP when both ends of the connection cannot support MPTCP. In this case, when the sender’s MPTCP capable flag is stripped out by a middlebox enroute to the receiver, the receiver thinks that the sender is not MPTCP capable and proceeds with a single path TCP connection.

The sender will see that traffic returning from the receiver is not MPTCP enabled (the flag is carried on all packets until acknowledged) and as such revert to single path TCP.

Question 14

14. Why are receive buffer sizes required to be larger for MPTCP enabled connections? What controls does MPTCP put in place to maximize memory efficiency?

Answer 14

The receive buffer allows out of order data to continue flowing in the event a packet is dropped and must be resent. For a standard TCP connection, the required buffer size is determined by the bandwidth delay product of the connection.
With multiple subflows across a single connection present in MPTCP, the worst case scenario is that a packet drop occurs early and must be re-sent across the slowest link (like a 3G mobile connection). This would require other subflows (like high bandwidth WiFi connections) to have larger buffers than would be required if it were the only connection, because it can send data much faster than the slower link that is retransmitting the lost packet.

MPTCP has several built in functions that allow a connection to make the most of the memory it has available. The first is opportunistic retransmission, where an idle subflow (waiting on receive window space) may retransmit unacknowledged data sent on another slower subflow. Additionally to prevent subflows from becoming a receive window bottleneck in the future, subflows that induce opportunistic retransmission can be penalized by reducing their congestion windows. This reduces the amount of traffic sent along this subflow allowing the faster link to send more data.

Additionally, the buffer itself can be autotuned and capped by MPTCP mechanisms. Since the buffering requirements for MPTCP are so large, MPTCP only allocates a portion of the maximum allowable buffer size at the start of the connection, and increases this allocation as needed throughout the lifetime of the MPTCP flow. If the flow does not require worst case buffering, the system overall conserves memory resources. Combined with capping congestion windows on subflows that are excessively filling buffers reduces the overall need for system resources for MPTCP flows.

Question 15

15. What is application flow control in the context of this paper, and what factor motivate its use? Based on the findings in the paper, application flow control interacts poorly with TCP mechanics. Briefly summarize the cause of this interaction and why it occurs.

Answer 15

Application flow control in this context refers to the application level sending behavior of YouTube server over a TCP connection to a client. The application level algorithm transmits video stream data as expected for a TCP flow during the initial buffering of a video, but once the desired buffer is full, data is sent in blocks to the client as necessary to maintain the buffer. This has the benefit of consuming less bandwidth, allowing more connections to run concurrently. Additionally, there are opportunistic benefits. For example, assume a user requests a 3 minute long video and the server greedily fulfills this request in 1 minute. If that user only watches the first 1 minute and 30 seconds of the video, only half of the data sent is actually consumed.

TCP congestion control and receive window mechanics expect a greedy transmission - meaning the limiting factor of a TCP connection transmission rate is expected to be the congestion window (the link capacity) or the receive window (the receiver’s capacity). In the case of application flow control - the limiting factor is the sender’s application level algorithm. This is further complicated by the block sending nature of the transmissions. Once the buffer has filled, the transmission is subject to long periods of inactivity, after which a large chunk of data is sent. Since the receive and congestion windows were emptied during the pause, the sudden transmission of a large amount of data in the next block is perceived as congestion on the link, resulting in packet loss and reduced throughput.

Question 16

16. Would you use a leaky bucket or a token bucket to traffic shape a constant bit rate (CBR) audio stream? Explain why.

Answer 16

Since a constant bit rate stream isn’t bursty, the traffic shaping mechanism doesn’t need to handle bursts. Since the original stream is “smooth”, it would be better to use the leaky bucket to keep the stream “smooth” and even out any bursts.

Question 17

17. If you want to traffic shape a variable bit rate (VBR) video stream with average bit rate 6 Mbps and maximum bit rate 10 Mbps, should you use a leaky bucket or a token bucket? What values should you use for rho and beta if you want to allow bursts of up to 500 ms?

Answer 17

Since a variable bit rate stream has bursts, it is better to use a token bucket that will allow short bursts, but even things out to the average bit rate of the stream in the long run. Rho is the rate of tokens being added to the bucket, so it should match the average bit rate: rho = 6 Mbps. Beta determines how large and how long a burst is allowed. Since we want to allow up to 10 Mbps bursts for up to 500 ms (0.5s), we should allow (10 – 6 Mbps)(0.5s), or beta = 2 Mb = 250 kB (or 245 kB). (Note: b = bit; B = byte.)

Question 18

18. Suppose you’re running an ISP and get the crazy idea that implementing Power Boost for your own network would be a good idea. For the 6 Mbps service plan (i.e., customers can have a sustained rate of 6 Mbps), you’d like to allow them to burst up to 10 Mbps for up to 10 seconds. In megabytes (MB), what should you set the beta parameter of your token bucket to? (Round to the nearest tenth of a MB, i.e., one decimal place.)

Answer 18

Similar to the last problem, (10 – 6 Mbps)(10s) = 40 Mb = 5 MB (or 4.77 MB)

Question 19

19. Read about the following two​ ​Active Queue Management (AQM)​ techniques:​ ​Random Early Detection (RED)​ and​ ​CoDel​. Although they vary in specifics, these two algorithms share a common basic approach to solving the buffer bloat problem. Explain what that approach is and why it works.

Answer 19

Their approach is to drop packets even when their buffers are not full. RED determines whether to drop a packet statistically based off how close to full the buffer is, whereas CoDel calculates the queuing delay of packets that it forwards and drops packets if the queuing delay is too long. By dropping packets early, senders are made to reduce their sending rates at the first signs of congestion problems, rather than waiting for buffers to fill.

Question 20

20. If you want to find out if a remote host (i.e., not ​your server) is currently under a DoS attack, would you use active or passive measurement? Explain why.

Answer 20

Active measurements, such as ping, are required here. Only the server’s owner or ISP would be able to use passive measurements, since they control the machines over which the server’s traffic is handled. Excessive ping delays to the server are a sign of congestion on the server’s link. (It’s hard to be sure that it’s due to a DoS attack without additional context, but it’s a sign that something is wrong…)

Question 21

21. If you want to compute the traffic intensity, I=La/R, on a router interface (i.e., the ratio between arrival rate and forwarding rate), would you use Counters, Flow Monitoring, or Packet Monitoring? Explain why.

Answer 21

The sending rate is a known quantity (it’s just the maximum rate of that device’s interface). The average length of packets and the average arrival rate of the packets can be determined from simple counters. (We do not need to inspect the packet contents, so packet monitoring is unnecessary. Since we are only concerned with all packets on a particular interface and do not care about which flow each packet belongs to, flow monitoring is also unnecessary. However, if you knew that traffic intensity was high and wanted to determine which source is responsible for most of the traffic, flow monitoring would come in handy in that case.)

Question 22

22. Discuss the drawbacks to over-buffering routers. If memory is widely available at low cost, why is it a bad idea to use massive buffers to ensure high link utilization?

Answer 22

Using massive buffers in internet routers increases the size, power consumption, and design complexity of routers. Large buffers are typically implemented in off chip DRAM, where small buffers can be implemented on chip.

Additionally, large off chip DRAM is slower to retrieve data than on chip SRAM. This means that retrieving buffered packets takes longer, which means the latency on the link will grow. During periods of congestion with a large amount of buffered packets, latency sensitive applications like live streaming and networked video games will suffer.

Further, TCP congestion control algorithms can also suffer under these conditions. Using large amounts of cheap memory may eliminate the need to worry about proper buffer sizing, but it induces hardware efficiency issues and presents problems for low latency applications.

Question 23

23. Under what conditions was the “rule-of-thumb” for buffer size (𝐵= 𝑅𝑇𝑇̅̅̅̅̅̅ 𝑋 𝐶) originally conceived? How does this fundamentally differ from current, real world conditions?

Answer 23

The “rule-of-thumb” is derived from an analysis of a single long lived TCP flow. The rate is designed to maintain buffer occupancy during TCP congestion avoidance, preventing the bottleneck link from going idle.

These conditions are not realistic compared to actual flows in backbone routers. For example a 2.5 Gb/s link typically carries 10,000 flows at a time, of which the life of the flow varies. Some flows are only a few packets, and never leave TCP slow start, and hence never establish an average sending rate.

Of the flows that are long lived, they have various RTTs and their congestion windows are not synchronized, which contrasts directly with a single long lived flow with a stable RTT and single congestion window.

Question 24

24. Statistical modeling of desynchronized long lived flows indicates that smaller buffer sizes are sufficient to maintain link utilization as the number of these long lived flows increases. However, not all flows can be expected to be long lived. Discuss why short lived flows (less than 100 packets) do not significantly detract from these findings.

Answer 24

Even when the vast majority of flows across a link are short lived, the flow length distribution remains dominated by the long lived flows on the link. This means that the majority of the packets on the link at any given time belong to long lived flows.

Required buffer size in the case of short lived flows depends on actual load on the links and the length of the flows, not the number of flows or propagation delays. This means that roughly the same amount of buffering required for desynchronized long lived flows will also be sufficient for short lived flows as well.

Question 25

25. Explain how standing queues develop in network buffers at bottleneck links. Why is a standing queue NOT correctly identified as congestion?

Answer 25

Queues develop at bottleneck links as a result of the bottleneck’s reduced forwarding speed. As some of the packets in the queue are forwarded, the TCP sender will begin to receive ACKs and send more packets, which arrive at the bottleneck link buffer, refilling the queue. The difference in the bottleneck link speed and the link RTT (driving the congestion window of the TCP flow) will result in a certain number of packets consistently occupying the buffer, until the flow completes, which is referred to as the standing queue. Standing queues are NOT congestion because it results from a mismatch in congestion window and the bottleneck link size. A standing queue can develop in single flow environments, and under usage limits that would eliminate actual congestion.

Question 26

26. Consider the CoDel active queue management algorithm. How does the algorithm decide whether or not drop a flow’s packets? What effect does dropping the packet have on the TCP sender?

Answer 26

CoDel assumes that a standing queue of the target size is acceptable, and that at least one maximum transmission unit (MTU) worth of data must be in the buffer before preventing packets from entering the queue (by dropping them). CoDel monitors the minimum queue delay experienced by allowed packets as they traverse the queue (by adding a timestamp upon arrival). If this metric exceeds the target value for at least one set interval, then packets are dropped according to a control law until the queue delay is reduced below the target, or the data in the buffer drops below one MTU. Dropping a flow’s packet triggers a congestion window reduction by the TCP sender, which helps to eliminate buffer bloat.

Question 27

27. If your browser has a page in the cache and wants to know if the page is still fresh and can be used, or is too old and should be replaced with fresh content from the server, which HTTP method should it use to find out? (If you are familiar with the If-Modified-Since header field, which we have not discussed in this class, please assume that we are not using If-Modified-Since.)

Answer 27

The HEAD method in HTTP requests a document just like the GET method except that the server will respond to a HEAD request with only the HTTP response header; the response body (which would normally contain the document data) is not included. This saves the delay of transmitting the actual document, e.g., if it is a large file, but allows the browser to check the Last-Modified field in the response header to find out if it's been changed since the time when the cached version was retrieved.

Question 28

28. Consider the HTTP protocol. What will cause a server to send a response message with the status code... a. 404 Not Found ? b. 302 Moved Temporarily (also sometimes called 302 Found) ? c. 200 OK ?

Answer 28

a. 404 Not Found ? The requested file does not exist on the server. That is, the file indicated by the path part of the GET method line cannot be found at that path. b. 302 Moved Temporarily (also sometimes called 302 Found) ? The requested file is not at this location (i.e., the path part of the GET method line), but the browser should instead use the URL provided in the Location field of the response to retrieve the file. However, the file may be found at this location in the future (unlike a Moved Permanently response), so the URL in the Location field should be used this once, but not necessarily again in the future. c. 200 OK ? The operation in the request message succeeded. What that operation is exactly depends on the request method. For example, if the request method was GET then 200 OK means that the document was retrieved and its content should be in the body of the 200 OK response. (200 OK responses to other methods do not necessarily contain a body, though. This also depends on what the method was.)

Question 29

29. Consider the HTTP protocol. What would the following header fields be used for? a. Last-Modified b. Host c. Cookie

Answer 29

a. Last-Modified This is the date and time that the requested document file was last modified on the server. It can be used to check if a cached copy is fresh (newer than the Last-Modified time) or stale (older than the Last-Modified time, indicating that it's been changed since the cached copy was retrieved). b. Host This is the domain name of the web request (e.g., from the domain part of the URL). One way this may be used is if a single web server (with a single IP address) is hosting websites for more than one domain. The web server can check the Host field to see which domain's pages should be retrieved for each request it gets. c. Cookie This is included in request messages that are sent to a domain that previously gave the browser a cookie. That cookie would have been provided by the Set-Cookie field in a response message, and after that (until the cookie expires) the browser should include the exact same cookie given by Set-Cookie in any request message it sends to the same domain. This allows the server to know that a request is coming from the same client that made another earlier request. For example, when you request to view your shopping cart, the web server may use cookies to know that you are the same person who earlier clicked on an item to add to your cart, so it can show you a cart containing that item.

Question 30

30. Of the various methods to redirect web requests to CDN servers, DNS redirection is the most common. Why would this method be more popular than the alternatives?

Answer 30

DNS-based redirection is much faster than HTTP redirection, as the latter requires a couple extra round trips to servers. (It's actually more than just one extra round trip because you need to establish a TCP connection to a second different server.) It also gives the CDN provider more control over who will be redirected where than a technique like IP anycast would. Finally, it is not too difficult to implement (even if slightly more complex than the other two) and it uses tools that are widely supported (i.e., DNS) and do not need any modifications to support this technique (i.e., DNS works out of-the-box).

Question 31

31. How does BitTorrent implement the tit-for-tat algorithm? Be sure to explain in detail, including the roles of both choking and unchoking.

Answer 31

A BitTorrent client sends data only to the top N peers who are sending to it, plus one peer who is optimistically unchoked. Let's say for example purposes that N=4. Your BitTorrent client will choose the 4 peers who are sending to it at the fastest rate and it will send data to them in return. It will not send to other peers, and they are said to be choked. Thus it provides tit-for-tat by sending to those who send the most to it, and choking those that are not sending to it, or are sending slowly. However, this creates a problem where two peers who might be able to send to each other are mutually choked. Neither will begin sending to the other because the other is not sending to it. Therefore, each client will optimistically unchoke one peer at any given time for a brief period. If the client sends fast enough to the optimistically unchoked client to get on its top-4 then the peer will send data back in return. If the client receives enough data from the peer for it to be in the top-4 then that peer becomes one of the new top-4 and the slowest of the previous top-4 will be choked. Thus they both end up in each other’s top-4. (The peer is no longer "optimistically" unchoked, and is merely unchoked. A new peer is selected to be optimistically unchoked.) On the other hand, if the client does not get into its peer's top-4, or if it does but the peer does not send fast enough in return to get in the client's top-4, then they will not end up in each other’s top-4. After some time, the client will stop optimistically unchoking that peer and stop sending to it. It will choose a new peer to optimistically unchoke. This process repeats forever (until the client has the entire file, that is) in order to keep exploring different peers for better matches than the client's current top-N. The game theoretic result is that clients will end up sending to peers that are able to send back about the same amount – fast peers will get paired up, while slow peers are matched with each other. This happens because a fast peer will readily drop a slow peer from its top-N in favor of another fast peer, matching fast peers together. Slow peers will not get matched with fast peers because the fast peers will soon learn to choke them, but they will pair up with other slow peers because neither peer can find a better match who is willing to unchoke them.

Question 32

32. In a distributed hash table, how many steps (hops) are required to lookup an item if the finger table is a constant size (i.e., its size does not depend on the number of DHT nodes in the system)? Explain why that is the right answer.

Answer 32

A lookup will require O(N) hops in this case. Suppose a constant size of 1, as an example. Each node only knows how to find the next one, so it basically forms a ring topology. In the worst case, the requested item is on the last node in the ring before getting back to the node that originated the request. So the request has to go all the way around the ring, taking N-1 hops. Based on similar reasoning, if a larger, constant number of nodes is in the finger table, a proportionately smaller amount of time may be required. However, for any given constant size finger table, as the number of nodes in the system grows, the number of hops required will still be on the order of O(N).

Question 33

33. For a more typical DHT setup where the finger table has O(log N) entries, for N DHT nodes in the system, explain why the number of steps to access an item is O(log N).

Answer 33

O(log N) entries in the finger table means that each node knows about the node halfway around the ring back to it, about the node halfway to that one, the one halfway to that one, and so on until the last entry in the finger table that is just the next node. This means that for any given item that could be on any node, each node knows the address of at least one node that is at least half way around the ring from itself to the item. Since each hop cuts the distance to the item in half, the number of hops required to get to the item from any starting point in the DHT is O(log N). (This should be understood by analogy to binary search, divide-and-conquer, etc.)

Question 34

34. Label each of the follow as being either a “control plane” or “data plane” protocol, and explain why it is so labeled 1. IS-IS 2. IP 3. UDP 4. DHCP 5. 802.11 (Wi-Fi)

Answer 34

1. IS-IS control – this is used to calculate routes that allow routers to later forward data packets, but does not carry data for any application 2. IP data – the actual IP packets that are forwarded by routers are the packets that contain application data 3. UDP data – similar to b), these UDP packets contain application data 4. DHCP control – this is used to automatically assign IP addresses to end hosts (and sometimes subnet and DNS server locations as well), which is required for that end host to then be able to send and receive data packets, but DHCP messages do not contain any application data themselves 5. 802.11 (Wi-Fi) data – this is a link layer protocol that carries data for applications or higher level protocols (which would be considered “data” by the link layer, even if they are not data at the application layer)

Question 35

35. Name some situations/scenarios in which using SDN provides a benefit. Be as specific as you can, and see if you can come up with at least two

Answer 35

One scenario in which SDN is helpful is when something breaks in the network (at the software/configuration level). Since the control plane is separate and policies are centralized in the SDN controller, it is easier to see the “big picture” of what your network configuration is actually doing and you can find and fix problems more easily. Another scenario is when you want to update your network. Instead of buying all new hardware to get the latest control plane features, you simply update your software in the SDN controller. Similarly, updating policies is easier as you just update the configuration expressed by the DNS controller software, and you don't have to go around to each network device and update its individual piece of the global policy separately (and hope that you didn't miss one or accidentally misconfigure one in the process!). Finally, SDN is useful in research or testbed network. Because SDN is flexible, you can create new control techniques or try different policies to experiment with them, without having to build a new piece of hardware that implements the new behavior. This is useful not only because experiments to test new ideas are easier and less expensive, but also because it allows rapid iteration on those ideas if it becomes apparent some further refinement on the idea is needed.

Question 36

36. Name some places where network virtualization is useful, and some places where it is not normally especially useful. (See if you can come up with 2 of each.)

Answer 36

Network virtualization is useful in multi tenant data centers (or “the cloud”) in order to provide each tenant with the illusion that they have a private network connecting their servers/Vms, and possibly to allow them some ability to configure their virtual network without affecting other tenants. It is also useful in R&D environments (e.g., universities or anyplace else research is done) in order to isolate networking experiments from the rest of the general-purpose traffic in their enterprise. Thus experimental techniques that be tried without causing problems for the rest of the network. Finally, it is useful in computer networking classes. Similar to the research scenario, we want to try doing some different things that may not be a good idea on the production network in order to learn more about how networking works. Virtualization allows us to try things without breaking the network for everyone else. Other answers may be possible, but these are three major use cases. Network virtualization is generally bad in situations where you can consider it overkill, or where the costs outweigh the benefits. For example your home network connecting to your ISP or the corporate network you use at work are poor candidates for network virtualization. Networks that are highly sensitive to latency are not good candidates. For example systems with system critical cyber-physical devices would likely not be able to trade a layer of virtualization to obtain the flexibility provided. For example, a network of hosts and physical devices used to launch manned space vehicles, conduct air traffic control, control a nuclear reactor, etc. are bad candidates for network virtualization.

Question 37

37. Why use the Pyretic programming API when the hardware itself exposes the OpenFlow API?

Answer 37

The Pyretic API provides a high-level abstraction for SDN programmers. The OpenFlow API exposed by devices supporting it is a low level API, on the level of assembly language. It is inordinately difficult to develop sophisticated SDN applications with the OpenFlow API. Additionally, the Pyretic runtime provides an efficient runtime that automatically installs generated low level rules on hardware devices throughout the network.

Question 38

38. How does a network policy implemented in python and executed on a Pyretic con-troller result in policies on OpenFlow switches?

Answer 38

First, using the Pyretic API, the programmer specifies a high level network policy. The Pyretic runtime connects via sockets to OpenFlow clients on the network. The Pyretic runtime interprets packets traversing these network clients against the policy, and using its socket connection installs OpenFlow rules to implement policy behavior. Additionally, these connections allow the Pyretic runtime to perform other actions, like proactively installing rules to reduce network latency, reading counters, etc.

Question 39

39. Describe the function of the following pyretic network policy functions: A. flood() B. match(dstip=‘192.168.1.15’) & match(srcip=‘192.168.1.120’) C. match(dstip=‘10.0.0.8’) >> fwd(12) D. match(dstip= ‘10.0.0.1’) >> ( match(srcip=‘10.0.0.15’) >> drop() + match(srcip= ‘10.0.0.25’) >> modify(dstip=‘10.0.0.30’) )

Answer 39

A. flood() Returns one packet per local port on the network spanning tree. B. match(dstip=‘192.168.1.15’) & match(srcip=‘192.168.1.120’) Two separate match predicates are composed, the result matches any packet that has destination IP = 192.168.1.15 and source IP – 192.168.1.120 C. match(dstip=‘10.0.0.8’) >> fwd(12) A single match predicate sequentially composed with another, the result of which matches packets any packet bound for IP 10.0.08 and forwards it along port 12. This effectively “filters out” all traffic not bound for IP 10.0.0.8. D. match(dstip= ‘10.0.0.1’) >> ( match(srcip=‘10.0.0.15’) >> drop() + match(srcip= ‘10.0.0.25’) >> modify(dstip=‘10.0.0.30’) ) This policy implements a complex policy. First, all traffic not bound for IP 10.0.0.1 is filtered. Any packets bound for 10.0.0.1 is then subject to parallel composition. If the packet is from IP 10.0.0.15, it is dropped. If the packet is from 10.0.0.25, it is returned, with the destination IP rewritten to 10.0.0.30.

Question 40

40. Recall that the three steps of traffic engineering: Measure, Model, and Control. - What are the two things that need to be measured, and how could each be measured? - What are two ways that control could be implemented?

Answer 40

-What are the two things that need to be measured, and how could each be measured? We need to measure the topology, including not only the connectivity but also the capacity of each link and router. This could be done by routers self-reporting, similar to how they exchange information in a Link State protocol, but in practice is probably more often simply entered as data by a network engineer. We also need to measure the traffic, or offered load. This can be done using the “simple counters” measurement technique that we learned about earlier, since we want to know how much traffic is on each part of the network but don't necessarily need the details of specific flows. -What are two ways that control could be implemented? The “traditional” way to implement control is by adjusting link weights, which indirectly affects the routes calculated by the routing protocol. In practice, link weights are more often used this way than to represent any “real” property of the network, like bandwidth or link latency. Another way to implement control is by using SDN to directly control the routes that are used on the network.

Question 41

41. In intra-AS multipath, traffic can be split among paths with the same path length (i.e., sum of link weights along that path). In inter-AS multipath, what properties of the paths (i.e., of the BGP advertisements) need to be equal in order to allow multipath over those paths? (You can limit your answer to the BGP properties that we learned about in class – there are couple that we didn't learn about that also apply here, but don't worry about those

Answer 41

LOCAL_PREF, the local preference parameter AS_PATH length, as determined by counting the number of ASes in the AS_PATH MULTI_EXIT_DISC, the MED value IGP metric to the NEXT_HOP, i.e., equal “hot potato” routing distance

Question 42

42. How does using pods and pseudo-MACs improve the scalability of a Layer 2 network?

Answer 42

This changes the flat layer 2 addressing (MAC addresses) into a hierarchical addressing (pseudo-MAC addresses). This means that switches only need to store a forwarding entry for each host in the same pod plus one for each other pod, rather than needing an entry for each host on the entire network. (Notice that hierarchical addressing is the same thing that allows IP to scalable at layer 3, so the idea is to push that concept down into layer 2.)

Question 43

43. What are the advantages of using a Jellyfish topology over a traditional hierarchical data center topology?

Answer 43

* Network load balancing – prevents bottleneck links and heavily loaded aggregation or core switches * Higher capacity – since the network is balanced, more hosts can reasonably be hosted on a network with the same number of switches * Shorter paths – shorter average number of hops between any two hosts results in faster network performance * Incremental expansion – allows adding switches to the network without reconfiguring the existing network infrastructure or adding additional “higher-level” switches

Question 44

44. What are the drawbacks or problems with using a Jellyfish topology?

Answer 44

* Does not handle heterogeneous switch devices well, except when expanding the network with switches larger than those originally used. * Long cable runs between random switch pairs may be necessary, but are inconvenient and difficult to install

Question 45

45. Briefly describe the functions of the logically centralized Fabric Manager used in PortLand. Where does this Fabric Manager reside?

Answer 45

The Fabric Manager is primarily responsible for maintaining network configuration soft state. Using this soft state, the Fabric Manager performs ARP resolution, provides multicast capability to the network, and achieves fault tolerance goals. The Fabric Manager is a user process, running on a dedicated machine. This machine may be located on the network itself, or it can reside on a separate control network.

Question 46

46. Explain how PMAC (Pseudo MAC) addresses are generated for end hosts in a PortLand network, i.e. What are the four components of a PMAC, and what does each component encode? How does this design improve forwarding table sizes on large scale data center networks?

Answer 46

A PMAC encodes the position of an end host in a fat-tree network. This encoding consists of four components in the format ​pod.position.port.vmid . The first component encodes the pod number the end host and the edge switch reside in, and the position number encodes the end host’s position in the pod. The port component encodes the switch’s physical port number the end host is attached to. The vmid component encodes a unique ID for each virtual machine that is present on the end host. The edge switch maintains a mapping for each VM, which uses its own AMAC (actual MAC) address. This permits multiplexing of virtual hosts resident on a single physical host. The use of PMACs greatly simplify layer 2 forwarding due to their hierarchical nature. Switches no longer need a forwarding table entry per virtual host. A single forwarding table entry can be used to aggregate hosts, enabling forwarding behavior that exploits longest prefix match. Using AMACs, switch state size is O(n), where n is the number of virtual hosts in the data center, whereas state size is O(k) for PMACs, where k is the number of ports on switches used to construct the fat tree network.

Question 47

47. Describe at a high level how a data center could generate a Jellyfish topology for their specific network. Assume the desired topology is of the simplest variety, meaning each switch has the same number of ports and will connect to the same number of servers.

Answer 47

To create a Jellyfish topology, we need to know three values: N, the number of racks / switches, k, the number of ports per switch, and r, the number of ports to be used to connect to other switches. Next, an approximation algorithm is used to generate a RRG (Random Regular Graph) using N, k, and r as input. The result is a blueprint for the Jellyfish topology that can be used to physically cable the switches and servers.

Question 48

48. Describe at a high level how a Jellyfish topology can be incrementally expanded, using the same assumptions from the previous question. Can we expect the expanded topology to be uniformly random after an incremental expansion?

Answer 48

To incrementally add a new server rack, it is not necessary to generate a new RRG with N+1, k, and r. At a high level, we can add the new rack by iteratively selecting connections between other ToR switches (not otherwise connected to the new ToR switch) and replacing that connection with two new connections, each to the new switch. This maintains the previous connectivity of the topology, and also consumes two of the r ports on the new ToR switch dedicated to connecting to other ToR switches. This process is repeated until one or zero or the r ports remain. It is important to note that after expansion, the new topology cannot be expected to be uniformly random, as it would be if a new RRG was created and the entire data center re-cabled appropriately.

Question 49

49.​ ​What kinds of attacks can BGPSec successfully protect against? i.e., what specific attacks are possible against BGP but are defeated by BGPSec? (Explain clearly how these attacks would be executed – if there's more than one way to execute an attack, consider those as two different attacks.)

Answer 49

A BGP message could be sent to a router by some host (e.g., a remote attacker) that is not the router's legitimate neighbor ○ Note that although BGPSec provides session authentication, this kind of attack can also be prevented without BGPSec by using the “TTL Hack”. ​An AS could lie about being the origin of a particular subnet (i.e., claiming that the AS contains a subnet when it does not, in fact) ○ BGPSec prevents this by providing certificates that sign the origin claim An AS could lie about the AS-path to a particular subnet (i.e., claiming that there is a path through the AS when there is not, or that there is a more efficient path than there really is) ○ BGPSec prevents this by providing a chain of signed paths, each partial path in the chain being signed by the AS that advertised that part of the path

Question 50

50. How does an attacker who performs BGP hijacking prevent being detected by traceroute?

Answer 50

When an attacker performs a BGP hijack and leaves its own AS out of the path, it can ensure that even traceroute cannot discover it (the missing AS, that is) by simply not decrementing the TTL field on the traceroute when it passes through the attacking AS. To traceroute, it then looks like that AS isn't actually there.

Question 51

51. How can DNS be manipulated (i.e., attacked) to allow someone to become a “man-in-the-middle”?

Answer 51

There are several ways this could happen, but the most common is DNS poisoning. The attacker can SPAM DNS responses with a bad domain→IP address mapping to a local DNS server. If the attacker is lucky, or keeps trying for long enough, at some point the local server will issue a query that a SPAMed response could potentially be a legitimate response to (i.e., it has an ID that matches the request). When this happens, the local server will accept the attacker's response and not only reply to the request with the bad mapping but also cache it and use it to respond to new requests for the same domain name. Once the bad entry is in place, hosts that want to reach that domain will instead go to the IP address given by the attacker. The attacker's machine at that IP could then intercept traffic as a MITM or simply spoof the legitimate server (e.g., to collect login credentials).

Question 52

52. How can ARP be used to mount a “man-in-the-middle” attack against a host on the same local (Layer 2) network as the attacker? (Notice how Wi-Fi is especially vulnerable to this, particularly “public hotspots”!) For a hint to help you get started, try a web search for “gratuitous ARP”.

Answer 52

ARP poisoning works similarly to DNS poisoning, except that there is not ID value that the attacker needs to guess (or SPAM enough guesses that one of them might be right). Not only that, a host will accept an ARP response even if no ARP request for that IP→MAC mapping was ever made – such a response is referred to as a “gratuitous ARP response”. An attacker could send gratuitous ARP responses for a particular IP address to hosts on its local network so that those hosts send messages to the attacker's MAC instead. For example, the attacker may send gratuitous ARP to a host for the network's gateway router, ensuring all packets headed for outside the local network instead come to the attacker's host instead. It could also send a gratuitous ARP to the router for the host's IP address, ensuring that return traffic is also sent to the attacker's host. This is particularly powerful because it's very easy to do and can let an attacker become a MITM for virtually all traffic to/from a target host. It's also a little harder to detect because the IP addresses are still the correct IP addresses for all the machines involved – only the MAC address have changed. The main drawback compared to something like DNS poisoning is that the attacker must be on the same local network as the target in order to do this. However, users connected to the same “public hotspot” are indeed all on the same local network, making them particularly vulnerable to this sort of attack.

Question 53

53. ​​How do SYN cookies work? How does this prevent resource exhaustion type denial of service (DoS) attacks on a server (i.e., trying to exhaust the server's resources, rather than exhausting the network's resources)?

Answer 53

The server does not allocate resources for the TCP connection immediately upon receiving a SYN packet, but instead waits for the ACK (final part of the 3-way handshake) to allocate those resources. In order to prevent attackers from simply doing an “ACK flood” instead of a SYN flood, the server's SYN/ACK response to the SYN packet contains a special “SYN cookie” that it uses as the connection's initial sequence number. When the server gets an ACK, it can calculate whether or not the sequence number in that ACK could have been legitimately generated as a SYN cookie. (The ACK number is the SYN cookie +1, so the server subtracts 1 to get the candidate SYN cookies that it tests.) If the ACK sequence number (SYN cookie) checks out, then the server knows 1) that the client has engaged in the entire 3-way handshake, rather than sending spurious ACKs, and 2) the client's IP address given by the IP headers is it's legitimate address, because otherwise it wouldn't have received the SYNACK that contains the SYN cookie. (There are some more details about how exactly it is able to programmatically verify the legitimacy of a SYN cookie extracted from an ACK message without having stored any data after the SYN and SYN/ACK steps, as well as how it is able to prevent replay attacks. However, we'll leave this answer at this moderate level of detail for now.)

Question 54

54. If you are trying to detect TCP SYN flooding attacks and want to raise an alarm when there are 1048576 (i.e., 1024^2​ ​) attack packets using a /12 subnet as the telescope, how many backscatter packets do you need to observe to detect the attack?

Answer 54

The /12 subnet contains 2^(3​2-12​) = 2^20​ = 1048676. So 1048576/1048576 = 1 packet to observe.

Question 55

55. Describe how (or if) BGP, origin authentication, soBGP, S-BGP, data plane verification and defensive filtering can be manipulated.

Answer 55

- BGP does not validate information in routing announcements, so a manipulator can announce any path they want and claim ownership of a victim’s IP prefix. - Origin Authentication uses a trusted database for verification so an AS can’t claim ownership of a victim’s IP prefix, but they can still announce a path that ends at the proper AS, although the path does not physically exist. - soBGP uses origin authentication and a trusted database to guarantee that any path physically exists, but the manipulator can advertise a path that exists but is not actually available. - S-BGP uses path verification, which limits a single manipulator to announcing available paths, but they could announce a shorter, more expensive, provider path while actually forwarding traffic on a cheaper, longer customer path. - Data plane verification prevents an AS from announcing a path and forwarding on another, so the manipulator must actually forward traffic on the path he is announcing. - Defensive filtering polices the BGP announcements made by stubs. With the model in the paper, each provider keeps a prefix list of the IP prefixes owned by its direct customers that are stubs. If a stub announces a path to any prefix it doesn’t own, then it is dropped. In this way, if all providers correctly implement this it eliminated attacks by stubs.

Question 56

56. The “Shortest-Path Export-All” strategy was proven not to be optimal for the manipulator. Describe the 3 counterexamples that were discussed.

Answer 56

Announcing longer paths can be better than announcing shorter ones. In the example given in Figure 9 of the paper, advertising the shortest path will only pick up traffic from one small provider. Announcing a longer path to the large provider, will attract more traffic overall as the large provider will prefer this path over the shorter, peer path as it will be cheaper. It is better for the manipulator to attract traffic from larger AS. This strategy will work against any secure routing protocol, except when launched by stubs in a network with defensive filtering, because it is only implementing a different export policy than usually used. Announcing to fewer neighbors can be better than announcing to more. In this strategy, by not exporting to certain Tier providers, customer paths to the victim can be eliminated and influential ASes will be forced to choose shorter peer paths over a longer customer path because the customer path was not made known to them. This will work against any secure protocol as it is just using a clever export policy to manipulate traffic. The identity of the ASes on the announce path matters since it can be used to strategically trigger BGP loop detection. With false loop prefix hijack, the manipulator claims an innocent AS originates the prefix to his provider. But when the false loop is announced, BGP loop detection will cause the AS to reject the path, removing the customer path from the network. This will force large ISPs to choose shorter peer paths. Unlike the first two attacks, this one will only work against BGP, origin authentication or soBGP because it involves false advertising of the path announced by an innocent AS.

Question 57

57. Describe the various rewiring activities that are unique to malicious ASes and how ASWatch captures these activities.

Answer 57

Malicious ASes change their providers often to avoid being detected or to avoid the negative consequences of their customers activities. Among these providers, they are also known to connect to Providers with lax security policies and / or long response times to abuse complaints. Even still, Malicious ASes have longer periods of downtime, due to depeering from their neighboring ASes and detection avoidance strategies they employ. ASWatch captures these activities by taking snapshots of AS relationships periodically and observing the changes in relationships over time. These activities are then used to feed the reputation engine that identifies malicious ASes.

Question 58

58. What is the motivation for malicious ASes to advertise fragmented BGP prefixes rather than their entire IP address space?

Answer 58

Malicious ASes conduct a wide variety of abusive actions, many of which can be countered with simple blacklisting. Examples of this would be DoS, spamming, and phishing. If a malicious AS consistently advertises its entire IP address space, it runs a higher risk of having the entire IP space blacklisted when these activities are detected. Small fragments of advertised space allow malicious activities to continue their activities in a fresh IP space fragment when they are blacklisted.

Question 59

59. Why are current defense methods against Botnet DDoS attacks ineffective against crossfire attacks?

Answer 59

Botnets conducting a crossfire attack do not need to spoof their IP addresses, and as a result defenses based on detecting spoofed IP addresses fail. Additionally, the traffic sent by these botnets to overload links is not unsolicited, the traffic flows from one participating host to another. Furthermore, the attack overloads links in aggregate, meaning many low intensity flows combine to DoS the target links. These links are harder to differentiate from legitimate traffic, which prevents flow monitoring efforts from detecting these attacks.

Question 60

60. Why would an attacker mounting a crossfire attack choose to dynamically change the set of target links during an attack (known as a rolling attack)?

Answer 60

Rolling attacks are implemented by an attacker to indefinitely continue an attack on a target area. Continuing to flood the same set of target links will ultimately have negative effects on the attack when router failure detection mechanisms are tripped. Additionally rolling attacks will make the crossfire attack even harder to detect by changing the attack vector without changing the overall target area.

Question 61

61. Briefly describe the 3 categories of attackers against DNS.

Answer 61

Off-path adversaries can’t observe DNS queries and responses. They will trigger specific DNS lookups, but must generate numerous packets in hopes of matching the request the resolver will accept as they must guess the transaction ID and other entropy. On-path adversaries can passively observe the actual lookups requested by a resolver and can directly forge DNS replies. As long as the resolver receives the forged reply before the legitimate one, it will accept the forged reply. In-path adversaries can both block and modify packets and can block the legitimate packet. Hold-On can’t help here as the legitimate packets can be blocked.

Question 62

62. How does the Hold-On algorithm work?

Answer 62

Because the legitimate reply cannot be blocked by on-path adversaries, the “Hold-On” period can be used to wait for the legitimate reply to arrive. The stub resolver/forwarded first learns the expected RTT and TTL associated with legitimate traffic to remote recursive resolver. Then after issuing a DNS query, it starts its Hold-On timer. If a DNSSEC-protected response is expected, local signature validation is done for each reply and returns the first fully validated reply to the client or a DNSSEC error if the Hold-On timer expires before one is validated. If there is no DNSSEC, the resolver compares the timing of the reply to the expected RTT and compares the TTL field in the header to the expected TTL. If a reply is validated it will return this reply to the client, but if there are mismatches, it ignores the response and continues to wait. If the timer expires, it will send the last reply received that was not validated.

Question 63

63. Describe the differences in the terms network virtualization and software defined networking (SDN). How can we use network virtualization to evaluate and test SDNs?

Answer 63

Network Virtualization refers to abstracting the network away from the physical equipment, which can be accomplished without SDN (we did this in Project 1 using Mininet!). On the other hand, SDN refers separating the control plane from the data plane by using a centralized logic controller. SDN does not necessarily imply Network Virtualization is employed. Network virtualization software like Mininet allows SDNs to be tested in a virtual environment by using logical processes to emulate physical network devices, including OpenFlow capable switches. By emulating the physical equipment, control plane logic for an SDN can be tested without the need for physical equipment and complicated data collection methods.