A few of the starter files have changed slightly, so if you've already copied the starter files over, please make these changes:
If you haven't copied the starter files already, they have been updated in /usr/class/cs144/src/router.
Sorry for the trouble with the update--this is so you have a function that gets called about every second to enforce timeouts. The previous starter code was purely event-driven, so timeout behavior would have been less predictable.
Also, we've updated this webpage by adding some more explanatory text and folding the assignment specs into this webpage. Hopefully this makes the assignment clearer for everyone.
Finally, a reference binary was posted to give you an idea about the functionality of a working solution.
In this lab assignment you will be writing a simple router with a static routing table. You will be passed raw Ethernet frames and given a function that can send a raw Ethernet frame. It is up to you to come up with the forwarding logic between getting a frame and potentially sending it out over another interface.
Your router will route real packets from the myth machines to application servers sitting behind your router. The application servers are running both an HTTP server and a FTP server. 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 a functioning router. For example, an example routing topology is shown below:
If the router is functioning correctly, all of the following operations should work:
Additional requirements are laid out in the Requirements section.
This assignment runs on top of the Virtual Network System which was built at Stanford. 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 more information about VNS (if you're curious) is available here.
The Getting Started screencast walks through the sections listed below, and is available here as a QuickTime movie:
The routing table presented in the screencast is wrong. The correct routing table is listed in the "Creating a Routing Table File" section below.
The first thing you will need to do is to create a testing topology similar to one in the example given in the introduction. You do this by running a topology creation tool provided by the VNS group:
The link contains information on how to download and run the topology creation tool.
Copy the files from your starter code into your working directory:
> cp /usr/class/cs144/src/router .
You should be able to build the router out of the box.
You'll notice that the starter code ships with a simple routing table file, rtable. The rtable file has the format:
prefix next_hop netmask interface
The base rtable file only has a default route to the firewall. You should edit the rtable file and add entries to that correspond to the nodes your router is connected to. For example, the routing table for router in the sample topology in the introduction follows:
0.0.0.0 172.24.74.11 0.0.0.0 eth0
192.168.128.204 192.168.128.204 255.255.255.255 eth1
192.168.128.206 192.168.128.206 255.255.255.255 eth2
You should now have all the pieces needed to build and run the router:
You can then build and run the starter code:
> make
> ./sr -t topo_id -v node_name -r rtable
Note: Currently, you can only run your sr binary on myth machines. If you try to run sr on pod, you won't be able to connect to the VNS servers.
From another terminal or another myth, try pinging one of the router's interfaces. Currently, all the starter code does is print that it gets a packet to the command line.
For example, when running the starter code on topology 6107, with the router on node1, and the routing table stored in a file rtable.6107, and then pinging an interface on the router from another terminal, we get the following output:
> ./sr -t 6107 -v node1 -r rtable.6107
Loading routing table
---------------------------------------------
Destination Gateway Mask Iface
0.0.0.0 172.24.74.11 0.0.0.0 eth0
192.168.128.204 192.168.128.204 255.255.255.255 eth1
192.168.128.206 192.168.128.206 255.255.255.255 eth2
---------------------------------------------
Client nham connecting to Server 171.67.71.18:12345
Requesting topology 6107
Router interfaces:
eth0 HWaddr70:00:17:db:00:02
inet addr 192.168.128.203
eth1 HWaddr70:00:17:db:00:04
inet addr 192.168.128.205
eth2 HWaddr70:00:17:db:00:06
inet addr 192.168.128.207
<-- Ready to process packets -->
# After running "ping 192.168.128.203" from another
# terminal or myth
*** -> Received packet of length 60
*** -> Received packet of length 60
*** -> Received packet of length 60
.
.
.
You'll find it quite useful for debugging errors to use a packet inspection tool like Wireshark or tcpdump. You can save packets to a packet log file using the -l option:
> ./sr -t topo_id -v node_name -r rtable -l logname
From there, you can use Wireshark, a graphical packet inspection tool, to open the logfile (currently this only works on the pod machines with X forwarding enabled):
> /usr/class/cs144/bin/wireshark logname
Alternatively, you can install Wireshark locally and run it from your own machine to inspect the packet log.
You can also choose to use tcpdump from the command line to inspect the packet log:
> tcpdump -r logname -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.
To get you started, an outline of the forwarding logic for a router follows, although it does not contain all the details. Given a raw Ethernet frame, if the frame contains an IP packet that is not destined towards one of our interfaces:
Obviously, this is a very simplified version of the forwarding process, and the low-level details follow. For example, if an error occurs in any of the above steps, you will may have to send an ICMP message back to the sender notifying them of an error. You may also get an ARP request or reply, which has to interact with the ARP cache correctly.
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.
Before operating on an IP packet, you should verify its checksum and make sure it meets the minimum length of an IP packet. You should understand how to find the longest prefix match of a destination IP address in the routing table, as described in Section 2. 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.
An IP packet my contain an ICMP message. 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:
The source address of an ICMP message can be the source address of any of the incoming interfaces, as specified in RFC 792.
As mentioned above, the only incoming ICMP message destined towards the router's IPs that you have to explicitly process are ICMP echo requests.
You may want to create your own struct for ICMP messages for convenience, but make sure to use the packed attribute so that the compiler doesn't try to align the fields in the struct to word boundaries:
struct sr_icmp_hdr {
// you fill in
} __attribute__ ((packed));
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 your 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.
An incoming IP packet may be destined for one of your router's IP addresses, or it may be destined elsewhere. If it is sent to one of your router's IP addresses, you should take the following actions, consistent with the section on protocols above:
Packets destined elsewhere should be forwarded using your normal forwarding logic.
A screencast on some of the following topics is below:
Screencast: Lab 4 Overview (pdf) (pptx)
There was a typo in the screencast where we typed hdr->ether_type == ntohs(ETHERTYPE_IP) and ntohs(ETHERTYPE_ARP). The ETHERTYPE_* constants are #define'd in sr_protocol.h, so they are actually in the host byte order, while hdr->ether_type is from a raw packet and therefore in network byte order. So the correct equality test is hdr->ethertype == htons(ETHERTYPE_IP) or htons(ETHERTYPE_ARP), so both sides of the equality are in network byte order.
Your router 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. The basic functions to handle these functions are:
void sr_handlepacket(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)
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.
You should not free the buffer given to you in sr_handlepacket (this is why the buffer is labeled as being "lent" to you in the comments). You are responsible for doing correct memory management on the buffers that sr_send_packet borrows from you (that is, sr_send_packet will not call free on the buffers that you pass it).
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.
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.
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.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).
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.
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.
There are a number of resources which describe the protocol headers in detail. Network Sorcery's RFC Sourcebook provides a condensed reference to the packet formats you'll be dealing with:
For the actual specifications, there are also the RFC's for ARP (RFC826), IP (RFC791), and ICMP (RFC792).
This assignment has been used at several universities as well as CS244A, and as a result a long FAQ page exists here:
Please consult the FAQ before posting a question to the newsgroup.
This assignment is considerably harder than the first 3 assignments, so get started early.
In our reference solution, we added 520 lines of C, including whitespace and comments:
> wc -l /usr/class/cs144/src/router/*.c | tail -1 1585 total > wc -l ~/cs144/router/solution/*.c | tail -1 2104 total
Of course, your solution may need fewer or more lines of code, but this gives you an idea a rough idea of the size of the assignment to a first approximation.
To help you debug your topologies and understand the required behavior we provide a reference binary here:
/usr/class/cs144/bin/sr_ref
Here is an example of running the reference router on topology id 6155, where the router is running on "node1" and uses the routing table file "rtable.6155" in the current working directory:
/usr/class/cs144/bin/sr_ref -t 6155 -v node1 -r rtable.6155
Substitute the correct values for your topology when running the reference router. You might want to run it to help you:
To submit, run
make submitfrom your project directory and submit the resulting tarball on the submission page.
You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assignment. You are not allowed to look at anyone else's solution (and you're not allowed to look at solutions from previous years). You may discuss the assignments with other students, but you may not look at or copy each others' code.
Click here to see your grade.