Router Dataplane

Description

• The solution represents the implementation of a router's dataplane. The router processes incoming packets, performs routing based on a routing table and handles protocols such as IPv4, ICMP and ARP.

Solution Components

1. Routing Process - IPv4 Protocol

• Initially, check if the packet is for the router or for the entire network (broadcast) and verify that the packet has the Ether Type field in the Ethernet header corresponding to the IPv4 value.

• Then, if the packet is indeed for the router, the router will respond with an ICMP Echo Reply (see ICMP Implementation).

• Otherwise, verify if the packet's checksum is correct, and if not, drop it. Check if the TTL field is 0 or 1, in which case send an ICMP Time Exceeded message and drop the packet. (see ICMP Implementation)

• Next, decrement the packet's TTL field and search for the destination IP address in the routing table to determine the interface through which we will send the packet. If the address is not found, send an ICMP Destination Unreachable and drop the packet. (see ICMP Implementation)

• If we found the destination IP address in the routing table, obtain the MAC address of the output interface, and if not found, send an ARP request (see ARP Implementation).

• Finally, recalculate the checksum, rewrite the source and destination addresses of the packet and send the packet to the output interface.

2. Efficient Longest Prefix Match using Trie

• I used a trie_node structure that contains a pointer to the left child (0 bit), the right child (1 bit) and to a route_table_entry structure that contains an entry in the routing table (only the trie leaves will contain a routing table entry).

• I implemented the insert_node insertion function, which I call for each entry in the routing table. This will insert as many nodes from the IP address prefix in the trie as there are 1 bits in the mask, and finally will add the current routing table entry in the leaf.

• I implemented the get_best_route function, which will search in the trie for the best route for the destination IP address. This will traverse all bits of the destination address, and at each bit will verify if we have reached the end of the trie or if we have found a new match (reached a leaf). Otherwise, continue to go right or left, depending on the value of the current bit in the address. Finally, return the best route found (the longest match found).

3. ICMP Protocol

• As I mentioned in the Routing Process - IPv4 Implementation section, I implemented the ICMP protocol to respond to an Echo Request message with an Echo Reply message, or to send a Destination Unreachable or Time Exceeded message.

• I implemented the icmp_echo_reply function, which will send the packet back, reverse the source and destination addresses, recalculate the checksum for the IP and ICMP headers, replace the ICMP message type with Echo Reply and reset the TTL field to the default value (64).

• I implemented the icmp_message function, which will create a new packet that will contain, above the ICMP header, the IP header and the first 8 bytes from the original packet's payload. After swapping the source and destination addresses, recalculate the checksum for the IP and ICMP headers, then format the ICMP header. Finally, send the packet to the output interface.

4. ARP Protocol

• As I mentioned in the Routing Process - IPv4 Implementation section, I implemented the ARP protocol to obtain the MAC address of the output interface, in case not found in the ARP table.

• I implemented the send_arp_request function, which will create a new packet that will contain the source address of the output interface and the destination address as the broadcast address, then format the ARP header. This function will be called if the MAC address corresponding to the destination IP address does not exist in the ARP table, for the route found to be the best in the routing table. Also, this function will add the packet we want to route to a queue, to send it after we find the desired MAC address through an ARP reply.

• I implemented the handle_arp_request function, which will respond to an ARP request by sending an ARP reply. It will modify the source and destination addresses and change the operation code to ARP reply, then send the packet.

• I implemented the handle_arp_reply function, which will add the MAC address - IP address correspondence to the ARP table, to be used in future searches. Then, it takes all packets that were waiting for this MAC address and sends them to their output interface.