[Solved] 64831 Assignment 3

AimsLearn about routing protocols and route propagation.Implement a routing protocol.OverviewIn this assignment, you will be writing code to simulate a network of routers performing routeadvertisement using a Distance Vector routing protocol.You will need to implement the algorithm in its basic form, and then with poisoned reverse/routepoisoning to improve the performance of the protocol. Your implementation will need to ensurethat the simulated routers in the network correctly and consistently converge their distance androuting tables to the correct state.You will find a more detailed description of the Distance Vector algorithm in the course notes andin section 5.2.2 of Kurose and Ross, Computer Networking, 7th Edition.Your TaskPart 1 (DV algorithm)You are to produce a program that:1. Reads information about a topology/updates to the topology from the standard input.Handle bad input:Printing a reasonable error message andTerminating the program with exit code 1;Bad input should not cause your program to crash.2. Uses DV algorithm or DV with PR algorithm, as appropriate, to bring the simulated routers toconvergence.11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 3/11Output 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 PR algorithm)You will need to modify/write a second version of the program that uses poisoned reverse/routepoisoning.The DV with PR algorithm program you are to provide should be named PoisonedReverse .In Your TaskYou will need to craft any internal data structures and design your program in such a way that itwill reliably and correctly converge to the correct routing tables. We have deliberately not providedyou with a code templates and this means that you will have more freedom in your design but thatyou 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 RequirementsYou may complete this assignment using the programming language of your choice, with thefollowing 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 useMakefile 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 theWeb Submission system, these are the same as those found in the labs and on the uss.csserver and include (but are not limited to):C/C++: g++ (GCC) 4.8.5Java: java version “1.8.0_201”Python: python 2.7.5 or python 3.6.8Your implementation may use any libraries/classes available on Web Submission system, butno external libraries/classes/modules.Your programs will be executed with the command examples below:For C/C++make./DistanceVector./PoisonedReverse11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 4/11You can find a simple example makefile for C++ HERE(https://myuni.adelaide.edu.au/courses/64831/files/8781526/download?download_frd=1) . Agood resource is here: https://makefiletutorial.com/ (https://makefiletutorial.com/)This will need to be customised for your implementation. Make sure you use tabs (actualtab characters) on the indented partsFor java:makejava DistanceVectorjava PoisonedReverseYou can find a simple example makefile for Java HERE(https://myuni.adelaide.edu.au/courses/64831/files/8781519/download?download_frd=1) . Agood resource is here: https://makefiletutorial.com/ (https://makefiletutorial.com/)This will need to be customised for your implementation. Make sure you use tabs (actualtab characters) on the indented partsFor Python:./DistanceVector./PoisonedReversePrograms 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 cloudinstance).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).AlgorithmDistance Vector (DV)At each node, x: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 costto get from v to y. This is the minimum cost considering both the cost from x to v and the cost fromv 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 wD_w(y) = Infinity for all destinations y in Nfor each neighbour wsend distance vector D_x = [D_x(y): y in N] to w11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 5/11LOOPwait (until I see a link cost change to some neighbour w or untilI 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 ysend distance vector D_x = [D_x(y): y in N] to all neighbours.FOREVERNote: 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.Poisoned Reverse (PR)In Poisoned Reverse, if a node A routes through another node B to get to a destination C, then Awill advertise to B that its distance to C is Infinity. A will continue to advertise this to B as long as Auses B to get to C. This will prevent B from using A to get to C if B’s own connection to C fails.Key AssumptionsIn a real DV routing environment, messages are not synchronised. Routers send out their initialmessages 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 theirupdate at the same time.The next set of updates will only be sent once all routers have received and processed theupdates from the previous round.When a link to a directly connected neighbour is updated or an update is received, and theupdate 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 routername)Send an update (in the next round).You should confirm for yourself that the assumptions above will not change the least-cost pathrouting table that will be produced at the nodes. (Although, for some topologies, you may takedifferent paths for the same cost.)Sample TopologyAt its most basic, your program should be able to calculate the correct routing tables for thefollowing network:11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 6/11As shown in lecturesInput FormatYour program will need to read input from the terminal/command line’s standard input.The expected input format is as follows:XYZX Z 7X Y 2Y Z 1X Z 5Z Y -11. The input begins with the name of each router/node in the topology.Each name is on a new lineRouter names are case-sensitiveRouter names may not contain spaces2. An empty/blank line separates each section.3. The next section of input contains 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, allseparated by spaces.e.g.Y X 2Y Z 1Weight values should always be integers.A weight value of -1 indicates a link/edge to remove from the topology if present.Once all values in this section are read in, your algorithm should be run with this topologyinformation to bring your simulated routers to convergence.4. An empty/blank line separates each section.11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 7/115. The next section again contains the details of each link/edge in the topology.The values in each of these sections should be used to update the topology.If a link is not included in any section, it should remain unchanged.As above, a weight value of -1 indicates a link/edge to remove from the topology ifpresent.Again, once all values in each of these sections are read in, your algorithm should be runwith this topology information to bring your simulated routers’ routing tables toconvergence.A user may input as many of these sections as they like.25/05/21 CLARIFICATION: This section may also be omitted, i.e. A user may input 0 ormore of these sections.6. This repeats until 2 empty/blank lines are received, at which point the program exitsnormally.The input above matches the sample topology with the following updates:Expected Output FormatAs this is Distance Vector, 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 packetswill be sent through, as shown below.Your program should print 2 types of output that repeat:1. The distance table of each router in the following format:router X at t=0Y ZY 2 INFZ INF 71. The name of the router, and the current step (starting at 0)2. The name of the destination router3. The name of the next hop router4. The current known distance (from the current router, to the destination, via the nexthop)Use INF to represent infinite values11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 8/11Use – where no link is presentInclude all routers except the current router in the rows/columns in the table, evenif no direct link is present.Rows/columns should be ordered by router name.Your rows/columns don’t have to align, and the amount of white-space you use isyour choice, but the easier it is to read the easier your debugging/testing will be.5. A blank line to separate each table.When running the algorithm to converge the routing tables, this table should be printed forevery router (in alphabetical order, by router name), at each step2. The converged routing information:router X: Y is n routing through Zwhere1. The name of the source router/node2. The name of the destination router/node3. The name of an immediate neighbour of the source4. The current total distance from the source to the destination routing via the next hop5. If a destination is unreachable from the source router/node, your output should look likerouter A: B is unreachableThis 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.Below is an example of what this output should look like for the provided topology and inputs(shortened, full output HERE(https://myuni.adelaide.edu.au/courses/64831/files/8785739/download?download_frd=1) ).router X at t=0Y ZY 2 INFZ INF 7router Y at t=0X ZX 2 INFZ INF 1router Z at t=0X YX 7 INFY INF 1…router X at t=2Y ZY 2 8Z 3 7router Y at t=2X ZX 2 4Z 5 1router Z at t=2X YX 7 3Y 9 1router X: Y is 2 routing through YX Z i 3 i h h Y11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 9/11router X: Z is 3 routing through Yrouter Y: X is 2 routing through Xrouter Y: Z is 1 routing through Zrouter Z: X is 3 routing through Yrouter Z: Y is 1 routing through Yrouter X at t=3Y ZY 2 6Z 3 5router Y at t=3X ZX 2 –Z 5 –router Z at t=3X YX 5 –Y 7 –…router X: Y is 2 routing through Yrouter X: Z is 5 routing through Zrouter Y: X is 2 routing through Xrouter Y: Z is 7 routing through Xrouter Z: X is 5 routing through Xrouter Z: Y is 7 routing through XRecommended Approach1. 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 Wikipediaentry (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 sampletopologyFeel 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 implementationDetermine what data structures you’ll need, choose a programming language, plan howyou’re going to parse the input and generate output, plan your algorithm’simplementation.Be sure to add logbook entries as you go.4. ImplementationDevelop your implementation, testing as you go.Write a makefile if required.Be sure to add logbook entries as you go.5. TestingEnsure your code runs on the university systems.Develop additional scenarios and topologies to ensure your systems function asexpected.11/10/2021, 15:32 Programming Assignment 3: Routing Algorithm Implementation Assignmenthttps://myuni.adelaide.edu.au/courses/64831/assignments/211818 10/11Be sure to add logbook entries as you go.