Building your own Internet Router

The topology assignment is here. Read it before trying the code.

The skeleton source code is here.

Make sure to read the Frequently Asked Questions

Introduction

In this assignment you will implement a fully functional Internet router that routes real network traffic. The goal is to give you hands-on experience as to how a router really works. Your router will run as a user process locally, and when finished will route real packets that are flowing across the Internet to application servers located at Stanford. We'll be giving you a skeleton, incomplete router (the "sr" or simple router) that you have to complete, and then demonstrate that it works by performing traceroutes, pings and downloading some files from a web server via your router.

Overview of the Virtual Network System (VNS):

The VNS was designed at Stanford (http://yuba.stanford.edu/vns/). It gives you hands-on experience working on projects requiring low level network access, such as routers. The VNS is comprised of two components: (1) The VN Server which runs in Stanford Lab, and (2) VN Clients such as your router. The server intercepts packets on the network, forwards the packets to the clients, receives packets from the client and injects them back into the network. The clients are run locally by the students as regular user processes and connect to the server via normal tcp connections. Clients, once connected to the server, are forwarded all packets that they are supposed to see in the topology. The clients can manipulate the packets in any way they wish, generate responses based on the packets, or make routing decisions for those packets and send the replies back to the server to place back onto the network.

For example, on the above topology, the VN Server might receive a TCP SYN packet from the Internet destined for application server 1. The VN Server sends the packet to the VN Client which would receive the packet on interface eth0, decrement the TTL, recalculate the header checksum, consult the routing table and send the packet back to the server with directions to inject it back onto the network out of interface eth1. What will the destination ethernet address be for the packet sent back by the client? What if the client doesn't know the ethernet address for application server 1?

In this assignment we provide you with the skeleton code for a basic VN client (called sr or Simple Router) that can connect and talk to the VNS server. Therefore, you don't need to be concerned about the interaction between VN server and client, or how packets flow in the physical topology. You can just focus on the virtual topology and your own router. Your job is to make the router fully functional by implementing the packet processing and forwarding part within the skeleton code. More specifically, you'll need to implement ARP, ICMP, and basic IP forwarding.

Test Driving the sr Stub Code:

Before beginning development you should first get familiar with the sr stub code and some of the functionality it provides. Download the Stub Code Tarball and save it locally. As described before, it handles all of the dirty-work required for connecting and communicating with the server. To run the code, untar the package (tar -zxvf sr_stub.tar.gz) and compile it via make. Once compiled, you can connect to a VNS server (vns-1.stanford.edu or vns-2.stanford.edu) as follows:

   ./sr -s vns-1.stanford.edu -t <topo-id>

for example, connecting to the server on topology 0 would look like:

   ./sr -s vns-1.stanford.edu -t 0

You can use ./sr -h to print a list of the accepted command line options. You can also use another server vns-2.stanford.edu.

After you connect successfully, the server will send you a description of the host including all the interfaces and their IP addresses. The stub code uses this to build the interface list in the router (the head of the list is member if_list for struct sr_instance). The routing table is constructed from the file rtable and by default consists of only the default route which is the firewall sitting between the Internet and your router. The routing table format is as follows:

destination gateway mask interface

a valid rtable file may look as follows:

172.24.74.213 172.24.74.213 255.255.255.255  eth1
172.24.74.228 172.24.74.228 255.255.255.255  eth2
0.0.0.0 172.24.74.17 0.0.0.0  eth0

Note: 0.0.0.0 as the destination means that this is the default route; 0.0.0.0 as the gateway means that it is the same as the destination.

The VN Server, on connection should return the IP addresses associated with each one of the interfaces. The output for each interface should look something like:

        INTERFACE: eth0

        Speed: 10
        Hardware Address: 70:00:00:00:00:01
        Ethernet IP: 172.24.74.41
        Subnet: 0.0.0.0
        Mask: 0.0.0.0

To test if the router is actually receiving packets try pinging or running traceroute to the IP address of eth0 (which is connected to the firewall in the assignment topology). The sr should print out that it received a packet. What type of packet do you think this is?

What should your router do on receipt of an ARP request packet?

Developing Your Very Own Router Using the SR Stub Code:

Data Structures You Should Know About:

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.h/c.
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 First Methods to Get Acquainted With:

The two most important methods for developers to get familiar with are as follows:

in sr_router.c

    
        void sr_handlepacket(struct sr_instance* sr, 
                uint8_t * packet/* lent */,
                unsigned int len,
                char* interface/* lent */)

This method 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.

in sr_vns_comm.c

    int sr_send_packet(struct sr_instance* sr /* borrowed */, 
                             uint8_t* buf /* borrowed */ ,
                             unsigned int len, 
                             const char* iface /* borrowed */)

This method will send an arbitrary packet of length, len, to the network out of the interface specified by "iface".

Dealing with Protocol Headers:

Within the sr framework you will be dealing directly with raw Ethernet packets. There are a number of resources which describe the protocol headers in detail, including www.networksorcery.com, Stevens Unix Network Programming book, and the Internet RFC's for ARP (RFC826), IP (RFC791), and ICMP (RFC792). The stub code itself provides some data structures in sr_protocols.h which you may use to manipulate headers. There is no requirement that you use the provided data structures, you may prefer to write your own or use standard system includes.

Inspecting Packets with tcpdump

As you work with the sr router, you will want to take a look at the packets that the router is sending and receiving. The easiest way to do this is by logging packets to a file and then displaying them using a program called tcpdump.

First, tell your router to log packets to a file in a format that tcpdump can read by passing it the -l option and a filename:

./sr -t <topo-id> -s vns-1.stanford.edu -l <logfile>

As the router runs, it will log the packets that it receives and sends (including headers) to the indicated file. After the router has run for a bit, use tcpdump to display the packets in a readable form:

tcpdump -r <logfile> -e -vvv -x

The -r switch tells tcpdump where to look for the logfile. -e tells tcpdump to print the headers of the packets, not just their payload. -vvv makes the output very verbose, and -x puts the packets in a hex format that is usually easier to read than ASCII. You may want to specify the -xx option instead of -x to print the link-level (Ethernet) header in hex as well.

Required Functionality:

We will declare that your router is functioning correctly if and only if:

The router correctly handles ARP requests and replies.
The router responds correctly to ICMP echo requests.
The router correctly handles traceroutes through it (where it is not the end host) and to it (where it is the end host).
The router can successfully route packets between the firewall and the application servers.
The router maintains an ARP cache whose entries are invalidated after a timeout period (timeouts should be on the order of 15 seconds).
The router queues all packets waiting for outstanding ARP replies. If a host does not respond to 5 ARP requests, the queued packet is dropped and an ICMP host unreachable message is sent back to the source of the queued packet.
The router does not needlessly drop packets (for example when waiting for an ARP reply)
The router handles tcp/udp packets sent to one of its interfaces. In this case the router should respond with an ICMP port unreachable.

Not Required but Smiled Upon:

Currently the stub code is event based. That is, code is executed each time a packet is received. This makes it hard to correctly enforce timeouts. For example, if the router is waiting for an ARP request that doesn't come, it will have to wait for another packet to arrive before it can handle the timeout. Of course, if a packet never arrives, the timeout will never be serviced. Though not required, an implementer may choose to enforce stronger guarantees on timeouts.