COMP3221代写、Python编程设计代写

日期：2023-03-19 12:25

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