Assignment3 ​ ​CP 372: Computer Networks - Winter 2020



Assignment 3:
Due Date: March 27th, 11:59 p.m.
Individual assignment
No Group work or group submission

Objectives​:
● Implementing a Link State routing algorithm for an autonomous system in python

Description
In this assignment you will implement a core functionality of the Link State routing algorithm for
an autonomous system. The input to the algorithm is a weighted directed graph with ​n​ vertices
(​labeled with 1, 2, 3,..., n​) that represents topology of a particular autonomous system. Each
vertice represents a router or a gateway router in the network. The gateway routers are
specified in the input as well. The output should print the forwarding table for each router other
than the gateway routers. Each entry in a forwarding table shows the next hop node along the
shortest path route from that node (source) to a gateway router (destination).

Input

The first line in the input represents the number of vertices, n. It is followed by
n lines representing the adjacency matrix of the graph with weights. Finally, there is one more
line representing a list of ​gateway routers​ ​x ​
1 ​, ..., x ​k ​, where each ​x ​i ​ ​is a distinct number
from the set ​{1,2,....,n} ​. Example input:

​6
0 1 10 -1 -1 2
10 0 1 -1 -1 -1
1 10 0 -1 -1 -1
-1 -1 2 0 1 10
-1 -1 -1 10 0 1
-1 -1 -1 1 10 0
2 5

The above input represents the following graph with vertices 2 and 5 being gateway routers.
Assignment3 ​ ​CP 372: Computer Networks - Winter 2020





Output
The output consists of ​n-k ​ forwarding tables (the forwarding tables for routers but not the
gateway routers). The output for the example input above should consist of 4 forwarding tables
– each containing 2 entries that correspond to least-cost path to gateway routers 2 and 5, as
below:


Forwarding Table for 1
To Cost Next Hop
2 1 2
5 4 6

Forwarding Table for 3
To Cost Next Hop
2 2 1
5 5 1

Assignment3 ​ ​CP 372: Computer Networks - Winter 2020


Forwarding Table for 4
To Cost Next Hop
2 4 3
5 1 5

Forwarding Table for 6
To Cost Next Hop
2 5 4
5 2 4

Note
● Implement Dijkstra algorithm that takes a graph and one source vertex, determines
least-cost path to all other vertices from the source and forms the forwarding table at the
source. Call this algorithm ​n-k​ times to produce desired results.
● do not assume that every vertex is reachable from any other vertex (imagine graph with
2 connected components for example); if a particular destination is not reachable from
the source print -1 as the “Cost” and -1 as the “Next Hop” destination
● you can assume correct input (no exceptions handling)
● Dijkstra algorithm allows one to compute not only single source shortest path weights,
but also predecessor for every node along the shortest path from the source, which is
useful when constructing forwarding table at the source
Bonus
Implement alternative forwarding: if there is an alternative path of the same weight from
the source to a particular destination, it might be useful to find it too. The entry in the forwarding
table in this case might have two “next hop” elements (separated by comma with no space in
between) which is helpful for the alternative forwarding.

Submission Instructions:
● Submit one file named ​LinkState.py.txt
● Do NOT submit eclipse project!
● NOTE: Make sure to use python version 3.5 or higher. Your program will be tested
with python3.5.
● Make sure to put your names on top of each python program file
● You must not import any python module. You should implement it using the built-in
functionality in python.
● your implementation must read input data from the system input and print the
tables to the system output!!
Test cases will be run with input redirection as follows

Python LinkState < test1.txt

Where​ test1.txt ​contains a particular input.
Assignment3 ​ ​CP 372: Computer Networks - Winter 2020


● As autograding will be used for marking this assignment, to get the same output
as mine, use the following format for printing a forwarding table: Off course you
need to replace the values (such as 1, 2, 3, etc.) with variables, but follow the
same formatting​:

print("Forwarding Table for 1")
print("{:>10} {:>10} {:>10}".format("To", "Cost", "Next Hop"))
print("{:>10} {:>10} {:>10}".format("2", "1", "2"))
print("{:>10} {:>10} {:>10}".format("5", "4", "6"))
print()
print("Forwarding Table for 3")
print("{:>10} {:>10} {:>10}".format("To", "Cost", "Next Hop"))
print("{:>10} {:>10} {:>10}".format("2", "2", "1"))
print("{:>10} {:>10} {:>10}".format("5", "5", "1"))
print()