Project - Dynamic Routing

With thanks to the Stanford High Performance Network Group

Overview

This assignment involves building advanced functionality on top of a basic VNS router. The goal is to develop a simple dynamic routing protocol, PWOSPF, so that your router can generate its forwarding table automatically based on routes advertised by other routers on the network. Specifically, your router is expected to be able to build its forwarding table from link-state advertisements sent from other routers, detect when routers join/or leave the topology and correct the forwarding tables correctly, and route traffic through complex topologies containing multiple nodes.

Expected Functionality

Your router should be able to build the correct routing tables and route traffic to the application servers on the assignment topology. Specifically, we expect to be able to start three instances of your router with the only static route being the default route on vhost1, and then be able to reach app1 and app2 within a reasonable amount of time. Your router should be able to correct the routing tables if a link goes down (such as the link between vhost1 and vhost2). We will likely test this by modifying the stub code to drop all packets out of a particular interface after a given time period.

Control Path versus Forwarding Path

High end hardware routers and software routing daemons (such as routed, zebra and xorp) abstract the control functionality of the router such as management, and routing protocols away from the forwarding functionality. The forwarding path should do just that, forwarding. The control path, on the other hand, tries to figure out what the particular configuration of the forwarding path should be and updates the forwarding path periodically. Typically, the configuration functionality will maintain copies of the forwarding path data structures (such as the routing table) and use those for updates. You have already developed a usable forwarding path in the earlier software router project. In this project, you will build a control path on top of that to update the routing table based on the calculated shortest path to each reachable subnet with Dijkstra's algorithm and PWOSPF.

Topology and Requirements Overview

Each team will be assigned the following three host topology for development:

Topology information is available on the Project Groups page.

Running Multiple Routers

Because this assignment requires multiple instances of your router to run simultaneously, you will want to use two new command-line options: -r and -v. This allows you to specify the routing table to use (e.g. r rtable1) and the host you want to connect to on the topology (e.g. -v vhost3).

./sr -t <topid> -s vns-1.stanford.edu -u <vns-user-name>  -r <rtableFile> -v <vhostNumber>    # Optional arguments: -a <authKeyFile> -l <logfile>

You will need to run one instance of your software router for each vhost in your topology. (Thus, the need to specify the specific vhost and routing table to be used)

Dealing With Routes

The software router project does not really require sophisticated handling of routes. However, when implementing pwospf, special care must be taken to ensure that routes are treated correctly by your router. Before starting pwospf development, we suggest that you first ensure your router properly handles default routes, gateways and subnets.

next hop: The routing table consists of 4 fields: <destination prefix> <next-hop IP> <network mask> <outgoing interface>. The next-hop specifies the IP address of the next router towards the destination. What if the destination is directly connected to one of the router’s interfaces? In this case, the next-hop value is 0 (0.0.0.0) serving as an indication to the router that the destination host is directly connected to outgoing interface specified by the route. If your router receives a packet to destination 1.2.3.4 and your router has a route 1.2.3.0 0.0.0.0 255.255.255.0 eth1 then your router should use 1.2.3.4 as the next hop IP address and forward the packet out of interface eth1.

subnets (and longest prefix mask): The network mask field of the routing table specifies the size of the subnet being routed to. More specifically, given a particular destination IP addresses (ipdest), it matches with a route if the following test is true:  (ipdest & mask) equals (destination prefix & mask).  Note that typically the destination prefix in the routing table is stored as(dest & mask) so and'ing with the mask is unnecessary.

It is important to note that a given destination IP address can match with multiple subnets. In fact, this is often the case! For example, all destinations match the default route. In these cases, the router must choose the best or most specific match. This is done by selecting the match with the longest prefix or the largest value subnet mask. Because you will be updating your forwarding table dynamically, you will need to find an (efficient) method for supporting longest prefix match rather than just selecting the first route that matches.

You will notice that each link in the 3 router topology above is assigned a subnet that only contains 2 IP addresses. Be sure to consider the subnet mask when handling routes. In this topology, the subnet mask is 255.255.255.254. (The VNS project does not have enough extra IP addresses lying around to give out larger subnets containing more than 2 addresses. Sorry.)

Static vs. Dynamic Routes: During operation, your routing table should contain both static and dynamic routes. Static routes are read in from the routing table (rtable) and should never be removed or modified. Dynamic routes are added/removed by your PWOSPF implementation. You must therefore keep track of which routes are static. You can handle this however you like, such as maintaining two separate tables or marking routes as static/dynamic.

PWOSPF

The routing protocol you will be implementing -- PWOSPF -- is a link state protocol that is loosely based on OSPFv2. Note that while PWOSPF is based on OSPFv2 it is sufficiently different that referring to the OSPFv2 as a reference will not be of much help and may instead confuse or mislead you.

Your router is responsible for advertising all of its static routes along with the subnets connected to each of its interfaces. Given any router on the network, aggregating all of this information properly should create a subnet graph from which you can calculate the correct routing table for that router to each of the advertised subnets. Exactly how to do this is part of the assignment challenge.

Tips

Be careful not to add a route in your routing table for subnets directly connected to one of your interfaces even if these subnets are being advertised.  In most cases, they will be (e.g. there is another router on the subnet).

You will almost certainly need to use threads in this assignment to support periodic PWOSPF updates (e.g. HELLO packets). Be careful to avoid race conditions. Your routing table in particular will be need to be locked off so that you don’t deadlock when looking up a route for a packet during updates.

Testing in this assignment can be difficult. You may want to add code to your router so than you can disable an interface at run time. You can use this to test whether your implementation converges after a link goes down (e.g. if the link between vhost1 and vhost2 goes down, app1 should still be reachable on the path vhost1 -> vhost3 -> vhost2 -> app1).

Getting Started

You are welcome to support PWOSPF in whatever manner you find appropriate. However, to help you get started, we’ve made available modified stub code that creates a PWOSPF subsystem structure within struct sr_instance and starts a thread that can be used to implement the necessary timer infrastructure. The new stub code also includes a header file pwospf_protocol.h which may contain useful definitions.

• pwospf_protocol.h
• sr_pwospf.c
• sr_pwospf.h

To add this code to your existing sr router built upon "scone-base", modify struct sr_instance in sr_base_internal.h and add

You'll also want to call pwospf_init(sr) somewhere in your software router to initialize it, such as from sr_integ_hw_setup() in sr_integration.c.

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.pacific.edu. For more details, see Project Submission.

Project Report

Your should extend your project report from the software UI project. You should update the document to address issues that were identified after the previous projects and you should add at least the following:

• A clear, concise description of how the dynamic routing protocol operates.
• A clear, concise description of how the dynamic routing protocol is implemented in software (what data structures are needed?)
• An updated and expanded description of your testing methodology

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.

Grading

This project will be graded out of 100 points.

• Implementation / correctness: 85 points
• Written report: 15 points

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