CPS 114 Introduction to Computer Networks: Lab 1

CPS 114 Introduction to Computer Networks: Labs

Lab 3: Dynamic Routing

Introduction

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/spring10/cps114/labs/lab3/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:

Keep a routing table with an entry for every possible destination network. Each routing table entry contains the destination network, the distance (also called a 'metric' or 'cost') to reach the destination, and the 'next-hop' router that is the next router on the chosen path to that destination.
Periodically, send a routing update to every neighbor. The update is a set of messages that contain all of the information from the routing table. It contains an entry for each destination network, with the distance to reach that destination.
When a routing update arrives from a neighbor G', add the cost associated with the network that is shared with G'. Call the resulting distance D'. Compare the resulting distances with the current routing table entries to that same destination network N. If the new distance D' for N is smaller than the existing value D, adopt the new route. That is, change the table entry for N to have metric D' and router G'. If G' is the router from which the existing route came, i.e., G' = G, then use the new metric even if it is larger than the old one.

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

Destination address: RIP represents destination networks by a "network address" and a corresponding "network mask", both of which are IPv4 addresses. Commonly, the network address and mask together are referred to as a "network prefix" and written as X.X.X.X / Y, where X.X.X.X is the network address and Y is the length in bits of the network mask.
Metric: Total cost of getting a datagram from the router to that destination network. This metric is the sum of the costs associated with the networks that would be traversed to get to the destination.
Next hop: The IPv4 address of the next router along the path to the destination. If the destination is on one of the directly-connected networks, this item is not needed.
Timestamp: Time information to determine when routing information is stale.

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 0.0.0.0. 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.

Periodic Update: a router sends advertisements every 10 seconds.
Triggered Update: (1) A local change (an interface went down or the cost of a local interface changed) in the table cause an immediate transmission of the RIP advertisement to neighbors. (2) A router received an advertisement that has caused it update to its local table. That update needs to be announced immediately.

Timers

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:

Periodic updates: Every 10 seconds, the RIP process sends an unsolicited Response message containing the complete routing table to every neighboring router.
Route timeout: RIP maintains a TTL field for each dynamic route (i.e., a route learned from a neighboring router. Local routes, which are directly connected networks, have an invalid TTL of -1). If a router sees an update containing a destination/next-hop pair that it is already in use, it updates the timestamp for that entry in its local routing table. If a route's timestamp reaches 20 seconds, the route's cost is set to infinity, and a triggered routing update is sent to notify the neighbors that the route has become invalid.

Requirements

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 10.0.0.2 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 10.0.6.2 on the lvns server. Analyze the convergence process. Will Split Horizon with Poison Reverse accelerate the convergence process?

Submitting

To submit the assignment, do the following:

Run the command make submit, this should create a file called lab-dr.tar.gz.
Upload lab-dr.tar.gz and your report to the lab3 assignment on Blackboard.

Collaboration policy

You can discuss with anyone, but you must not look at each other's code, or copy code from others.

Acknowledgement

This lab is adapted from Dynamic Routing

Last updated: 03/2010