COS-461 Assignments: Router


Assignment 2: Building your own Internet Router

  • The assignment source code is here.

    In this lab assignment you will be writing a simple router with a static routing table. Your router will receive raw Ethernet frames. It will process the packets just like a real router, and forward them to the appropriate outgoing interface. We’ll make sure you receive the Ethernet frames; your job is to create the forwarding logic so packets go to the correct interface.

    Your router will route real packets from an emulated host (client) to two emulated application servers (http server 1/2) sitting behind your router. The application servers are each running an HTTP server. 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:

    Additional requirements are laid out in the 'Required Functionality' section.

    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 like a real router. You don't have to know how Mininet works to complete this assignment, but more information about Mininet (if you're curious) is available here.

    Environment Setup

    cd ~
    wget http://www.cs.princeton.edu/courses/archive/spr14/cos461/assignments/router/ass2.tar.gz
    tar -xzvf ass2.tar.gz
    cd ass2/
    sudo ./config.sh
    

    Configuration Files

    There are two configuration files.

    The default IP_CONFIG and rtable should look like the following:

    > cat ~/ass2/IP_CONFIG
    server1 192.168.2.2
    server2 172.64.3.10
    client    10.0.1.100
    sw0-eth1 192.168.2.1
    sw0-eth2 172.64.3.1
    sw0-eth3 10.0.1.1
    > cat ~/ass2/rtable
    10.0.1.100  10.0.1.100  255.255.255.255 eth3
    192.168.2.2 192.168.2.2 255.255.255.255 eth1
    172.64.3.10  172.64.3.10  255.255.255.255 eth2

    Test Connectivity of Your Emulated Topology

    Start Mininet emulation:

    > cd ~/ass2/
    > export PYTHONPATH=$PYTHONPATH:/usr/lib/python2.7/site-packages/:/usr/lib/python2.6/site-packages/:~/ass2/pox_module/
    > sudo ./run_mininet.sh
    You should see some output like the following:
    
    *** Shutting down stale SimpleHTTPServers  
    *** Shutting down stale webservers  
    server1 192.168.2.2
    server2 172.64.3.10
    client 10.0.1.100
    sw0-eth1 192.168.2.1
    sw0-eth2 172.64.3.1
    sw0-eth3 10.0.1.1
    *** Successfully loaded ip settings for hosts
     {'server1': '192.168.2.2', 'sw0-eth3': '10.0.1.1', 'sw0-eth1': '192.168.2.1', 'sw0-eth2': '172.64.3.1', 'client': '10.0.1.100', 'server2': '172.64.3.10'}
    *** Creating network
    *** Creating network
    *** Adding controller
    Unable to contact the remote controller at 127.0.0.1:6633
    *** Adding hosts:
    client server1 server2 
    *** Adding switches:
    sw0 
    *** Adding links:
    (client, sw0) (server1, sw0) (server2, sw0) 
    *** Configuring hosts
    client server1 server2 
    *** Starting controller
    *** Starting 1 switches
    sw0 
    *** setting default gateway of host server1
    server1 192.168.2.1
    *** setting default gateway of host server2
    server2 172.64.3.1
    *** setting default gateway of host client
    client 10.0.1.1
    *** Starting SimpleHTTPServer on host server1 
    *** Starting SimpleHTTPServer on host server2 
    *** Starting CLI:
    mininet> 
    Keep this terminal open, as you will need the Mininet command-line for debugging. (Do not do ctrl-z)

    Start POX controller:

    Mininet requires a controller, which we implemented in POX. In a second terminal, run the following command:
    > cd ~/ass2/
    > sudo ./run_pox.sh
    You should be able to see some output like the following:
    
    POX 0.0.0 / Copyright 2011 James McCauley
    DEBUG:.home.mininet.ass2-test.ass2.pox_module.cos461.ofhandler:*** ofhandler: Successfully loaded ip settings for hosts
     {'server1': '192.168.2.2', 'sw0-eth3': '10.0.1.1', 'sw0-eth1': '192.168.2.1', 'sw0-eth2': '172.64.3.1', 'client': '10.0.1.100', 'server2': '172.64.3.10'}
    
    INFO:.home.mininet.ass2-test.ass2.pox_module.cos461.srhandler:created server
    DEBUG:.home.mininet.ass2-test.ass2.pox_module.cos461.srhandler:SRServerListener listening on 8888
    DEBUG:core:POX 0.0.0 going up...
    DEBUG:core:Running on CPython (2.7.4/Sep 26 2013 03:20:26)
    INFO:core:POX 0.0.0 is up.
    This program comes with ABSOLUTELY NO WARRANTY.  This program is free software,
    and you are welcome to redistribute it under certain conditions.
    Type 'help(pox.license)' for details.
    DEBUG:openflow.of_01:Listening for connections on 0.0.0.0:6633
    
    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, you will see the following output in the POX terminal:
    INFO:openflow.of_01:[Con 1/196179870038597] Connected to b2-6c-af-77-3a-45
    DEBUG:.home.mininet.ass2-test.ass2.pox_module.cos461.ofhandler:Connection [Con 1/196179870038597]
    DEBUG:.home.mininet.ass2-test.ass2.pox_module.cos461.srhandler:SRServerListener catch RouterInfo even, info={'eth3': ('10.0.1.1', '26:17:b5:a3:3f:29', '10Gbps', 3), 'eth2': ('172.64.3.1', 'f2:62:e2:cd:ea:4c', '10Gbps', 2), 'eth1': ('192.168.2.1', '52:3d:27:94:a5:2a', '10Gbps', 1)}, rtable=[('10.0.1.100', '10.0.1.100', '255.255.255.255', 'eth3'), ('192.168.2.2', '192.168.2.2', '255.255.255.255', 'eth1'), ('172.64.3.10', '172.64.3.10', '255.255.255.255', 'eth2')]
    Ready.
    POX>
    Keep POX running. (Do not do ctrl-z)

    Start reference solution:

    Now you are ready to test out the connectivity of the environment setup. To do so, open a third terminal and run the reference solution binary file “sr_solution”:
    > cd ~/ass2/
    > ./sr_solution
    You should be able to see some output like the following:
    Loading routing table from server, clear local routing table.
    Loading routing table
    ---------------------------------------------------------------------
    Destination     Gateway         Mask                     Iface
    10.0.1.100     10.0.1.100      255.255.255.255   eth3
    192.168.2.2   192.168.2.2    255.255.255.255   eth1
    172.64.3.10   172.64.3.10    255.255.255.255   eth2
    ---------------------------------------------------------------------
    Client ubuntu connecting to Server localhost:8888
    Requesting topology 0
    successfully authenticated as ubuntu
    Loading routing table from server, clear local routing table.
    Loading routing table
    ---------------------------------------------------------------------
    Destination     Gateway         Mask                     Iface
    10.0.1.100     10.0.1.100      255.255.255.255   eth3
    192.168.2.2   192.168.2.2    255.255.255.255   eth1
    172.64.3.10   172.64.3.10    255.255.255.255   eth2
    ---------------------------------------------------------------------
    Router interfaces:
    eth3    HWaddr86:05:70:7e:eb:56
            inet addr 10.0.1.1
    eth2    HWaddrb2:9e:54:d8:9d:cd
            inet addr 172.64.3.1
    eth1    HWaddr36:61:7c:4f:b6:7b
            inet addr 192.168.2.1
     <-- Ready to process packets --> 

    In this particular setup, 192.168.2.2 is the IP for server1, and 172.64.3.10 is the IP for server2. You can find the IP addresses in your IP_CONFIG file.

    Testing router functionality

    To test the router functionality, you issue commands in the Mininet console. To run a command on an emulated host, type the host name followed by the command. Three examples follow.

    For example, the following command issues 3 pings from the client to the server1.

    mininet> client ping -c 3 192.168.2.2
    You should be able to see the following output.
    PING 192.168.2.2 (192.168.2.2) 56(84) bytes of data.
    64 bytes from 192.168.2.2: icmp_req=1 ttl=63 time=66.9 ms
    64 bytes from 192.168.2.2: icmp_req=2 ttl=63 time=49.9 ms
    64 bytes from 192.168.2.2: icmp_req=3 ttl=63 time=68.8 ms

    You can also use traceroute to see the route between client to server1.

    mininet> client traceroute -n 192.168.2.2
    You should be able to see the following output.
    traceroute to 192.168.2.2 (192.168.2.2), 30 hops max, 60 byte packets
     1  10.0.1.1  146.069 ms  143.739 ms  143.523 ms
     2  192.168.2.2  226.260 ms  226.070 ms  225.868 ms

    Finally, to test the web server is properly working at the server1 and server2, issue an HTTP request by using wget or curl.

    mininet> client wget http://192.168.2.2
    You should see the following output.
    --2012-12-17 06:52:23--  http://192.168.2.2/
    Connecting to 192.168.2.2:80... connected.
    HTTP request sent, awaiting response... 200 OK
    Length: 161 [text/html]
    Saving to: `index.html'
    
         0K                                                       100% 17.2M=0s
    
    2012-12-17 06:52:24 (17.2 MB/s) - `index.html' saved [161/161]

    Finally, to close Mininet, simple type "exit" in the Mininet console, and to close POX type ctrl-D.

    Starter Code

    In this assignment, you will replicate the functionality of sr_solution. To help you get started, we provide some starter code.

    After following the steps in the 'Environment Setup' section, you should have all the pieces needed to build and run the router.

    The starter source code

    You can build and run the starter code as follows:

    > cd ~/ass2/router/
    > make
    >./sr 

    The starter code initializes the routing table given a file and it gets the router ready to receive packets.

    Logging Packets

    You can log the packets receives and generated by your SR program by using the "-l" parameter with your SR program. The file will be in pcap format, i.e., you can use wireshark or tcpdump to read it.

    > ./sr -l logname.pcap

    Besides SR, you can also use mininet to monitor the traffic goes in and out of the emulated nodes, i.e., router, server1 and server2. Mininet provides direct access to each emulated node. Take server1 as an example, to see the packets in and out of it, go to mininet CLI:

    mininet> server1 sudo tcpdump -n -i server1-eth0

    or you can bring up a terminal inside server1 by

    mininet> xterm server1

    then inside the newly popped xterm,

    > sudo tcpdump -n -i server1-eth0

    General Forwarding Logic

    To get you started, an outline of the forwarding logic for a router follows, although it does not contain all the details. There are two main parts to this assignment: Handling ARP and IP forwarding

    IP Forwarding

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

    Obviously, this is a very simplified version of the forwarding process, and the low-level details follow in the 'Protocols to Understand' section. For example, 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.

    Handling ARP

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

    Details on how to handle ARP packets are discussed in the 'Protocols to Understand' section.

    Protocols to Understand

    Ethernet

    You are given a raw Ethernet frame and have to send raw Ethernet 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.

    Internet Protocol

    Before operating on an IP packet, you should verify its checksum and make sure it meets the minimum length of an IP packet. You should understand how to find the longest prefix match of a destination IP address in the routing table described in the "Environment Setup" section. If you determine that a datagram should be forwarded, you should correctly decrement the TTL field of the header and recompute the checksum over the changed header before forwarding it to the next hop.

    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:

    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.

    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.

    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).
  • 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:

    Length of Assignment

    This assignment is considerably harder than the first 2 labs, so get started early.

    In our reference solution, we added 520 lines of C, including whitespace and comments:

    > wc -l ~/ass2/router/*.c | tail -1
     1585 total
    > wc -l ~/cos461/router/solution/*.c | tail -1
     2104 total
    Of course, your solution may need fewer or more lines of code, but this gives you a rough idea of the size of the assignment to a first approximation.

    Reference Binary

    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:

    We have talked about how to use it in the "Test Connectivity of Your Emulated Topology" section, please refer to the instructions there.

    Required Functionality

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

    Extra Credit

    Supporting Outbound Two-way TCP Traffic (2 points)

    Note that the extra credit part for this assignment is "on your own" meaning that you can only ask clarification questions and not get other help from the TAs or fellow students.

    The extra credit is basically a simple firewall. If you implement the extra credit, it should be able to be turned on/off. So we can test your required functionality.

    Note that simply allowing packets from the internal hosts (in this assignment, from the client to any of the servers) to go through the router is not enough to establish a working connection to an external service, because most (if not all) TCP/IP services entail two-way communications. Therefore, packets that belong to a flow initiated by an internal end-host that arrive to the external interface must be allowed through the secure router. To support this feature the router maintains a "flow table" that contains all the active (and allowed) flows that traverse it. In this context, a flow is defined as a 5-tuple <srcIP, dstIP, IPprotocol, src-port, dst-port>.

    When the first "internal" packet arrives at the router, two entries are added to the flow table, one for each direction of communication. The entry for the external-to-internal flow can be generated by inverting the order of source and destination IP addresses and ports. When a packet arrives to the external interface, the router checks if it matches one of the entries in the flow table. If it does then the packet is not dropped and it is forwarded to the internal interface.

    Entries remain on the flow table as long as packets that match these entries go through the firewall. To support this feature each entry has a time-to-live (TTL). Each time a packet matching the flow entry is received, the entry's TTL is set to X seconds. The router periodically scans the flow table and removes all entries whose TTL has expired. (Note: You should update the entries associated with both directions of a flow when a packet is received.)

    The flow table can hold up to Y entries at each time. You can make this parameter Y a constant. If a new entry needs to be added when the flow table is full, first a scan is initiated to determine if one or more stale entries exist in the flow table. If all entries are valid, then an ICMP response is returned (Destination Unreachable - Port Unreachable) to the originator and a log entry is generated.

    A proper firewall supports adding explicit rules to allow/disallow flows to traverse the firewall in a "rule table". You don't need to worry about adding exceptions or creating a "rule table" i.e., you reject all external to internal traffic by default unless it matches an entry in the flow table. You don't need to worry about responding properly to pings or traceroutes in SE mode. Also you don't need to worry about packet fragments i.e., if a packet fragment arrives with the transport level header missing then the fragment (as well all other subsequent fragments) are dropped.

    Your log of dropped packets should have the following format:

    <srcIP, dstIP, protocol, src-port, dst-port, drop-code>

    The drop-code for 'flow not allowed' is 2. The drop-code for 'flow table full' is 3.

    Here's an example:

     
    <1.2.3.4, 5.6.7.8, UDP, 54321, 23, 2>
    <4.3.2.1, 9.8.6.5, TCP, 12345, 80, 3>
    

    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.


    Last updated: Tue May 13 09:10:26 -0400 2014