1 | ANU College of Engineering and Computer Science October 2020
PASSiNg thE MESSAgE
Assignment for all students of
Systems, Networks and Concurrency
This is the second, carefully marked assignment of the
course. Extra care is expected on all levels. A good solu-
tion will have a surprisingly small amount of code. Make
sure that this code is excellently written – in whichever
language you prefer.
Overview
Routers are basic ingredients of most distributed systems. they commonly have no a-priori
knowledge about the wider network topology in which they are embedded. Nevertheless they
are expected to send messages via a network port which will move those messages closer to
their destinations. Many constraints can be taken into consideration for a practical router, yet
this assignment focuses on sending messages on the shortest paths to their destinations.
What an individual router needs to provide to clients:
• Accept a message from a client (in an predefined format). the message also contains a des-
tination id. the expectation is that this message will eventually end at the router of this id.
• Store and provide received messages for a client to pick up (in an predefined format).
What is accessible to an individual router:
• the local network ports which are connected to other routers.
• the Id’s of all neighbouring routers. in the physical world this would need to be established
by means of initial communications first, yet we assume here that this already happened.
• the total number of routers as well as the fact that they are numbered consecutively from 1
to the total number of routers. in a real router you would use hash tables for the router id’s.
What the routers need to agree upon before they are deployed:
• One or multiple message formats which are exchanged between routers (in addi-
tion to the already given formats used to send to and received from clients).
• the semantics for those messages.
What a router can do:
• Send messages in any of the globally defined inter-router formats over
any of its ports to any of its directly connected neighbours.
• Receive messages on any local port and process their contents.
What a router cannot do is to sneak behind the scenes and extract the global topology of the
network from a central place in a direct way. Routers can still organize themselves in whichever
form they see fit. thus a central place could for instance be one router which by election, or
other means nominated itself as a central place. Communication with this router would need to
go through the normal network channels though – no secret direct wires to a central coordina-
tor. Yet there does not need to be any central instance at all – distributed solutions are usually
also more robust.
2 | ANU College of Engineering and Computer Science October 2020
How to implement a router
You can implement this router in any language or environment, as long as it roughly follows
the frame described above. One essential feature for your implementation needs to be kept
in mind: the connections between routers are “wires” – not software buffers. A close software
equivalent to a wire is synchronous message passing. Any buffer which might be needed,
will need to be implemented as part of the router. You can emulate synchronous (or otherwise
“immediate”) communication by means of multiple asynchronous messages or by means of
asynchronous messages combined with signals/interrupts.
there is a framework available to you in Ada which generates a number of classical network
topologies and places router tasks inside a chosen topology. it also runs a simple evaluation
which sends messages from each router to every other one and takes notes about the number
of hops the message passed through.
if you decide to write it in another language than Ada, then you will need to program this simple
infrastructure as well (details below). Simply contact us which your specific plans and we will
see what is achievable with reasonable effort in your chosen environment.
The Ada framework
the program test_routers can be fully controlled via command line parameters:
Available network topologies are denoted by name (out of the list above) together with the
parameters which are required for a given topology. thus you can test your routers in a 4-d
hypercube by: ./test_routers -t Hypercube -d 4
You can allow your routers some time to get themselves organized and specify for instance:
./test_routers -t Hypercube -d 4 -w 0.2
for a 200 ms preparation phase during which no client messages will be sent through the
network. After this settling time for the routers, the evaluation phase starts and a messages
will be sent via every router to every other router. those messages will be sent in groups, i.e. all
messages originating from a specific rout-
er will be sent in bulk (“One to all”). this
will be changed via the command line
parameter -m All_To_One to a schema,
where all messages which are destined to
a specific router will be send in bulk. the
default time-out for any network activity is
100 ms (but can also be adjusted via the
command line interface). if a router does
not respond after this time-out then the
communication test is noted as unsuc-
cessful. From the testing environment
it cannot be distinguished whether the
message was not delivered or whether the
destination router is not responsive, as
uwe@Paddington-i9 Executables % ./test_routers
accepted options:
[-t {Topology : String }] -> CUBE_CONNECTED_CYCLES
by Size : Line, Ring, Star, Fully_Connected
by Degree, Depths : Tree
by Dimension, Size : Mesh, Torus
by Dimension : Hypercube, Cube_Connected_Cycles,
Butterfly, Wrap_Around_Butterfly
[-s {Size : Positive }] -> 20
[-g {Degree : Positive }] -> 3
[-p {Depths : Positive }] -> 4
[-d {Dimension : Positive }] -> 3
[-c {Print connections : Boolean }] -> TRUE
[-i {Print distances : Boolean }] -> TRUE
[-w {Routers settle time : Seconds }] -> 0.10
[-o {Comms timeout : Seconds }] -> 0.10
[-m {Test mode : String }] -> ONE_TO_ALL
Available modes: One_to_All, All_to_One
[-x {Dropouts : Natural }] -> 0
[-r {Repeats : Positive }] -> 100
———————– Instantiating router tasks —————————–
=> Routers up and running
——————————– Waiting —————————————
Time for routers to establish their strategies : 0.10 second(s)
—————————— Measurements ————————————
Number of runs : 100
Minimal hops : 1
Maximal hops : 6
Average hops : 3.22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
+————————————————————————+
1 | . 2 2 3 2 3 4 3 4 3 3 2 4 4 3 5 4 4 6 5 5|
2 | . 2 3 3 2 2 3 4 4 3 3 2 4 5 4 4 4 3 5 6 5|
3 | . 2 3 3 3 2 3 4 4 5 2 2 3 4 4 4 3 4 5 5 6|
4 | 2 2 . 4 3 4 3 2 3 4 4 3 3 3 2 6 5 5 5 4 4|
5 | 2 3 3 . 3 4 4 2 2 4 5 4 3 3 2 5 6 5 4 4 3|
6 | 2 3 3 . 4 4 5 3 2 3 3 4 4 2 2 5 5 6 4 3 4|
7 | 3 2 3 4 3 4 . 2 2 5 4 4 6 5 5 3 3 2 4 4 3|
8 | 2 2 3 4 4 . 2 3 3 4 4 3 5 6 5 3 3 2 4 5 4|
9 | 3 2 3 4 4 5 . 2 3 3 4 3 4 5 5 6 2 2 3 4 4|
10 | 4 3 4 3 2 3 2 2 . 6 5 5 5 4 4 4 4 3 3 3 2|
11 | 3 4 4 2 2 2 3 3 . 5 6 5 4 4 3 4 5 4 3 3 2|
12 | 4 4 5 3 2 3 2 3 3 . 5 5 6 4 3 4 3 4 4 2 2 |
13 | 3 3 2 4 4 3 5 4 4 6 5 5 . 2 2 3 2 3 4 3 4|
14 | 3 3 2 4 5 4 4 4 3 5 6 5 . 2 3 3 2 2 3 4 4|
15 | 2 2 3 4 4 4 3 4 5 5 6 . 2 3 3 3 2 3 4 4 5|
16 | 4 4 3 3 3 2 6 5 5 5 4 4 2 2 . 4 3 4 3 2 3|
17 | 4 5 4 3 3 2 5 6 5 4 4 3 2 3 3 . 3 4 4 2 2|
18 | 3 4 4 2 2 5 5 6 4 3 4 2 3 3 . 4 4 5 3 2 3|
19 | 5 4 4 6 5 5 3 3 2 4 4 3 3 2 3 4 3 4 . 2 2|
20 | 4 4 3 5 6 5 3 3 2 4 5 4 2 2 3 4 4 . 2 3 3|
21 | 4 3 4 5 5 6 2 2 3 4 4 3 2 3 4 4 5 . 2 3 3|
22 | 6 5 5 5 4 4 4 4 3 3 3 2 4 3 4 3 2 3 2 2 . |
23 | 5 6 5 4 4 3 4 5 4 3 3 2 3 4 4 2 2 2 3 3 . |
24 | 5 5 6 4 3 4 3 4 4 2 2 4 4 5 3 2 3 2 3 3 .|
+————————————————————————+
————— Information about the selected network topology —————-
Topology : CUBE_CONNECTED_CYCLES
Dimension : 3
Number of nodes in topology : 24
Constant connection degree : 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
+————————————————————————+
1 | . <-><-><-> |
2 |<-> . <-> <-> |
3 |<-><-> . <-> |
4 |<-> . <-><-> |
5 | <-> . <-> <-> |
6 | <-><-> . <-> |
7 | . <-><-><-> |
Figure 1: Command line options
uwe@Paddington-i9 Executables % ./test_routers
accepted options:
[-t {Topology : String }] -> CUBE_CONNECTED_CYCLES
by Size : Line, Ring, Star, Fully_Connected
by Degree, Depths : Tree
by Dimension, Size : Mesh, Torus
by Dimension : Hypercube, Cube_Connected_Cycles,
Butterfly, Wrap_Around_Butterfly
[-s {Size : Positive }] -> 20
[-g {Degree : Positive }] -> 3
[-p {Depths : Positive }] -> 4
[-d {Dimension : Positive }] -> 3
[-c {Print connections : Boolean }] -> TRUE
[-i {Print distances : Boolean }] -> TRUE
[-w {Routers settle time : Seconds }] -> 0.10
[-o {Comms timeout : Seconds }] -> 0.10
[-m {Test mode : String }] -> ONE_TO_ALL
Available modes: One_to_All, All_to_One
[-x {Dropouts : Natural }] -> 0
[-r {Repeats : Positive }] -> 100
———————– Instantiating router tasks —————————–
=> Routers up and running
——————————– Waiting —————————————
Time for routers to establish their strategies : 0.10 second(s)
—————————— Measurements ————————————
Number of runs : 100
Minimal hops : 1
Maximal hops : 6
Average hops : 3.22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
+————————————————————————+
1 | . 2 2 3 2 3 4 3 4 3 3 2 4 4 3 5 4 4 6 5 5|
2 | . 2 3 3 2 2 3 4 4 3 3 2 4 5 4 4 4 3 5 6 5|
3 | . 2 3 3 3 2 3 4 4 5 2 2 3 4 4 4 3 4 5 5 6|
4 | 2 2 . 4 3 4 3 2 3 4 4 3 3 3 2 6 5 5 5 4 4|
5 | 2 3 3 . 3 4 4 2 2 4 5 4 3 3 2 5 6 5 4 4 3|
6 | 2 3 3 . 4 4 5 3 2 3 3 4 4 2 2 5 5 6 4 3 4|
7 | 3 2 3 4 3 4 . 2 2 5 4 4 6 5 5 3 3 2 4 4 3|
8 | 2 2 3 4 4 . 2 3 3 4 4 3 5 6 5 3 3 2 4 5 4|
9 | 3 2 3 4 4 5 . 2 3 3 4 3 4 5 5 6 2 2 3 4 4|
10 | 4 3 4 3 2 3 2 2 . 6 5 5 5 4 4 4 4 3 3 3 2|
11 | 3 4 4 2 2 2 3 3 . 5 6 5 4 4 3 4 5 4 3 3 2|
12 | 4 4 5 3 2 3 2 3 3 . 5 5 6 4 3 4 3 4 4 2 2 |
13 | 3 3 2 4 4 3 5 4 4 6 5 5 . 2 2 3 2 3 4 3 4|
14 | 3 3 2 4 5 4 4 4 3 5 6 5 . 2 3 3 2 2 3 4 4|
15 | 2 2 3 4 4 4 3 4 5 5 6 . 2 3 3 3 2 3 4 4 5|
16 | 4 4 3 3 3 2 6 5 5 5 4 4 2 2 . 4 3 4 3 2 3|
17 | 4 5 4 3 3 2 5 6 5 4 4 3 2 3 3 . 3 4 4 2 2|
18 | 3 4 4 2 2 5 5 6 4 3 4 2 3 3 . 4 4 5 3 2 3|
19 | 5 4 4 6 5 5 3 3 2 4 4 3 3 2 3 4 3 4 . 2 2|
20 | 4 4 3 5 6 5 3 3 2 4 5 4 2 2 3 4 4 . 2 3 3|
21 | 4 3 4 5 5 6 2 2 3 4 4 3 2 3 4 4 5 . 2 3 3|
22 | 6 5 5 5 4 4 4 4 3 3 3 2 4 3 4 3 2 3 2 2 . |
23 | 5 6 5 4 4 3 4 5 4 3 3 2 3 4 4 2 2 2 3 3 . |
24 | 5 5 6 4 3 4 3 4 4 2 2 4 4 5 3 2 3 2 3 3 .|
+————————————————————————+
————— Information about the selected network topology —————-
Topology : CUBE_CONNECTED_CYCLES
Dimension : 3
Number of nodes in topology : 24
Constant connection degree : 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
+————————————————————————+
1 | . <-><-><-> |
2 |<-> . <-> <-> |
3 |<-><-> . <-> |
4 |<-> . <-><-> |
5 | <-> . <-> <-> |
6 | <-><-> . <-> |
7 | . <-><-><-> |
Figure 2: Measurements
3 | ANU College of Engineering and Computer Science October 2020
the internal states of the routers are not accessed. Next, the results of the communication tests
are displayed (Figure 2). in the provided framework the routers do not exist yet, thus this sec-
tion will not appear up on your screen until you provide a router implementation.
the minimum number of hops for a message should be ‘1’, and the largest measured number
of hops should represents the diameter1 of
the chosen topology. the average number of
hops is characteristic for a specific topology.
By using the command line option -i True
you will also see the full table of individual
measurements between all nodes. As we only
consider bidirectional connections, the
number of hops should be identical in both
directions between any two routers. if the
measurements are different, warnings will be
displayed. 1-hop connections are left blank to
make the matrix somewhat more readable.
the last section (Figure 3) which will appear
on screen gives general parameters of the
current topology, like the minimum and maxi-
mal connection degree and the total number
of nodes. You can also print the connec-
tions inside the topology as a matrix – which
should be the mirror image of the empty
spots in the measurement matrix. Double arrows denote bidirectional connections.
the individual routers need to respond to the following four pre-defined entries:
task type Router_Task (Task_Id : Router_Range := Draw_Id) is
entry Configure (Links : Ids_To_Links);
entry Shutdown;
entry Send_Message (Message : Messages_Client);
entry Receive_Message (Message : out Messages_Mailbox);
Configure is only called once right after the task has been created. the existing links to neigh-
bouring routers are delivered here in the form of an array over the router id’s in which connect-
ed routers will appear while all other entries are null.
type Ids_To_Links is array (Router_Range) of Router_Task_P;
type Router_Task_P is access all Router_Task;
two message formats are already defined, yet you need to add at least one more message
format and entry which you will be using for communications between routers.
type Messages_Client is record
Destination : Router_Range;
The_Message : The_Core_Message;
end record;
type Messages_Mailbox is record
Sender : Router_Range;
The_Message : The_Core_Message;
Hop_Counter : Natural := 0;
end record;
the purpose of Shutdown (which will be called upon once after all tests have been performed) is
to allow for a graceful way to stop operations. if your router accepts this call, it is assumed that
[1] The diameter of a given topology is the greatest distance between any two nodes.
Figure 3: Topology
Last login: Wed Sep 21 10:11:02 on ttys005
localhost:~ uwe$ cd /Users/uwe/Documents/Sources/CDS-Course/Assignments/Assignment\ 2\ 2011/Routers/Executables
localhost:Executables uwe$ ./test_routers -c TRUE -i TRUE -t Wrap_Around_Butterfly -d 3 -s 4 -g 3 -p 3 -w 0.1
accepted options:
[-t {Topology : String }] -> WRAP_AROUND_BUTTERFLY
by Size : Line, Ring, Star, Fully_Connected
by Degree, Depths : Tree
by Dimension, Size : Mesh, Torus
by Dimension : Hypercube, Cube_Connected_Cycles,
Butterfly, Wrap_Around_Butterfly
[-s {Size : Positive }] -> 4
[-g {Degree : Positive }] -> 3
[-p {Depths : Positive }] -> 3
[-d {Dimension : Positive }] -> 3
[-c {Print connections : Boolean }] -> TRUE
[-i {Print distances : Boolean }] -> TRUE
[-w {Routers settle time : Seconds }] -> 0.10
[-o {Comms timeout : Seconds }] -> 0.10
[-m {Test mode : String }] -> ONE_TO_ALL
Available modes: One_to_All, All_to_One
———————– Instantiating router tasks —————————–
=> Routers up and running
——————————– Waiting —————————————
Time for routers to establish their strategies : 0.10 second(s)
—————————— Measurements ————————————
Minimal hops : 1
Maximal hops : 4
Average hops : 2.39
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
+————————————————————————+
1 | . 2 2 3 2 2 3 3 2 2 2 3 3 3 3 2 3 3 4 4|
2 | . 2 2 2 2 3 3 3 2 3 2 3 3 2 2 3 3 4 3 4|
3 | . 2 2 3 2 2 2 3 3 2 2 3 2 3 3 3 3 4 4 3|
4 | 2 2 . 3 3 2 3 2 2 3 3 3 2 2 3 4 4 3 2 3|
5 | 2 2 . 3 3 3 2 2 3 3 2 2 3 2 4 3 4 2 3 3|
6 | 2 2 3 . 2 3 3 2 2 3 2 3 2 2 4 4 3 3 3 3|
7 | 3 2 2 3 3 2 . 2 2 3 2 3 3 4 4 2 2 3 3 3|
8 | 2 2 3 3 3 . 2 2 2 3 3 4 3 4 2 3 2 3 3 2|
9 | 2 2 2 3 3 . 2 2 3 3 3 3 4 4 3 2 2 3 2 3|
10 | 3 3 2 3 2 2 2 2 . 3 4 4 3 2 3 3 3 3 2 2 |
11 | 3 3 3 2 2 2 2 . 4 3 4 2 3 3 3 3 2 2 3 2|
12 | 2 3 3 2 2 2 2 3 . 4 4 3 3 3 3 3 2 3 2 2|
13 | 2 2 3 3 3 3 2 3 3 4 4 . 2 2 3 2 2 3 3 2|
14 | 2 3 2 3 3 2 2 3 3 4 3 4 . 2 2 2 2 3 3 3|
15 | 2 2 3 2 3 3 3 3 4 4 3 . 2 2 3 2 2 2 3 3|
16 | 3 3 3 2 2 3 4 4 3 2 3 2 2 . 3 3 2 3 2 2|
17 | 3 3 2 2 3 2 4 3 4 2 3 3 2 2 . 3 3 3 2 2 |
18 | 3 2 3 2 2 4 4 3 3 3 3 2 2 3 . 2 3 3 2 2|
19 | 3 2 3 3 4 4 2 2 3 3 3 3 2 2 3 3 2 . 2 2|
20 | 2 3 3 4 3 4 2 3 2 3 3 2 2 2 3 3 3 . 2 2|
21 | 3 3 3 4 4 3 2 2 3 2 3 2 2 2 3 3 . 2 2 3|
22 | 3 4 4 3 2 3 3 3 3 2 2 3 3 2 3 2 2 2 2 . |
23 | 4 3 4 2 3 3 3 3 2 2 3 2 3 3 3 2 2 2 2 . |
24 | 4 4 3 3 3 3 3 2 3 2 2 2 3 3 2 2 2 2 3 .|
+————————————————————————+
————— Information about the selected network topology —————-
Topology : WRAP_AROUND_BUTTERFLY
Dimension : 3
Number of nodes in topology : 24
Constant connection degree : 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
+————————————————————————+
1 | . <-><-> <-> <-> |
2 |<-> . <-><-> <-> |
3 |<-><-> . <-> <-> |
4 | <-> . <-><-> <-> |
5 |<-> <-> . <-> <-> |
6 | <-><-> . <-> <-> |
7 | . <-><-> <-> <-> |
8 | <-> <-> . <-><-> |
9 | <-> <-><-> . <-> |
10 | <-> . <-><-> <->|
11 | <-><-> <-> . <-> |
12 | <-> <-><-> . <-> |
13 | <-> . <-><-> <-> |
14 | <-> . <-><-> <-> |
15 |<-> <-><-> . <-> |
16 | <-> <-> . <-><-> |
17 | <-> <-> . <-> <->|
18 | <-> <-><-> . <-> |
19 | <-> . <-><-> <-> |
20 | <-> <-> . <-><-> |
21 | <-> <-> <-><-> . |
22 | <-> <-> . <-><->|
23 | <-><-> <-> . <->|
24 | <-> <-> <-><-> . |
+————————————————————————+
localhost:Executables uwe$
4 | ANU College of Engineering and Computer Science October 2020
the router task (and all tasks or resources initiated by it) will terminate eventually. if the call to
Shutdown is not accepted then an abort of this task is attempted by the environment.
All this sounds complicated but it really isn’t. the core of the assignment is just to decide in
which direction to forward a specific message and to use your knowledge from the course to
implement your strategy without locking up, unnecessary busy-waiting loops or losing informa-
tion. in short: your solution should be implementing a router which is responsive on all ports
and directs traffic onto the optimal routes.
Implementation alternatives
the basic requirements for an implementation in another language are:
• Option to select between and parametrize topologies as provided in the framework.
• Make sure that you routers do not access any information other than the initial connection
list to neighbouring routers and the information which they gain by exchanging messages.
• instantiate the number of routers required to populate the topology.
• the routers need to be instantiated as processes, threads, tasks, or what-
ever your operating system or language will provide as concurrent entities.
• Provide each router entity with communication links to neighbouring routers. those
links shall resemble a “wire” semantic, i.e. synchronous forms of communication.
• Run a simple test by sending messages from every router to every oth-
er router and measure the actual number of hops the messages took.
• Summarize the results as maximal as well as average number of measured hops.
if this sounds too demanding for your chosen environment, then contact us and we will work
out a plan which can be done – a concurrent implementation of the router tasks is obviously
mandatory though.
Candidates include Erlang, go (basic templates provided for both), Rust, Smalltalk, LabViEW,
Occam, OpenMP… just as long as you can rely on message passing (synchronous message
passing might be emulated by asynchronous message passing) and support for concurrency.
if your environment cannot be reproduced by us with reasonable effort in order to run your pro-
gram then we will potentially ask you to provide more detailed documentation of your tests.
Extension
As you have been attentive you will have noticed a command line parameter (-x) which controls
the number of routers dropping out. After the initial configuration phase (and before normal
traffic starts) a specific number of random routers can be powered down purposefully. Many
network topologies offer multiple routes to the same node, so the resulting network may still be
fully operational (minus any direct communication to the powered down nodes obviously).
Your extension assignment is to design routers which are robust with respect to such losses
in the network and will still deliver the packets to the destination, even if the original/optimal
path became unavailable. in the provided Ada framework routers will detect the loss of an im-
mediate neighbour by receiving a Tasking_Error exception when trying to communicate to an
already terminated router task. handle this exception and provide an alternative route.
Reflect first for a moment on the following issues (all of which will be related to specific topolo-
gies):
• how many dropped out routers can you handle and still guarantee delivery?
• how does the number of dropped out routers affect the performance? You may want to dis-
tinguish the situation when you first detect the failure from the following routing operations.
• Can you respond locally or will you need to propagate the detection of the failure?
this extension is meant for the student who wants to dig deeper and find out more about real-
world routing.
5 | ANU College of Engineering and Computer Science October 2020
Deliverables
You do not need to provide a rationale or any report of sorts if you believe that your design is
obvious and a few comments inside your code will make the idea sufficiently clear.
Yet you need to provide two items:
a. the sources for a working router (and an environment to test them in for the stu-
dents not using the provided Ada framework). Zip up the Router directory (which
should hold all sources which you manipulated or added) for submission.
b. A graphical representation of the workings inside your router (as a pdf file named
Diagram.pdf). Add this file to your Router directory before you zip it up.
in any case, we will read your sources carefully. the core part of your router will be small – take
your time to structure this part well.
Different entities in your graphical representation will have different meanings: Use different
lines / arrows / colours / shadings / etc. to indicate what is what and provide a legend. Before
you start drawing: decide what the main aspect of our diagram should be. Will you primarily
provide a call-graph / data-flow-graph / synchronization-graph / dependency-graph / etc. or
a mixture of multiple aspects. if you need multiple diagrams for multiple aspect, then please
provide multiple diagrams (in the same pdf file). Your diagram will likely contain text labels, yet
should not include full sentences or paragraphs.
there is no predefined template for your diagram as the idea is that you communicate your
concept with it – whichever format supports this best is for you to decide.
Tutor-eyesight-health-warning: Make sure that your graphics will appear technically in vector
(scalable) format inside your pdf file – never as an image made out of pixels!
Criteria
When you design your system, you might want to keep the following criteria in mind:
• Messages shall arrive at the destination router eventually (this is the minimal requirement).
• the number of hops should be minimal.
• the setup time should be proportional to the number of nodes or even bet-
ter to the diameter of the network. Beware of combinatorial explosions.
• Performance of the solution. Did you arrange concurrent entities inside
your router to guarantee minimal delivery delays? Assume that your rout-
er can be provided with any number of physical concurrent entities.
• Elegance of the solution. Elegance is often a measure related to compactness and sim-
plicity but not always. You will see whether your design is elegant once you reevalu-
ate/scrutinize your sources a few days after you achieved a running system.
• Clarity and expressiveness of the provided graph. A meaningful graph will use
a clear legend of graphical elements to distinguish different issues.
• Robustness of the routing algorithm. Could you design an algorithm which han-
dles dropped out routers gracefully and with minimal effect to performance? if
you do not target a high distinction in this assignment, you may consider drop-
ping this criterion and focus on the remaining ones (this one is hard).
Final words
implementing this basic router will give you a good starting point to look further and deeper
into the world of distributed systems. the assignment combines what you now know about
concurrent systems and expands your practical abilities towards problems in distributed envi-
ronments. getting closer to the end of the course, try to recollect the new concepts and tools
which you have now at your disposal. While you should not expect that we made an experi-
enced designer of concurrent and distributed systems out of you quite yet, you do have now a
6 | ANU College of Engineering and Computer Science October 2020
substantial amount of knowledge to already join in at discussions among professionals in the
field.
Outlook
Students in Real-time and Embedded Systems (final year course) will be working with actual
hardware (below) and concurrent and distributed algorithms under strict real-time constraints.
there is strong demand for outstanding professionals who can handle high integrity systems
interacting with the physical world. Your course provides many foundations for any such career
– academic or industrial.