This document covers the implementation of the Data Plane of a router in C++ using ISO/OSI network and data layer concepts.
The main workflow of the program is as follows:
- At each iteration, a new packet is obtained.
- All headers from the received packet are parsed.
- Depending on the packet type, a certain branch of the code is executed.
On the first day, the basic protocols (IPv4, ICMP) were implemented. The other days were dedicated to the ARP protocol (the most demanding) and the routing process.
Within the main loop, messages are received on any interface of the router, processed, and either response packets are transmitted or the same packets are routed on the path chosen by the router. It also checks if there are messages received by the router and not yet routed that are in the queue, checking if they can be sent following the receipt of an ARP response.
In this part, ARP requests and ARP responses received by the router are processed, and ARP requests can also be constructed as needed. This area also includes the ARP queue for routing messages for which the MAC address corresponding to the IP address of the next "hop" is not yet known. The queue from C++ is used for the ARP queue.
A send_arp_p function is used to construct and send a new ARP packet (using known information, such as spa, tpa, etc.).
Here, ICMP responses are constructed that the router sends if problems occur with IPv4 packets or if an ICMP echo request is received.
In this section, received IPv4 packets are processed to determine what will happen to them. It is checked if there are any problems with the received packet (incorrect version, transmission errors, insufficient TTL), generating an ICMP response if necessary. It is also checked if the packet is destined for the router itself. If not, then the routing process continues, in which the routing table is searched for the packet's destination address.
If a "hop" is not found, an ICMP response is generated and sent back to the source. If a "hop" is found, but the corresponding MAC address is not known, then the message is inserted into the ARP queue to be routed later, after an ARP response is received (and ICMP responses generated by the router are subject to this process). If all information is available, the packet is routed on the spot. Updating the TTL for a routed packet is performed using the incremental checksum calculation algorithm.
The routing table search algorithm is performed in logarithmic complexity O(log n) because the table is already sorted within the init_route_table initialization function (binary search is used).
The incremental checksum calculation algorithm from RFC 1624 is implemented in the ip_checksum_bonus function.
- There were some problems with implementing binary search / Trie search. The logic of the search algorithm was changed to solve the first problem.