Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP3221
Assignment 1: Routing Algorithm
The purpose of this assignment is to develop a routing protocol for a specified network topology
by utilizing Python’s Socket and Multi-threading programming. This project can be done in a
group of two students, with only one team member submitting the work on behalf of the group.
You need to register a group on the Canvas page: COMP3221→ People→ Group - A1.
1 Learning Objectives
Your assignment involves developing routing protocols within a predefined network using
Python. Specifically, you are tasked with creating a Python application that facilitates efficient
exchange of routing information between nodes and identifies the least-cost paths within the
network. Moreover, the program must be capable of managing network challenges, including
changes in link costs and node failures.
Completing this assignment will equip you with comprehensive skills in:
• Routing Protocol Design and Implementation: Develop efficient routing protocols to
find least-cost paths and optimize network data flow.
• Socket and Multi-threading Programming in Python: Enhance your programming
skills with networking and concurrent programming for improved protocol efficiency
and responsiveness.
• Dynamic Routing Management: Learn to adapt to network changes, managing link
cost variations and failures for robust communication.
2 Assignment Guidelines
2.1 Network Architecture and Simulation
2.1.1 Creating Your Network Topology
Your task begins with constructing a network topology consisting of 10 nodes interconnected
by at least 15 randomly generated links. Figs. 1 provides an example network topology
with the required number of nodes and connections. You must design a unique topology and
not replicate the provided sample.
1
COMP3221 Routing Algorithm
Figure 1: A sample network topology with 10 nodes and 15 connections.
2.1.2 Simulation Environment
Due to the unavailability of a physical network for deployment, you will simulate this network
on a single computer for both implementation and testing purposes. This simulation involves
running separate instances of your program for each node within the network topology, utiliz-
ing "localhost" for communication. Each node will correspond to a different terminal window
on your machine, allowing for a comprehensive test environment.
2.2 Program Structure
Your program should be named COMP3221_A1_Routing.py and should accept command-
line arguments as follows:
1 python COMP3221_A1_Routing.py
Command-Line Arguments:
• Node-ID: A unique identifier assigned to each node in the network topology. In this
assignment, Node-IDs are indexed using letters of the English alphabet, e.g., A, B, C, ...
• Port-NO: Each node in the network listens for updates from its neighbors on a specific
port number. In this assignment, Port-No is an integer, starting at 6000 for the first
node and incrementing by one for each subsequent node. For instance, the topology in
Figs. 1 has 10 nodes: A, B, C, D, E, F, G, H, I, and J. Then, their port numbers are 6000,
6001, 6002, 6003, 6004, 6005, 6006, 6007, 6008, and 6009, respectively.
• Node-Config-File: This is the path to a configuration file that contains detailed infor-
mation about a node’s direct neighbors within the network. This file includes the cost to
reach each neighbor and the port number each neighbor listens on. The file begins with
Distributed Systems Page 2
COMP3221 Routing Algorithm
a number indicating how many neighbors the node has. Following this, each line pro-
vides details for one neighbor: the neighbor’s Node-ID, the cost to reach this neighbor
(a floating-point number), and the neighbor’s listening port number.
For Node F, you might have a configuration file named Fconfig.txt with content like:
1 4
2 A 2.3 6000
3 C 3.2 6002
4 E 2.8 6004
5 J 5.4 6009
where 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. The second line indicates that the cost to
neighbor A is 2.3 (floating-point numbers), and Node A uses 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).
Usage example:
1 python COMP3221_A1_Routing.py F 6005 Fconfig.txt
This tells the program that it’s operating as Node F, should listen on port 6005 for updates,
and can find details about its neighbors in Fconfig.txt.
2.3 Assignment Tasks
Your node program should incorporate multi-threading and socket programming to perform
multiple tasks concurrently, which is essential for the efficient operation of network protocols.
For the assignment, your node program needs to manage at least three critical functions
simultaneously using separate threads:
1. Listening Thread: This thread is dedicated to listening for incoming routing informa-
tion from neighboring nodes. It continuously monitors the designated port for mes-
sages and processes any received data. The information typically includes updates from
neighbors about their link costs and network topology changes.
2. Sending Thread: This thread periodically sends out the node’s current routing infor-
mation to its neighbors. At regular intervals, it broadcasts the latest routing table or
link-cost updates to all neighboring nodes. This ensures that all nodes maintain an
up-to-date view of the network topology.
3. Routing Calculations Thread: This thread triggers the execution of routing algorithm
calculations upon detecting changes in link costs or receiving new routing information.
Whenever there’s a change in the network topology (e.g., link cost update, node ad-
dition/removal), this thread recalculates the least-cost paths to all other nodes in the
network using the node’s routing algorithm.
Distributed Systems Page 3
COMP3221 Routing Algorithm
2.3.1 Finding the Least-Cost Paths
At the start of the process, each node in the network generates an update packet, which
includes necessary information such as its neighboring nodes and the costs associated with
reaching them. You are free to define the structure of these packets. Then, nodes should period-
ically broadcast these update packets to their neighbors every 10 seconds. This ensures that
all nodes in the network continually share and receive up-to-date information about their
connections and any changes in link costs.
After receiving update packets from the entire network, each node constructs a routing table,
also known as a reachability matrix. This matrix provides a detailed network representation
from the node’s perspective, indicating which nodes are directly accessible and the associated
costs for reaching them. With this information at hand, the node employs a routing algorithm
(e.g., Bellman-Ford, Dijkstra, etc.) to compute the shortest paths to all other nodes within
the network. To ensure that every node has gathered sufficient information for an accurate
network overview, each node should wait for 60 seconds after startup, and then execute the
routing algorithm.
Upon completing the routing algorithm, each node outputs the least cost path to every other
node in the network, excluding itself, to the terminal. This output includes both the path
taken and the cost associated with that path. For illustration, consider the output for Node F
in the example network shown in Figs. 1:
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 node program is designed to run indefinitely in a continuous loop. This means that each
node is responsible for regularly broadcasting its information value packets to all neighbors
every 10 seconds, ensuring the network’s routing information remains up-to-date. Addition-
ally, the routing algorithm within each node should be re-executed whenever the link costs
change, allowing the network to adapt dynamically to changes in its topology.
Note that you can choose any routing algorithm covered in the lectures for this assign-
ment. However, all algorithms must be implemented from scratch. You are not allowed
to use pre-existing libraries that provide routing protocol functionalities.
2.3.2 Dealing with Link Cost Changes and Node Failures
Your program must be capable of adapting to changes in link costs and network failures. This
adaptability is crucial for ensuring the network can reconverge and update its routing paths
to reflect the new costs or topology changes.
Distributed Systems Page 4
COMP3221 Routing Algorithm
Simulate Link Cost Changes: You must provide a command-line interface (CLI) that al-
lows users to modify the costs associated with links connecting a node to its neighbors. For
instance, this could be achieved by implementing a separate thread within each node’s pro-
gram tasked with monitoring and applying changes to the configuration files based on the
commands entered into the CLI. Any adjustments made via the CLI should also be updated
to the node’s configuration files, reflecting the new link costs in the network’s topology.
Simulate Node Failures: You can also use the CLI to enable users to disable or enable nodes
within the network. For example, this could be managed by adding commands to the CLI
that mark a node as down or up. When a node is marked as down, it simulates a failure by
stopping the broadcast of update packets and ignoring received packets, effectively removing
it from the network topology. Marking it as up reverses this process, reconnecting the node
into the network.
Adapting to Changes and Failures: Upon detecting changes in link costs or node failures,
the available nodes in the network must recalculate the least cost paths to reach other nodes,
then broadcast the updated routing information to their neighbors. This triggers a cascade
of updates across the network, with each node adjusting its routing table based on the re-
ceived information. This iterative process continues until the network achieves convergence,
reflecting a consistent understanding of the network’s current state among all nodes.
To validate the robustness and correctness of your implementation in handling link cost
changes and node failures, it’s essential to examine the output of your routing algorithm
before and after simulating such failures. Below is an illustrative example focusing on Node
F in Fig. 1, demonstrating the expected output changes due to the failure of Node C.