CPS 114 Introduction to Computer Networks: Lab 1

CPS 114 Introduction to Computer Networks: Labs

Lab 2: Simple Router

Introduction

In this lab assignment, you will write a simple router with a static routing table. We will pass to your code raw Ethernet frames and give you a function that can send a raw Ethernet frame. It is up to you to implement the forwarding logic between getting a frame and sending it out over another interface.

Figure 1: sample topology

Your router will route real packets from any machine to application servers sitting behind your router. The servers are running HTTP applications. 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 router. If the router is functioning correctly, all of the following operations should work:

Pinging to any of the router's interfaces
Pinging to any of the app servers
Downloading a file using HTTP from one of the app servers

This lab runs on top of Stanford's Virtual Network System. VNS allows you to build virtual network topologies consisting of nodes that operate on actual Ethernet frames. You don't have to know how VNS works to complete this assignment.

Getting started

You should be able to finish your assignment on any machine in the department's linux cluster: linux.cs.duke.edu. If you prefer to finish your assignment on your own machine, you may download and install ubuntu. You may run Ubuntu in a virtual machine such as the free VirtualBox. We do not support MAC or Windows. Sorry.

First download and untar the assignment code.

xwy@linux21$ wget http://www.cs.duke.edu/courses/spring10/cps114/labs/lab2/router.tar.gz
xwy@linux21$ tar xzvf router.tar.gz

You will also need to download your testing topology and auth_key file from class Forum (DO use your own topology and auth_key file). Please

copy the auth_key file into your assignment directory
set up your routing table file rtable in your assignment directory in the following format:

Destination     Gateway(next_hop)     Mask     Iface

Here is one sample rtable file for topology in Figure 1. The base rtable file only has a default route to the firewall.

You can then build and run the assignment code (TOPOLOGY_ID and USER_NAME are in the topology file):

xwy@linux21$ make
xwy@linux21$ ./sr -s vns-2.stanford.edu -t <TOPOLOGY_ID> -u <USER_NAME>

From another terminal or another machine, try pinging one of the router's interfaces. Currently, all the assignment code does is print that it gets a packet to the command line.

Understanding the code

Data Structure

sr_router.[h|c]: The full context of the router is housed in the struct sr_instance (sr_router.h). sr_instance contains information about the topology the router is routing for as well as the routing table and the list of interfaces.

sr_if.[h|c]: After connecting, the server will send the client the hardware information for that host. The assignment 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].

sr_rt.[h|c]: 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.

sr_arpcache.[h|c]: 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 these operations 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. You must fill out the sr_arpcache_sweepreqs function in sr_arpcache.c that gets called every second to iterate through the ARP request queue and re-send ARP requests if necessary. Psuedocode for this is provided in sr_arpcache.h.

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. sr_utils.[c]: It provides useful functions that print out various headers for debugging purpose.

Important Functions

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

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

void sr_arpcache_sweepreqs(struct sr_instance *sr)

The assignment requires you to send an ARP request about once a second until a reply comes back or we have sent five requests. This function is defined in sr_arpcache.c and 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.

Requirements

Your simple router must support the following:

The router can successfully route packets between the firewall and the application servers.
The router correctly handles ARP requests and replies.
The router responds correctly to ICMP echo requests.
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 enforces guarantees on timeouts--that is, if an ARP request is not responded to within a fixed period of time, the ICMP host unreachable message is generated even if no more packets arrive at the router.

Functions and data structures you need to implement

There is no specific requirement which function you can/cannot modify. To make the simple router work, you need to handle 4 kinds of packets correctly: Ethernet, IP, ICMP and ARP. For the actual specifications, there are also the RFC's for ARP (RFC826), IP (RFC791), and ICMP (RFC792).

In our reference implementation, we developed sr_ip.[h|c], sr_icmp.[h|c] (you need to add these source files to the Makefile). We also modified sr_router.[h|c], protocol.h and sr_arpcache.[h|c]. Total work load is around 550 lines of c code.

Understanding Protocols

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

You should understand how to find the longest prefix match of a destination IP address in the routing table. 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 used to send control information back to the 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:

Echo reply (type 0): Sent in response to an echo request (ping) to one of the router's interfaces. (This is only for echo requests to any of the router's IPs. An echo request sent elsewhere should be forwarded to the next hop address.)
Destination unreachable (type 3, code 0): Sent if there is a non-existent route to the destination IP (no matching entry in routing table when forwarding an IP packet).
Destination host unreachable (type 3, code 1): Sent if five ARP requests were sent to the next-hop IP without a response.
Protocol unreachable (type 3, code 2): Sent if an IP packet containing a UDP or TCP payload is sent to one of the router's interfaces. This is needed for traceroute to work.
Time exceeded (type 11, code 0): Sent if an IP packet is discarded during processing because the TTL field is 0. This is also needed for traceroute to work.

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

Testing and Debugging

For testing purposes, you may wish to download the test script here. Copy the test script to you assignment directory and modify the values of eth[0|1|2]ip, app[1|2]ip, topology number and username according to your topology information. Run the test script as following:

xwy@linux21$ python ./test_sr.py

The above test case does not include Destination Host Unreachable, Destination Unreachable and Protocol Unreachable tests. To do these three tests, you may use test4 at cps114.cod.cs.duke.edu. Before you start these tests, you need to reconfigure your router/rtable. Let's take Figure 1 as an example.

Suppose your topology is shown in Figure 1, the allocated IP block is 171.67.243.176/29 (8 IP addresses). Packets heading to this IP block will be routed to your router. This IP block consists of 4 /31 blocks. They are 171.67.243.176/31 (connected to eth0), 171.67.243.178/31, 171.67.243.180/31 (connected to eth1) and 171.67.243.182/31 (connected to eth2). 171.67.243.178/31 is not connected to any interface.

For Destination Host Unreachable test, if you add a route entry

171.67.243.179  171.67.243.178  255.255.255.254  eth1

to your routing table, once your router receives a packet heading to 171.67.243.179, it will send ARP request for 171.67.243.178 through eth1. There will be no reply since 171.67.243.178 does not exist at all. After 5 ARP requests without any reply, a Destination Host Unreachable ICMP packet will be generated by your router. At this point, your route/rtable should look like

0.0.0.0            172.24.74.17       0.0.0.0            eth0
171.67.243.181     171.67.243.181     255.255.255.255    eth1
171.67.243.183     171.67.243.183     255.255.255.255    eth2
171.67.243.179     171.67.243.178     255.255.255.254    eth1

For the Destination Unreachable test, We do following changes to the above routing table. First, we remove the default route. Second we remove the routing table entry for 171.67.243.179. Third, we add a entry for any PC in Figure 1. For example, if any PC is cps114.cod.cs.duke.edu, we add a entry for its IP address (152.3.145.121) to the routing table. After these three changes, your routing table should look like.

152.3.145.121      172.24.74.17       255.255.255.0      eth0
171.67.243.181     171.67.243.181     255.255.255.255    eth1
171.67.243.183     171.67.243.183     255.255.255.255    eth2

Right now, your router/rtable is ready for the Destination Unreachable test. You may simply send a UDP packet heading for 171.67.243.179 from cps114.cod.cs.duke.edu(152.3.145.121). Your router should be able to generate a Destination Unreachable ICMP packet and send it to cps114.cod.cs.duke.edu. At this point, you may think about why do we do the above three modifications. Try not to delete the default route, what do you find?

For the Protocol Unreachable test, you may simply send one UDP packet to any of your router interfaces. Your router should be able to generate a protocol unreachable packt and send it to you.

For the Destination Host Unreachable test, Destination Unreachable test and Protocol Unreachable tests, you can log on to cps114.cod.cs.duke.edu with your cs appartment account and use test4 to send UDP packets and receive ICMP feedbacks. You need to create and modify config.xml. <dst> stands for your UDP packet's destination address, <intf> is the interface IP addresses of your router. Then run the test case as following.

xwy@cps114:~$ test4 config.xml

This test4 sends 3 UDP packets to your specified IP address, grabs received ICMP packets and check these packets' source addresses, ICMP type and code fields.

Submitting

To submit the assignment, do the following:

Run the command make submit, this should create a file called router.tar.gz.
Upload router.tar.gz to the lab2 assignment on Blackboard.

In the final submission, you must finish all required functions of this lab. For the checkpoint submission, your code should at least handle ARP requests/replies, and update the ARP cache correspondingly. Please call sr_arpcache_dump function in sr_arpcache_sweepreqs. This will dump your ARP cache periodically. We will use test4 to send UDP packets to one of the http servers. Your router should be able to update ARP cache correctly.

Collaboration policy

You can discuss with anyone, but you must not look at each other's code, or copy code from others.

Acknowledgement

This lab uses VNS and is one of VNS's assignments. You can read more about how VNS works here.

Last updated: 02/2010