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.
At a high level, the basic
procedure carried out by every entity (i.e., router) that participates in
the routing protocol is as follows:
Keep a routing table (or more accurately, a forwarding table) with an entry for every possible destination network. Each routing table entry contains the destination network, the distance D (also called a 'metric' or 'cost') to reach the destination, and the 'next-hop' router G 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 (i.e., link) that is shared with G'. (This should be the network over which the update arrived.) 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.
More specifically, 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.
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.
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.
Route timeout: RIP
maintains a TTL (time to live) 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 using, it updates the timestamp for that entry in its
local routing table.
If the timestamp of a route reaches is more than 20 seconds old, the route
is removed from the routing table and a RIP advertisement is broadcast.
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.
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.
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 launch_dr.sh 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:~> ./launch_dr.sh 5
All this is explained in detail in the README file accompanying the code. Feel free to post questions to the newsgroup as well.
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?
A: 0.0.0.0
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 submitfrom your project directory and submit the resulting tarball on the submission page.
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.