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.
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.
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).
At a high level, the basic procedure carried out by every entity 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 in the system. The entry contains the distance D to the destination, and the first router G on the route to that network.
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, with the distance shown to that destination.
When a routing update arrives from a neighbor G', add the cost associated with the network 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. 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: The IPv4 address of the destination.
Metric: Total cost of getting a datagram from the router to that destination. 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.
Timers: Various timers associated with the route.
Flags: To indicate that information about the route has changed recently.
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).
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).
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 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.
Route timeout: RIP
maintains a TTL (time to live) field for each dynamic route (the one
learnt from neighboring routers, not a local one). The TTL of a route is set to
20 seconds when it is first introduced and every
time RIP receives an update for that route. Every 1 second, RIP
decrements the TTL of all dynamic routes. If a TTL of a route reaches 0, the route
is removed from the routing table.
clack-1.0.0-rip1.jar : The JAR file containing the Clack library
reference.topo : A Clack configuration file that will load Clack with ALL routers running the reference implementation of RIP
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.
RIPRouting.java : 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.
RIPClackLoader.java : 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 RIPRouting.java You do not need to understand the internals of either the configuration files or the RIPClackLoader class.
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="vns-2.stanford.edu" 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.
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.topoYou should see Clack load and connect, presenting you with a view of your network. If not, make sure that Java is properly installed.
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.topoNotice that the console output includes output specific to your RIPRouting.java 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.
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 http://yuba.stanford.edu/vns/ .
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 http://www.clackrouter.net/demo/tutorial1.html
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; m_ports[PORT_UPDATE_OUT].pushOut(ip_packet);
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...
}
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 maskA couple important things to note:
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 ....
}
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
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 10.0.0.3 from 10.0.0.4 . 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("10.0.0.2");
InetAddress dst = InetAddress.getByName("10.0.0.3");
RIPRoutingUpdate update = new RIPRoutingUpdate();
VNSIPPacket ip_packet = VNSIPPacket.wrap(update, VNSIPPacket.PROTO_CLACK_RIP, src, dst);
m_ports[PORT_UPDATE_OUT].pushOut(ip_packet);
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!");
setTimer(10);
}
Only one timer may be set at a time. Calling setTimer() again before it expires cancels the previous timer.
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");
}
}
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.
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,
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.
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!
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).
Remember to use the .equals() functionality when testing for equality with objects such a String or InetAddress . Using == will simply check pointer equality.
Using an IDE, such as Eclipse, with syntax completion can speed things up significantly when you are working with an unfamiliar API. Many IDE's also have graphical debugging and exception handling capabilities.
Check out Clack javadoc for Clack classes at http://www.clackrouter.net/rip/javadoc/ and the standard Java API reference for other classes such as java.net.InetAddress.
More resources, including a Clack Developer Doc , are available at http://www.clackrouter.net . For a VERY in-depth look at Clack, you can browse the undergraduate thesis writeup about clack.