Lab 4: Dynamic Routing

Due date: Thursday, Nov. 12th @ 4:15 PM.

Routing Information Protocol (RIP)

RIP description taken from Clack RIP assignment

This section provides enough details about RIP so that you can implement it.

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 (the network's diameter) is 15 hops.  RIP version 2 is specified in RFC 2453. You will NOT implement all features supported by RIP version 2.  Below is a brief description of the protocol (adapted from RFC 2453) that outlines the specific functionality your code must support.

RIP Basic Procedure

At a high level, the basic procedure carried out by every entity (i.e., router) that participates in the routing protocol is as follows: 

More specifically, 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.

Split Horizon with Poisoned 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 poisoned 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 should use split-horizon with poison reverse.

Triggered Updates

Split horizon with poisoned 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 message.


RIP has several types of timers for sending periodic updates, timing out routes and actually removing routes from the routing table, see RFC 2453 for details. However, you will implement the following simpler timers.


There are several conditions under which a router needs to send out a RIP advertisement. We summarize these below:

In addition to sending RIP advertisements, your router should also handle advertisements it receives, according to the specifications in the previous section.

Getting Started

Download and unpack the starter directory.

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

Putting it all together

In the starter code, we have provided five 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.

In addition, you will run LVNS server which handles communication between the routers. The server will also allow you to introduce network events: link cost changes and links going down.

To make it easier for you to run dr instances, you can use the script to connect to your lvns server. It pipes the output from your dr instances into log files.

myth1:~> ./lvns -t complex.topo
# In another terminal on the same server
myth1:~> ./ 5

All this is explained in detail in the README file accompanying the code. Feel free to post questions to the newsgroup as well.

Testing the assignment

This assignment should be easier than Lab 3 and can be implemented in ~500 lines of code. Since the primary purpose is to understand dynamic routing, we will not provide you with testing scripts. Instead, you should use pen and paper to walk through your topologies and understand how routing tables change as the state of the network changes.

We will grade this lab by examining your routing tables. Additional topologies could be announced later on.


Q: Do we need to implement the garbage routes?
A: Optional. You may delete entries upon timeout.

Q: What is the next hop of a directly connected subnet?

Q: What is the destination IP address and next hop for a RIP advertisement?
A: Use the defined RIP_IP constant for the destination IP address and next hop.

Q: What are some basic checks on RIP packets that we should do?
A: Sanity check for command, version, and a unicast source address.

Q: What next_hop should I return if there is no existing route?
A: You should return 0xFFFFFFFF for this case since 0 is reserved for a directly connected network.


To submit, run

make submit
from your project directory and submit the resulting tarball on the submission page.

Collaboration policy

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.