Building your own Internet Router

Check out the the list of Frequently Asked Questions
The assignment source code is here.


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, for an introductory networking course. 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 at Stanford, and (2) A number of VN Clients which connect to the server. Your router is an example of a VN Client. 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 physical setup of the VNS is shown in the figure.

layout

The VNS Server:

The server is a user level process running here at Stanford. The machine hosting the server is connected to a hub which is connected to two Linux servers running basic internet services (currently http and ssh) (referred to as application servers). The VN Server simulates a network topology which consists of multiple links and VN Clients. The application servers sit on the other side of the network topology. For example, the simplest topology is one with a single VN Client and one application server, as shown below in the figure.

layout

A client wanting access to traffic in the network connects to the server via a normal tcp socket and requests the traffic seen on links in the topology, in this case, topology 0. Assuming the traffic is not already being sent to some other user, the server accepts the request and sends the traffic on the link to the client over the tcp socket. The client would then inspect the packet, determine where the next hop in the network (which would be fairly easy in the case of topology 0) and send the packet back to the server to be injected back into the network.

The VNS Server can handle multiple (2^16) topologies simultaneously. This means that each student can have his or her own topology to connect to and route over. The VN Server ensures that clients are only sent traffic belonging to their topology.

The VNS Client:

A VNS client is any program that speaks the VNS protocol and connects to the VNS server. In the case of this assignment we provide you with the code for a basic VNS client (called sr or Simple Router) that can connect to the VNS server. The clients are run locally by the students as regular user processes and connect to the server via normal tcp sockets. 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 (topology 0), the VN Server might receive a TCP SYN packet destined for vns-app-1.stanford.edu. The VN Server sends the packet to the VN Client which would receive the packet on interface zero, 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 one. What will the destination hardware address be for the packet sent back by the client? What if the client doesn't know the hardware address for www-server-1?

In this assignment you will implement a fully functional router by extending the sr code given to you.

Packet Flow Through the System:

The following scenario is a step by step explanation of how a client routes traffic on a simple topology.

Nick has just finished developing his router for programming assignment #3. He was assigned topology 42 for testing which is shown in the figure below.

To test, Nick runs his router from mycomputer.home.edu and connects to the VNS server at vns-1.stanford.edu, topology 42. The VNS server sends Nick's router the list of interfaces and their IP addresses.

To generate traffic for routing, Nick fires up a standard web browser from his local computer pointed at the IP of the application server on topology 42. Nick's router will now get the opportunity to route all packets between his web browser and the web server.

We'll now walk through the first few significant steps that take place when packets flow between Nick's web browser and the web server.

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 the VNS server 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)

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. The routing table format is as follows:

ip 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

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 First Methods to Get Acquainted With:

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

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 Stevens UNP, www.networksorcery.com 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.

To Help You Get Started:

We have connected a functioning router to topology 2 to demonstrate how your router should behave once completed. Topology 2 consists of a router with 3 interfaces connected to 2 application servers as shown below:


The router's interface addresses are as follows: additionally, topology 2 has two application servers with the following addresses: You should be able to traceroute to the router or through it to the application servers. Additionally, you should be able to connect to the application servers via an Internet browser and be able to download the posted files. Tracerouting to the application servers should look something like the following.
[casado@yuba ~]$ /usr/sbin/traceroute 171.67.71.24
traceroute to 171.67.71.47 (171.67.71.47), 30 hops max, 38 byte packets
 1  Gates-rtr (171.64.74.1)  0.546 ms  0.329 ms  0.287 ms
 2  vns-firewall (172.24.74.11)  0.393 ms  0.302 ms  0.285 ms
 3  171.67.71.20 (171.67.71.45)  2.332 ms  1.165 ms  1.435 ms
 4  171.67.71.24 (171.67.71.47)  3.243 ms  2.098 ms  2.094 ms
[casado@yuba ~]$
Required Functionality:

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

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.