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
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
Checklist
Do
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 (https://myuni.adelaide.edu.au/courses/85255/pages/logbook) .
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).
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:
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 Task
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. We 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 Web
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 Web 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
(https://myuni.adelaide.edu.au/courses/85255/files/12505279/download?wrap=1)
(https://myuni.adelaide.edu.au/courses/85255/files/12505279/download?download_frd=1) . 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
(https://myuni.adelaide.edu.au/courses/85255/files/12505278/download?wrap=1)
(https://myuni.adelaide.edu.au/courses/85255/files/12505278/download?download_frd=1) . 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
(https://myuni.adelaide.edu.au/courses/85255/files/12505278/download?wrap=1)
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 Vector (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. We cover poison reverse in the Lectures, but Split Horizon is
simpler but similar in its goal. We 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 different 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 "DISTANCEVECTOR"
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 "UPDATE".
Your algorithm should run when the keyword "UPDATE" 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 "UPDATE" section. This section ends with the keyword
"END".
If there is input in the "UPDATE" 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 "UPDATE" section, the program exits normally when the keyword
"END" is inputted.
Expected Output Format
As 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 packets will 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:
X Distance Table at t=0
Y Z
Y 2 INF
Z INF 8
where
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
2. The routing table:
X Routing Table:
Y,Y,2
Z,Y,5
where
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 (https://myuni.adelaide.edu.au/courses/85255/files/12879690/download)
(https://myuni.adelaide.edu.au/courses/85255/files/12879690/download?download_frd=1) ).
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
Z Distance Table at t=2
X Y
X 8 5
Y 10 3
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
Y Distance Table at t=3
X Z
X 2 INF
Z 7 INF
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
Recommended Approach
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 diff'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: https://versioncontrol.adelaide.edu.au/svn/aXXXXXXX/yyyy/s1/cna/routing )
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)
DistanceVector correctly calculates the routing table for sample configuration: 30 marks
DistanceVector 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, DistanceVector and SplitHorizon, correctly calculate tables for arbitrary unseen
networks: (120 marks)
All marks above are from passing Web Submission tests. No additional marks are given after a
manual review.
However, your marks are scaled and reviewed based on the following:
1. 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/insufficient/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 Web 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:
1. All submissions before the deadline will be run against an acceptance testing script.
This script will compile your programs, and run your DistanceVector code for the sample config.
Use this as a sanity check to ensure your code compiles and runs on the WebSubmission
system and works as expected.
Be sure to add a logbook entry for each submission you make here.
2. 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 DistanceVector 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.
3. 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
4. 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.