Skip to content

README.md

Latest commit

 

History

History
110 lines (73 loc) · 5.67 KB

README.md

File metadata and controls

110 lines (73 loc) · 5.67 KB

Dataplane Router

Forwarding

First of all, I allocated memory for arrays such as arp entry and route table entry. Then, the router will insert each entry into the trie data structure.

After the router's preparation phase, it will begin receiving packets from any link, separating each header type (Ethernet, IP, ARP) and handling them accordingly.

First things first, the router will check if the EtherType is ARP. If so, it must determine the type of ARP message.

If the packet is of type IPv4, the router will verify its checksum and TTL, update the checksum, and perform a longest prefix match on the packet's destination address.

If the longest prefix match yields a next-hop address, the router must determine its corresponding MAC address. To do this, it first checks its ARP cache. If no entry is found, it sends an ARP request.

At the end, it will update the destination MAC address in the Ethernet header with the one from the ARP entry, set the source MAC address to the MAC address of the current interface, and send the packet.

LPM

For the longest prefix match, I decided to implement a trie, represented by a structure that contains a value field (which can be null or hold the route table entry found), and a children array representing the node's children (children[0] corresponds to bit 0, children[1] to bit 1).

For the trie, I’ve implemented the following functions:

  • init_trie() (initializes the root)
  • create_node() (allocates a new node)
  • insert_prefix() (inserts a new prefix into the trie)
  • longest_prefix_match() (returns the found route table entry)

ARP

ARP REPLY

If the router receives an ARP request, it must respond with an ARP reply. It will do so as follows:

  1. The router will check if the source of the ARP request is itself.
  2. The ARP header is configured with the following values:
  • Hardware Type: Set to 1, indicating Ethernet.
  • Protocol Type: Set to 0x0800 (IPv4).
  • Opcode: Set to 2, indicating an ARP reply.
  • Hardware Address Length: Set to 6 (MAC address length).
  • Protocol Address Length: Set to 4 (IPv4 address length).
  • Source Protocol Address: Set to the target protocol address (tprotoa) from the ARP request.
  • Target Protocol Address: Set to the source protocol address (sprotoa) from the ARP request.
  1. The router will send the ARP reply.

ARP REQUEST

  1. Look for ARP Entry:
    The router first attempts to find an ARP entry corresponding to the next-hop IP address (found_entry->next_hop) using get_arp_entry(). This function returns a pointer to the corresponding ARP table entry if found, or NULL if no entry exists.

  2. If the ARP entry is not found (arp_entry == NULL), the following actions are taken:

  • Queue the Packet:
    The current packet (buf) is copied into a packet_t structure (pkt) and enqueued into the ipv4_queue for later processing once the ARP reply is received. The packet's length (pkt.len) is also set.

  • Get Interface MAC Address:
    The MAC address of the interface is retrieved using get_interface_mac(), and stored in aux_mac.

  • Send ARP Request:
    An ARP request is sent using the arp_request() function. This function takes the following parameters:

    • The source MAC address (aux_mac)
    • The target IP address (found_entry->next_hop)
    • The source IP address of the interface (converted using ip_string_to_uint32())
    • The interface through which to send the request.

After the router receives the ARP reply, it will perform the following steps:

  1. Check for Pending Packets
    If the IPv4 packet queue is empty, the router continues without processing. Otherwise, it dequeues the first pending packet.

  2. Extract Headers
    From the dequeued packet (pkt_deqeued), the Ethernet and IP headers are extracted for modification and further processing.

  3. Update ARP Table
    The sender's MAC and IP from the received ARP reply are added to the ARP table using add_in_arp_table().

  4. Check for ICMP Echo Request to Router
    If the destination IP address of the dequeued packet matches the router's own interface IP, it identifies it as an ICMP Echo Request (i.e., ping). In this case, the router sends an ICMP Echo Reply using the send_icmp() function and continues to the next packet.

  5. Update Ethernet Header for Forwarding
    If the packet is meant to be forwarded:

    • The destination MAC address in the Ethernet header is updated with the sender MAC address from the ARP reply.
    • The source MAC address is updated with the MAC address of the current interface using get_interface_mac().

  6. Send Packet
    Finally, the packet is sent.

ICMP

The ICMP logic is implemented through a function called send_icmp(). The send_icmp() function handles the sending of ICMP packets, both replies and error messages, based on the provided type.

  • If the ICMP type is not REPLY_ICMP_TYPE (i.e., it's an error like Time Exceeded or Destination Unreachable):

    • A new packet is created and populated with updated Ethernet, IP, and ICMP headers.
    • The original IP header and the first 8 bytes of its payload are copied into the ICMP payload, as per the ICMP standard.
    • Checksums for IP and ICMP headers are computed.
    • The packet is then sent via send_to_link().

  • If it's a simple Echo Reply:

    • The original packet headers are updated in-place (source/destination IPs and MACs are swapped).
    • The ICMP type is set, and the checksum is recalculated.
    • The updated packet is sent back to the sender.

This function supports sending both ICMP Echo Replies and error messages required by router ICMP logic.