COMP SCI 3001/COMP SCI 7039 - Computer Networks and Applications - Programming Assignment 3: Routing Algorithm Assignment

Programming Assignment 3: Routing Algorithm Assignment (Must Use Logbook) (DV) Due 1 Jun by 17:00 Points 200 Available 1 May at 1:00 - 29 Jun at 17:00 CourseNana.COM

Assessment Weighting: 20% (200 Marks) Task description: In this assignment, you will be writing code to simulate the Distance Vector routing protocol in a network of routers. Academic Integrity ChecklistDo  Discuss/compare high level approaches  Discuss/compare program output/errors  Regularly commit your work and write in the logbook Be careful  Code snippets from reference pages/guides/Stack Overflow must be attributed/referenced.  Only use code snippets that do not significantly contribute to the exercise solution. Do NOT  Submit code not solely authored by you.  Post/share code on Piazza/online/etc.  Give/show your code to others Before you begin Although this practical is marked automatically , all marks will be moderated by a marker using the following information. You must complete a logbook as you develop your code (this process should be familiar to those that have or are doing the Computer Systems course). You can find details on how to do that and what that should look like in this guide During manual marking and plagiarism checks, we will look look at your development process. If we do not see a clear path to a solution (i.e. code changes and regular commits and logbook entries reflecting your learning to develop your implementation you may forfeit up to 200 marks. An example case of forfeiting all 200 marks would be the sudden appearance of working code with no prior evidence of your development process . It is up to you to provide evidence of your development through regular submissions and logbook entries . This practical requires thought and planning. You need to start early to allow yourself time to think of what and how to test before modifying any code. Failing to do this is likely to make the practical take far more time than it should. Starting the practical in the final week or days is likely to be an unsuccessful strategy with this practical; further your logbook entries are likely to be overlapped in close succession and, depending on the quality of the entries, is likely to lead to a mark that will be scaled lower (due to possibly poor documentation in the logbook). CourseNana.COM

Automatic Zero Marks You will get an automatic zero for: a) code that does not compile; b) code that crashes during execution; c) code not submitted and/or leaving code in svn repository only; d) not using correct file names. No exceptions will be made for not following our advice and guidelines. The expectation is that will thoroughly test your implementation prior to submission. Aims Learn about routing protocols and route propagation. Implement a routing protocol. Overview In this assignment, you will be writing code to simulate a network of routers performing route advertisement using a Distance Vector routing protocol. You will need to implement the algorithm in its basic form, and then with Split Horizon to improve the performance of the protocol. Your implementation will need to ensure that the simulated routers in the network correctly and consistently converge their distance and routing tables to the correct state. You will find a more detailed description of the Distance Vector algorithm in the course notes and in section 5.2.2 of Kurose and Ross, Computer Networking, 7th Edition. Your Task Part 1 (DV algorithm) You are to produce a program that: CourseNana.COM

1. Reads information about a topology/updates to the topology from the standard input.
2. Uses DV algorithm or DV with SH algorithm, as appropriate, to bring the simulated routers to convergence. Output the distance tables in the required format for each router at each step/round. Output the final routing tables in the required format once convergence is reached.
3. Repeats the above steps until no further input is provided. The DV algorithm program you are to provide should be named DistanceVector . Part 2 (DV with SH algorithm) You will need to modify/write a second version of the program that uses Split Horizon. The DV with SH algorithm program you are to provide should be named SplitHorizon . In Your T ask You will need to craft any internal data structures and design your program in such a way that it will reliably and correctly converge to the correct routing tables. W e have deliberately not provided you with a code templates and this means that you will have more freedom in your design but that you will have to think about the problem and come up with a design. You will need to record your progress and development cycle in a logbook as described in the 'Before you Begin' section above. Programming Language/Software Requirements You may complete this assignment using the programming language of your choice, with the following restrictions : For compiled languages (Java, C, C++ etc.) you must provide a Makefile. Your software will be compiled with make (Please look at this resource on how to use Makefile build tool: https://makefiletutorial.com/ (https://makefiletutorial.com/) ) Pre-compiled programs will not be accepted. Your implementation must work with the versions of programming languages installed on the W eb Submission system, these are the same as those found in the labs and on the uss.cs server and include (but are not limited to): C/C++: g++ (GCC) 4.8.5 Java: java version "1.8.0_201" Python: python 2.7.5 or python 3.6.8 Your implementation may use any libraries/classes available on W eb Submission system, but no external libraries/classes/modules . Your programs will be executed with the command examples below: For C/C++ make ./DistanceVector ./SplitHorizon You can find a simple example makefile for C++ HERE A good resource is here: https://makefiletutorial.com/ (https://makefiletutorial.com/) This will need to be customised for your implementation. Make sure you use tabs ( actual tab characters ) on the indented parts For java: make java DistanceVector java SplitHorizon You can find a simple example makefile for Java HERE A good resource is here: https://makefiletutorial.com/ (https://makefiletutorial.com/) This will need to be customised for your implementation. Make sure you use tabs ( actual tab characters ) on the indented parts For Python: ./DistanceVector ./SplitHorizon Programs written using an interpreted language such as python: Will need to use UNIX line endings (always test on a uni system such as the uss cloud instance ). Will not be built with make (as shown above, because they are not compiled) Will require a 'shebang line' at the start of your file to run as above. e.g. #!/usr/bin/env python2 (Python 2) or #!/usr/bin/env python3 (Python 3). Algorithm Distance V ector (DV) At each node, : D_x(y) = minimum over all v { c(x,v) + D_v(y) } The cost from a node x to a node y is the cost from x to a directly connected node v plus the cost to get from v to y . This is the minimum cost considering both the cost from x to v and the cost from v to y . At each node x: INITIALISATION: for all destinations y in N: D_x(y) = c(x,y) / If y not a neighbour, c(x,y) = Infinity / for each neighbour w D_w(y) = Infinity for all destinations y in N for each neighbour w send distance vector D_x = [D_x(y): y in N] to w LOOP wait (until I see a link cost change to some neighbour w or until I receive a distance vector from some neighbour w) for each y in N: D_x(y) = min_v{c(x,v) + D_v(y)} if D_x(y) changed for any destination y send distance vector D_x = [D_x(y): y in N] to all neighbours. FOREVER Note: Infinity is a number sufficiently large that no legal cost is greater than or equal to infinity. The value of infinity is left for you to choose. Split Horizon (SH) Split Horizon is used to avoid network routing loops. In Split Horizon, a router will not transmit the routing information back in the direction it came from. W e cover poison reverse in the Lectures, but Split Horizon is simpler but similar in its goal. W e leave it as an exercise for you to study this simple algorithm. Some resources: https://www .geeksforgeeks.org/route-poisoning-and-count-to-infinity-problem-in-routing/ (https://www.geeksforgeeks.org/route-poisoning-and-count-to-infinity-problem-in-routing/) https://www .geeksforgeeks.org/poison-reverse-vs-split-horizon/ (https://www.geeksforgeeks.org/poison-reverse-vs-split-horizon/) With Split Horizon, if a router learns of a disconnection (INF) from it to a neighbour , then the router break the SH rule and advertises the disconnection. Key Assumptions In a real DV routing environment, messages are not synchronised. Routers send out their initial messages as needed. In this environment, to simplify your programs, you should assume: All routers come up at the same time at the start. If an update needs to be sent at a given round of the algorithm, all routers will send their update at the same time. The next set of updates will only be sent once all routers have received and processed the updates from the previous round. When a link to a directly connected neighbour is updated or an update is received, and the update affects the routing table: Choose the new best route from the distance table, searching in alphabetical order . Where multiple best routes exist, the first one is used (in alphabetical order , by router name) Send an update (in the next round). You should confirm for yourself that the assumptions above will not change the least-cost path routing table that will be produced at the nodes. (Although, for some topologies, you may take dif ferent paths for the same cost.) Sample Topology Consider the following network sample topology in our description of the required input format: Your program will need to read input from the standard input (terminal/command line) to construct such a given topology . Then, the perform updates, as illustrated below , and also given via the standard input (terminal/command line).

Please refer to this sample topology with the following updates above when looking into the expected input examples below . Input Format Your program will need to read input from the terminal/command line's standard input. The expected input format is as follows: X Y Z DISTANCEVECTOR X Z 8 X Y 2 Y Z 3 UPDATE Y Z -1 X Z 3 END The input begins with the name of each router/node in the topology . Each name is on a new line Router names will be a letter from the alphabet only Router names are case-sensitive This section ends with the keyword " DIST ANCEVECT OR" The input continues with the details of each link/edge in the topology . Written as the names of two routers/nodes followed by the weight of that link/edge. Weight values should always be integers A weight value of -1 indicates a link/edge to remove from the topology if present. This section ends with the keyword " UPDA TE". Your algorithm should run when the keyword " UPDA TE" is inputted and bring your simulated routers' routing tables and distance tables to convergence. Then, show the Expected Output for each router . The input continues with the update details of each link/edge in the topology given a link and cost. The values in each line of input in this section should be used to update the current topology . In this section, links can be added or removed while routers can be added only . As an example, a weight value of -1 indicates a link/edge to remove from the topology if present. As an example, if an unseen new router/node name has been inputted in this section, your program should be able to add this new router to the topology . Y A 10 From the example input given above, your program should add A as a new router into the topology where it has a link with a cost of 10 to Y. A user may input 0 or more lines in the "UPDA TE" section. This section ends with the keyword "END ". If there is input in the " UPDA TE" section, your implementation should run when the keyword "END" is inputted and bring your simulated routers' routing tables and distance tables to convergence. Then, show the Expected Output for each router . After that, the program exits normally . If there is no input in the " UPDA TE" section, t he program exits normally when the keyword "END" is inputted . Expected Output Format As this is Distance V ector , a node will only be able to communicate with its neighbours. Thus, node X can only tell if it is sending data to Y or Z. You should indicate which interface the packets will be sent through, as shown below . Your program should print 2 types of output that repeat: CourseNana.COM

1. The distance table of each router in the following format: X Distance Table at t= 0 Y Z Y 2 INF Z INF 8

where CourseNana.COM

1. The name of the router , and the current step (starting at 0).
2. The name of the destination router .
3. The name of the next hop router .
4. The current known distance (from the current router , to the destination , via the next hop ) Use INF to represent infinite values and where no link is present
5. Include all routers except the current router in the rows/columns in the table, even if no direct link is present.
6. Rows/columns should be ordered by router name in alphabetical order .
7. Your rows/columns don't have to align , and the amount of white-space you use is your choice , but the easier it is to read the easier your debugging/testing will be.
8. A blank line at the end of the table. When running the algorithm to converge the routing tables and distance tables, this table should be printed for every router (in alphabetical order , by router name), at each step
9. The routing table: X Routing Table: Y,Y,2 Z,Y,5

where CourseNana.COM

1. The name of the router/node.
2. The name of the destination router/node.
3. The next hop ( an immediate neighbour of the source ).
4. The total minimum cost/distance from the router/node to the destination via the next hop.
5. If a destination is unreachable from the source router/node, your output should look like Y,INF,INF
6. The destination need to be printed in alphabetical order .
7. A blank line at the end of the table.
8. This output should be printed for every router , and every destination (in alphabetical order , by router name, then destination name), each time the routers have reached convergence.
9. Where multiple best routes exist, the first one (next hop) is used (in alphabetical order , by router name). Below is an example of what this output should look like for the provided topology and inputs (shortened, full output HERE X Distance Table at t=0 Y Z Y 2 INF Z INF 8 Y Distance Table at t=0 X Z X 2 INF Z INF 3

Z Distance Table at t=0 X Y X 8 INF Y INF 3 ... X Distance Table at t=2 Y Z Y 2 11 Z 5 8 Y Distance Table at t=2 X Z X 2 8 Z 7 3 CourseNana.COM

Z Distance Table at t=2 X Y X 8 5 Y 10 3 CourseNana.COM

X Routing Table: Y,Y,2 Z,Y,5 Y Routing Table: X,X,2 Z,Z,3 Z Routing Table: X,Y,5 Y,Y,3 X Distance Table at t=3 Y Z Y 2 6 Z 5 3 CourseNana.COM

Y Distance Table at t=3 X Z X 2 INF Z 7 INF CourseNana.COM

Z Distance Table at t=3 X Y X 3 INF Y 5 INF ... X Routing Table: Y,Y,2 Z,Z,3 Y Routing Table: X,X,2 Z,X,5 Z Routing Table: X,X,3 Y,X,5 CourseNana.COM

Recommended Approach CourseNana.COM

1. Start by ensuring you're familiar with the DV algorithm. Review the course notes, section 5.2.2 of Kurose & Ross (7th Ed.), and the Wikipedia entry (https://en.wikipedia.org/wiki/Distance-vector_routing_protocol) . Be sure to add logbook entries as you go.
2. Manually determine the expected distance and routing tables at each step for the sample topology Feel free to ask questions and check your tables with your peers on Piazza. Be sure to add logbook entries as you go.
3. Plan your implementation Determine what data structures you'll need, choose a programming language, plan how you're going to parse the input and generate output, plan your algorithm's implementation. Be sure to add logbook entries as you go.
4. Implementation Develop your implementation, testing as you go. Write a makefile if required. Remember , you must add logbook entries as you go.
5. Testing Ensure your code runs on the university systems. Develop additional scenarios and topologies to ensure your systems function as expected. Be sure to add logbook entries as you go. Use input/output redirection - read the input from a file and redirect the output into a file for easy testing and dif f'ing (see: https://www .geeksforgeeks.org/input-output-redirection-in-linux/ (https://www.geeksforgeeks.org/input-output-redirection-in-linux/) ) Submission, Assessment & Marking Submission Hand-in key yyyy/s1/cna/routing (Note: create and checkout a new folder in your SVN repository at Assessment The assignment is marked out of 200. These 200 marks are allocated as follows using automated testing (prior to the deadline) and automated testing by a marker overseeing the process (after the deadline): Acceptance Testing (available to each submission before deadline; see below for details) ( free testing service ) DistanceV ector correctly calculates the routing table for sample configuration: 30 marks DistanceV ector correctly calculates the routing table after the link weights are changed: 20 marks Full Testing ( applied only after the deadline ; see below for details) ( 30 marks ) SplitHorizon correctly calculates the routing table for sample configuration SplitHorizon calculates the routing table after the link weights are changed Both programs, DistanceV ector and SplitHorizon , correctly calculate tables for arbitrary unseen networks: (120 marks) All marks above are from passing W eb Submission tests . No additional marks are given after a manual review . However , your marks are scaled and reviewed based on the following:
6. Up to 10 marks may be deducted for poor code quality . Below is a code quality checklist to help (notably this is not an exhaustive list but describes our expectations): write comments above the header of each of your methods, describing what the method is doing, what are its inputs and expected outputs describe in the comments any special cases create modular code, following cohesion and coupling principles don't use magic numbers don't misspell your comments don't use incomprehensible variable names don't have long methods (not more than 80 lines) don't have TODO blocks remaining
   2. As noted earlier , up to 200 marks (all marks) may be deducted for poor/insuf ficient/missing evidence of development process. The two above will be assessed manually . To obtain all of the marks allocated from tests, you will need to ensure your code is of sufficient quality and document your development process using the logbook entries . Marking Process You should not be using W eb Submission for debugging. As part of your design phase, you should work out what sequence of updates you expect to happen and what you expect the final distance tables will be. As such your submission will be marked in 3 stages :
7. All submissions before the deadline will be run against an acceptance testing script. This script will compile your programs, and run your DistanceV ector code for the sample config. Use this as a sanity check to ensure your code compiles and runs on the W ebSubmission system and works as expected. Be sure to add a logbook entry for each submission you make here.
8. After the deadline your most recent submission prior to the deadline will be run against the full testing script. This script will run the tests from the acceptance testing script as well as a number of additional tests against both your DistanceV ector and SplitHorizon code. It's important that you've thoroughly tested your implementation to ensure it will be able to pass these, as you will only get 1 chance at them.
9. You code will then be reviewed for quality and evidence of your development process by a marker . Marks will be deducted if your code and/or development process are not of a reasonable standard. Note: This is not a review of code functionality , and you will not receive extra testing marks for it
10. You will get an automatic zero for: a) code does not compile; b) code that crashes during execution; c) not submitting code and leaving it in svn only; d) not using correct file names. No exceptions will be made for not following our advice and guidelines. The expectation is that you know how to test code and will thoroughly test your implementation prior to submission.