Data Networks
Project 3 - Implementing Intra-Domain Routing Protocols


Handed out: Thursday, 28 June 2007
Due: Friday, 20 July 2007 at 11:59pm


Project description

The project description can be found in the following PDF file:

Please follow the project requirements carefully. We will enforce these requirements strictly. Remember that your implementation has to work on the CIP machines.

Download

We provide an implementation of the GSR9999 simulator in C++ and Java. Please remember that we ask you not to change any existing simulator file besides the RoutingProtocolImpl class. You might want to create additional classes though.

To extract the archive run tar -xzf simulator_cpp.tgz or tar -xzf simulator_java.tgz.

Each archive contains a Makefile that will build the simulator. There is a folder tests that contains some sample configurations for the simulator. The Java version also contains a README file that gives you Java-specific hints on the simulator.

Testing

There are three simple examples included in the source tarballs. You can use them to test your implementation and as a starting point to write your own configurations. We will provide more complex examples later. But we encourage you to test your implementation heavily with your own configurations, too.

Testing will consist of mainly two parts:

First, we will test your implementation on its own. It has to handle different topologies (e.g., trees, rings, meshes, ...) and events (e.g., links going down, link coming up, data packets sent from random sources to random destinations, ...). This tests if your implementation works correctly.

Second, we will run the simulation with multiple deployed routing protocols, e.g., your implementation runs on half of the nodes and a reference implementation runs on the other half. This tests if your implementation follows the protocol specification and can inter-operate with other implementations.

A simple test to find out if your protocol implementation works correctly is to send data packets from random sources to random destination and check if it arrives at the destination and if any routing loops are present.

Below you find a tarball with 4 sample tests and a check-script. It is obvious that just four test cases cannot cover all possible corner cases your protocol might run into. We advice you to write your own test cases. But keep in mind that the design you are implementing is simplified and not optimized for practical usage at all. In particular, it takes quite a while for the DV protocol to converge just because of high timeout values.

The four test cases are:

The tarball includes a small perl script that checks if the sent packets eventually arrive at their destination. The script takes a config file and a simulator output file as an input. Below is an example how to use this:

The script simply checks how many of your packets get lost. For our test cases above we tried to use configurations that avoid any packet loss (e.g., by giving the network a lot of time to converge after a link went down or up). You might imagine that it is infeasible to test every detail of the router implementation, it is just too complex for this.

Our tests for grading will use very similar tests. But we will also run two different protocol implementation together to test interoperability (i.e. correct protocol implementation following the specification). Furthermore, we might also check the path a packet takes through the network.

Grading

As before we did not grade any submissions that will not compile or will not work. We did honour any instructions given in attached README files for the testings.

Grading included 4 parts. The points were split equally between the individual tests of each part.

  1. Original tests (36%): We ran the four original tests published here and used the included test script to check how many packets arrived at the destination.
  2. New tests (36%): We slightly changed the four original tests and used the same script as before to check how many packets arrived at the destination.
  3. Path correctness (10%): We tested on a simple scenario if the routing protocol implementation chooses the shortest path.
  4. Protocol interoperability (18%): We ran the submitted implementation together with our sample solution and checked if the protocols work together (thus follow the protocol specifications and packet formats). Therefore we checked if packets get successfully delivered from one network to the other.

For 1, 2, and 4 we gave full points if at least 80% of all packets arrived at the destination and half the points if at least 20% arrived for a particular test.

All the tests and scripts used can be downloaded here.
Running multiple protocol implementations was done with a simple change in Simulator.{java,cc}: In init_routing_protocol() use the node ID to decide which routing protocol to instantiate.