关于算法:COMP3221路由算法研究

Due: March 31st, 2023 (Friday, Week 6) by 11:59 PM
COMP3221
Assignment 1: Routing Algorithm
The goal of this assignment is to implement routing protocols for a network topology using
Socket and Multi-threading Programming in Python. Important: This is an individual project;
therefore, each student has to submit his/her own assignment.
1 Learning Objectives
In this assignment, you are required to implement routing protocols for a specified network
using Python. In particular, your task is to complete a program that helps each node exchange
routing information with its neighboring nodes, and then finding the least-cost path to all
nodes in the network. Furthermore, your program has to deal with link cost changes and
failures in the network. It should have at least three separate threads to do the necessary
tasks for each node such as listening (for receiving information from its neighbors), sending
(for sending information updates after every 10 seconds), and routing calculations (when
link-cost changes).
On completing this assignment you will gain sufficient expertise in the following skills:
Designing a routing protocol
Socket and Multithreaded programming using Python
Handling routing dynamics
2 Network Architecture and Simulation
You are required to generate a network topology including 10 nodes and at least 15 connec-
tions between nodes. Those connections and their link costs are generated randomly. Figure 1
is a sample network topology with 10 nodes and 15 connections (you are not allowed to reuse
this sample topology).
Since we do not have access to a real network, we will simulate the network on a single
machine and use it for implementation and testing. You can use different terminals (one
for each node in the net topology) to run different instances of your program on the same
machine (use “localhost”).
Figure 1: A sample network topology with 10 nodes and 15 connections.
3 Program structure
The program should be named as COMP3221_A1_Routing.py and accept the following
command line arguments:
1 python COMP3221_A1_Routing.py
For example:
1 python COMP3221_A1_Routing.py F 6005 Fconfig.txt
Node-ID: the ID of a node in the net topology. In this assignment, Node-ID is indexed
following the English alphabet, for example, A, B, C, D, etc.
Port-NO: the port number of a node listening to the information update packets. The
port number is indexed using integers starting from 6000 and is increased by one for
each node. For example, the net topology in Figs. 1 has 10 nodes including: A, B, C, D,
E, F, G, H, I, and J. The port number of each node is 6000, 6001, 6002, 6003, 6004,
6005, 6006, 6007, 6008, and 6009, respectively.
Node-Config-File: Fconfig.txt, for example, is the configuration file for Node F that
has the following details:
1 4
2 A 2.3 6000
3 C 3.2 6002
4 E 2.8 6004
5 J 5.4 6009
The first line of this file indicates the number of neighbors for Node F (it is not the total
number of nodes in the network). The next four lines are to determine the connection
of Node F to its neighbors. Those lines start with the neighbor ID, followed by the cost
Distributed Systems Page 2
COMP3221 Routing Algorithm
to reach this neighbor from Node F, and finally the port number that this neighbor is
using for listening.
For example, the second line in the Fconfig.txt above indicates that the cost to neighbor
A is 2.3 (floating-point numbers) and Node A is using port number 6000 for receiving
information update packets. It is noted that all link costs are symmetric (the same in
both directions, e.g., the cost from F to A is the same as that from A to F). Moreover,
Node F must not have global knowledge (i.e. information about the entire network
topology).
Initially, each node creates an information update packet (containing the appropriate infor-
mation: its neighboring nodes and cost links between it and its neighbors) and sends this
packet to all direct neighbors. You are free to define the exact format of the information up-
date packets. Upon receiving these information update packets, each neighboring node will
incorporate the provided information for routing algorithms. Each node should periodically
broadcast the information update packet to its neighbors every 10 seconds.
On receiving information update packets from all other nodes, a node can build up a reach-
ability matrix. Given a view of the neighboring nodes and their reachability, a node should
run a routing algorithm (Bellman-Ford, Dijkstra, etc..) to compute the shortest paths to all
other nodes within the network. Each node should wait for 60 seconds since starting-up and
then execute the routing algorithm.
Once a node finishes running the routing algorithm, it will print out to the terminal the least
cost path to each destination node in the topology (excluding itself) along with the cost of
this path. The following is an example output for node F in some arbitrary network:
1 I am Node F
2 Least cost path from F to A: FA, link cost: 2.3
3 Least cost path from F to B: FAGB, link cost: 4.7
4 Least cost path from F to C: FC, link cost: 3.2
5 Least cost path from F to D: FCD, link cost: 4.3
6 Least cost path from F to E: FE, link cost:4.5
7 Least cost path from F to G: FAG, link cost: 4.5
8 Least cost path from F to H: FEH, link cost: 5
9 Least cost path from F to I: FCDI, link cost: 5.8
10 Least cost path from F to J: FJ, link cost: 5.4
Your program should execute forever (as a loop). In other words, each node should keep
broadcasting information value packets every 10 seconds and the routing algorithm should
be executed every time the link cost change occurs.
Please note that all routing algorithms must be implemented by yourself from scratch,
using libraries is not allowed.
4 Dealing with changes in link cost and failure
You must ensure that your program has the ability to deal with the changes in link costs
and failures. Whenever the link cost changes the network must be able to reconverge to
accommodate the costs.
Distributed Systems Page 3
COMP3221 Routing Algorithm
To simulate the changes in link cost and failures, you must provide a command-line interface
(CLI) for each node to give the ability to modify the link-cost to its neighbors. A simple
method would be using a separate thread to modify the configure files. Any modification on
the CLI will affect the configured files.
Once the cost of a link changes, the connected nodes must recalculate the cost of reaching
other nodes and must also provide an update to its neighbors, who will then notify their
neighbors and so on until the network converges.
Here is an example of the correct output for Node F before and after the failure of Node C is
given. You should check your implementation for correctness at all nodes with multiple node
failures.
Output with all nodes working:
1 I am Node F
2 Least cost path from F to A: FA, link cost: 2.3
3 Least cost path from F to B: FAGB, link cost: 4.7
4 Least cost path from F to C: FC, link cost: 3.2
5 Least cost path from F to D: FCD, link cost: 4.3
6 Least cost path from F to E: FE, link cost:4.5
7 Least cost path from F to G: FAG, link cost: 4.5
8 Least cost path from F to H: FEH, link cost: 5
9 Least cost path from F to I: FCDI, link cost: 5.8
10 Least cost path from F to J: FJ, link cost: 5.4
Output after Node C fails:
1 I am Node F
2 Least cost path from F to A: FA, link cost: 2.3
3 Least cost path from F to B: FAGB, link cost: 4.7
4 Least cost path from F to D: FAGBD, link cost: 5.4
5 Least cost path from F to E: FE, link cost: 4.5
6 Least cost path from F to G: FAG, link cost: 4.5
7 Least cost path from F to H: FEH, link cost: 5
8 Least cost path from F to I: FAGBDI, link cost: 6.9
9 Least cost path from F to J: FJ, link cost: 5.4
5 Submission and Report
You are required to submit the following files to Canvas separately.
? Code (zip file includes all implementation, and config files for all nodes)
SSID_COMP3221_Code.zip.
? Code Text (including all implementation in one file exported in a txt file for Plagiarism
checking)
SSID_COMP3221_Code.txt.
? Readme (Clearly state how to start the program, change link-cost, client failures, and
Distributed Systems Page 4
COMP3221 Routing Algorithm
running environment)
SSID_COMP3221_Readme.txt.
Report (pdf)
SSID_COMP3221_Report.pdf.
The size of your report MUST be under 2 pages. Your report should briefly document your net
topology, routing algorithm, techniques and methodology used for implementation and the
simulation results of each requirement. It should act a reference for your markers to quickly
figure out what you have and haven’t completed, how you did it, and it should mention
anything you think that is special about your system.
Please note that you must upload your submission BEFORE the deadline. The CANVAS would
continue accepting submissions after the due date; however, late submissions would carry
penalty per day with maximum of 5 days late submission allowed.
6 Academic Honesty / Plagiarism
By uploading your submission to CANVAS you implicitly agree to abide by the University
policies regarding academic honesty, and in particular that all the work is original and not
plagiarised from the work of others. If you believe that part of your submission is not your
work you must bring this to the attention of your tutor or lecturer immediately. See the policy
slides released in Week 1 for fusrther details.
In assessing a piece of submitted work, the School of Computer Science may reproduce it
entirely, may provide a copy to another member of faculty, and/or communicate a copy of
this assignment to a plagiarism checking service or in-house computer program. A copy of
the assignment may be maintained by the service or the School of Computer Science for the
purpose of future plagiarism checking.
7 Marking
This assignment is worth 15% of your final grade for this unit of study. The ratio of assign-
ment parts is divided as follows.
Code: 80%.
Report: 20%.
Please refer to the rubric in Canvas (Canvas -> Assignment 1 -> Rubric) for detailed marking
scheme. The report and the code are to be submitted in Canvas by the due date.
After Assignment 1 marks come out, please submit your inquiries about marking within
the 1st week. All inquiries after that will NOT be responded.
Distributed Systems Page 5