router-dataplane

A software router implementation in C that handles IPv4 packet forwarding, ARP resolution, and ICMP messaging. Uses a Trie data structure for efficient Longest Prefix Match (LPM) routing.

How It Works

• The router sits between network interfaces and forwards packets based on its routing table. It processes three types of traffic:

IPv4 Forwarding

1. Receives a packet and validates the checksum
2. Checks the TTL — if expired, sends back ICMP Time Exceeded
3. Looks up the destination IP in the Trie for the best matching route
4. If no route is found, sends ICMP Destination Unreachable
5. Resolves the next-hop MAC address via ARP cache or sends an ARP Request
6. Forwards the packet to the correct interface

ARP Protocol

• ARP Request — when the MAC address for a next-hop IP is unknown, the router broadcasts an ARP request and queues the packet
• ARP Reply — when the router receives a reply, it updates the cache and flushes all queued packets waiting for that MAC address
• ARP Response — when another host asks for the router's MAC, it responds with an ARP reply

ICMP Messages

• Echo Reply (type 0) when someone pings the router itself
• Destination Unreachable (type 3) when no route is found for the destination IP
• Time Exceeded (type 11) when packet TTL reaches 0 or 1

Longest Prefix Match — Trie

• Instead of linearly searching through the routing table (O(n)), the router uses a binary Trie for O(W) lookups where W = 32 (bits in an IPv4 address).
• Each bit of the destination IP selects a branch. The deepest node with an associated route entry is the best (longest) prefix match.

Packet Queue

• When a packet needs forwarding but the next-hop MAC is unknown:

1. The packet is enqueued
2. An ARP Request is broadcast
3. When the ARP Reply arrives, all matching packets are dequeued and sent
4. Non-matching packets remain in the queue for future ARP replies Dependencies Linux (uses raw sockets) Standard C libraries (arpa/inet.h, string.h, stdlib.h)