Lab 5: Network Address Translator

Due date: Thursday, December 2 @ 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. Expect to refer often to these RFCs.

Before beginning this lab, it is crucial that you:

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.

Just like with lab3, the NAT sits in VNS between the app servers and myth. The internal interface of the NAT is connected to myth, while the external interfaces are connected to app servers beyond. The app servers are "outside" the NAT, while myth is "inside." This is counter-intuitive, since the rest of the internet counts as being "inside" the NAT as well; we do this so that you can test form myth, while inside the NAT.

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

In this topology, the NAT rewrites packets from the myth machines, setting the source IP address to When the NAT receives packets addressed 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 this assignment, interface eth0 will always be the internal interface and all other interfaces will always be external interfaces.

A correct implementation should support the following operations from the myth machines:

All packets to external hosts (app servers) should appear to come from eth1's address (e.g. above).

General NAT Logic

There are three major parts to the assignment:

Note that your NAT is not required to handle UDP. It is entirely up to you whether you drop or forward UDP traffic.

Static Router

Your NAT builds on the static router of lab 3. You must 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 query 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 mapping MUST NOT expire less than 60 seconds after its last use. This value MUST be configurable, as described below.

Other lab3 ICMP behavior should continue to work properly (e.g. responding to an ECHO request from an external host addressed to the NAT's external interface).

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.

IMPORTANT NOTE: hairpinning for TCP is NOT required. It is up to you whether you support it, or other behavior not required here.


When assigning a port to a mapping, you are free to choose a port any way you choose. The only requirement is that you do not use the well-known ports (0-1023).

As noted above, mappings should be Endpoint Independent. Once a mapping is made between an internal host's (ip, port) pair to an external port in the NAT, any traffic from that host's (ip, port) directed to any external host, and any traffic from any external host to the mapped external port will be rewritten and forwarded accordingly.

When dealing with multiple external interfaces, it is up to you whether you use the same mappings for all external interfaces or different per-interface mappings. For the purposes of this lab, it is simplest to use the same set of mappings.

Cleaning up defunct mappings

Your NAT must clean up defunct mappings. Your NAT must periodically timeout both defunct ICMP query sessions and idle TCP connections. Once all connections using a particular mapping are closed or timed out, the mapping should be cleared. Once cleared, a mapping can be reused in new connections.

The periodic function that handles timeouts should fire in its own separate thread (more on threading below). The following three timeout intervals for mappings should be configurable via command-line flags:

  -I INTEGER -- ICMP query timeout interval in seconds (default to 60)
  -E INTEGER -- TCP Established Idle Timeout in seconds (default to 7440)
  -R INTEGER -- TCP Transitory Idle Timeout in seconds (default to 300)

TCP Established Idle Timeout applies to TCP connections in the established (data transfer) state. TCP Transitory Idle Timeout applies to connections in other states (e.g. LISTEN or FIN_WAIT_1). Refer to the TCP state diagram.

Note: Though the RFCs specify minimum timeout intervals, these are reflected in the defaults. The intervals should be configurable to times below those minimums so that we are able to test your timeout functionality in a reasonable time.

Implementation Guidance

Mapping data structure and Concurrency

Mapping state and delaying incoming SYN connections will require a data structure similar to the ARP cache from lab 3. Unlike lab 3, however, in this assignment it is up to you to implement it!

Be sure to study how the ARP cache works. For handling timeouts, a separate thread is spawned (at the top of sr_router.c) that periodically runs. NAT timeouts should have their own thread as well. Because the main forwarding thread and the ARP cache timeout thread share the data structure, the ARP cache accessors and mutators use locks. Be sure that your NAT's mapping data structure uses locks as well, otherwise nasty concurrency bugs will be sure to crop up.

In addition, be careful how your mapping table returns mappings, you do not want to hand out pointers to structures that may be freed by the periodic timeout. Take a look at the sr_arpcache_lookup code in the ARP cache.

To get you started on the right track, we provide skeleton code for a possible NAT mapping data structure. Download it here. It is up to you whether you decide to build upon it or create your own from scratch.

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 to be conservative with your locks; a race condition is much harder to debug than a deadlock.

Tracking Connections

You do not need to keep lots of state per connection. For example, there is no need to track seqnos or window values (leave ensuring TCP packets are in proper order to the end hosts). Keep only the information that is useful to the NAT for establishing or clearing mappings.

When re-writing TCP packets, remember to update the checksum (over the psuedo-header, tcp header, and payload). The TCP checksum is calculated like the IP checksum, so you can reuse the cksum function. Note that if the checksum is incorrect when the packet comes in, you can drop it; you should not "correct the checksum" as that would hide potential attackers or errors.

Adding command-line flags

You must add the following command-line flags to sr_main.c:

  -n         -- Enable NAT functionality
  -I INTEGER -- ICMP query timeout interval in seconds (default to 60)
  -E INTEGER -- TCP Established Idle Timeout in seconds (default to 7440)
  -R INTEGER -- TCP Transitory Idle Timeout in seconds (default to 300)
Make sure to adjust the parameter to getopt, and add the proper cases.

Starting your nat with:

  ./sr -u USERNAME -T nat -s -r rtable.vrhost -n -I 70 -R 40

Would enable NAT functionality, timeout ICMP mappings after 70 seconds, TCP mappings with at least one established connection after 7440 seconds, and TCP mappings with only transitory connections after 40 seconds.

Reference Binary

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


A new template topology 'nat' is provided for this assignment. Pass in '-T nat' to ./sr in order to use it. This template is similar to the one shown in the figure above.

Additionally, the web server /index.html links to a dynamic page displaying the IP address and port that the app server observes. You should use this information to determine if your NAT is functioning properly.

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.

WARNING: if you create any files (or use sr_nat.h/c provided above), remember to add them to sr_HDRS and sr_SRCS in the Makefile, otherwise they will not be included in the tarball.

Other Notes

Make sure that if you

Testing correct behavior of unsolicited SYN or simultaneous open requires one to be able to send packets to the external interface of the NAT. This is can be done by mapping

Random Web Traffic

The web is full of random, unsolicited traffic, and VNS is no exception. You may see extraneous traffic in your router.


You can use TCP validation in wireshark to confirm that the TCP checksum recalculation is correct.

If you keep getting 'incorrect ... maybe caused by TCP checksum offload' this is a known bug (check out In these cases, try using a different packet analyzer.

If TCP chksums for long packets (downloading pictures for example), try increasing PACKET_DUMP_SIZE