Assignment 2: Routing Simulations Assignment 2 Routing Simulations Distance vector, is due Thursday, February 23 (midnight) Contents Description Details Obtaining, Building, and Running the Simulator Write-Up Submission Grading References Description In this assignment, students will take an existing network routing simulator in Java and add code to simulate distance-vector routing protocol. The purpose of this assignment is to reinforce students' understanding of distance-vector 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. Details 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. 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. 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. Obtaining, Building, and Running the Simulator The source code for the simulator can be downloaded here: routing-simulator.tar.gz Type gzip -cd routing-simulator.tar.gz | tar xvf - to unpack the simulator. Type javac *.java in the simulator directory to build the simulator. Type java Network filename.net to run the simulator with a given topology file. The directory containing the compiled java source files must be in your CLASSPATH, or CLASSPATH must not be set. Java 1.3 or higher is required. Write-Up Students must write a short (no more than three pages, double-spaced) report for the routing algorithm 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. Submission Use the submit_cps214 command. On the CS Department systems, the full path is /usr/local/bin/submit_cps214. On ACPUB systems, the full path is /afs/acpub/project/cps/bin/submit_cps214. For example: submit_cps214 proj2 writeup.pdf Node.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. Grading 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? References Peterson & Davie, Computer Networks, pp.284-290, 292-298. Descriptions of distance-vector and link-state routing algorithms. Cormen, Leiserson, and Rivest, Introduction to Algorithms, pp. 465, 470, and 527. Graph representation, breadth-first searches, and Dijkstra's shortest-path algorithm. Javadoc API documentation for the routing simulator
