Description
You will implement a “routing demon” as a normal userspace program under Linux.
Instead of sending its routing packets over real network interfaces, your routing demon
will communicate with its peer demons (which run in parallel on the same machine)
through local sockets. Each instance of the demon runs as a separate process. Your
program should be a text mode program, no credit will be given for providing a graphical
user interface.
Roughly speaking, your demon program will operate in three stages:
• At the beginning it reads a configuration file (whose name has to be supplied as
a command line parameter – please avoid any interactive reading of the filename)
which contains a unique identification for the routing demon instance, the port
numbers on which the demon receives routing packets from peer demons (input
ports), and specifications of the outputs towards neighbored routers. Clearly,
any output port declared for one router should be an input port of another router.
The information in the configuration file is only meant to inform demons about
links, the demons internal routing table is still empty at this stage.
• Next the demon creates as many UDP sockets as it has input ports and binds one
socket to each input port – no sockets are created for outputs, these only refer to
input ports of neighbored routers. One of the input sockets can be used for sending
UDP datagrams to neighbors.
• Finally, you will enter an infinite loop in which you react to incoming events (check
out the select() system call and its equivalent in Python.1
) An incoming event
is either a routing packet received from a peer (upon which you might need to
update your own routing table, print it on the screen, or possibly send own routing
messages to your peers), or it is a timer event upon which you send an unsolicited
RIP response message to your peers. Please ensure that you handle each event
atomically, i.e. the processing of one event (e.g. a received packet) must not be
interrupted by processing another event (e.g. a timer).
1One of select()’s important properties is that it blocks while you wait for events, i.e. your program
does not consume CPU time. This property is important and your program needs to have it. Note
that select() blocks an entire process – if your process contains several threads (e.g. one per router)
then all threads are blocked, not only the calling one.
3
4 Problem Description
All the routing demons will be instantiated on the same Linux machine, so you will have
to use the IP address for the local host (127.0.0.1). You should use the UDP protocol
for routing messages.
One hint for your design: many protocol specifications (and even more so their implementations) are expressed using the formalism of extended finite state machines or
finite automata (i.e. state machines / automata that have variables added and where
transitions can be conditioned on both an event and the value of one or more variables).
This can be a very useful design framework. You would have to identify all possible
events, the set of variables, and the set of states. You then have to specify for each state
what will happen when when an event comes in. This has to be done for each event.
4.1 The Configuration File
Your program should be a single executable which can be started with a single command line parameter. This parameter will be the filename of a configuration file. The
configuration file should be an ASCII file that can be read and edited by humans.
I recommend to choose a very simple syntax for the configuration file and to keep the
parser very easy, no extra credits will be given for an elaborate syntax (nothing XMLish or any other similarly baroque format!), fancy parsing code or the like. However,
basic syntax and consistency checks (when a number is expected it should be checked
that indeed a number is present and is in the allowed range) need to be made. Each
instance of the router demon will be started with a separate configuration file.
The configuration file should allow users to set at least the following parameters (one
parameter per line, please allow for empty lines and comments):
• Router id, which is the unique id of this router. A suggested format for this
parameter is:
router-id 1
The router id is a positive integer between 1 and 64000. Each router must have its
own unique router-id, and thus each router configuration file must have a different
value for this parameter.
• Input port numbers: this is the set of port numbers (and underlying sockets) on
which the instance of the routing demon will listen for incoming routing packets
from peer routing demons. There needs to be a separate input port for each
neighbor the router has. A suggested format for this parameter is:
input-ports 6110, 6201, 7345
i.e. the port numbers could be separated by commas. You do not have to follow
precisely this format, but your parser for the configuration should ensure that:
– All port numbers are positive integers x with 1024 ≤ x ≤ 64000 (find out
why 1024 was chosen as lower bound!)
4
4 Problem Description
– You can specify arbitrarily many such entries, but all in one line
– Each port number occurs at most once.
• Outputs: here you specify the “contact information” for neighboured routers, i.e.
routers to which a direct link should exist and with which you exchange routing
information. A suggested format for this parameter is:
outputs 5000-1-1, 5002-5-4
As before, different outputs are separated by commas. For one output, for example
5002-5-4, the first number 5002 specifies the input port number of the peer router,
i.e. the port number on which the peer router will listen to packets from the current
instance. The second number 5 represents the metric value for the link to the peer
router. The third number 4 represents the router-id of the peer router, so that
your instance knows which router is really behind this link. The port numbers
given here must satisfy the same conditions as the port numbers given for the
input-ports parameter. Furthermore, none of the port numbers given for the
outputs parameter should be listed for the input-ports parameter. The metric
values should conform to the conditions given in [1].
• Values for the timers you are using in your implementation. It is wise to use
timer values (for periodic updates and timeouts) smaller than the ones given in
the standard, since this can shorten experimentation times. However, please ensure
that the ratio of the timer values remains the same (180/30 = 6 for timeout vs.
periodic, similarly for garbage collection).
The first three parameters (router-id, input-ports, outputs) are mandatory, if one
of them is missing your program should stop with an error message. When you set
up several configuration files (one for each router), you must ensure manually that the
following conditions are met:
• The router-id’s of all routers are distinct
• When you want two routers A and B to be neighbored, you should:
– provide an input port x at B that is also listed as output port of A
– provide an input port y at A that is also listed as output port of B
– ensure no other host than A has listed port x as an output port
– ensure no other host than B has listed port y as an output port
– ensure no other host than A has listed port y as an input port
– ensure no other host than B has listed port x as an input
– and finally, ensure that the metrics that A specifies for its output with port
number x is the same as the metric that B specifies for its output port y.
5
4 Problem Description
4.2 Exchanging Routing Packets and Route Computations
In this section it is assumed that you are already intimately familiar with the RIP
protocol specification [1]. Here we will just give a few hints on which parts of the
specification can be ignored, should be simplified, or need to be modified.
• Scope of implementation is essentially Section 3 of [1]. None of the extensions in
section 4 is to be included (no extra credit).
• Please implement split-horizon with poisoned reverse. This means that for any
update message or unsolicited response a separate packet needs to be created for
each neighbor.
• Implement triggered updates only when routes become invalid (i.e. when a router
sets the routes metric to 16 for whatever reason, compare end of page 24 and
beginning of page 25 in [1]), not for other metric updates or new routes.
• Do not use the UDP port specified in [1], but the port numbers from the configuration file.
• Do not implement request messages, you should use only the periodic and triggered
updates.
• The version number is always 2.
• You do not route to subnetworks and do not handle IPv4 addresses, but you only
route to the various routers (as identified by their router-id). You also do not
need to take care of default addresses, host routes or subnet masks.
• RIP response packets always include the entire routing table, and to each neighbor
a separate copy of this table is sent (according to the split-horizon-with poisoned
reverse rule, which implies that each neighbor might get a different view of the
table).
• Do not multicast response messages, just send them to the intended peer through
its input port.
• Packet format:
– Ignore the issue of network byte order
– Please use the 16-bit wide all-zero field in the RIP packet common header for
the router-id (since otherwise you would have no identification of the router
sending out an update. Furthermore, you should also work with router-id’s
instead of IPv4 addresses.
– Important: Please perform consistency checks on incoming packets: have
fixed fields the right values? Is the metric in the right range? Non-conforming
packets should be dropped (and perhaps a message printed, this helps your
debugging).
6
5 Deliverables
• Regarding periodic updates: You need to find out how to generate periodic timer
events and how to write own handlers for this event. It could also be useful to
introduce some randomness to the periodic updates, for example by setting the
timer in question randomly to a value that is uniformly distributed over the range
[0.8 · period, 1.2 · period]. Why could such a randomization be useful?
Some other things:
• If a demon has several input ports, it needs to listen to all of them simultaneously.
This can be achieved through the select() system call / its Python equivalent.
It goes without saying that you should perform various tests with your setup. These
tests should show that your routing protocol design and implementation converge to the
“right” routing tables (which you will have to establish from inspection) and respond
“in the right way” to certain failure events (e.g. one process is shut down and re-started
later). To properly conduct these tests it is also important to formulate in advance
which behaviour your implementation should show and to compare the actual outcome
against it.
5 Deliverables
To receive marks for the assignment, each pair of students has to do two things:
• Demonstrate your program and explain the source code to me.
• Submit a .pdf file with all fonts embedded, which includes:
– A cover sheet with your names and student-id’s,
– answers to questions (see below),
– an example configuration file used in the demonstration, and
– you have to print the plagiarism declaration form from the learn page of
COSC 364, sign it, scan it, convert the scanned form into a pdf and include
this into your report.
• Submit a single .py file with your complete source code. Please add your names
and student id’s in a comment at the top of the file.
Please make sure only one member of a team submits the report and the source code.
Warning:
• Reports that are not in pdf format or which contain more than one
file (beyond the .py file with your source code) automatically receive
0 marks!!
• Submissions which do not include the signed plagiarism declaration
form automatically receive 0 marks!!
7
5 Deliverables
5.1 The Demonstration
The demonstrations will take place shortly after assignment submission, dates will be
arranged shortly before. A demonstration session will use the Linux computers in the
COSC labs (Important: make sure your program runs from the bash command line
under Linux!) and will have the following structure:
• The first ten minutes are a live presentation of the program:
– First we will start up all router instances and check whether the routing tables
converge and the resulting routes are ”minimum hop”. Please make sure that
your program generates sufficient output for me to check this – for example,
you could print the routing table after each change or each periodic update.
– Next, we will switch off one or more of the routers and expect that the remaining network converges again into a minimum hop state after a flurry of
activity.
– Finally we will switch the failed router(s) on again and expect to see that the
network converges back into the initial state.
• The second ten minutes are devoted to a code walk-through of your program, to
be done by the first partner. The second partner of a team will wait outside.
Important: each partner should be able to explain the entire program!
• The other partner will do the code walk-through in the third ten minutes.
The most important factors influencing the marking are:
• The achieved functionality as shown in the first ten minutes
• The contribution percentage of either partner
• The understanding of the code shown in the walk-through
The functionality counts most, the source code as such does not count a lot.
For the demonstration you need to set up configuration files for the example network
shown in Figure 1. In the figure, the vertices represent routers and their router-id,
the edges represent bi-directional links. The edges are labeled with cost values for the
respective link.
Please make sure that we can see what is happening during the demonstration. In
particular, each router instance should print its current routing table periodically and/or
after each change in an easily readable format. The table should list all the destinations,
the costs, the next hop router, and the current values of the timers associated with the
destination.
5.2 The Report
The report needs to be a single .pdf file for each pair (the source code is submitted
separately in a .py file). The report needs to include:
8
5 Deliverables
Figure 1: Example network for demonstration
• A title page listing name and student-id of both partners.
• Answers to the following questions (please answer each question with one or two
paragraphs at most):
– A percentage contribution of each partner to the overall project. Important:
this must be agreed upon by you and your partner, the relative weights will
influence grading.
– Which aspects of your overall program (design or implementation) do you
consider particularly well done?
– Which aspects of your overall program (design or implementation) could be
improved?
– How have you ensured atomicity of event processing?
– Have you identified any weaknesses of the RIP routing protocol?
• There should be a substantial discussion (much more than two paragraphs) about
the testing you have performed (for each test: what was to be tested, what was
the expected outcome and what was the actual outcome) and which conclusions
these tests allow about the correctness of your design and implementation.
• One example configuration file for the example network of Figure 1.
9
6 Marking
• You have to print the plagiarism declaration form from the learn page of COSC
364, sign it, scan it, convert the scanned form into a pdf and include this into your
submission.
Warning:
• Report submissions that are not in pdf format or which contain more
than one file automatically receive 0 marks!!
• Submissions which do not include the signed plagiarism declaration
form automatically receive 0 marks!!
Important:
• Please make sure that your .pdf file contains all fonts and can be completely
printed on UC printers – if it cannot be printed it will not be marked. Files not
submitted in .pdf format will not be marked!
• Please make sure that there is only one submission (report, source code) for each
pair.
The documentation has to be submitted via the learn page for COSC364. The
submission deadline is Friday, May 1, 2020, 11.59pm. Late submissions are not
accepted, unless approved through the UC special consideration process.
6 Marking
Marking will be based on the following factors:
• Achieved functionality (70%). This includes: convergence to correct routing tables,
robustness against station failures, syntax and consistency checks (e.g. correct
packet format, correct values and ranges for numbers, handling of read accesses
beyond the end of the file etc.), CPU load, ability to read filename parameter
from the command line. For this factor first a “raw value” is determined based
purely on achieved functionality. Following this, these raw marks will be weighted
against the relative contributions of each group member and individual marks will
be determined.
• The quality of the submitted responses / documentation, in particular your comments about testing (15%).
• Your ability to explain the source code, its architecture and major functions. This
is determined individually and normally weighted with 15%, but if you give the impression that you have not even been remotely present when the software has been
created, you will receive significant reductions in marks or even fail the assignment,
depending on the case at hand.
10
References
• When after a quick glance I find that your source code is particularly ugly and
un-organized, I will apply deductions of up to 10% of the achievable marks. These
will be applied to both team members equally.
References
[1] G. Malkin. RIP Version 2. RFC 2453, 1998.
11