Distance Vector Routing

 

By Farrokh Ghani Zadegan and Niklas Carlsson, August 2013
(Based on an assignment by Juha Takkinen)

Contents

Overview of the Assignment

This assignment has two parts. The first part consists of four tasks: design, implementation, test and demonstration of a program in Java that implements a distributed and asynchronous distance vector routing protocol, based on the Bellman-Ford equation. The solution should include the "Poisoned Reverse" technique, which solves the problem of looping in routing topologies. For the second part you should write a report in which you carefully describe and discuss (i) how distance vector routing works, (ii) how you tested the algorithms, (iii) some cases in which poisoned reverse may fail, and (iv) a solution to this problem.

Important note: Before starting to do the coding for this assignment, you need to: Ignoring the above "important note" (and advice) typically results in many extra hours in the lab. You should REALLY understand how distance vector routing works before you making changes to the code. Carefully writing down the algorithms and tracing through some example scenarios may also help here.

What You Should Implement

The main challenge in this assignment is that your code must be asynchronous. For this assignment you will use an event-driven simulator that manages communication between routers. You should implement the part of the algorithm which is executed in each router. Although routers are active in the same program (simulator), they can only communicate with each other by sending messages through the simulator.

For this assignment you will use the following files (which can be downloaded from here):

After extracting the above archive, a Test folder is also created which contains three versions of the simulator that can be used to test your code:

Figure 1
Figure 1: Network with three nodes in RouterSimulator3.java
Figure 2
Figure 2: Network with four nodes in RouterSimulator4.java
Figure 3
Figure 3: Network with five nodes in RouterSimulator5.java

For this assignment, you should only add code to the RouterNode.java file. For testing your implemented code (in RouterNode.java), you may also need to (slightly) modify the code in the RouterSimulator.java. You can use the F class in the F.java file to perform simple formatted text output.

You should add code for the constructor and methods in the RouterNode class that is in the RouterNode.java file. You may only communicate with other routers via the sendUpdate() method. You should not add any static member to this class, or by any means get around the requirement that all information must go via sendUpdate(). Moreover, it is not acceptable to use specific values for link costs (such as negative numbers) to signal the other routers to perform an operation.

Other methods in the file are:

Important note: Your tables should preferably be self-explanatory, and when you demonstrate your code to the lab assistant, you should be able to explain exactly what your tables contain.

Your solution should implement the poisoned reverse technique. Your solution should also easily allow poisoned reverse switch on/off, such that the system can be compared with and without poisoned reverse (during the demonstration, for example).

Execution of the Simulator

You start the simulator by typing

% java -DTrace=3 RouterSimulator

The simulator starts by initializing each router. A number of windows appear on the screen, one for the simulator output and one for each router node that is initialized, see Figure 4. The title of the window describes what is in it. The graphical user interface is implemented in the file GuiTextArea.java. In your implementation, in the window of each of the router nodes, the minimum distance vector and route (next hop) to take to reach each of the destinations should be displayed. Optionally, the physical cost to each of the neighbors as well as minimum distance vectors received from neighboring nodes can also be shown.

Figure 4
Figure 4: Contents of the screen when simulation starts

From this starting point, your code should ensure that updates occur on the network, i.e., since the simulator stops as soon as there are no packets being transmitted, your code should be such that as soon as a node is initialized, it sends updates to its neighbors. The simulator will run until the routing tables have converged, i.e., when there are no more messages or events in the system.

You can change the seed value for pseudo-random numbers in the simulator. For example, to use a value of 123, you can use -DSeed = 123 as shown:

% java -DSeed=123 RouterSimulator

Using another initial value for pseudo-random numbers gives a different sequence of events for the messages in your network.

Note: The provided Makefile can be used to facilitate doing this assignment. For example, entering the following command in the terminal, compiles the files and starts the simulation with DTrace=3:
% make test

Or you can select among the provided
RouterSimulator classes, which are implemented in RouterSimulator3.java, RouterSimulator4.java and RouterSimulator5.java, by entering either of the following commands:
% make install3
% make install4
% make install5
Each of the above three commands overwrites the current version of RouterSimulator.java, and therefore asks you to confirm the overwrite by pressing Ctrl+D (or cancel it by pressing Ctrl+C).

Another useful command is make clobber  which deletes the results of previous compilation. Such deletion of .class files ensures that the next make test uses the most recent version of the .java files.

You can examine the Makefile and modify it according to your needs.

Link Costs and Events

You should make sure that the network topology or the link costs will not change as a result of running your implementation of the distance vector routing. You can, however, as you will see later in this manual, use events in the RouterSimulator class to study how your algorithm responds to the changes in link costs.

When you demonstrate your solution and/or your TA tests your code, he/she might use other values for the link costs in the topology. You should change the values to test your code more thoroughly only by initializing the data structure connectcosts[][] in the RouterSimulator(), see Figure 5. However, make sure to put the same link costs in both directions on each link, as this assignment only considers symmetric link costs. It is also here that different topologies can be encoded. You can also experiment with new topologies by changing the number of nodes (if required) and initializing the connectcosts[][]array as required. To change the number of nodes, you should modify the value assigned to NUM_NODES in the constructor of the RouterSimulator class.

Figure 5: A sample code showing initialization of link costs in the RouterSimulator for the network topology in Figure 2

The simulator will never send RouterPacket messages itself. It is your code which must ensure that the information are exchanged between routers in the network.

The RouterNode.java file has a variable called costs which is initialized in the constructor. The simulator sets the link costs associated with a node through the costs variable. For example, in the network shown in Figure 2, the link costs for node 1 is set via the vector {1, 0, 1, RouterSimulator.Infinity} , which means that the cost of the link (from Node 1) to node 0 is 1, to itself is 0, to node 2 is 1, and to node 3 is infinity.

Costs for all links are set in the constructor for the RouterSimulator class as was discussed for Figure 5. Further down in that code, two events are added which change the link costs at specific times during the simulation period. The link between eventity and dest changes to cost at time evtime. A sample code for adding such a cost changing event is shown in Figure 6. Note that the link costs will not change if you do not change the value for the constant LINKCHANGES to true in the beginning of the RouterSimulator.java file. Please change link costs and the events to test your code. When a link cost change (which is scheduled by using the above-mentioned events) happens, the simulator notifies the router nodes by calling the updateLinkCost() method, which you should implement.

Figure 6: A sample code showing insertion of an event that changes the link cost between Node 0 and Node 1 to 60 at simulation time 40

Each of the three copies of the simulator (for the networks illustrated in figures 1, 2 and 3) have at least one link cost changing event scheduled. The following figures show how in each of the topologies link costs change:

Figure 7: Change of link costs

More information about implementation of distance vector routing can be found in RFCs, such as the following :

as well as in many other online resources, books, and publications.

Development Strategy

As a general remark, it is suggested that you take a step-by-step approach for this assignment, such that initially the constructor, the recvUpdate() method, and the printDistanceTable() method are implemented and tested using RouterSimulator4.java and RouterSimulator5.java. In the second step updateLinkCost() should be implemented and tested using RouterSimulator3.java. In RouterSimulator3.java, the constant LINKCHANGES is set to true by default which causes a link cost change to happen at simulation time 40. At this point you will observe the count-to-infinity problem. Additionally, you may want to set LINKCHANGES to true in the RouterSimulator4.java and RouterSimulator5.java files and examine the results. In the third step Poisoned Reverse should be implemented to address the count-to-infinity problem. Your implementation should be such that "poisoning" can be easily enabled and disabled, for example, using a Boolean variable (this helps a lot when demonstrating your implementation to the TA).

Beyond Poisoned Reverse

The "Poisoned Reverse" technique solves the problem with the loops in the network topologies that you test in this lab. Give an example of a topology (e.g. an extension of one of networks in this lab) where the algorithm would not work, and explain the reason. Give a solution for this new problem and explain how the problem is resolved by your solution. Even if using solutions proposed in the literature, please use your own words and clearly explain the above issues and solutions.

Demonstration and Reporting

To complete this lab you should demonstrate your solution to the TA. Your TA might use topologies other than those two used for this assignment to test your code. Be ready to explain what the printDistanceTable() displays on the screen, and how you have implemented the Poisoned Reverse algorithm.

You should also write a short report in which you carefully describe and discuss (i) how distance vector routing works, (ii) how you tested the algorithms, (iii) some cases in which poisoned reverse may fail, and (iv) a solution to this problem. Make sure you have responded in detail to the questions above (particularly to those related to bullets (iii) and (iv)) and use valid sources as references.

After your demonstration, you should deliver your report (including the code and the answer to bullets (iii) and (iv)) in a signed IDA lab cover to your TA. You should also email your RouterNode.java file to your TA.