Cleveland State University

Department of Electrical and Computer Engineering

EEC 484/584 Computer Networks

Spring Semester 2007

Course Project

Link State Routing

Demo Due: 5/2 and 5/9 6-8pm (signup sheet will be made available soon)

Project report due: 5/9/2007 11:59pm in the form of hardcopy or email attachment

In this project, you will implement a link state routing algorithm and its execution environment. This project is to be completed individually, or by a team of up to 2 members. The project, once finished, should consist of the following components:

A routing daemon. The routing daemon simulates the software running within a router in the communication subnet. Several routing daemons will run according to the topology of the network simulated.
A test program sending packets to the network. The packets should be routed properly according to the link state algorithm by the routing daemons to their destinations.
A test program receiving packets delivered by the network.

The relative roles of these components are illustrated in the following figure.

In this project, we have the following assumptions.

Addressing. Any network protocol must use an addressing scheme to identify different entities in the network. There is no exception for our routing protocol used in our virtual communication subnet. We will be using English alphabet characters to identify the routers in our network, i.e., each router is assigned unique character such as ‘A’, or ‘B’, etc., as shown in the figure above.
Network topology. Due to our addressing scheme, our network is naturally limited to 26, i.e., there are up to 26 routers can exist in our network. The network topology is supplied by a configuration file. The topology must not be hard-coded in the routing daemon.
Routing protocol. Similar the Internet Protocol, our routing protocol provides an unreliable connectionless routing service. Each router (i.e., routing daemon) loads the topology file when starting. It also calculates the shortest path from itself to each other router in the network using the Dijkstra’s algorithm. Then, the forwarding table is determined based on the shortest path calculation. Except for the extra credit tasks, we assume the topology does not change during each run and the routers do not fail (neither the link cost). Packets injected to the network should contain both the source and destination addresses. On receiving a packet, a router should retrieve the destination address and look up the forwarding table to determine to which router it should forward the packet to, or to deliver the packet to the receiving application if the packet is sent to its local network (i.e., the packet’s destination address is identical to the router’s address).
Test applications. We assume a pair of test applications (Alice and Bob in the figure above) will be used to inject packets to the subnet and to receive them. The applications do not have their own addresses, instead, they assume the addresses of the routers that they directly connect to. The sending application may join the local network of any router, and may send packets to any destination in the subnet. Again, such information is supplied in the figuration file, rather than hard-coded to the application. The receiving application should be capable of receiving packets from any router.
Execution. We assume all processes are run at the same local host. It is possible to run each routing daemon at a different host, but you need to supply (a lot) more information in the configuration file and modify the Node class (perhaps other classes as well).

For your convenience, a reference implementation is provided in the form of a Java jar file, and partial source code. You are encouraged to use them as the starting point for your project. You are free to use any other programming language for this project. However, you will not get the benefit of the template source code, which is in Java.

The reference implementation consists of the following files:

Alice.java – An application program that injects packets to the subnet.
Bob.java - An application program that receives packets injected by Alice from the subnet.
ByteArrayUtils.java – implements utility methods that convert byte array to integer/char and vice versa.
RoutesMap.java – Base Interface for the subnet topology.
DenseRoutesMap.java – This class implements the RoutesMap interface and provides the data structure representing the network topology.
DijkstraEngine.java – This class reads the network topology and provides APIs to compute the shortest path from any node to any other node in the network.
LinkState.properties – The configuration file for this project. It includes the subnet topology information and the routers the test application should connect and send to. The topology is represented as a comma-separated list of links. Each link is in the form of nodei-nodej-linkcost. For example, A-B-5 stands for a link between router A and B, with link cost of 5 (from A to B, or from B to A). Note that the network size must be consistent with the number of nodes present in the network. Futhermore, the addresses used should also be consistent with the size of the network. For example, for a network with size of 4, only the first 4 alphabet characters A, B, C, and D can be used as the addresses (not E or F etc.).
LinkStateCofig.java – This class is responsible to read the configuration file and covert the information to a DenseRoutesMap object. It also retrieves configuration information for the test applications.
Node.java – Data structure for each router. In particular, it implements the addressing scheme for our routing protocol.
Packet.java – The class that defines the structure of the packet, i.e., the transmission unit of our routing protocol. Encoding (converting the packet object to a byte array) and decoding (converting a byte array to a packet object) methods are also provided.
Routed.java – The class that implements the main functionality of our routing protocol, such as determining the forwarding table and carrying out the actual forwarding operations.

Note that the following files are provided with their full implementation and they are obtained from http://renaud.waldura.com/doc/java/dijkstra/ (with some modifications): RoutesMap.java DenseRoutesMap.java, DijkstraEngine.java, Node.java.

How to run the reference implementation binaries:

Download the jar file (linkstate.jar) for the reference implementation and expand it in your working directory (note that you should not attempt to execute the jar file directly because there are several classes that have the main function):

jar xf linkstate.jar

Read the configuration file: LinkState.properties. The default configuration consists of 4 routers, A, B, C and D. You can try different topologies by modifying the configuration.
Start all routing daemons. You need multiple DOS terminals, or XTerms, one for each daemon. You must supply the address of the daemon you want to start in the command line. For example, to start routing daemon as router A, type

java Routed A

Then, start Alice and Bob in two different terminals (with Bob started first):

java Bob

java Alice

If everything works fine, you should see each routing daemon output the topology and its forwarding table content. Alice sends a single packet to Bob and quit. The packet injected into the network is routed properly to its destination Bob, and Bob should output the payload of the packet: “Hello World”.

Tasks:

Before you start implementing this project, you should make sure you have a good understanding of the link state routing algorithm. You should read the relevant section in the textbook and other materials on the Internet. In line with this requirement, you are required to write a two-page or longer summary of the link state routing algorithm in your own words. Consider this task as the first task for this project.

If you choose to implement this project in a different language, you have to implement all functionalities provided by my reference implementation, as described above, and finish tasks 4-6 (in the context of your framework). You are free to incorporate existing libraries into your implementation, just like what I did (don’t forget to cite the source though).

If you decide to use my template code, below are the specific tasks you should accomplish. Most of the files above are provided with full implementation. But you do need to add the omitted sections in some files and modify the provided code according to the instructions below. Your tasks include:

Thoroughly read and understand the code provided. Try to execute the binary files provided, study their behavior, and learn what you are expected to achieve.
Complete the populateForwardingTable() method in Routed class.
Compete the lookupForwardingTable() method in Routed class.
Once you have completed task 1-3, run the test applications (Alice and Bob) at least 5 times, each with a different configuration (network topology, and to which router Alice and Bob connect to). Record the output from each routing daemon and derive the path the packet has taken in each run. Then, manually verify the correctness of the path taken in each case.
Modify Alice and Bob’s code so that for each packet sent by Alice, it is echoed back by Bob. To do this, you must study and understand the Packet class.
Performance is always a very important consideration for any network protocol. In this task, you will learn how to measure the round-trip latency of the packet sent by Alice. Obviously, you can proceed to doing this task only after you have completed task 5. To get accurate measurement of the latency, you should comment out all printouts in the source code. Since one round trip is so short, you need to measure the total time elapsed after a substantial number of iterations, say 1000. You should record the starting time prior to the start of the iterations, and record the ending time of right after the iterations are over. From the timing difference, and the number of iterations, you can derive the average latency for each round-trip. The best API to get timing measurement is: System.currentTimeMillis().

Deliverables:

Completed Source code.
A project report containing the following sections

Summary of the link-state routing algorithm (at least 2 pages long, ideally with original illustrations)
Summary of your understanding of the reference implementation: the flow of control, the functionality of each class, etc. If you are not using my reference implementation, describe your design and implementation.
Documentation of the tasks 2-6: your implementation (high level, do NOT include your source code here!), output of each task (if applicable), analysis of the output (applicable for tasks 4 and 6).
References. Provide bibliography on the references that you have used to complete this project.

Demonstration (May 2 and May 9, 6-8pm).

Evaluation Rubrics:

The following rubrics will be used to evaluate your project quality and to determine your grade.

Summary of the link-state routing algorithm: correctness, easy to read, no grammatical errors or typos, high quality illustrations, full bibliography (up to 20%)
Summary of your understanding of my reference implementation, or your implementation if you do not use my implementation: correctness, thoroughness, easy to read, no grammatical errors or typos, flow charts are encouraged (up to 20%)
Good naming and coding convention used in the code you wrote (up to 10%)
Correct implementation of tasks 2 and 3 as judged from your source code (up to 10%)
Correct execution of task 4, with correct and sound explanations of the actual path taken by each packet (remember to verify manually the observed paths), as judged from your project report and your demonstration (up to 10%)
Correct implementation of task 5, as judged from your project report and your demonstration (up to 20%)
Correct implementation of task 6, as judged from your project report and your demonstration (up to 10%)

Note that the project demo is not assigned a separate credit. It is used as a way to help me determine the correctness of your implementation and your understanding of the project.

Extra credit task (5% of the course):

The reference implementation uses UDP to send the packets around. UDP is an unreliable, connectionless protocol. In most of the cases, you are not going to see any packet loss because we have assumed all processes run on the same host. In practice, however, that might not be the case. If Alice and Bob want to communicate reliably, they will have to run a reliable communication protocol on top of the routing protocol. To earn the extra credit, you need to modify Alice and Bob’s code and implement an improved version of the “Simplex ARQ Protocol with (1-bit) Sequence Numbers for a Noisy Channel”. Recall that I pointed out some problems with the protocol in class and the sequence number must also be used in the ACK frame as well. Your implementation should reflect this improvement. Furthermore, you need to simulate loss by intentionally dropping DATA and ACK frames, at the sending node and in the subnet (i.e., some router might discard a packet received). This is needed to verify the correctness of you protocol design and implementation. Once you have completed these steps, you need to repeat task 6 with this new protocol. You should also provide a detailed description of your design, implementation, correctness verification, and performance evaluation of the protocol in your project report. A demonstration is also required. Finally, this extra credit opportunity is open only to those who have earned at least 90% of the credit for the main project.