CS 456 Spring 2013 - Assignment 2

(Version: Jun 20 10:00:17)

Due Date: Tuesday, July 30, 2013, 23:59 - no late submission!

In this assignment, you must implement a variant of distance vector routing called Path Vector Routing in a simulated network node. Path vector routing is very similar to distance vector, but with one modification: route advertisements contain the full path to the destination. Using this information, nodes can determine whether using a neighbour's announcement would result in a routing loop. You can implement your solution in any programming language, provided it can be executed in the linux.student.cs environment.

Configuration and communication between nodes is simulated by reading and writing files. Complex setups can be executed by a script. Your task is to design and implement a program that performs path vector route computation. Each invocation of the routing program performs one complete routing table computation at one node. The program is invoked with a parameter determining the node identity. Each program run completes, before another one is started. Multiple consecutive invocations of the routing program with the same or different node identities simulate the operation of multiple routers. There is no concurrency between multiple runs, but to simulate asynchronous execution, no particular execution order of program invocations can be assumed.

Details

During each invocation, the program reads input from files, computes its routing table, and writes the output to a table file. Multiple invocations and indirect communication via files simulate asynchronous execution of and communication between multiple nodes - with the intention of reducing the overall complexity of the assignment. The detailed operation of your program is as follows (see further below for details of file naming):

Read own table file to obtain current routing table.
Read edge file, but only use information about local links.
Read table files from direct neighbours, if available, and treat as announcements.
Compute new routing table using the Bellman-Ford algorithm while avoiding loops by using the path vectors.
Store new routing table in own table file.
Terminate.

The network graph file specifies undirected edges (i.e. duplex links) between network nodes and their costs. It must be named edges in the current working directory. It contains one edge specification per line as

<node1> <node2> <cost>

for a link between <node1> and <node2> with an positive integer cost <cost>. The file can also contain empty lines to structure the contents for readability. The edge file might be changed between program runs to simulate changes in the network topology.

Table File

A node's routing table file must be named table.X in the current working directory, where 'X' is replaced with the node's integer identifier, e.g., table.1 for Node 1. Each node learns from the edge file to which other nodes it has direct links and reads those table files, if they are available. The table file must contain lines of the following format:

<destination> <path cost> <node1> <node2> <node3> ...

where <destination> is the destination node and <path cost> is the total cost of the path. Node <node1> is the next hop neighbour towards this destination, <node2> the next hop along the path, and so on, up to the last hop before the destination.

Transient Loops

Because nodes do not necessarily execute synchronously (in any particular order), transient loops are still possible with path vector routing, even if alternative paths are available. Construct a scenario where a loop is formed and later resolved by using an alternative path. Prepare two edge files and a script (shell, perl, etc.) that executes nodes and puts the edge files in place to demonstrate the loop scenario.

Procedures

What to hand in

Hand in source code files, including appropriate comments. All files must be stored in the same directory. There should be no directory hierarchy or package definitions. Your assignment must come with a Makefile. The targets in the Makefile must include:
- 'clean' to remove all object files, as well as all log and temporary files; and
- 'all' to build all object and executable files
After executing 'make all', one executable (or start script) must exist in the current directory. The executable 'pvr' must accept an integer node identifier as the singe command-line parameter:
```
pvr <ID>
```
Your code can make use of standard libraries for your programming language, e.g., for containers. However the Bellman-Ford algorithm must not be taken from third-party code. If in doubt, consult with the instructor. Clearly document what you do.
Submit files 'edges.loop.1' (original topology) and 'edges.loop.2' (topology after single link failure) and an executable script 'loop' that demonstrate the formation and resolution of a transient loop as discussed above. The script should copy the edge files in place during the execution to simulate a link failure. Explain the scenario and the script in your design document (see below), so that the marker can quickly verify the scenario.
'README' file: Indicate which machines your program was built and tested on. This file should also document which parts of the assignment have or have not been completed. The file should contain at most 200 words.
'a2doc.pdf' file: A pdf document describing the design and testing of your implementation (e.g., design justifications, reasoning behind optimizations). The document most not contain more than five pages, using at least a 10 pt font.

Evaluation

The assignment is to be done individually. Your program must work in the linux.student.cs environment. Your program should not silently crash under any circumstances. At the very least, all fatal errors should lead to an error message indicating the location in the source code before termination. Marks will be assigned as follows:

Functionality and Correctness: 70%
Code Quality and Documentation: 20%
Loop Example: 10%

Submission Instructions

After you have completed testing your code, hand it in using the dropbox feature of the Learn environemnt. Combine all files into a zip/tar/gzip/bzip2 archive with any of the following corresponding names: a2.{zip,tgz,tbz}. Make sure to execute 'make clean' before handing in and do not include temporary or object files. Late submissions are not permitted.

Example

The following shows an sample edge file along with the resulting table files after a sufficient number of executions.

edges

table.1

2 3
3 5 2
4 10 2 3

table.2

1 3
3 2
4 7 3

table.3

1 5 2
2 2
4 5

table.4

1 10 3 2
2 7 3
3 5