Lab 5: Network Address Translator

Due date: Thursday, December 3 @ the beginning of class.


In this lab assignment you will be writing a simple NAT that can handle ICMP and TCP. It will implement a subset of the functionality specified by RFC5382 and RFC5508.

Just as lab 2 built on lab 1, lab 5 builds on lab 3: your lab 3 grade is the maximum of your lab 3 and lab 5 grades. You should start with your static router code and extend it to include NAT functionality.

So you can generate traffic from myth machines to application servers in VNS, it is not the case that nodes behind the NAT (myth machines) have private IP addresses. Nevertheless, your NAT will rewrite packets from myth machines going to the application servers, such that they appear that they are coming from the IP interface facing the application servers. For example, consider this topology, where your NAT's internal interface (eth0) faces myth and its external interface (eth1) has two application servers connected with a switch:

In this topology, your NAT will rewrite packets from the myth machines so that they come from IP address When your NAT receives packets to, it determines whether the packet has a valid mapping to an internal source, and if so, translates the address to the corresponding myth machine.

For your NAT, interface eth0 is always the internal interface and all other interfaces are always external interfaces.

If your NAT is working correctly, all of the following operations should work from myth machines:

Furthermore, all packets to the app servers should appear to come from

General NAT Logic

There are three major parts to the assignment: translating ICMP echo messages (and their corresponding replies), translating TCP packets, and cleaning up defunct mappings between internal addresses and the external address. Your NAT does not have to handle UDP.

Static Router

Your NAT builds on the static router of lab 3. You should add a new command-line flag, -n, which controls whether the NAT is enabled. If the -n flag is not passed, then the router should act following the requirements of lab 3. For example, it should be possible to traceroute across the router when the -n flag is not passed. All of the ICMP errors in lab 3 still apply. For example, trying to open a TCP port on the router should cause an ICMP port unreachable reply (with the caveat of TCP requirement 4 below). More precisely:

  1. Your NAT MUST generate and process ICMP messages as per the static router of lab 3.


The first four bytes of an ICMP echo request contain a 16-bit identifier and a 16-bit sequence number. Because multiple hosts behind the NAT may choose the same identifier and sequence number, the NAT must make their combination globally unique. It needs to maintain the mapping between a globally unique identifier and the corresponding internal address and internal identifier, so that it can rewrite the corresponding ICMP echo reply messages. The first three requirements for your NAT are:

  1. Your NAT MUST translate ICMP echo requests from internal addresses to external addresses, and MUST correctly translate the corresponding ICMP echo replies.
  2. ICMP echo requests MUST be external host independent: two requests from the same internal host with the same query identifier to different external hosts MUST have the same external identifier.
  3. An ICMP query session timer MUST NOT be shorter than 60 seconds.That is, an ICMP query mapping MUST NOT expire less than 60 seconds after its last use. This value MUST be configurable, as described below.

TCP Connections

When an internal host opens a TCP connection to an external host, your NAT must rewrite the packet so that it appears as if it is coming from the NAT's external address. This requires allocating a globally unique port, under a set of restrictions as detailed below. The requirements for your NAT are a subset of those in specified in RFC5382; in some cases they are more restrictive. Refer to the RFC for details on the terms used. Your NAT has the following requirements:

  1. Your NAT MUST have an "Endpoint-Independent Mapping" behavior for TCP.
  2. Your NAT MUST support all valid sequences of TCP packets (defined in [RFC0793]) for connections initiated both internally
    as well as externally when the connection is permitted by the NAT. In particular, in addition to handling the TCP 3-way handshake mode of
    connection initiation, A NAT MUST handle the TCP simultaneous-open mode of connection initiation.
  3. Your NAT MUST have an "Endpoint-Independent Filtering" behavior for TCP.
  4. Your NAT MUST NOT respond to an unsolicited inbound SYN packet for at least 6 seconds after the packet is received. If during this interval the NAT receives and translates an outbound SYN for the connection the NAT MUST silently drop the original unsolicited inbound SYN packet. Otherwise, the NAT MUST send an ICMP Port Unreachable error (Type 3, Code 3) for the original SYN.
  5. If your NAT cannot determine whether the endpoints of a TCP connection are active, it MAY abandon the session if it has been idle for some time. In such cases, the value of the "established connection idle-timeout" MUST NOT be less than 2 hours 4 minutes. The value of the "transitory connection idle-timeout" MUST NOT be less than 4 minutes. This value MUST be configurable, as described below.
  6. Your NAT MUST NOT have a "Port assignment" behavior of "Port overloading" for TCP.
  7. Your NAT MUST support "hairpinning" for TCP. The hairpinning behavior MUST be of type "External source IP address and port".

Cleaning up defunct mappings

Your code must clean up defunct mappings. Your NAT has two timeout configurations: the first is for defunct ICMP query sessions, the second is for idle TCP connections. Cleaning up these mappings will require you to spawn a new thread that walks your mapping data structure periodically. Be sure to use locks to protect the data structure, as both the forwarding path and the cleaning thread might try to access it concurrently. Take a look at the code provided in lab 3 for the ARP cache as a starting point.

Your ICMP query timeout should be a #define ICMP_QUERY_TIMEOUT, such that passing a -D flag when compiling (e.g, -DICMP_QUERY_TIMEOUT=30) can override it (units are seconds):


Passing a -D flag at the gcc command line should also be able to redefine the TCP idle timeout, TCP_IDLE_TIMEOUT (units are seconds):

#define TCP_IDLE_TIMEOUT 7440

Implementation guidance

Tearing down mapping state and delaying incoming SYN processing will require a data structure similar to the ARP cache from lab 3. Unlike lab 3, however, in this assignment you have to implement these data structures. The ARP code is a good place to start. For handling timeouts, the ARP cache spawns a thread that periodically runs. Because the main forwarding thread and this thread share the cache as a shared data structure, the ARP cache accessors and mutators use locks.

If you do not have thread programming experience, then Lectures 9, 10, and 13 of CS110 might be helpful introductions. There are also many resources on the web explaining why and when systems use them. Finally, there are lots of good pthreads tutorials on the web, for concrete programming guidance. You can also use the ARP cache code as a guide. Since this isn't a high performance system, it's better it be conservative with your locks; a race condition is much harder to debug than a deadlock.

Reference Binary

To help you debug your topologies and understand the required behavior we will provide a reference binary in the week of November 16th. There will be information on the newsgroup on where you can find it. We may provide some additional sample topologies.


A new template topology 'nat' is provided for this assignment. This template is similar to the one shown in the figure above.

Additionally, the web server will send you a HTML page containing the observed IP address and port. You should use this information to determine if your NAT is functioning properly.

A reference binary sr_nat is available for use in /usr/class/cs144/bin

Finally, a hairpinning test is also available in /usr/class/cs144/bin.

  1. Copy uctest and from /usr/class/cs144/bin to your router directory.
  2. Set ethIP in to your NAT's eth1 IP address.
  3. Run your NAT (-n flag)
  4. Run on ** Due to compatibility issues with myth, this test script only works off of corn.

Collaboration policy

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assignment. You are not allowed to look at anyone else's solution (and you're not allowed to look at solutions from previous years). You may discuss the assignments with other students, but you may not look at or copy each others' code.


Please create a README file with your SUNET ID (network login) and any description/overview of your implementation that you feel is relevant.

To submit, run

make submit
from your project directory and submit the resulting tarball on the submission page.