Implementing the Routing Information Protocol (RIP)

Deadline: Thursday, April 6th, 2:00 PM

This is a group project, each group has up to TWO students. You can do it alone, but you will get NO extra credits for that.  


RIP Summary

Building and Running Clack

Basics of Using Clack

Clack API's for Routing and RIP

Debugging Tips

Development Tips

Quick Links:  Assignment Code   RFC 2453 (RIP)   Clack Demo   Clack APIs   Virtual Network System



In this assignment, you will implement a simplified version of the Routing Information Protocol (RIP); the intra-domain routing protocol  used in many networks in the Internet. You will implement and test your routing protocol in a fully-functioning, application-level, router called Clack. Clack is implemented in Java and has an interesting graphical interface that enables you to visualize the network topology and the flow of packets inside the router.

You will be provided the code of all components of the Clack router, except the RIP component, which you will add. By the end of this project your modified  Clack router should be able to build its own forwarding table from advertisements sent by other routers, send the appropriate advertisements to neighboring routers, and route traffic through complex topologies containing multiple nodes.

More specifically, each team will be assigned the virtual network shown in the following figure.

Although the above network is virtual, every element (more accurately, every network interface) has a real IP address and is reachable from  the Internet. This is accomplished using the Virtual Network System (VNS). You do not need to know how VNS works to do this assignment, you are welcome to check it out though.

Nodes labeled vhost2 and vhost3 will be running fully-functioning Clack routers that implement RIP. Your own Clack router will run on vhost1. You will need to implement RIP in your Clack router and make it  interoperate with the other two routers.

Probably, it will be a good idea check out the Clack router web page before your proceed with the assignment. There is a cool demo on that page, we recommend you try it out. 

Routing Information Protocol (RIP)

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

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  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 (which is backward compatible with RIP version 1 specified in RFC 1058).  We recommend reading the newer RFC 2453, but you will NOT implement all features supported by RIP version 2.  Below is a brief description of the protocol (adapted from RFC 2453).

RIP Basic Procedure

At a high level, the basic procedure carried out by every entity 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 using information gathered by means not specified in this  protocol.  The metric for a directly-connected network is set to the cost of that network.  Typically, 1 is the used as the network cost.  In that case, the RIP metric reduces to a simple hop-count.  More complex  metrics may be used when it is desirable to show preference for some  networks over others (e.g., to indicate of differences in bandwidth or reliability).

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

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.

Message Format

RIP is a UDP-based protocol.  Each router that uses RIP has a routing  process that sends and receives datagrams on UDP port number 520. All routing update messages are sent from the RIP port.  The RIP version 1 packet format is:

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
| command (1) | version (1) | must be zero (2) |
| |
~ RIP Entry (20) ~
| |

There may be between 1 and 25 (inclusive) RIP entries. A RIP entry
has the following format:

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
| address family identifier (2) | must be zero (2) |
| Destination IPv4 address (4) |
| must be zero (4) |
| must be zero (4) |
| metric (4) |

   Every message contains a RIP header which consists of a command and a  version number. The command field can be:

The remainder of the datagram contains a list of Route Entries (RTEs). Each RTE contains an Address Family Identifier (AFI), destination IPv4 address, and the cost to reach that destination (metric). AFI is set to 2 for the Internet Protocol.  The metric field contains a value between 1 and 15 (inclusive); or the value 16 (infinity), which indicates that the destination is not reachable. Fields that are zeroed out are used only in RIP ver 2 extensions, which you will not implement in this assignment.  


 RIP ver 2 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.

Building and Running a Modified Version of Clack

Unpacking the Code

Unzip your archive. It should contain the following files:
  1. clack-1.0.0-rip1.jar : The JAR file containing the Clack library

  2. reference.topo : A Clack configuration file that will load Clack with ALL routers running the reference implementation of RIP

  3. development.topo : A Clack configuration file that will load Clack with host 'vhost1' running YOUR implementation of RIP, and with all other routers running the reference implementation.

  4. : The java file for your implementation of RIP. It already contains the basic boiler-plate for required for Clack components and some initial functionality to get you started.

  5. : A java file to load Clack and make it aware of your new RIP functionality.

The only file of these you will need to modify at any time is You do not need to understand the internals of either the configuration files or the RIPClackLoader class.

Running Clack

  1. Before running Clack, you need to tell it to connect to your specific virtual network, called a topology. You should have received a topology number via email. Open both development.topo and reference.topo and the line at the top of the file that looks like:

     < topology number="999-999" server="" port="12345" >
    Change all values of 999 to be your topology number, (e.g. If I have topology 149, i would change it to "149-149"). You may only ever have one Clack instance connected to a topology at a single time, otherwise you will be prompted to enter an alternate topology number.
  2. To test your java runtime setup, we will now try to run Clack without any of your RIP specific code. You can later use this as a test of whether changes you made to *.java files are causing problems with Clack. Run Clack with :

    java -cp clack-1.0.0-rip1.jar net.clackrouter.gui.ClackLoader -f reference.topo
    You should see Clack load and connect, presenting you with a view of your network. If not, make sure that Java is properly installed.
  3. Now we want to run Clack using the RIPRouting component that you can modify. First, build the two java file using:

    javac -cp clack-1.0.0-rip1.jar *.java 

    If this fails, you may have to update to a newer version of your Java compiler (version 1.4 or above).

    Now run your version of Clack with the reference topology file:

    java -cp .:clack-1.0.0-rip1.jar RIPClackLoader -f reference.topo  

    Note the addition of the current directory to the classpath. This loads a network of Clack routers, all using the reference RIP implementation.

    Now run Clack with the configuration file that will load a single router running your RIP component:

    java -cp .:clack-1.0.0-rip1.jar RIPClackLoader -f development.topo 
    Notice that the console output includes output specific to your file. At the router-view level, your component should flash red whenever it receives a packet to notify you that it currently drops all packets.
This is all you need to know about compiling and running Clack so that you can add your own RIP functionality.

The Basics of Using Clack

While you do not need to become a Clack expert to succeed at this assignment, a bit of background about Clack will help you understand what is going on. Clack provides a graphical view of a virtual network of routers and allows you to explore inside a router to see what is going on. Clack is based on the Virtual Network System (VNS), but this is designed to be largely transparent to the user. For more information on VNS, see .

When you open up Clack, you see a view of a network of routers. This network is connected to the Internet via a firewall host and also contains to application servers, which each host a webserver. Clack topologies, while virtual, are actually connected to the Internet, so when you are done with this project, you will have written a routing protocol that has directed real Internet traffic. This view is called the "topology-level view" and provides an overall picture of your network. Each host displays its IP address(es) and how it is connected to other hosts in the network.

Use the zoom-in button on the tool-bar to explore within your router, which is the one highlighted with blue (you can also just double-click it). This shows the "router-level view", which show the internal operation of your router as it handles traffic in real-time. Different bits of router functionality are performed by different "components" that pass packets between them. Packets enter the router at one of the grey input interface blocks near the top that represent input interfaces, and leave via the grey interface blocks at the bottom. Components pass packets to each other via "wires" that are connected to different "ports" on the component. Double-clicking on a component will bring up its "property view" pane, which provides several different tabs of information including live-statistics, information about component ports, and a general description of the component's behavior.

You will be implementing a simple component, RIPRouting, with one input port for accepting routing packets and one output port for sending routing packets.

To see a live tutorial of the Clack router, using the following command to run Clack with an accompanying HTML tutorial. Note: use either of the application servers on your topology as the webserver, and you will have to wait a few seconds for the routing protocol to converge before your routers will be able to handle live traffic. Feel free to skip the later steps once you have a good idea of how Clack works (only one of the two webservers has large files to download).

java -cp .:clack-1.0.0-rip1.jar RIPClackLoader -f reference.topo -t

Each Clack component is a Java object that extends the base class ClackComponent. Each packet processed by Clack is also a Java class that extends the basic VNSPacket class. Most components, like your RIP component, receive traffic to process when a connected components "pushes" a packet into its only "in" port. For your router configuration, this will be a L3Demux component that demultiplexes different types of Level-3 traffic. To receive packets your component implements the method:

    public void acceptPacket(VNSPacket packet, int port_number) {
    	if(port_number != PORT_UPDATE_IN) return;
    	VNSIPPacket ip_packet = (VNSIPPacket)packet;
		// now look inside IP header and payload ... 

Your component's input and output ports both only accept packets of the class VNSIPPacket, so you can safety cast from a VNSPacket to VNSIPPacket. To send packets to other components, you "push" them out a different port. In the case of the RIP component, its only output port is connected to an element that forwards IP packets. The following code snippet pushes out an IP packet (m_ports is an instance variable inherited from ClackComponent) :

	VNSIPPacket ip_packet = (VNSIPPacket)packet;

Clack API's for Routing and RIP

Finding Out About Local Link Information

To route you need to know about the immediate links your router is connected to. Your RIP component will learn about the links connected to it by querying its instance of the Router class, which is configured with this information when Clack starts. The LocalLinkInfo class represents this information for a single link:

public class LocalLinkInfo {
	public String local_iface;  // name of the local interface (e.g. "eth0")
	public InetAddress next_hop;  // IP address of the interface on the other end of the link
	public int metric;  // your routers value for the cost of this link
	public boolean is_up;  // tells if the interface is currently capable of transmitting/receiving packets
	public is_routing_iface;  // tells if this link is connected to another host that is participating in the RIP routing protocol
	public InetAddress network, subnet_mask;  // network and mask representing this link's subnet

Your component should ask its router for the local link information, which keeps this information in a Hashtable using the name of the local interface as a key:

	Hashtable local_links = getRouter().getLocalLinkInfo();
	for(Enumeration e = local_links.keys(); e.hasMoreElements(); ){
		String iface_str = (String) e.nextElement();
		LocalLinkInfo info = (LocalLinkInfo) local_links.get(iface_str);
		// do something with local link info...  

Accessing and Modifying the Routing Table

Of course, to be a useful routing protocol you will also need to be able to access your router's routing table. Remember that you are implementing routing, which is the process of deciding what information should be in the routing table. The process of forwarding, which uses the routing table to forward packets out a particular interface is handled by the IPRouteLookup component.

Clack provides a generic abstraction to the routing table that supports different routing protocols. For RIP, each entry in the routing table will be an instance of the following class:

RIPRoutingEntry {

	public short mTTL;
	public int mCost;
	public boolean mIsLocal;
	public InetAddress mDestination;
	public InetAddress mNextHop;
	public InetAddress mMask;
	public String      mInterface;

The routing table is implemented by the RoutingTable class, which has the following key methods for use with routing protocols:

public RoutingEntry getEntry(int i) // get a particular entry from the table

public int numEntries()  // total number of entries in the table

public void addEntry(RoutingEntry entry)  // add an entry

public void deleteEntry(RoutingEntry entry) // remove an entry

public RoutingEntry getRouteForPrefix(InetAddress net, InetAddress mask) // gets the current route that has
 									//  the specified destination net and mask

A couple important things to note:
  1. The RoutingTable API deals with RoutingEntry objects, of which RIPRoutingEntry is a sub-class. You will need to cast routing entries returned from the table
  2. Don't confuse getRouteForPrefix() with a longest-prefix match look-up. It is different in a VERY important way. This method will an entry only if the routing table has an entry with the equivalent network address (after masking) and a prefix of the SAME length as the one provided.

The constructor of your RIPRouting class stores a reference to the router's routing table in the instance variable mRtable . You could iterate through all routing entries using this code:


   	for(int i = 0; i < mRtable.numEntries(); i++){
		RIPRoutingEntry rip_entry = (RIPRoutingEntry)mRtable.getEntry(i);
		// do something with each routing entry ....

Creating and Reading RIP Update Packets

RIP components on different routers communicate by exchanging RIP routing information via specialized routing packets. Clack has a special class called RIPRoutingUpdate to represent these network packets. By using its getters/setters you avoid the trouble of parsing network packets. A RIP update packet contains a list of routing entries, each of which describe a specific route in the routing table of the sender. The source IP address is assumed to the the next-hop that has sent this routing information. Each entry is represented by the following inner class:


	RIPRoutingUpdate.Entry {
		public InetAddress net, mask;  // the destination network and mask, describing the route this entry refers to
		public int cost; // cost of this route from the advertising router
		public short ttl; // time-to-live of the routing information in seconds
Below we discuss how to read/send these packets from/to the network layer. Here we will discuss how to read or set the data contained in the packets. The following methods of the RIPRoutingUpdate class will be the most important for you to use:
	public RIPRoutingUpdate()  // create an empy packet
	public RIPRoutingUpdate(ByteBuffer packetBuffer)  // create a packet from IP payload

	public void addEntry(InetAddress dest, InetAddress mask, int cost, short ttl)  // add an entry to the packet's list of entry
	public ArrayList getAllEntries()  // get all entries contained in a packet

Encapsulating/Decapsulating IP Packets

Your routing protocol operates at Layer 3 and uses IP as a transport mechanism.

The following code snippet shows how to process a packet in the context of an acceptPacket() method. It first checks the IP protocol field see if it is a RIP packet, then reads the name of the interface the packet was received on and the IP source address. It then takes the payload of the IP packet and uses it to construct an instance of the RIPRoutingUpdate class.

    	VNSIPPacket ip_packet = (VNSIPPacket)packet;
        byte protocol = ip_packet.getHeader().getProtocol();
        if(protocol == VNSIPPacket.PROTO_CLACK_RIP) {
           String incoming_iface = ip_packet.getInputInterfaceName();
           InetAddress src_addr = InetAddress.getByAddress(ip_packet.getHeader().getSourceAddress().array());
			RIPRoutingUpdate update = new RIPRoutingUpdate(ip_packet.getBodyBuffer());

You will also need to be able to go in the reverse direction when you send routing packets. The following example creates an update packet, and sends it to from . Of course, you will want to put routing data in your packets!

Note the use of the m_ports array to send the IP packet to another component in the Clack router. In your router, this port is connected to another component responsible for forwarding IP packets.

	InetAddress src = InetAddress.getByName("");
	InetAddress dst = InetAddress.getByName("");
	RIPRoutingUpdate update = new RIPRoutingUpdate();
	VNSIPPacket ip_packet = VNSIPPacket.wrap(update, VNSIPPacket.PROTO_CLACK_RIP, src, dst);

Using Timers in Clack

Timers are provided by the setTimer(). Your RIPRouting component must also implement a call-back function, which will be called when the timer expires.

   public void timerCallback() {
   		System.out.println("Reschuling the timer for 10 more seconds!");

Only one timer may be set at a time. Calling setTimer() again before it expires cancels the previous timer.

Handling Changes to Local Links

Finally, since your routing protocol is dynamic, it must have some way of learning about link failures or changes to the routing metric on local links. Clack uses the LocalLinkInfo class, introduced above to alert the router to such changes via the following call-back that provides the old and new link characteristics as input :
public void localLinkChanged(LocalLinkInfo old_info, LocalLinkInfo new_info){

    if(old_info.is_up != new_info.is_up){
    	System.out.println("Link Status Changed");
    }else if(old_info.metric != new_info.metric){
    	System.out.println("Link Metric Changed");

Debugging Tips

Hopefully you now have a good idea how to use the API's you need to finish your assignment. Still, you will need to be able to see exactly what's going on inside your router to debug and test your implementation. Of course you can print statements or use a Java debugger to do this, but Clack also provides some tools to make things easier for you.

Printing Output

Your RIPRouting component already comes with a convenience method dumpRIPRoutingTable() to print a routing table to standard out on your machine. Additionally, each component has its own individual log, which can be viewed by double-clicking the component and using the "log" tab at the bottom of the property view. As a programmer, you can use either the log(String s) or error(String s) methods of the ClackComponent class to write to the log. The only difference between the two is that the latter also writes the String to standard error. You can also use the signalError() method to cause the component to flash red when something bad happens,

Viewing Routing Tables from the GUI

The topology-level view of Clack allows you to see the contents of the routing table on all routers in the network in real-time. The diamond shape button on the tool-bar toggles between this "Routing Table View Mode" and the standard mode. You can also use View - > ToggleRouteTableView . Routes used recently to forward IP packets are highlighted in a light blue to help you realize how the router is using the routing table. The "iface" field in the router table shows which outgoing interface the next-hop is on, as well as the last octet of the next-hops IP address.

Using Ethereal

How can you find out what messages routers are sending to each other? Clack now includes an Ethereal Protocol Analyzer like tool that let's you inspect packets sent between routers. Two toolbar buttons control the starting and stopping of an ethereal instance. The small "e" ethereal icon starts ethereal, and the same icon with a red "X" through it stops ethereal. When starting or stopping ethereal, you must choose which host you wish to "sniff" packets from. You can start start an instance for each router on your network.

If you are unfamiliar with the basic interface of Ethereal, please learn more about it on its website. A main difference with our version of Ethereal is that it captures packets on ALL interfaces of a particular router, instead of just a single interface. As a result, the farthest right entry in the packet-list table in ethreal specified the router interface that the packet was received on, and whether it was entering or leaving the router when it was captured.

This tool already has parsers to understand many standard protocols and we added the ability to parse RIP packets. By selecting a RIP packet in the upper packet-list table, you can explore its contents in great deal using the two lower views. This can be a very powerful debugging tool, so be sure to use it!

Changing link status and metric info.

To really stress your routing protocol once you have things basically working, you will want to be able to change the status of links. This includes enabling and disabling links and changing the metrics of a link. Before we discuss how to do this, it is important to realize a major difference between changing a link's up/down status and changing a link's metric. The action of enabling or disabling a link affects routers on both ends of the link. The RIP process on both ends of the link are alerted to this type of change. Conversely, the act of changing a weight affects only the local router. .

Now, let's look at how to change link characteristics. Both types of changes require the use of the "Clack Shell", which is a command line interface to each of the routers. Launch the shell with the black shell icon on the toolbar, or using View - > SpawnClackShell . While the shell supports a wide variety of applications, we will use only a simple one: ifconfig

Enable of disable a link by specifying the router interface that is connected to that link:

	ifconfig eth2 up  
	ifconfig eth1 down

Change the metric (cost) for a router to use a particular link, again by specifying the local interface of that link

	ifconfig eth2 metric 10

View the status of each interface, including current up/down status and link metrics, etc.

	ifconfig all

Unfortunately, the Clack Shell is still a bit fragile, so if you get an error about null command, simply type it again. This occurs because the cursor is moved away from the current command-line (a downside of using JTextArea).

Development Tips

Page last updated April 2nd, 2006