IN3230/4230 - Home Exam 1 - Fall 2019
Routing
Formally
This assignment will count towards your final grade and must be solved individually. The grade assessed on this assignment will make up about 20% of your final grade. Your submission will be marked with respect to how well you have fulfilled the requirements listed in the "Task" section.
Handouts
You shall test your solution using the h1 mininet topology configuration as defined here.
It must be possible to perform ping measurements between MIP address 10 and MIP address 100.
Task
The goal in this assignment is to implement a routing daemon that offers routing services to the network layer. Using these services, the network layer can perform end-to-end transmission of packets between all end hosts that are attached to the network. Even in instances where there are no direct Ethernet links between two hosts, they must be able to communicate with eachother with assistance from intermediate hosts. Hosts that only receive packets and pass them on towards a destination act as routers. All nodes in the network must be capable of operating both in end host and router capacities simultaneously. You will implement the Distance Vector Routing (DVR) with Split Horizon routing mechanism.
The core task in this assignment is the implementation of DVR with split horizon. You must implement a routing protocol at the network layer which builds and maintains routing tables as defined in the DVR scheme. Assume that all directly connected neighbours have distance 1.
Specific implementation requirements
You must implement a routing daemon. Every host runs such a routing daemon, which offers routing services by communicating with the MIP daemon on the same host. The interface between the MIP daemon and the application must not be changed from how it worked in the mandatory assignment. This implies that each node only supports a single application at a time, because the MIP daemon implements the network layer. Despite this limitation, the MIP daemon must differentiate between packets exchanged between routing daemons and regular application traffic. In this sense, we do not consider the routing daemon to be a standard application.
The MIP daemon as implemented in the mandatory assignment will need to be modificatied somewhat. It must be able to request the MIP address of the correct next hop neighbour from the routing daemon, enabling communication between hosts which are not directly connected at the link layer. This implies that the ping server and client applications as developped in the mandatory assignment should keep working without modification. However, it will now be possible for a client to ping a server located more than one network layer hop away.
The routing daemon must answer routing requests made by the MIP daemon to enable the latter to perform packet forwarding. It receives a MIP destination address from the MIP daemon and returns the MIP address of the corresponding neighbour node which is to serve as the next hop. The routing daemon must communicate with other routing daemons running on other hosts through the intermediary of the MIP daemon. To differentiate routing requests (between the local MIP daemon and routing daemon) and route information exchange (between the local routing daemon and remote routing daemons), you are to use two separate UNIX domain sockets in the interface between the MIP daemon and the routing daemon.
The routing daemon must regularly (periodically) update its routing table. The routing algorithm to be implemented is Distance Bector Routing with Split Horizon. The MIP daemon will discriminate routing packets (used as part of the routing protocol) from MIP-ARP and application payloads by setting the TRA-bits in the MIP header to the 010 bit combination. The routing process begins as soon as both the MIP and routing daemons are started on a host.
The MIP daemon must forward transport packets (TRA combination 100) in accordance with the current routing table state, or pass it up to the application if the destination address is local to the host.
When the MIP daemon forwards a packet in its router capacity, it must decrement the Time to Live (TTL) field of the MIP header by one. When the TTL reaches a value of -1, the MIP daemon must drop the packet rather than forwarding it further. This prevents packets from travelling in infinite loops should errors be introduced in the routing tables.
Neither MIP-ARP lookups nor routing lookups should block (delay) the forwarding of packets arriving after the initiation of such lookups. In other words, lookups should happen asynchronously.
Deliverables
- A design document in PDF format comprising the following:
- A cover page bearing your candidate number, the title of the document, the course code and the semester. You must not indicate your name or username anywhere in your submission!
- A description of your DVR with split horizon implementation.
- An illustration of the design of your programs (e.g. a flow chart).
- Documentation on running and using your programs.
- Notes regarding any other peculiarities your solution may have.
- The C source code of your solution. The code must be appropriately commented to aid in the comprehension of your solution. You should document the following for all functions in your code:
- What the function does
- What the function parameters and return value are and how they are used.
- Any global variables used within the function.
Regarding grading
- A router performs two tasks: routing and forwarding. Forwarding is simpler to implement than routing and will therefore be weighted less than routing.
- No points will be assessed for parts of the mandatory assignment being reused as is, such as the ping applications.
- However, how you integrate the routing mechanism into the MIP daemon will be assessed. If you opt to use the precompiled MIP daemon we provide in your final submission, you will be docked points.
- After having performed an ARP lookup on a path for the first time, subsequent transmissions on the same path should not incurr delays. You can test this with the ping application.
Development and test environment
You will develop and test your implementation on the same virtual machine image used in the mandatory assignment, hosted on the UH-IaaS cloud platform.
Please do not attempt to solve the assignment locally on your own machine or in any way which deviates from these instructions.
Submitting
Electronic submission
Exams at UiO are anonymously graded. It is your responsability to ensure that no part of your submission contains any identifying information such as your name, username and so on.
Your exam solution must be submitted through the Inspera exam system.
We recommend that you confirm that the archive you uploaded contains what it should by downloading it and unpacking it again after submission. If you deliver the wrong files, there is nothing we can do about it when we process your delivery. We also recommend you upload draft versions as you work, to ensure you have a deliverable in the system should you experience last minute technical difficulties etc.
Deadline
The deadline for submitting this exam is Tuesday October 15 at 23:59 Oslo local time.
This is an absolute deadline, failure to deliver on time will result in the grade F for this part-exam.
The course management is not able to handle any enquiries regarding medical extensions and so forth, you must contact the study administration directly.
You are expected to strictly comply with the rules governing studies and exams at the University of Oslo.