Homework 9: Roll-Your-Own 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.

The Virtual Network System

In this homework, we use the Stanford Virtual Network System (VNS) to create a separate, virtual, router for each student in the class. The router is directly connected to the Internet, and to two (virtual) web servers that are connected to the Internet via your router.

What's unique about your VNS router is that its outsources its logic to a program on your computer: whenever it receives a packet, it'll send it to your program, and your program gets to decide what to do next: forward the packet out some other interface, send some other packet in response, etc.

To get you started, you're given a dumb router that just receives packets and prints something out. Your job is to make it do what routers do.

Setup: Fetching your authorization key

After exporting the template, you need to update the file auth_key with your specific key. To get your key, log into the VNS web interface and click "Your Profile". Your key is listed on that page.

Setup: Your routing table

Your router will make routing decisions based on a fixed routing table. This is available from the VNS web page as well. Under "Your Profile", click on the link to your specific topology (bottom of the table), then "Topology Routing Table".

171.67.71.22 171.67.71.22 255.255.255.255 eth1 
171.67.71.24 171.67.71.24 255.255.255.255 eth2 
171.64.22.20 171.67.71.24 255.255.255.254 eth2 
0.0.0.0 172.24.74.17 0.0.0.0 eth0

The format of a single line is: prefix next_hop netmask interface

Where prefix is an IPv4 base address, next_hop is the IP address of the host that is the next step in the routing sequence, netmask is a netmask telling the router how which addresses are covered by this rule, and interface is the name of an Ethernet interface on the router. So for this example, packets for 171.67.71.22 (and only 171.67.71.22) are routed directly to that host out interface eth1. Packets that do not make a longer prefix match are caught by the default rule at the bottom, which sends packets with no longer prefix match out eth0 to be forwarded by 172.24.74.17 (which happens to be the firewall).

Save the routing table for your topology in the file rtable in the template.

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 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. You also need to create a file named “auth_key” in the folder with the stub code. This “auth_key” file should have your authentication key which lets the server know who you are. You can get this key by logging into [[http://vns-2.stanford.edu/login/][the VNS web interface] and going to “Your Profile.” Be careful to copy your authentication key exactly as it appears.

Now you can connect to the VNS server as follows:

./sr -s vns-1.stanford.edu -t <your_topology_number> -u <your_userid>

for example, connecting to the server on topology 0 as user dgu might look like this:

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

(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 implementing the internal representation of the routing table along with the lookup algorithm is part of this assignment. 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.

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?

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

You may also optionally use scp to copy the log file to another machine and use Wireshark to inspect the packets there.

Rolling Your Own Router Using the SR Stub Code

The majority of the code which makes the router work is provided for you. You will be responsible for implementing important elements of several subsystems within the router. All code must be added to sr_router.c and sr_router.h.

You are responsible for implementing:

  • in sr_handlepacket(): parse the provided ethernet frame, verify that it is valid and to this interface, and call handle_ip() or handle_arp() as needed.
  • in handle_arp(): handle incoming ARP requests by sending a reply if necessary.
  • in handle_ip(): verify the validity of the IP header, handle packets destined for the router (only ICMP Ping must be handled, all data packets should receive an error response), and forward/drop packets NOT addressed to this router as appropriate.
  • in rtable_find_route(): find the best route in the routing table, and return a pointer to that element in the linked list of routing table entries.
  • in router_queue_ethernet_frame(): craft an outgoing ethernet packet based on the given payload, source, and destination, and send it out via sr_send_packet.
  • in network_send_packet_from(): allocate a new IP packet, set its headers and payload correctly, and call router_send_ethernet_frame to send it along.
  • in icmp_send(): allocate, fill, and send a new ICMP packet using network_send_packet or network_send_packet_from. If the src ip is null, you can use network_send_packet to set the src ip based on the routing decision for the destination.

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

Tracerouting to the application servers should look something like this:

[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

Required Functionality

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

  • The router can successfully route packets between the firewall and the application servers.
  • The router correctly handles ARP requests and replies.
  • The router correctly handles traceroutes through it (where it is not the end host) and to it (where it is the end host).

Simplifying assumptions/requirements

  • no IP Options
  • no IP Fragmentation
  • no IPv6
  • all non-ICMP messages sent directly to routers receive an 'ICMP Protocol Unreachable' message in reply.
  • the only ICMP message you must reply to is ICMP Ping.
  • all ARP packets must be for the Ethernet hardware type and IP protocol type.
  • Only ARP Requests and ARP Replies are to be processed.

Deliverables

The source code for your router. You may add files to those provided with the stub code; be sure to update your Makefile if you do. Your README file describing design decisions that you made, and any trade offs that you encountered in the design.

Special thanks to the Stanford High Performance Networking Group and Stanford University

Appendix

This is some additional information that was there in the original homework description. You may find it useful.

Overview of the Virtual Network System (VNS)

The VNS was designed at Stanford, for Stanford's introductory networking course CS144. 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 physical setup of the VNS is shown in the figure.

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 HTTP servers, referred to as application servers. The VNS Server simulates a network topology which consists of multiple links and VNS Clients. The application servers sit on the other side of the network topology. For example, a simple topology would be one with a single VNS Client and one application server, as shown below in the figure.

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 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 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 VNS Server might receive a TCP SYN packet destined for vns-app-1.stanford.edu. 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 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 #2. He is using the hypothetical topology 42 for testing which is shown in the figure below.

To test, Nick runs his router from ieng6.ucsd.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.

  • A SYN packet leaves Nick’s machine destined to the web server’s IP and is routed to the VN Server.
  • Late in the evening before the project was released, Chris arranged for Nick’s packet to be delivered to topology 42, starting with the IP address of interface zero on Nick’s client. The hop before Nick’s router sends an ARP packet requesting the hardware address of the interface with IP of interface zero on Nick’s client.
  • The VNS Server sends the raw Ethernet, ARP packet over the socket to Nick’s VNS Client which responds with an ARP reply.
  • On receipt of the ARP reply, the hop before Nick’s router, then forwards the packet to the Nick’s router.
  • The VNS Server intercepts the packet and sends the raw Ethernet IP packet over the socket to Nick’s VNS Client for his to route.
  • Nick’s router decrements the TTL field in the IP header and recalculates the checksum.
  • Nick’s router consults its routing table and determines the next hop is the ip for the web server.
  • When Nick’s router has made its routing decision, it must send back to the VN Server a properly formatted Ethernet packet. This means that the client must find the Ethernet address of the next hop. To do this, the client sends an ARP, in the usual way, to find out the Ethernet address belonging to the next hop IP address.
  • The next hop, which could be another client or an application server, responds to the ARP, and Nick’s client completes the Ethernet packet and sends it back to the VNS server. (The client also caches the ARP reply for future use).
  • The VNS Server sends the packet out of the correct interface, and to the next hop in the topology.
  • …. etc.
Topic revision: r4 - 2012-11-22 - 16:50:35 - Main.jakob
 
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
WISEST
Helping Women Faculty Advance
Funded by NSF