CPS 114 Introduction to Computer Networks: Labs

Lab 3: Dynamic Routing


Your task is to implement a simplified Routing Information Protocol (RIP). RIP is a routing protocol based on the Bellman-Ford (or distance vector) algorithm. RIP has been used as the intra-domain routing algorithm in many small-scale autonomous systems (ASes) in the Internet since the early days of the ARPANET. RIP is limited to networks whose longest path is 15 hops. RIP version 2 is specified in RFC 2453. You are NOT required to implement all features supported by RIP version 2. Below is a brief description of the protocol that outlines the specific functionality your code must support.

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 a virtual machine such as the free VirtualBox. We do not support MAC or Windows. Sorry.

Download and untar the lab3.tar.gz.

xwy@linux21$ wget http://www.cs.duke.edu/courses/spring11/cps114/labs/lab3.tar.gz
xwy@linux21$ tar xzvf lab3.tar.gz

In the starter code, we have provided you six sample topologies. To create your own topology, all you need is a file that lists routers with their corresponding name and interfaces and a list of links defining how the routers are connected. you will run lvns server which handles communication between the routers. The server will also allow you to introduce network events, such as link cost changes and links going down.

You should be able to run the command make to build the starter code. To make it easier for you to run dr instances, you can use the launch_dr.sh script (run it in another terminal) to connect to your lvns server. It pipes the output from your dr instances into log files.

xwy@linux21$./lvns -t complex.topo
xwy@linux21$./launch_dr.sh 5

Read the included README file very carefully, as it gives specific instructions on how to run the program and what functions need to be implemented.

Understanding RIP

The basic procedure carried out by every router that participates in the routing protocol is as follows:

Each node maintains a routing table, with each entry contains at least the following information:

The entries for the directly-connected networks are set up by the router when providing the topology. The next hop of a directly connected subnet is The destination IP address and next hop for a RIP advertisement is RIP_IP constant defined in dr_api.c. The next hop is 0xFFFFFFFF if there is no existing route.

Split Horizon with Poison Reverse

To prevent routing loops involving two nodes from occurring and to accelerate convergence in case of link cost changes, RIP uses a scheme called "split horizon with poisoned reverse." The simple split horizon scheme omits routes learned from one neighbor in updates sent to that neighbor. Split horizon with poison reverse includes such routes in updates, but sets their metrics to infinity (infinity is typically set to 16, since the maximum path limit in RIP is 15). In this assignment, you are required to implement split-horizon with poison reverse.

Triggered Updates

Split horizon with poison reverse will prevent any routing loops that involve only two routers. However, it is still possible to end up with patterns in which three routers are engaged in mutual deception. For example, A may believe it has a route through B, B through C, and C through A. Split horizon cannot stop such a loop. This loop will only be resolved when the metric reaches infinity and the network involved is then declared unreachable. Triggered updates are an attempt to speed up this convergence. To get triggered updates, we simply add a rule that whenever a router changes the metric for a route, it is required to send update messages almost immediately, even if it is not yet time for one of the regular update messages. There are several conditions under which a router needs to send out a RIP advertisement.


RIP has several types of timers for sending periodic updates, timing out routes and actually removing routes from the routing table. You are required to implement the following timers:


There is no test case for this lab. You are required to use the dr_dump_rtable function to dump your routing tables every 4 (or less) seconds. We will grade this lab by examining your routing tables.

Optionally, you can observe and analyze RIP convergence processes on the following two test topoplogies.

Run your implementation on the line.topo topology. Disable / Enable Split Horizon with Poison Reverse. (You can provide a switch in your code for this purpose.) Run intf down on the lvns server. Analyze the convergence process.

Run your implementation on the cti.topo topology. Enable Split Horizon with Poison Reverse. DISABLE the triggered updates when timeout happens. Run intf down on the lvns server. Analyze the convergence process. Will Split Horizon with Poison Reverse accelerate the convergence process?


To submit the assignment, do the following:

Collaboration policy

This is a group project. You may form a group of 2 or 3 to work on this assignment.


This lab is adapted from Dynamic Routing

Last updated: 03/2011