Fast Reroute and Multipath Router

In this project, we present two feature extensions to the NetFPGA reference router: Fast Reroute and Multipath.

This work was originally intended as an advanced feature project for CS344 "Building an Internet Router" class, in the year 2009 at Stanford University.

Show Contents...Hide Contents...

Project summary

Status

Released

Version

1.0

Authors

Hardware: James Hongyi Zeng (hyzeng@stanford.edu)
Software: Mario Flajslik(mariof@stanford.edu), Nikhil Handigol(nikhilh@stanford.edu)

NetFPGA source

2.0

Introduction

Fast reroute

Detection of link failure or topology change in the reference router is generally based on the OSPF messages timing out. However, this causes packets to be dropped in the interval between the actual failure and failure detection. These intervals are as large as 90 seconds in PW-OSPF.

Fast reroute~\cite{rfc4090} is a technique that detects link failures at the hardware level and routes packets over alternative routes to minimize packet drops. These alternative routes are pre-computed by the router software.

Multipath routing

Multipath routing is a routing strategy where next-hop packet forwarding to a single destination can occur over multiple "best paths". This enables load-balancing and better utilization of available network capacity.

Our implementation of multipath routing is similar to ECMP; packets are forwarded over only those paths that tie for top place in routing metric calculations. This has the two-fold advantage of keeping the routing protocol simple and robust as well as minimizing packet reordering.

Download

NetFPGA source file and bitfile

 git clone git://github.com/eastzone/frmp_router.git

Router Software

 git clone git://github.com/mariof/cs344_spring09.git

GUI Source Code

 git clone git://github.com/nikhilh/cs344_spring09_gui.git

Regression Tests

The regression tests verify the functionality of the fast reroute and multipath router. In order to run the tests, you need to have the machine connected for the regression tests as stated in the Run Regression Tests section of the Guide.

After connecting the cables. Run the following command to run the regression tests.

 nf2_regress_test.pl --project frmp_router

Most of the regression tests of these two projects are the same to the reference router. Follow the Beta Release Regression Tests for details of those tests.

Moreover, 2 extra tests are created to test advanced features (fast reroute and multipath routing).

Test 1: Fast reroute

Project

frmp_router

Name

test_advanced_fastreroute

Description

1. Set duplicate entries in the routing table
2. Pull down some links via registers
3. Send a number of packets
4. Verify the packets and counters

Location

 projects/frmp_router/verif/test_advanced_fastreroute

Output

 SUCCESS!

Test 2: Multipath

Project

frmp_router

Name

test_advanced_multipath

Description

1. Set multipath entries in the routing table
2. Send a number of packets
3. Verify the packets and counters

Location

 projects/frmp_router/verif/test_advanced_multipath

Output

 SUCCESS!

Usage

Software Router

Get software router from:

 git clone git://github.com/mariof/cs344_spring09.git

Modify cpuhw file to match your topology configuration, e.g.

 interface   IP              netmask           MAC
 nf2c0       192.168.14.1    255.255.255.0     00:01:46:32:44:00
 nf2c1       192.168.4.1     255.255.255.0     00:01:46:32:44:01
 ...

Compile and run the router (must run it with sudo because it opens a raw socket)

 make
 sudo ./sr

Access the CLI by telnetting into the machine on port 2300. Type help for info on available CLI commands

 
 telnet localhost 2300
 ~>help

GUI

Run python backend server

Run Java GUI

How does it work?

Please refer to our NetFPGA Developers Workshop 2009 paper.