You are here: Home / Past Courses / Spring 2011 - ECPE 293B / Projects / Project - Software Router

Project - Software Router

Overview

The first stage in the development of the software for the router is to develop a functional skeleton router completely in software. You will be using the Virtual Network System (VNS) to emulate your network topology and to give you access to traffic on the Internet. You should make sure you are comfortable with the material in the VNS tutorial, as the VNS is used heavily throughout the course.

 

Getting Started

In the VNS tutorial the overall structure of the software router framework was introduced. In this project, you will extend that framework to build the basis of a functional router.

 

Dealing with Protocol Headers

Within the software router 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' network programming books, Network Sorcery, and the Internet RFC's for ARP (RFC 826), IP (RFC 791), and ICMP (RFC 792). You should define your own packet header data structures for all headers needed for your router.

 

VNS Topology

Each group will get their own simple topology (1 router, two end hosts) to use for building and testing the router. Each group has already been assigned a VNS topology (see Project Groups).

 

Requirements

Your router must support the following functionality. Note that some functionality will not be tested for this project, but will greatly simplify your work in future projects.

  • Your code must compile and run under Linux on the ecs-network class server.
  • ARP
    • Create an ARP cache of IP/MAC pairs
      • Permanently cache IP/MAC pairs from received ARP requests, incoming packets, and solicited ARP replies
      • Must be thread-safe (even though it won't be accessed by multiple threads yet)
    • Respond to ARP requests
    • Issue ARP requests and queue packets pending the replies
  • IP
    • Check incoming IP packets for validity
      • Must be version 4
      • Must have no options
      • Must not be fragments
      • Must have a valid checksum
    • Build a static routing table
      • Read static routing entries from a text file (usually named rtable). The file name should be a command-line parameter to enable testing of different routing files.
        • Each line of the file contains a routing entry of the format "DestIP Gateway Mask Interface"
        • If the Destination IP and Mask are both zero, then the entry is a default route (e.g. 0.0.0.0 10.143.201.194 0.0.0.0 eth0)
        • The rtable routing file for your group's VNS topology can be found at the VNS management interface.  For login information, see your Group information.
      • Must support a default route with a mask of 0.0.0.0
      • Must support longest prefix match on routing table entries
      • Must support a gateway of 0.0.0.0 which denotes that the next hop is equivalent to the destination (this is useful for subnets directly connected to interfaces)
      • Must be thread-safe (even though it won't be accessed by multiple threads yet)
      • Must be able to dynamically add/remove/change routes (even though we won't do this yet)
    • Forwarding
      • Decrement the TTL
      • Recalculate checksum
      • Forward modified packet to next hop
  • ICMP
    • ICMP echo reply in response to an ICMP echo request addressed to any of the router's interfaces (regardless of which interface the request arrives on)
    • ICMP "host unreachable" message for packets with last hops that don't respond to ARP requests
    • ICMP "network unreachable" message for packets with next hops that don't respond to ARP requests
    • ICMP "time exceeded" message for packets that should be forwarded whose decremented TTL is less than 1
    • ICMP "no route to host" message if route does not exist in routing table
  • Ethernet
    • Create/modify Ethernet headers as required for all above tasks

 

ICMP Example

This is an example of a traceroute to a server on the other side of a VNS software router, which may be useful for your testing.

shafer$ traceroute 171.67.245.173
traceroute to 171.67.245.173 (171.67.245.173), 64 hops max, 52 byte packets
 1  10.10.207.254 (10.10.207.254)  0.837 ms  0.336 ms  0.286 ms
 2  10.0.0.5 (10.0.0.5)  0.415 ms  0.366 ms  0.316 ms
 3  10.0.0.101 (10.0.0.101)  0.391 ms  0.351 ms  0.341 ms
 4  138.9.253.252 (138.9.253.252)  1.498 ms  1.039 ms  0.944 ms
 5  74.202.6.5 (74.202.6.5)  6.177 ms  6.450 ms  6.079 ms
 6  pao1-pr1-ge-2-0-0-0.us.twtelecom.net (66.192.242.66)  7.747 ms  7.983 ms  7.913 ms
 7  137.164.131.62 (137.164.131.62)  8.042 ms  8.073 ms  8.412 ms
 8  dc-svl-core1--svl-px1-10ge-2.cenic.net (137.164.46.12)  8.743 ms  8.648 ms  8.506 ms
 9  dc-svl-agg1--svl-core1-10ge.cenic.net (137.164.47.120)  8.378 ms  7.934 ms  8.566 ms
10  dc-stanford--svl-agg1-10ge.cenic.net (137.164.50.158)  8.871 ms  9.092 ms  8.590 ms
11  boundarya-rtr.stanford.edu (68.65.168.33)  9.109 ms  9.047 ms  8.906 ms
12  serv-rtr.stanford.edu (68.65.168.100)  8.914 ms  8.957 ms  9.882 ms
13  * * *
14  171.67.245.168 (171.67.245.168)  54.844 ms  22.722 ms  23.170 ms
15  171.67.245.173 (171.67.245.173)  99.057 ms  33.195 ms  35.113 ms

There are several items to note in the traceroute. The traceroute proceeds normally up to hop #12, which is the Stanford gateway router. Beyond the gateway router, Stanford filters all ICMP replies for security/obscurity reasons. Thus, hop #13, the VNS firewall, is essentially invisible on traceroute because its replies are dropped in-route. Hops 14 and 15 are the software VNS router and final destination, respectively. You might think that their ICMP replies would also be dropped by the same filtering, but that is not the case. Based on conversations with VNS staff, we have learned that these packets take a different routing path back to the destination. For security reasons, the whole VNS system cannot send packets back onto the Stanford network.

 

Design

This basic router will provide the foundation for the rest of the project. Design it well! There are many clever designs that are of academic interest and aren't optimal in practice. The real testimony of a good design is that it gracefully handles testing, maintenance and the addition of new components.

Your router will be extended to support a user interface which will need to inspect and modify your router at runtime. The user interface will be running in a separate thread, so be sure to design your router such that it can be accessed by multiple threads safely and efficiently.

You will optionally be adding support for a router-to-router protocol in the future. This means your design should support a thread-safe and dynamic routing table. Getting this wrong can make the later stages of the project very difficult.

 

Style

Coding style is very important for a large scale project of this type. Good style simplifies coding, debugging, maintenance, and extension of your code. You should refer to the following Software Style Guide for some pointers.

 

Deliverables

Project meetings

We will have regular project meetings throughout the semester. (Please consult the Schedule for the specific days). Over the course of this project, you group will be asked to informally discuss your design and implementation during these meetings.

 

Source code

You will submit your source code for the software router, which we will then build, run, and test on ecs-network.serv.pacifric.edu. For more details, see Project Submission.

 

Project Report

Your project report should effectively be a clear and concise design document. It should include at least the following:

  • The division of labor between group members for this project, as described in the project honor code policy
  • A brief introduction describing what this report is about
  • A clear, concise description of the overall structure of your router
    • The modularity of your design
    • The thread-safety of your design
  • A clear, concise description of the design and implementation of the major subsystems, including
    • The routing table
    • The ARP system
  • A clear overview of packet flow through your router
    • For this section, there is no need for poetics. A complete bulleted list or diagram will be sufficient.
    • You may present packet flow for multiple scenarios (e.g. locally adressed packets, forwarded packets, bad packets etc.)
  • A clear, concise description of how you tested your router (adding testing hooks or stubs is encouraged!), and any additional support you added for debugging
  • Your report should convince us of the following:
    • Your design will handle extension and modification elegantly
    • Your design is thread safe
    • Your design is efficient

We strongly encourage you to develop this document over the course of the project. It should serve as a design document for you in the beginning of the project, and should evolve to clearly describe the decisions you made and why you made them. This document serves to describe what you feel to be the correct functionality of your router. If it does not match your implementation, you will be penalized.

You should expect to answer questions about the design points listed above during the project meetings. You should have an evolving design document at these meetings that you can refer to and show us in order to answer these questions.

 

Grading

This project will be graded out of 100 points.

  • Implementation / correctness: 70 points
  • Written report: 30 points

This guideline is not binding; we reserve the right to assign whatever grade we believe is fair.