« Back to the main CSCI1680 website

Homework 3 (Solutions)

Due Monday, October 31, 2022 at 11:59PM EST

Meta-note

• You are welcome (and encouraged!) to collaborate with your peers, though the answers you write down must be your own
• When you are done, please upload a PDF of your work to Gradescope under the assignment labeled "Homework 3". If you have issues accessing Gradescope, please contact the course staff

Problem 1: FTP vs NAT (20 pts)

Network Address Translation (NAT) allows multiple clients in a private network to share a single public IP address (on the NAT gateway).

Suppose a router performing NAT with public address 205.10.2.5 is operating on behalf of the nodes in your home, which are part of the internal network 192.168.100.0/24.

Part A (7 pts)

When a client with address 192.168.100.2 sends a TCP packet to an outside server at 134.21.4.10 (as shown in the table below), how does NAT modify the packet?

To express your answer, fill in the table with the translated version of the packet header and explain your reasoning below. When writing the packet fields, be as specific as you can—if there are multiple options for certain fields, just choose an arbitrary value.

Original packet (before NAT):

	Source	Destination
IP	192.168.100.2	134.21.4.10
TCP Port	5555	20

After NAT:

	Source	Destination
IP	205.10.2.5	134.21.4.10
TCP Port	12345	20

NAT rewrites the IP source of the packet to match the outside IP, and it selects a new source port for the connection. The source port (here, 12345) can be any unused ephemeral TCP port (actual answer is dependent on the NAT's implementation).|

Part B (3 pts)

What information does the router need to keep internally in order to properly translate and forward the server’s response?

Assume that the response packet has the same IPs and ports as the server receives, with the roles of source and destination reversed. You don’t need to precisely describe what data structures the router is using—just specify what information it will need to store to forward the response.

The router's NAT table needs to record that packets destined for 205.10.2.5:12345 should be translated back to 192.168.100.2:5555. This will ensure that H1 receivse a packet that looks like it came from the same TCP connection.

Part C (4 pts)

FTP (File Transfer Protocol) is a protocol that runs on top of TCP, and needs two parallel connections: one for commands, and one for data. The relevant parts of the protocol work as follows:

• First, a client opens an FTP control connection to a server on port 20. * Then, the client sends a PORT command to the server, which includes the client’s IP address (as known by the client) and the port the client is listening on (say, port 7000).
• The server then opens a data connection to the client on that IP and port.

In our example, the client would open a connection to 134.21.4.10 on port 20 and would send a command PORT 192.168.100.2,7000 to the server. Since our client is behind a NAT gateway, the data connection does not work. Why not?

This doesn't work because 192.168.100.2 is not routable on the public Internet (and the IP lives behind the NAT). Since any number of networks might use the private 192.168.0.0/16 prefix, there is no way to get the packet back to it intended destination. Furthermore, if the server tries to connect to this port, the packet would likely be dropped somewhere along the way since it pertains to a private network and should not be forwarded on the Internet.

Part D (3 pts)

Suppose the FTP client is smart and is able to determine NAT’s outside IP address. Thus, it instead sends the command PORT 205.10.2.5, 7000 to the server, but this still does not work. Why not?

While this is better, R1 doesn't have a rule in its NAT table to translate packets arriving on 205.10.2.5:7000, and thus will drop the packet.

Part E (3 pts)

Based on its description in this problem, why does FTP’s PORT command violate good principles of layering in network protocols?

FTP is "violating layering" because the application-layer protocol depends on network-layer information (ie, the client's IP) in order to function. This is not good practice because either the the application would need to change in order to handle certain networking configurations (like NAT), or the network would need to be aware of the FTP protocol and operate differently to allow it to function. In contrast, it's more advantageous to separate out these network and application-layer concerns, so that both can evolve independently.

Bonus (Extra credit: +4 pts)

If you can change the router’s NAT implementation (including understanding the FTP protocol and potentially modifying the the FTP messages), how could you make the data connection work?

When the NAT sees a PORT command (say, for port 7000), it can add a NAT rule and rewrite the PORT message in a similar way for the new connection. This is non-ideal and somewhat expensive, howerver, as it requires the router to identify the FTP protocol and parse the payload.

Problem 2: Distance Vector (20 pts)

Consider the following topology in a distance vector routing protocol, such as RIP, that does not use poison reverse or split horizon.

Part a (7 pts)

Suppose the A-B link is disconnected. Describe a sequence of events (eg. A announces a distance of X, B adds route for A with cost X+1, etc.) that leads to a count-to-infinity scenario.

1. A-B link fails, B sets its distance entry for A to (A, 16, A) (where (x, y, z) is (destination, cost, next hop))
2. B sends an update to D with (A, 16). D has route (A, 2, B) in its table and thus updates its entry for A to (A, 16, B)
3. C sends an update to D using its (now old) route information, (A, 2). D sees a shorter path to A, so it updates its table to (A, 3, C)
4. D sends an update to B, (A, 4). B sees a shorter path to A, and updates its table to (A, 5, D)
5. B sends an update to C, (A, 5). C has route (A, 2, B), so it sees this as new information and updates its table to (A, 5, B)
6. C sends an update to B, ... (repeat)

Part b (7 pts)

In this topology, does using split horizon (ie, when you don't advertise routes learned from some neighbor router X back to X) prevent count to infinity to happening? Why or why not?

No, split horizon does not prevent this problem when there are more than 2 nodes. The loop of at least 3 nodes ensures that each node learns about the outdated information from a node other than its next hop–so restricting advertisments to the next hop has no effect on these cases.

Part c (3 pts)

Why can't count-to-infinity happen in a link state routing protocol?

In a link-state protocol, each node has a complete graph of the network, rather than relying on messages only from its neighbors. Since each node knows about the entire graph, it can use a shortest-path algorithm locally to determine the best paths without creating any loops.

Part d (3 pts)

Why can't count-to-infinity happen in a path vector protocol (like BGP)?

A path vector protocol like BGP includes the full routing path when advertising a prefix. This means that it is generally not possible to create a routing loop, as an AS would see itself in an advertised path.

Problem 3: BGP - AS relationships and Gao-Rexford principles (20 pts)

Consider the figure below, where nodes represent ASes and arrows represent customer-provider AS relationships. Note that the arrows do not constrain the direction of traffic–they only relate to the BGP announcements!

For this problem, assume that ASes follow the Gao-Rexford model we discussed in class, and that ASes A and B eventually learn all of the advertisments that the other one makes via their respective providers.

Part a (4 pts)

What is the largest prefix that A can advertise to its providers, given that it has two customers X and Y, with prefixes as shown in the figure?

A can aggregate the prefixes for X and Y and advertise 100.20.0.0/16.

Part b (4 pts)

True or False: If B and A decide to become peers, B will start advertising Y's prefix. Explain your reasoning.

False. As a peer, B will learn about X and Y from A, but it will not advertise routes to them. If B did this, it would end up receiving transit traffic for X and Y, which is not in B's best interest.
(Grading note: Must explain reasoning for credit–true/false is not sufficient.)

Part c (4 pts)

If X decides to also become a customer of B (creating the dashed line in the figure), what new prefix will B advertise to its providers?

B will advertise X's prefix, 100.20.128.0/17.

Part d (4 pts)

Normally, X receives BGP announcements about Y from A, which allows nodes in X to know how to reach nodes in Y. If X becomes a customer of B (ie, when the dashed line is created), does B receive a route to reach Y via X? Why or why not?

No. X will not export routes about A or Y to B, since B is a provider for X. If B advertised these prefixes, it would end up receiving transit traffic for A and Y, which is not in X's best interest.

Part e (4 pts)

Say the administrators of X were considering becoming a customer of B, but then decided not to do so (ie, no dashed line). B's administrators get mad and advertise X's prefix anyway, even though they have no link to X. What happens to traffic sent to or from X?
This is prefix hijacking–all traffic destined for X will be routing to B, as B is advertising a more specific prefix than A (which is advertising 100.20.0.0/16, per part (a)).
(Grading note: Okay if response indicates that only some traffic destined for X will reach B if answer for part (a) does not mention prefix aggregation.)