Project 2: IPv4 Router

Due: Tuesday 11/15 by 5pm.

For your questions: ecalp at cs dot wisc dot edu

News:

• 11/15: Example test case for you to write your own scenarios are here.
• 11/14: How are we supposed to hand it in?
• 11/11: New test case available!
• 11/07: FAQ is updated. Make sure to check it before sending an email!
• 11/05: Test case for part 3 (Item 4&5) is now available

Overview

Now that you have built a simple learning Ethernet switch and feel more comfortable with the Switchyard framework, you will get to do even more cool stuff using it. In this assignment, you are going to complete a series of tasks to eventually create a fully functional IPv4 router. At a high level, your router will have the following capabilities:

• Responding to/Making ARP requests
• Receiving packets and forwarding them to their destination by using a lookup table
• Responding to/Generating ICMP messages

Details

In order to create this cool router with the aforementioned capabilities, you will implement 5 main functionalities:

1. Respond to ARP (Address Resolution Protocol) requests for addresses that are assigned to interfaces on the router
2. Make ARP requests for IP addresses that have no known Ethernet MAC address. A router will often have to send packets to other hosts, and needs Ethernet MAC addresses to do so
3. Receive and forward packets that arrive on links and are destined to other hosts. Part of the forwarding process is to perform address lookups ("longest prefix match" lookups) in the forwarding information base. You will eventually just use "static" routing in your router, rather than implement a dynamic routing protocol like RIP or OSPF
4. Respond to Internet Control Message Protocol(ICMP) messages like echo requests ("pings")
5. Generate ICMP error messages when necessary, such as when an IP packet's TTL (time to live) value has been decremented to zero

• Item #1 (NOTE: You will also implement the functionality that is described in One more note on the same page)
• Item #2 and Item #3
• Item #4 and Item #5

Address Resolution Protocol (ARP) Review

Internet Control Message Protocol (ICMP) Review

Testing your code

Just like the previous assignment, you should test the correctness of your implementation by writing your own test cases. As your friendly TA, I should warn you that in this assignment you will be implementing more functionalities and your router will be handling more events concurrently compared to the previous assignment. Therefore, you should think about reasonable ways to test the correctness of your implementation. One thing you can do is create test separate test cases that only tests certain functionalities. This will allow you to see whether the individual parts of your router is working properly. Then, you can generate larger test cases to make sure that the separate modules work together properly without breaking each other. As always, do not forget to consider corner cases (read: try to break your implementation).

Once you test your implementation with test scenarios, you can also test your router in Mininet. You can find more information on how to run Mininet tests for the aforementioned functionalities on their corresponding web pages.

Need a reminder on how to create test scenarios?

Test Scenarios

• More test case for you here.
  
• Test case for part 3 is here.
  
• You can find the test scenarios for part 1&2 here.
  
  • Note: First two test scenarios only test the router functionalities that are defined in part 1 of the assignment. Rest of the test scenarios will work after you implement part 2 as well. When you run the first test scenario you might get an error even if you pass all 3 tests. You can ignore this. The second test scenario should fail after you finish part 2 of the assignment. I will send out more test scenarios to cover the final part of the assignment.

Handing it in

For submitting your work, you should put the following files into one partner's handin directory. Handin directory is ~cs640-1/handin/login/p2 where login is your CS login.

• myrouter.py: Your router implementation
• README.txt: This file will contain a line for each student in your team: [name_of_student][single whitespace][10-digit UWID]

IMPORTANT: The file names in your handin directory has to exactly match the file names above. Otherwise, you will lose points!

In addition to these files, you will also submit your test scenarios. Please submit your Python files(.py), not the compiled version with the .srpy extension.

Grading

50% of your grade will be based on successfully implementing the functional components of the router to create the target functionalities. The remaining 50% will be based on successfully passing the test cases, which will test that the implemented functionalities work correctly over a range of conditions.

Notes

1. Great news! You can keep using the same development environment that you used for doing your first assignment. In case people removed their development environments or have decided to switch to the VM image that I provided, here are the useful information:
   • You can find the VM image here. (user name: cs640user - password: cs640)
   • You can learn more about importing a VM image in VirtualBox here. CSL machines already have VirtualBox installed so you should be able to use the image there without any problems. You are also free to use your favorite virtuaization software for importing the image but you will most probably have to deal with the possible issues on your
2. If you are a free soul and want to setup Switchyard in a different environment you are welcome to do that as well. You can find some useful information here. I prepared a file with commands that I have used to setup the Switchyard environment on Ubuntu 14.04. This might or might not be useful for you depending on your environment.
3. Documentation for Switchyard is available at http://cs.colgate.edu/~jsommers/switchyard.
4. Instructions for submitting the assignment will be announced later.
5. I will update the FAQ if multiple people run into the same problems, so it might be useful to regularly check the FAQ. Otherwise, you can always shoot me an e-mail.

FAQ

1. Q: What should the router do in the following scenario? Packet for a certain IP address arrives at the router and it sends an ARP request to find the MAC address. Before receiving the ARP reply, the router receives another packet (non-ARP) for the same IP address, does it send an ARP request again?
   
   A: No, in this case you do not retransmit the ARP request for the second packet. More generally, your router might receive many packets for a certain IP address while there is an outstanding ARP request for that IP address. In this case, your router should not send out any new ARP requests or update the timestamp of the initial ARP request. However, your router should buffer the new data packets so that it can transmit them to the destination host once it receives the ARP reply. IMPORTANT: If your router buffers multiple packets for a destination host that has an outstanding ARP request, upon receiving the corresponding ARP reply these packets has to be forwarded to the destination host in the order they arrived to the router!


2. Q: When an ARP request arrives at the router for a destination IP address that is not assigned to one of the router's interfaces, does the router need to flood the ARP request? Or just drop it?
   
   A: Your router should drop the packet in this case.


3. Q: When the router needs to make an ARP request for the next hop IP address (which is obtained after the longest prefix match lookup), should it flood the request on all ports?
   
   A: The router does not flood the ARP request on all ports. The ARP query is merely broadcast on the port obtained from doing a longest prefix match lookup. The response ARP query *should* come back on the same port but it doesn't actually need to (and it doesn't matter for the purposes of forwarding the packet or sending out the ARP request).
   
   
4. Q: When sending ICMP echo replies or error messages, does the router need to do table lookup & send ARP requests if needed? Can the router send the ICMP messages back on the interface through which the IP packet was received?
   
   A: The router will still need to do an ARP query as it normally does for forwarding an IP packet. It doesn't matter that an echo request arrives on, say port 0. The echo reply may end up going out on a different port depending on the forwarding table lookup. The entire lookup and ARP query process should be the same as forwarding an IP packet, and will always behave exactly this way.
   
   
5. Q: How many error messages will be generated if a packet has TTL expired and network unreachable errors at the same time?
   
   A: Your router will only generate a network unreachable error in this case. Since the router decrements the TTL field after doing a lookup, if the lookup fails then your router will not reach at decrementing the TTL value.
   
   
6. Q: I get the following error message when running the test cases. What is going on???
   

   IP packet should be forwarded to 172.16.42.2 out router-eth2
   In particular:
   A wildcard match failed.  when comparing the packet you sent
   versus what I expected, and the predicate (lambda pkt:
   pkt.get_header(IPv4).ttl == 63) passed.  Here is the packet
   that failed the check: Ethernet
   20:00:00:00:00:01->30:00:00:00:00:01 IP | IPv4
   192.168.1.100->172.16.42.2 ICMP | ICMP EchoRequest 0 42 (0
   data bytes).  Here is what I expected to match: Ethernet
   20:00:00:00:00:01->30:00:00:00:00:01 IP | IPv4
   192.168.1.100->172.16.42.2 ICMP | ICMP
   EchoRequest->EchoRequest.
   

   A: Make sure the Ethernet frame headers are correct and reflect the right source and destination address. Ethernet addresses need to be modified for each hop.
   
   
7. Q: Following up from Q1: if there are multiple packets buffered for the same destination host or next hop and the router doesn't receive an ARP reply after sending 5 retransmissions of ARP requests what should the router do?
   
   A: As it is explained in the part 3 of the project, your router will send an ICMP destination host unreachable message back to the host referred to by the source address in the IP packet. When there are multiple packets buffered for the same destination address, the router will send an ICMP error message to each source host of these packets (even if the same source host sent multiple packets).