Computer Networks

COS 461, Princeton University Spring 2015


Assignment 2: Internet Router

Due 11:59 p.m. Monday, April 6, 2015

  • The assignment source code is here.

    In this assignment you will write a simple router with a static routing table. Your router will receive raw Ethernet frames and forward them to the appropriate outgoing interface.

    Your router will route real packets from an emulated host (client) to two emulated HTTP servers sitting behind your router. When you have finished the forwarding path of your router, you should be able to access these servers using regular client software. In addition, you should be able to ping and traceroute to and through your functioning Internet router. A sample routing topology is shown below:

    alt text

    If the router is functioning correctly, all of the following operations should work:

    Network Emulation using Mininet

    This assignment runs on top of Mininet which was built at Stanford. Mininet allows you to emulate a topology on a single machine. It provides the needed isolation between the emulated nodes so that your router node can process and forward real Ethernet frames between the hosts. We provide scripts to set up the Mininet topology above on which your router will work. In addition your code will use the POX controller on Mininet in order to run your code on the router in the Mininet topology. We also provide the scripts to set up POX and your code on the topology. In the following section we will tell you how to set up your environment to emulate the the topology above using Mininet and POX given the scripts that we have provided.

    Environment Setup
    After you have downloaded the assignment source, you can set up your working directory by using tar with the following command: 'tar -xzvf ass2.tar.gz'. This will create your working directory, ass2/. Once you have changed into that directory, you must run the configuration script provided as follows: 'sudo ./config.sh'. There are two configuration files. The IP_CONFIG file lists the IP addresses assigned to the emulated hosts. The rtable file is the static routing table used for the simple router.

    In order to start Mininet, first export your Python path: 'export PYTHONPATH=$PYTHONPATH:/usr/lib/python2.7/site-packages/:/usr/lib/python2.6/site-packages/:~/ass2/pox_module/'. Then begin the Mininet set up script that we provide: 'sudo ./run_mininet.sh' Keep this terminal open, as you will need the Mininet command-line for debugging. (Do not do ctrl-z)

    Next you will begin the POX controller for Minnet. In a new terminal, begin the POX set up script that we have provided: 'sudo ./run_pox.sh'. Please note that you have to wait until Mininet is able to connect to the POX controller before you continue to the next step.
    Once Mininet is connected to POX, keep POX running. (Do not do ctrl-z)

    In order to start reference solution proviced, in a third terminal, start the reference solution binary, sr_solution: ' ./sr_solution'. The output from the reference solution will begin by loading the routing table as specified in rtable. IP addresses for the hosts in the topology are in the IP_CONFIG file.

    To test the router, you can issue commands in the Mininet console. To run a command on an emulated host, type the host name followed by the command. For example to have the clinet ping HTTP server 1, you would run the following command: 'client ping -c 3 192.168.2.2'. The client can find the route to HTTP server 1, using traceroute in the following command: 'client traceroute -n 192.168.2.2'. The client can retrieve the main page of HTTP server 1 using client 'wget http://192.168.2.2'

    To help you get started, we provide some starter code. After following the previous steps in this section, You can build and run the starter code as follows: 'make;./sr'. The starter code initializes the routing table given a file and it gets the router ready to receive packets. You can log the packets received and generated by your program by using the "-l" parameter with your SR program: './sr -l logname.pcap' The file will be in pcap format, so you can use wireshark or tcpdump to read it. Besides SR, you can also use mininet to monitor the traffic that goes in and out of the emulated nodes such as the router, server1 and server2, using tcpdump. (For example to do so for HTTP server one, in the mininet console, use the command: 'server1 sudo tcpdump -n -i server1-eth0'.)

    General Forwarding Logic

    There are two main parts to this assignment: Handling ARP and IP forwarding.

    Your router will receive raw Ethernet frames and have to send raw Ethernet frames. To handle these frames you should understand source and destination MAC addresses and the idea that we forward a packet one hop by changing the destination MAC address of the forwarded packet to the MAC address of the next hop's incoming interface.

    Address Resolution Protocol

    ARP is needed to determine the next-hop MAC address that corresponds to the next-hop IP address stored in the routing table. Without the ability to generate an ARP request and process ARP replies, your router would not be able to fill out the destination MAC address field of the raw Ethernet frame you are sending over the outgoing interface. Analogously, without the ability to process ARP requests and generate ARP replies, no other router could send your router Ethernet frames. Therefore, your router must generate and process ARP requests and replies.

    To lessen the number of ARP requests sent out, you are required to cache ARP replies. Cache entries should time out after 15 seconds to minimize staleness. The provided ARP cache class already times the entries out for you.

    When forwarding a packet to a next-hop IP address, the router should first check the ARP cache for the corresponding MAC address before sending an ARP request. In the case of a cache miss, an ARP request should be sent to a target IP address about once every second until a reply comes in. If the ARP request is sent five times with no reply, an ICMP destination host unreachable is sent back to the source IP as stated above. The provided ARP request queue will help you manage the request queue.

    In the case of a received ARP request, you should only send an ARP reply if the target IP address is one of your router's IP addresses. In the case of an ARP reply, you should only cache the entry if the target IP address is one of your router's IP addresses. Note that ARP requests are sent to the broadcast MAC address (ff-ff-ff-ff-ff-ff). ARP replies are sent directly to the requester's MAC address.

    Handling ARP

    Given a raw Ethernet frame, if the frame contains an ARP packet, check:

    IP Forwarding

    Given a raw Ethernet frame, if the frame contains an IP packet that is not destined towards one of our interfaces:

    If an error occurs in any of the above steps, you will have to send the appropriate ICMP message back to the sender notifying them of the error.
    Internet Control Message Protocol

    ICMP is a simple protocol that can send control information to a host. In this assignment, your router will use ICMP to send messages back to a sending host. You will need to properly generate the following ICMP messages (including the ICMP header checksum) in response to the sending host under the following conditions:

    IP Packet Destinations

    An incoming IP packet may be destined for one of your router's IP addresses, or it may be destined elsewhere. If it is sent to one of your router's IP addresses, you should take the following actions, consistent with the section on protocols above:

    Code Overview

    Basic Functions

    Your router receives a raw Ethernet frame and sends raw Ethernet frames when sending a reply to the sending host or forwarding the frame to the next hop. The basic functions to handle these functions are:

    void sr_handlepacket(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)
    This method, located in sr_router.c, is called by the router each time a packet is received. The "packet" argument points to the packet buffer which contains the full packet including the ethernet header. The name of the receiving interface is passed into the method as well.
    int sr_send_packet(struct sr_instance* sr, uint8_t* buf, unsigned int len, const char* iface)
    This method, located in sr_vns_comm.c, will send an arbitrary packet of length, len, to the network out of the interface specified by iface.

    You should not free the buffer given to you in sr_handlepacket (you'll see the comment "lent" or "borrowed" whenever you should not free a buffer). You are responsible for doing correct memory management on the buffers that sr_send_packet borrows from you (that is, sr_send_packet will not call free on the buffers that you pass it).

    The assignment requires you to send an ARP request about once a second until a reply comes back or we have sent five requests. To do so, you must implement the function sr_arpcache_sweepreqs defined in sr_arpcache.c. This function is called every second, and you should add code that iterates through the ARP request queue and re-sends any outstanding ARP requests that haven't been sent in the past second. If an ARP request has been sent 5 times with no response, a destination host unreachable should go back to all the sender of packets that were waiting on a reply to this ARP request. You must add this functionality to the handle_arpreqs function defined in sr_router.c. Pseudocode for these operations is provided in sr_arpcache.h.

    Debugging Functions

    We have provided you with some basic debugging functions in sr_utils.h, sr_utils.c. Feel free to use them to print out network header information from your packets. Below are some functions you may find useful:

    Data Structures

    The Router (sr_router.h):

    The full context of the router is housed in the struct sr_instance (sr_router.h). sr_instance contains information about topology the router is routing for as well as the routing table and the list of interfaces.

    Interfaces (sr_if.c/h):

    After connecting, the server will send the client the hardware information for that host. The stub code uses this to create a linked list of interfaces in the router instance at member if_list. Utility methods for handling the interface list can be found at sr_if.c/h.

    The Routing Table (sr_rt.c/h):

    The routing table in the stub code is read on from a file (default filename "rtable", can be set with command line option -r ) and stored in a linked list of routing entries in the current routing instance (member routing_table).

    The ARP Cache and ARP Request Queue (sr_arpcache.c/h):

    You will need to add ARP requests and packets waiting on responses to those ARP requests to the ARP request queue. When an ARP response arrives, you will have to remove the ARP request from the queue and place it onto the ARP cache, forwarding any packets that were waiting on that ARP request. Pseudocode for how to use the ARP cache and request queue is provided in sr_arpcache.h.

    The base code already creates a thread that times out ARP cache entries 15 seconds after they are added for you.

    Protocol Headers (sr_protocol.h)

    Within the router framework you will be dealing directly with raw Ethernet packets. The stub code itself provides some data structures in sr_protocols.h which you may use to manipulate headers easily. There are a number of resources which describe the protocol headers in detail. Network Sorcery's RFC Sourcebook provides a good reference to the packet formats you'll be dealing with:

    For the actual specifications, there are also the RFC's for ARP (RFC826), IP (RFC791), and ICMP (RFC792).

    Requirements

    Also, don't forget to fill out your readme! (It is worth 1 point)

    This assignment is considerably harder than the first two assignments, so please get started early. To help you debug your topologies and understand the required behavior, we provide a reference binary and you can find it at ~/ass2/sr_solution in your directory.

    Extra Credit

    Extra Credit will be posted on March 23, 2015. It must be done entirely on your own. You may only get clarifications from course staff and no help from anyone.

    Submission

    You should submit your completed router by the due date to CS Dropbox. In your README, describe design decisions that you made, and any trade-offs that you encountered in the design.