NAT Traversal through Tunneling (NATTT)

Network Address Translation (NAT) is prevalent in today's Internet as it is deployed everywhere from large enterprise networks to millions of residential home networks. NAT allows networks to use private IP addresses internally while still being able to access the public Internet, but it does not allow external hosts to initiate communication to private internal addresses, a hurdle to many emerging applications, such as VoIP and P2P. Although a plethora of NAT traversal solutions have been proposed in recent years, they suffer from being application-specific, complex, or dictated by specific NAT implementations. Given NAT is likely to be with us for a long time, we need a simple, generic NAT traversal solution for all applications.


Objective: To allow an external host to initiate a connection to a host behind a NAT such that:
  1. the connection works with all applications and transport protocols,
  2. it supports nested NATs,
  3. and the solution is incrementally deployable and easy to deploy.

Key concepts in our design include the use of UDP tunnels and a sequence of NAT box addresses and private IP addresses to uniquely identify a host. We propose simple and incrementally deployable changes to DNS as a mechanism to learn the addresses (e.g., the sequence of tunnels and private addresses) and require only minimal modifications as discussed below .


Our NAT traversal design aims to achieve two main goals. First, the solution should be generic. It should support all applications and transport protocols, and it should also support nested NATs. Second, it should be incrementally deployable. It should be compatible with existing infrastructures, including NAT boxes, hosts, and applications, and the cost and gains of deploying the solution should align at the same place.

The basic idea is to tunnel packets through NAT boxes to restore end-to-end reachability. Suppose an external host A wants to initiate communication with an internal host B behind a NAT box Y. If A knows both Y's public address (Ypub) and B's private address, A can tunnel packets to B as follows. The outer header of a packet is destined to Ypub, so that the packet can be routed over the public Internet to reach Y; The inner header is addressed to B, so that when Y receives the packet, it can remove the outer header and find out where to forward the packet within the private network.

To implement this idea, three main design questions must be answered. (1) How does the initiator of communication learn the tunnel end-point(s) at the destination network? (2) Although tunneling can solve the reachability problem for hosts behind NAT, those hosts still suffer from the non-uniqueness problem of their NAT addresses. That is, even if a host A can reach other hosts behind NATs, these other hosts may be behind different NATs and happen to have the same private IP addresses, how can A distinguish different remote hosts when they use the same (private) IP addresses? (3) How can the new design handle the current NAT traffic, and work with the existing NAT boxes?

A successful design must answer these questions with the two main goals in mind: be generic and be easy to deploy. We propose to use DNS to learn tunnel end-point addresses, use a generic user-level program on the client host to mask the non-uniqueness of private IP addresses from transport protocols and applications, and use UDP tunnels (instead of IP-in-IP tunnels) to encapsulate packets which can traverse deployed NAT boxes. In the rest of the document we will outline our solution and deployment considerations.

Tunneling Through NAT


Figure 1. Tunneling through a NAT box (Y) to access a private server (B) from the public Internet

We first use an example to illustrate the tunneling mechanism. In Fig.1, let us assume that client A on the public Internet wants to access web server B behind a NAT box Y. By querying B's DNS name, A learns B's private IP address and Y's public IP address (See next section for details). A then encapsulates its packets in UDP. The outer IP/UDP header is destined to Y on a well-known UDP port number assigned for the use of NATTT (we use 100 in this writing). The inner header is destined to B on its service port, which is 80 for its web service in this example. Routers in the Internet will forward the packet according to its outer header until it reaches Y, which recognizes it as a NAT tunnel packet because of the well-known destination UDP port number 100. Y removes the outer header and forwards the packet to B according to the inner header. The server B receives, processes, and sends packets as usual without any change or being aware of the NAT. When Y receives the outbound packet from B to A, it encapsulates the packet in UDP and sends it back to A. Upon receiving the packet, A can uniquely identify the packet source by using addresses of both Y and B.


Figure 2. The client side NAT box (X) does traditional port mapping

When A itself is behind a NAT box X which does not understand the tunneling scheme, X can simply forward the packet with the traditional port mapping scheme (Fig. 2). In this situation, A can only create a tunnel using its own (private) address as the source address. However, after the packet reaches B, returning packets must be addressed to A's NAT box, X. For this reason, when Y decapsulates the packet (2) to (3) in Fig. 2, it replaces the inner source (A:3456) by the outer source (X:5000), and records the original inner source, which will be restored when it encapsulates outbound packet (4) to (5). This inner header rewrite by Y enables client NAT X and server host B to work with the new tunneling scheme without any changes.


Figure 3. Recursively tunneling through nested NAT boxes (Y and Z)

This traversal mechanism can be extended recursively to support nested NATs. For example, suppose B is behind two levels of NAT, Y and T. A learns from DNS (1) Y's public IP address Ypub, (2) T's NAT address in the outer NAT, and (3) B's NAT address in the second level NAT. A encapsulates its packets in two levels: the outermost header is destined to Y:100, the middle header T:100, and the innermost header B:80. The same tunneling mechanism will be able to deliver the packets.

Building and Managing the Tunnel


Figure 4. DNS queries and Address Mapping at the Local Host

In order to handle DNS lookups and packet en/decapsulation, the client host needs to run a user-space NATTT daemon program, natttd, which works like a DNS proxy. natttd captures DNS queries issued by local applications through the system's configuration (e.g., /etc/resolv.conf) and/or a packet filtering API (e.g., netfilter in Linux), forwards the queries to servers, and intercepts the replies (Fig. 4). When a DNS lookup returns a type A resource record (RR), it indicates the destination host has a public IP address; natttd will return the IP address to the application and will not capture its future packets. When the DNS reply says that the A RR does not exist, natttd will follow up by querying for the NAT RR, a new RR that contains all the addresses necessary for building (nested) tunnels to reach the destination host. If the destination network supports NATTT, it will reply with the IP addresses of the destination host (B) and its NAT box (Y).

However, natttd cannot return both addresses to the application since applications and transport protocols expect only one IP via the socket API; it also cannot return either one since only the combination of the two can uniquely identify the server host on the Internet. The solution is to return an unused IP address in the range and record the mapping. Now applications and transport protocols communicate with a locally unique destination IP, and natttd captures their network traffic, converts the address and does packet en/decapsulation. Therefore applications and transport protocols do not have to make any changes or be aware of NATTT. natttd will provide interfaces to its mapping table, \eg, a diagnosis tool can query natttd and list all current connections with external IPs.

Deployment Considerations

On the client side, NATTT only requires users to install a daemon program on the local host. There is no change to applications, operating systems, or network devices such as NAT boxes. Since most client users can benefit from applications enabled by NATTT, they have the incentive to deploy, but may not have the expertise to make significant changes.

On the server side, the NAT box needs to be upgraded to support NATTT tunnels, and the DNS zone file needs to include the new NAT resource record for servers behind NAT. Hosts behind the NAT do not need any changes. This works well for enterprise networks as the system administrators can make the necessary changes at a couple of places, without the need to upgrade a large number of server hosts.


Figure 5. Deploying a NATTT box (T) behind a legacy NAT box (Y)

To deploy NATTT in residential home networks, we can get around the requirement of upgrading NAT boxes and DNS zone files as follows. In Fig. 5, a legacy NAT box Y is configured to forward traffic of UDP port 100 to a host T behind Y, and T is installed with a NATTT proxy package. T decapsulates and forwards packets to their internal destinations. All the user needs to do are (1) installing a software package on a regular host T, and (2) configuring one UDP port forwarding entry on the legacy NAT box Y. This scheme can also be used by enterprise networks as an incremental deployment approach. For modifying DNS records, there are a number of free DNS services available for end users to register their server hosts. In the case that users do not have access to add a new type of resource record, they can add additional A RR to emulate the NAT RR. For example, querying returns B's private IP, querying returns B's NAT box, Y's public IP, and natttd can be configured to accommodate this setup.


In summary, we combine UDP tunneling, a new type of DNS resource record, and the use of 127/8 addresses to achieve a simple and generic NAT traversal solution. It supports different applications, transport protocols, NAT implementations, nested NATs, and can be incrementally deployed without disrupting existing services. We plan to flesh out the complete design, implement it on major operating systems, and test it with different network devices and applications. If NATTT is successful, in the long run, we would like to explore possibilities of incorporating other capability, such as support for host mobility, into the same framework.