In this assignment, students will take an existing network routing simulator in Java and add code to simulate distance-vector and link-state routing protocols. The purpose of this assignment is to reinforce students' understanding of distance-vector and link-state routing.

This assignment uses a simulator rather than having students write an actual routing daemon implementing RIP or OSPF to avoid as much implementation overhead as possible and focus on the algorithms themselves. Java was chosen as the implementation platform in keeping with this goal -- students can write the same algorithms without worrying as much about data structure and memory management code.

Students are provided with a discrete-event network simulator that maintains a network topology as a set of nodes and links and simulates events such as packet delivery and changes in link state. The simulator includes a graphical front-end to display the network topology, the routing table for each node, and buttons for stepping through and ending the simulation. The simulator uses semi-realistic packet timings: packets arrive some nonzero time after they are sent depending on the latency of the link and the number of characters in the packet divided by the bandwidth of the link.

Students must write routing code to run on each virtual node by filling in methods of the "Node" class. The simulator provides each node with a list of neighbors, the ability to send packets to each neighbor, and callbacks for node initiation, packet receipt, and changes to the state of the links connected to a node. The node itself (with code written by students) must determine what packets are sent, when, and with what format/contents, as well as what to do with packets that it receives. Nodes must also react to changes in the state of links to their neighbors.

Although the simulator provides information about the cost of each link, students may ignore that and assume that each link has a cost of 1. Implementations that properly find routes with minimal cost will receive extra credit.

Students may use and experiment with the code for the routing simulator but are expected to make changes only to the "Node" class or to new classes that they introduce. To clarify, all projects will be graded on an unmodified version of the simulator, so please restrict your changes to Node.java or any new files.

Students must turn in part 1 (a distance vector implementation) separately from part 2 (a link state implementation).

Further details (e.g., the API provided to students and the functions that students must write) can be found in the file README.assignment in the simulator source file.

Students must write a short (no more than three pages, double-spaced) report for each of the routing algorithms describing how the algorithm works and its advantages and disadvantages (yes, roughly summarizing what the book says -- prove that you understand it), how their design corresponds to the algorithm, and any significant implementation experiences (problems, insights, etc.).

Please submit your write-up electronically in Portable Document Format (PDF) if possible, or as plain text otherwise.

Use the submit_cps196.1 command. On the CS Department systems, the full path is /usr/local/bin/submit_cps196.1. On ACPUB systems, the full path is /afs/acpub/project/cps/bin/submit_cps196.1.

Submissions for part 1 (distance vector) use the assignment name distance_vector. Submissions for part 2 (link state) use the assignment name link_state.

For example:
  submit_cps196.1 distance_vector writeup.pdf Node.java
  submit_cps196.1 link_state writeup.pdf Node.java Graph.java

Remember, only submit Node.java, your write-up, and new source files, if any. Do not submit any other existing source files, any Makefiles, or any .class files.

• 50% for correctness: Does the program find optimal routing tables for each node using the appropriate algorithm? (Note: distance vector does not always find optimal routes quickly, e.g., the count-to-infinity problem. Students do not need to solve "fundamental" problems with distance-vector routing.)
• 30% for style: Is the code readable, apparently correct, and well commented?
• 20% for the write-up: Does the write-up sufficiently describe the algorithm, the design, and the group's implementation experience?
• Extra credit for implementing link costs (5% for distance-vector routing, 10% for link-state routing): does the implementation find routes with minimal path costs rather than just path lengths?