Due: March 28th, 2025 (Friday, Week 5) by 11:59 PM
COMP3221
Assignment 1: Routing Algorithms
Contents
1 Learning Objectives 2
2 Network Architecture 2
3 Program Structure and Implementation Requirements 2
3.1 Programming Language and Wrapper Script . . . . . . . . . . . . . . . . 2
3.2 Execution Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4 Core Functions and Threading 3
4.1 Listening Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
4.2 Sending Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.3 Routing Calculations Thread . . . . . . . . . . . . . . . . . . . . . . . . . 4
5 Dynamic Commands and Graph Operations 4
5.1 CHANGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5.2 FAIL and RECOVER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.3 QUERY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.4 QUERY PATH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.5 MERGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.6 SPLIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.7 RESET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.8 CYCLE DETECT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.9 BATCH UPDATE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Submission Requirements 8
6.1 Files to be Submitted . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 Test Cases and Marking . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1
COMP3221 Routing Algorithms
1 Learning Objectives
In this assignment, you are required to design and implement an advanced routing
protocol that:
1. Computes least-cost paths using algorithms such as Dijkstra’s algorithm.
2. Handles dynamic changes in network topology.
3. Processes a variety of dynamic commands that modify the network state.
4. Performs advanced graph operations including detecting disjoint subgraphs, merg-
ing and splitting components, cycle detection, and batch processing of commands.
5. Implements rigorous error handling for malformed inputs.
2 Network Architecture
The network is modeled as an undirected weighted graph
G = (V,E)
where each node v ∈ V is identified by a unique identifier (e.g. A, B, C, . . . ), and each
edge (u, v) ∈ E has a non-negative cost w(u, v) ∈ R≥0. Each node only knows about its
immediate neighbours.
3 Program Structure and Implementation Requirements
3.1 Programming Language and Wrapper Script
You may implement your solution in any programming language of your choice. How-
ever, your submission must include a wrapper script named Routing.sh that serves
as the single entry point. For example, if you choose Python, your wrapper script might
look as follows:
1 #!/bin/bash
2 python3 your_solution.py "$@"
You are not permitted to use any libraries outside the core libraries provided for your
programming language. For example, if you were to use Python, you may use libraries
such as socket, but not networkx. Using any disallowed libraries will result in an im-
mediate 0 for this assignment. If you are unsure if a specific library is allowed, please
ask on Ed.
Distributed Systems Page 2
COMP3221 Routing Algorithms
3.2 Execution Format
Your program must be executed using the following command:
1 /Routing.sh
where:
1. Node-ID is a unique identifier (e.g. A, B, C, ...).
2. Port-NO is the port on which the node listens (ports start at 6000 and increment
by one).
3. Node-Config-File is a file specifying the node’s immediate neighbours. The first
line contains an integer n (the number of neighbours), followed by n lines. Each
line contains three tokens: a neighbour’s Node-ID, the cost (a non-negative floating-
point number), and the neighbour’s listening port.
For example, a configuration file for Node F (named Fconfig.txt) might be:
1 4
2 A 2.3 6000
3 C 3.2 6002
4 E 2.8 6004
5 J 5.4 6009
4 Core Functions and Threading
Your program must use multi-threading and socket programming to handle the follow-
ing tasks concurrently:
4.1 Listening Thread
The Listening Thread continuously reads messages from STDIN. It must process:
• Update Packets: in the exact format:
1 UPDATE
↪→ ::,::,...
• Dynamic Commands: as described in Section 5.
Update packets must be forwarded to the Routing Calculations Thread, and dynamic
commands must trigger immediate actions.
Distributed Systems Page 3
COMP3221 Routing Algorithms
4.2 Sending Thread
Every 10 seconds, the Sending Thread must broadcast the current update packet via
STDOUT in the format:
1 UPDATE
↪→ ::,::,...
This output must exactly reflect the current configuration with no additional text.
4.3 Routing Calculations Thread
This thread is responsible for computing the least-cost paths:
• At startup (after a 60-second delay).
• Whenever a valid update packet or dynamic command is received.
Immediately output the complete routing table in the format:
1 I am Node
2 Least cost path from to : , link
↪→ cost:
3 Least cost path from to : , link
↪→ cost:
4 ...
Note on Path Printing: Paths are printed as a continuous string of node IDs with no
spaces. For example, if the least-cost path from A to D is A, B, C, D, then the output
should be:
1 Least cost path from A to D: ABCD, link cost:
5 Dynamic Commands and Graph Operations
Implement the following commands exactly as specified. Each command must produce
the output or confirmation message described below.
5.1 CHANGE
Format:
1 CHANGE
Update the cost of the edge to with the new cost . Im-
mediately broadcast the updated configuration and recalculate the routing table.
Example: If the command is
Distributed Systems Page 4
COMP3221 Routing Algorithms
1 CHANGE B 3.5
then all paths using the edge to B must now use cost 3.5.
5.2 FAIL and RECOVER
Format:
1 FAIL
2 RECOVER
If matches your node:
• On FAIL, stop broadcasting update packets and output:
1 Node is now DOWN.
• On RECOVER, resume broadcasting update packets and output:
1 Node is now UP.
If does not match your node, simply update your routing table accordingly.
Example: For the command
1 FAIL C
if your node is C, output “Node C is now DOWN.”
5.3 QUERY
Format:
1 QUERY
Output the least-cost path from your node to in the format:
1 Least cost path from to : , link
↪→ cost:
Example: If your node is A and the command is
1 QUERY D
a possible output is:
1 Least cost path from A to D: ABCD, link cost: 7.2
5.4 QUERY PATH
Format:
1 QUERY PATH
Distributed Systems Page 5
COMP3221 Routing Algorithms
Output the least-cost path from to (even if is
not your node) in the same format as QUERY.
Example: For the command
1 QUERY PATH B E
the output could be:
1 Least cost path from B to E: BCE, link cost: 5.0
5.5 MERGE
Format:
1 MERGE
Merge the subgraph containing into the subgraph containing .
After this command, the graph is updated so that all nodes formerly in the component of
are now part of the component of . In cases of overlapping
edges, select the edge with the lower cost. Important: The identity of
remains unchanged; is absorbed into it. After merging, output:
1 Graph merged successfully.
Then recalculate and output the updated routing table.
Example: For the command
1 MERGE A C
Node C is merged into node A; all edges incident to C become edges incident to A
(using the lower cost if duplicates exist).
5.6 SPLIT
Format:
1 SPLIT
Partition the current graph G = (V,E) using the following fixed rule:
1. Sort the set of nodes V in alphabetical order.
2. Let k = ⌊|V |/2⌋. Define V1 as the first k nodes and V2 = V \ V1.
3. Remove all edges connecting nodes in V1 with nodes in V2.
Each node outputs the routing table corresponding to the partition it belongs to. First,
output:
1 Graph partitioned successfully.
Distributed Systems Page 6
COMP3221 Routing Algorithms
Example: If V = {A,B,C,D,E} (in order A, B, C, D, E), then k = 2 and V1 = {A,B}
while V2 = {C,D,E}. Remove all edges between V1 and V2; each node outputs the
routing table for its partition.
5.7 RESET
Format:
1 RESET
Reset your node’s internal state and routing table to the configuration specified in the
Node-Config-File. Immediately broadcast a new update packet and output:
1 Node has been reset.
Then, output the routing table computed from the original configuration.
Example: For the command
1 RESET
if your node is A, output “Node A has been reset.” followed by the routing table based
on the original configuration.
5.8 CYCLE DETECT
Format:
1 CYCLE DETECT
Analyse the current graph G = (V,E) using a cycle detection algorithm (e.g. depth-first
search). If a cycle exists, output:
1 Cycle detected.
Otherwise, output:
1 No cycle found.
Example: For the command
1 CYCLE DETECT
output one of the two messages as appropriate.
5.9 BATCH UPDATE
Format:
1 BATCH UPDATE
Read the file , which contains one valid dynamic command per line (each
command must exactly adhere to one of the formats specified above). Process these
Distributed Systems Page 7
COMP3221 Routing Algorithms
commands sequentially. After processing, output:
1 Batch update complete.
Then, recalculate and output the updated routing table.
Example: For the command
1 BATCH UPDATE updates.txt
output “Batch update complete.” followed by the new routing table.
6 Submission Requirements
6.1 Files to be Submitted
You must submit the following files via Ed:
1. Source Code (in the programming language of your choice)
2. README (which must include details about your coding environment, package
versions and instructions for running your program. This will not be marked, and
is only for reference if there are issues when your program is run against the test
cases. However, if you do not submit this file, you forfeit the option to challenge
the failure of any test cases upon submission of the assignment.)
6.2 Test Cases and Marking
Test cases are divided into:
• Public Test Cases: Both the input and output of each case is visible.
• Hidden Test Cases: The input and output of these test cases is hidden, but you
can still see whether or not they pass.
• Private Test Cases: The input and output are hidden, and you will not be able to
see if you pass these test cases until after the deadline.
Each test case carries a specific weight, and your overall mark is determined by the
cumulative weighted score across all test cases. Your program will be tested only against
the criteria specified in this assignment.
Distributed Systems Page 8
COMP3221 Routing Algorithms
Academic Honesty and Plagiarism
By submitting your assignment via ED, you agree to abide by the University policies on
academic honesty. All work must be your original work. If any part of your submission
is not your own, you must immediately inform your tutor or lecturer. Refer to the policy
slides from Week 1 for further details. The School of Computer Science may share your
assignment with a plagiarism checking service.
From Semester 1 2025, you can use AI tools like Microsoft Copilot Chat for your assign-
ments, unless your unit coordinator has prohibited the class from using it. For exams
and tests, you will not be allowed to use AI unless your unit coordinator has expressly
permitted it. Different units and assessments will have different rules.
At the same time, it’s important to understand when use of AI is unethical, inappro-
priate, or breaches the University’s rules about academic integrity. Submitting assess-
ments that aren’t your original work – including work produced by AI – may constitute
a breach of academic integrity.
In assessable work, the unapproved use of automated writing tools or generative AI,
or failing to acknowledge them, is currently considered to be a breach of academic
integrity, and penalties may apply. If you’re unsure about whether you can use AI, or
how you can use them, it’s important that you speak with your unit coordinator.
For general learning purposes, as opposed to assessments, you are permitted to use
generative AI tools, as long as you follow all University policies including the Academic
Integrity Policy 2022, Acceptable Use of ICT Resources Policy 2019 and the Student
Charter 2020.
Distributed Systems Page 9
COMP3221 Routing Algorithms
Appendix A: I/O Requirements and Error Handling
Below are some errors your program may encounter and how they need to be handled.
Any errors beyond those listed here will not be tested; if in doubt, please ask on Ed.
General I/O Errors
Scenario Input / Condition Expected Output
Missing
Arguments
./Routing.sh F 6005 Error: Insufficient
↪→ arguments provided.
↪→ Usage: ./Routing.sh
↪→
↪→
Invalid Node-ID ./Routing.sh AB 6005
↪→ Fconfig.txt
Error: Invalid Node-ID.
Invalid Port
Number
./Routing.sh F xyz
↪→ Fconfig.txt
Error: Invalid Port
↪→ number. Must be an
↪→ integer.
Config File Not
Found
./Routing.sh F 6005
↪→ missing.txt
Error: Configuration
↪→ file missing.txt not
↪→ found.
Non-numeric
Neighbour
Count
(in config file,
first line: four)
Error: Invalid
↪→ configuration file
↪→ format. (First line
↪→ must be an integer.)
Malformed
Neighbour
Entry
(in config file:
A two 6000)
Error: Invalid
↪→ configuration file
↪→ format. (Each
↪→ neighbour entry must
↪→ have exactly three
↪→ tokens; cost must be
↪→ numeric.)
Extra Tokens in
Config File
(in config file:
A 2.3 6000 extra)
Error: Invalid
↪→ configuration file
↪→ format.
Malformed CLI
Command
e.g.
SET COST A B abc
Error: Invalid command
↪→ format. Expected
↪→ numeric cost value.
Distributed Systems Page 10
COMP3221 Routing Algorithms
Appendix B: Dynamic Command and Graph Operation
Error Handling
Command
Scenario
Input / Condition Expected Error Output
Malformed
Update Packet
Packet not starting
with UPDATE (e.g.
UPD8
↪→ A:2.3:6000)
Error: Invalid update
↪→ packet format.
Malformed
CHANGE
Command
CHANGE A two (not
exactly two tokens or
non-numeric cost)
Error: Invalid command
↪→ format. Expected
↪→ numeric cost value.
Malformed FAIL
Command
FAIL AB (invalid node
ID)
Error: Invalid command
↪→ format. Expected a
↪→ valid Node-ID.
Malformed
RECOVER
Command
RECOVER ab (invalid
node ID)
Error: Invalid command
↪→ format. Expected a
↪→ valid Node-ID.
Malformed
QUERY
Command
QUERY AB (destination
invalid)
Error: Invalid command
↪→ format. Expected a
↪→ valid Destination.
Malformed
QUERY PATH
Command
QUERY PATH A b (not
exactly three tokens
or invalid IDs)
Error: Invalid command
↪→ format. Expected two
↪→ valid identifiers for
↪→ Source and Destination.
Malformed
MERGE
Command
MERGE A b (invalid
node IDs)
Error: Invalid command
↪→ format. Expected two
↪→ valid identifiers for
↪→ MERGE.
Malformed
SPLIT
Command
SPLIT extra (extra
tokens)
Error: Invalid command
↪→ format. Expected
↪→ exactly: SPLIT.
Malformed
RESET
Command
RESET now (extra
tokens)
Error: Invalid command
↪→ format. Expected
↪→ exactly: RESET.
Malformed
CYCLE DETECT
Command
CYCLE DETECT extra
(extra tokens)
Error: Invalid command
↪→ format. Expected
↪→ exactly: CYCLE DETECT.
Malformed
BATCH UPDATE
Command
BATCH UPDATE (not
exactly two tokens or
missing filename)
Error: Invalid command
↪→ format. Expected:
↪→ BATCH UPDATE
↪→ .
Distributed Systems Page 11
COMP3221 Routing Algorithms
Extra Tokens in
Dynamic
Command
e.g.
CHANGE A 2.5 extra
Error: Invalid command
↪→ format. Expected
↪→ exactly two tokens
↪→ after CHANGE.
Missing Tokens
in Dynamic
Command
e.g. FAIL Error: Invalid command
↪→ format. Expected: FAIL
↪→ .
Note: All error messages must be written exactly as shown. If any such error is de-
tected, your program must exit immediately with a non-zero exit code.
The ↪→ character refers to places where a newline is shown in the specifications, but
not in the actual output.
Distributed Systems Page 12

学霸联盟