COS-461 Assignments: Router

Assignment 2: Building your own Internet Router



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 their introductory networking course and they're nice enough to let us use it too. 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 VNS Server which runs in a lab at Stanford, and (2) A number of VNS Clients which connect to the server. Your router is an example of a VNS 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 VNS Server

The server is a user level process running at Stanford. The machine hosting the server is connected to a hub which is connected to two Linux servers running a few internet services (http, ftp, and a streaming music server on port 8888), referred to as application servers. The VNS Server simulates a network topology which consists of multiple links and VNS Clients, and allows access to application servers from the Internet. For example, the simplest topology (say, topology 0) is one with a single VNS Client and one application server, as shown below in the figure. In the figure, elaine17 runs a web client and accesses an application server on www-nickm. A VNS server one hop before www-nickm intercepts the packets and sends them to the VNS client named "Nick's VR Client", which implements the routing logic.

A VNS client wanting access to traffic in the network connects to the VNS server via a normal TCP socket and requests the traffic seen on links in the topology. 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 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 VNS 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 VNS clients are run locally by the students as regular user processes and connect to the VNS server via normal TCP sockets. VNS clients, once connected to the VNS server, are forwarded all packets that they are supposed to see in the topology. The VNS 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 VNS server to place back onto the network. For example, in topology 0, the VNS server might receive a TCP SYN packet destined for an application server. The VNS server sends the packet to the VNS 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 VNS server with directions to inject it back onto the network out of interface one.

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

Packet Flow Through the System

VNS allows you to build virtual network topologies consisting of nodes that operate on actual Ethernet frames. This is why your router node can process and send real Ethernet frames and send them over the network like a real router. You don't have to know how VNS works to complete this assignment, but the following packet flow example may be useful, for example, while debugging.

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. The firewall shown is simply the hop before Nick's assigned topology.

Nick runs his router from and connects to the VNS server at, 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/web server on topology 42. Nick's router will now get the opportunity to route all packets between his web browser and the web server. Note that Nick can run his web browser on any machine and not necessarily on the one running the VNS client.

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

You should login to the VNS and change the default password we gave you. Before beginning development you should first get familiar with the sr stub code and some of the functionality it provides. Download the stub code (from the top of this page) 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 -t <topo-id>

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

./sr -s -t 0

(you can use ./sr -h to print a list of the accepted command line options)

Remember that the latest version of the code requires you to have a (default) routing table file and an authentication key file before you can test out the stub code. You can get these from your VNS account and save them as 'rtable' and 'auth_key' respectively

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 might look like this: eth1 eth2 eth0

The VNS 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:

To test if the router is actually receiving packets try pinging or running traceroute to the IP address of eth0. 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?

Inspecting Packets with tcpdump or Wireshark

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. You can also use Wireshark.

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

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:

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.

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.

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, 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

Here is an example of what a traceroute to an application server should look like. ( is the app server, is the router).

-bash-3.1$ traceroute
traceroute to (, 30 hops max, 40 byte packets
 1  ignition.CS.Princeton.EDU (  0.578 ms  1.189 ms  1.473 ms
 2  csgate.CS.Princeton.EDU (  3.721 ms  4.002 ms  4.849 ms
 3  gigagate1.Princeton.EDU (  4.253 ms  4.254 ms  4.236 ms
 4  vgate1.Princeton.EDU (  4.527 ms  4.212 ms  4.499 ms
 5 (  7.054 ms  7.041 ms  7.027 ms
 6 (  8.141 ms  7.508 ms  7.701 ms
 7 (  19.086 ms  16.794 ms  16.549 ms
 8  * * *
 9 (  47.958 ms  47.980 ms  47.709 ms
10 (  80.013 ms  79.636 ms  80.603 ms
11 (  79.880 ms * *
12 (  87.746 ms  87.706 ms *
13 (  89.250 ms  89.015 ms *
14 (  90.206 ms  91.027 ms  90.627 ms
15  serv-rtr.Stanford.EDU (  90.633 ms  90.196 ms  90.231 ms
16  * * *
17 (  243.466 ms  302.609 ms  301.237 ms
18 (  910.107 ms  909.833 ms  769.265 ms

Required Functionality (10 points)

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

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

Extra Credit (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.

a) Guaranteed Timeouts (0.5/2.0)

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.

b) Basic Security

In addition to routing packets between the local networks and the Internet, a virtual router can also provide some secuirty. Routers on the Internet often work as firewalls as well. You are not required to implement a proper firewall, but only add a few security features to your router for extra credit. These features are as follows:

Supporting Outbound Two-way TCP Traffic (1.0/2.0)

Note that simply allowing packets from the internal hosts 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:

<,, UDP, 54321, 23, 2>
<,, TCP, 12345, 80, 3>

Generating Outbound Traffic

In order to fully test the firewall’s functionality, you will need to generate outbound traffic from within your topology. To do this, you will need to use the Topology Interactor Tool. This tool allows you to send an echo request from a node inside your topology to a destination outside your topology. The destination will send an echo reply which your firewall should allow back in. Here’s an example of to use it:

./ -s -t <topology_id> -u <username> -a /path/to/your/auth_key
Connecting to VNS server at ...
Authenticating as dgu
Authentication successful.
>>> ping from server1
requested that server1 send a ping to (
tap on server1:eth0 has been installed
server1:eth0 received ECHO REPLY from
tap on server1:eth0 has been disabled
>>> exit


You should submit your completed router by the due date to CS Dropbox. You may add files to those provided with the stub code; be sure to update your Makefile if you do. You should answer the questions in the README file, describe design decisions that you made, and any trade offs that you encountered in the design.

Last updated: Sun Mar 27 20:12:36 -0400 2011