next up previous contents
Next: Virtualizing the Network Up: Title Previous: History

NAT and Networks

Subsections

Introduction

When network address translation was invented it was a mere hack to circumvent IP shortage. Meanwhile it has proven to be useful in completely different fields nobody had thought of at the beginning, and there are probably many more useful applications that have not been found yet. In that context I want to try to explain the role NAT currently has and that it might gain in the future, proving that it is more than a short term solution and that it will stay with us for much longer, especially when we look at the current state of the IPv6 implementation. Experiments done by some people have shown that the IPv6 protocol itself does not cause many problems so migration could be swift, but lots of applications cause problems and it is therefore likely that IPv4 will be the major Internet- and Intranet-protocol for longer than expected.

Before we begin explaining NAT's role in todays and future networks I want to show in what different areas NAT is being used today. The explanations will be made from a technological point of view, i.e. I will not try to give advice on how a special kind of NAT should be used. The following sections are just an overview. The details that have to be thought of when implementing NAT or examining implications of using NAT are laid out in the chapter thereafter.

I have divided the overview into two parts. I call the first one classic NAT , meaning that this is the original NAT as invented in the early nineties which is covered by RFC 1631, mainly meant to save IP address space on the Internet. The second part introduces more recent forms of NAT-usage that do not serve the original purpose but opened up additional fields.

Classic NAT Techniques

Speaking about NAT we must know that address translation can be done statically or dynamically. In the first case the assignment of NAT-IPs to original IPs is unambiguous, in the latter case it is not. In static NAT a certain fixed original IP is always translated to the same NAT IP at all times, and no other IP gets translated to the same NAT-IP, while in dynamic NAT the NAT IP depends on various runtime conditions and may be a completely different one for each single connection.

In the following sections m,n are defined as follows:

m: number of IPs that need to be translated (original IPs)

n: number of IPs available for translation (NAT IPs)

Static Network Address Translation

m:n-Translation, m,n>=1 and m=n (m,n in N)

With static address translation we can translate between IP networks that have the same size (contain the same number of IPs). A special case is when both networks contain just one IP, i.e. the netmask is 255.255.255.255. This NAT strategy is easy to implement, since the entire translation process can be written as one line containing a few simple logic transformations:

new-address = new-network OR (old-address AND (NOT netmask))

In addition, no information about the state of connections that are being translated needs to be kept, looking at each IP packet individually is sufficient. Connections from outside the network to inside hosts are no problem, they just appear to have a different IP than on the inside, so static NAT is (almost) completely transparent.

 
Example:

[static NAT example]

Dynamic Address Translation

m:n-Translation, m>=1 and m>=n (m,n in N)

Dynamic address translation is necessary when the number of IPs to translate does not equal the number of IPs to translate to, or they are equal but for some reason it is not desirable to have a static mapping. The number of hosts communicating is generally limited by the number of NAT IPs available. When all NAT IPs are being used then no other connections can be translated and must therefore be rejected by the NAT router, for example by sending back 'host unreachable'. Dynamic NAT is more complex than static NAT, since we must keep track of communicating hosts and possibly even of connections which requires looking at TCP information in packets.

As mentioned above, dynamic NAT may also be useful when there are enough NAT IPs, i.e. when m=n. Some people use this as a security measure: it is impossible for someone outside a network to get useful IP numbers to connect to of hosts behind a NAT router doing dynamic address translation by looking at connections that take place, since next time the same host may connect using a completely different IP. In this special case even having more NAT IPs than IPs to be translated (m<n) may make some sense.

Connections from outside are only possible when the host that shall be reached still has a NAT-IP assigned, i.e. if it still has an entry in the dynamic NAT table, where the NAT router keeps track of which internal IP is mapped to which NAT IP. For instance, non-passive FTP sessions, where the server attempts to establish the data-channel, are no problem (for protocol specific problems see Section [*]), since when the server sends its packets to the FTP-client there is already an entry for the client in the NAT-table, and it is extremely likely it still contains the same client-IP to NAT-IP mapping that were there when the client started the FTP-control channel, unless the FTP session has been idle for longer than the timeout of the entry.
However, if an outsider wants to establish a connection to a certain host on the inside at an arbitrary time there are two possibilities: the inside host does not have an entry in the NAT-table and is therefore unreachable, or it has an entry, but which NAT-IP must be used is unknown, except, of course, the IP to connect to is known because the internal host is communicating with the outside. In the latter case, however, only the NAT-IP is known but not the internal IP of the host, and this knowledge is valid only while the communication of the internal host takes place plus the timeout of the entry in the NAT routers table.

Example:

[dynamic NAT example]

Masquerading (NAPT)

m:n-Translation, m>=1 and n=1 (m,n in N

A very special case of dynamic NAT is m:1-translation, a.k.a. masquerading which became famous under that name because Linux can do it. It is probably the kind of NAT-technique that is used most often these days. Here many IP numbers are hidden behind a single one. In contrast to the original dynamic NAT this does not mean there can be only one connection at a time. In masquerading an almost arbitrary number of connections is multiplexed using TCP port information. The number of simultaneous connections is limited only by the number of TCP-ports available.

A special problem of masquerading is that some services on certain hosts only accept connections coming from privileged ports in order to ensure that it does not come from an ordinary user. The assumption that only the superuser can access those ports is not valid, since on DOS or Windows machines everybody can use them, nethertheless, some programs rely on this and cannot be used over a masqueraded connection. The Linux implementation uses no privileged ports for masquerading to avoid interfering with 'regular' connections to these ports. Masquerading usually uses ports in the upper range, in Linux this range starts at port 61000 and ends at 61000+4096, which is the default and can easily be changed by editing linux/include/net/ip_masq.h. This also shows that the Linux implementation by default only allows 4096 concurrent connections. To allow masqueraded connections on ports outside of such a port range requires keeping and managing even more information about the state of connections. Linux, for example, simply treats all packets with destination IP = local IP and destination port is inside the range used for masquerading , as packets that have to be demasqueraded, i.e. they are answers to packets that have been masqueraded on their way out.

Incoming connections are impossible with masquerading, since even when a host has an entry in the masquerading table of the NAT device this entry is only valid for the connection being active. Even ICMP-replies that belong to connections (host/port unreachable) do not get through to the sender automatically but must be filtered and relayed by the NAT-routers software.
While it is true that incoming connections are impossible we can take additional measures to enable them, but they are not part of the masquerading code. We could, for an example, set up the NAT-device so that it relays all connections coming in from the outside to the telnet-port to a host on the inside. However, since we have just one IP that is visible outside for enabling incoming connections for the same service but for different hosts on the inside we must listen on different ports on the NAT-device, one for each service and internal IP. Since most applications listen on well-known ports that cannot be easily (and transparently!) changed, this is quite inconvenient and often no option, especially not for public services. The only solution is to have as many (external) IPs as the number of services that shall be provided. An external IP can still be shared by different services, and then be remapped to different internal IPs using NAT, but that is not part of masquerading, then.

Example:

[masquerading example]

The greatest advantage of masquerading for many people is that they only need one official IP-address but the entire internal network can still directly access the Internet. This is so important because IP addresses have become quite expensive. As long as there are application level gateways we do not need any IPs or any kind of NAT and one IP is still enough, but for some protocols, e.g. all UDP based services, there is just no gateway so direct IP connectivity is necessary.

At the time of this writing there existed an Internet Draft (which I should not reference here, since it is just a draft) from the same people who wrote RFC 1631 (NAT). It explains masquerading, that they call Network Address Port Translation (NAPT), in great depth. There is no IETF-paper (none that I could find, at least) on more recent forms of NAT like the ones introduced in the following chapters, although there are (commercial) implementations of them. It seems like for the IETF NAT only exists for helping to solve the classical Internet address space shortage problems described above.

Other NAT Techniques

While classic NAT technologies serving the purpose of saving valuable address space have been known for a long time (when measured in Internet-time) other uses for this technology have been found, that are independent of the problems NAT was proposed to help to solve. That means, NAT will not be obsoleted by the long term solutions (like IPv6) developed to solve all of the problems discussed at the beginning of this paper, since completely new fields of application have been found.

Some of these new technologies are introduced below. I write 'some', because I am sure more are to follow that nobody even dreams of today. Not that NAT is vitally important, we could probably live without it somehow, but that is true for many more things developed or invented in the past X*1.000 years. It just can make life easier sometimes. It can also make it harder -- again, this is true not only for NAT, since everything can be used for good and bad.

Virtual Servers (Load Balancing)

Since the notion of a virtual server gets used in a variety of ways, here it means to have an IP that represents the virtual server, for which there is no real device to which this IP belongs to, and several other IPs, for each of which there is a real device. When a host connects to the virtual IP the NAT device exchanges the destination address, which is the virtual IP, against an IP of one of the real devices. Depending on the algorithm that is used to select the (real) server IP, virtual servers can serve various purposes.

[virtual servers]

Example:

[virtual server example]

Load Balancing

The algorithm used to determine which real IP to use may, for instance, check the load on each of these servers (e.g. by counting the packets/second that flow through the NAT device to the servers) and select the IP of the server with the lightest load, thereby achieving a relatively equal distribution of the traffic on the virtual IP over the servers. The number of algorithms that might be used here is uncountable, but virtually all of them will be compromises, since the notion load cannot be clearly and uniquely defined. We could, for example, run a daemon on each of the servers that informs the NAT-router about the load on that machine -- however the machine's load maybe defined -- and remap new connections to the system where this number is the lowest. This requires communication between the hosts and the NAT-router, so we might prefer to use data available on the router anyway, such as the number of connections that are currently being remapped to a host, or we might use data that is not naturally available on the router but that can easily be collected, such as the average number of bytes or packets per second, that a host currently handles.

The critical element here will always be the algorithm used to achieve equal load distribution. The more accurately we try to measure the load, the more data we need to handle on the NAT-router and the harder it gets to collect the data in the first place. This is somehow similar to Heisenberg's Uncertainty-Principle in Quantum theory, so we must find a way to minimize the tradeoff between what it costs to determine the load and what possible use we can get out of that knowledge.
Even when we assume we could find a way to accurately determine the load (based on an ultimate definition of what load actually is) practice does not honour our efforts: Since an IP packet has a minimum size (like a quantum in physics) and, in addition, we can only select to which host we want to send it when a new connection is opened, we will never be able to achieve an infinitely equal load distribution. Of course, the above is not of any practical interest, but it certainly is interesting. It does have a practical impact in so far that it shows us when it is useless to refine the algorithms any further.

There are numerous other approaches to load balancing, most of them on a higher (user) level. One example is described in RFC 1794 (DNS Support for Load Balancing). Here the DNS controls the load of machines by giving away the IP of the least busy machine when queried. Since DNS-queries will be cached by subsequent DNS-servers the control is severely limited, but it will work quite well if there are many queries and when they come from a lot of different clients. However, even if load balancing may work under certain circumstances this approach will not help when one of the servers fails and is no longer available, since even if this particular IP is no longer given in queries, it still is in many caches.
Another example is the famous cache program squid , which uses complicated algorithms to find out where to get an object from[7]. This solution is no general solution but limited to this particular program. With NAT on the other hand we can do load distribution for a much larger variety of services, as long as they are based on IP. Squid serves a different purpose so a comparison does not work, I used it as an example where the intelligence to do load balancing and to collect the data is implemented in all the programs involved and not in an independent central authority.

Backup Systems

Virtual servers can also be used to achieve a higher availability of a service, since the service provided by the virtual server is available as long as any one of the real servers is able to provide it. When the probability of a failure of a single server is p, the probability that a virtual server formed by n real servers fails can be calculated as follows:

p1...pn: probability of a failure of server n in N is number of servers that provide the virtual service

pNAT: probability of a failure of the NAT-router, which fails independently of the other devices

pvirt: probability of a failure of the virtual server, when the individual servers fail independently of one another

[formula]

Of course, the setup used above for load balancing must be enhanced in order to make changes to the list of servers used by the NAT-router to remap connections to as soon as one of the real servers is no longer available. This, however, does not belong in the NAT-code but can better be controlled in higher layers, even from shell-scripts. There must than be a mechanism to remove servers from the virtual server table. Since there must be an interface to build the virtual server table in the first place anyway it is not hard to add features, so that IPs can be added and removed from a virtual server during run time. With this setup we have combined the two functions load balancing and high availability, using virtual servers, and it is even transparent to all hosts, users and programs using the virtual service.

Multiple Routes per Destination

We have seen above that we can use NAT to distribute load over several hosts and achieve a higher availability of host based services. Can we use NAT to do the same for networks? Yes, we can. Above we have introduced virtual hosts that represent several real hosts, we can also create a virtual network connection that consists of several real wires which has the same advantages and disadvantages as the virtual server technique.

How can we do this with NAT? Imagine, we had two Internet providers. Two, because we do not want to rely on the network of just one of them in case of a failure of their networks. Every host that needs Internet connectivity needs a unique IP, so we buy one IP for each of them from each provider. When our hosts want to use provider one they use this provider's IP as local IP; when they want to use provider two they use the IP given by this one as local IP. Every host with an IP of both providers can now use either one to send its packets to the same destination.
Now we already see where we are going. The setup described has the potential to solve the problem, we could do load distribution by letting some hosts use provider one and others provider two, and we have a higher availability of the connection to the Internet, since it is more unlikely that both providers have a major breakdown than it is for one of them (how we calculate the probability has been illustrated above). However, as it is easy to imagine we would have a very hard time trying to do load balancing when each host decides on its own where it sends its packets, not to mention how hard it would be to convince a network application to use one or the other local IP. This calls for a central authority to do the decision which host should use which provider, and this authority will, of course, be a special NAT-router.

[virtual routes example]

Using NAT, our local computers need just one IP, since it is no longer up to them to decide which provider (and therefore which IP) to use. If we had a favorite provider, we could use this providers IPs for our hosts, but we can also use internal IPs. Now, when an internal hosts wants to establish a new connection with a destination on the Internet, it just sends its packets to its default router, which is the NAT-router (in the end, there might be other routers involved), and the source IP is the hosts local (internal) IP. The NAT-router, because it knows all connections, decides which provider will route this connection, replaces the source hosts (internal) address with one of the provider chosen and sends it out to this providers router. Since the source address is an address of this providers network, the answers will also come in that way. The host where the packets originated never gets to know which provider had been chosen by the NAT-router, so this process is transparent.

We can use the same algorithms as for virtual servers, so we can do load balancing and we have the high availability feature. The essential difference to the virtual server implementation is that we have to interfere with the routing process. In the above example we actually have two default routes, for example.

Problems Common to All Techniques

The very special thing with all kinds of NAT is that the five-tuple that uniquely identifies a connection: protocol , source IP and port , destination IP and port that is the same on the source, the destination and on routers in between, is different for all three entities as soon as NAT is active on the router. Special, since we now suddenly have three different such five-tuples where each identifies the same connection on a different section of the route: section one is from the source to the NAT router, section two is from the NAT router to the destination and, at last, section three is inside the NAT router that has to know both the other two sections. We could also say only the NAT router knows what is really going on, which also means the NAT device has to store lots of information about the connection it translates which 'regular' routers do not need to do.
This is something they have in common with firewalls: because they both do not just relay packets from one side to another but also control the data flows they must know as much about every connection as each network device knows about its own connections, i.e. they must keep state information. It is obvious that this requires a significant overhead compared to simply routing packets.

I must not forget to say that if NAT is being used all packets must go through the NAT-router, i.e. there must not be any alternative routes a packet could take, circumventing the address translation. The reason is obvious, but due to their nature as tools for organizing private networks NAT routers are mostly placed on the borderlines of internal (leaf) networks this should be no problem.

Keeping State Information

Except for static NAT we need to store and manage dynamic information about the clients currently using the system as a router and possibly about their connections. In addition, this state information must eventually timeout, so that hosts that have long been switched off or stopped transmitting packets for some other reason are deleted from our list eventually so that the NAT IP assigned to this host can be reused. This timeout is also the reason why looking at TCP-headers is recommended: The timeout can be short for TCP-connections that have just been closed and must be high for TCP connections that are still established, since for example many telnet-sessions may hang around for a very long time without exchanging any packets. In this case, if we have sufficient NAT-IPs left we do not need to let these connections time out, but we might want to assume they are dead when there are lots of new connection requests that need NAT-IPs from the pool.

On the other hand, if we do not keep state information but only look at the IPs that need a NAT-IP assigned, it is much simpler to implement NAT and it will in many cases work as well as the more complicated solution above. Under light load, i.e. when there are always enough unused NAT-IPs left, we will not notice much difference between both variants, except for in the telnet-session (and related programs, e.g. ssh) case. Only when there are not many NAT-IPs left keeping state information is recognizably of advantage, since we are able to exactly identify connections that have just been closed and can reassign their associated NAT-IPs immediately without waiting for a timeout. That keeping track of the state of individual connections adds to overall security if it is used by firewall code is another issue that has nothing to do with NAT.

There is another case where NAT should not just look at the IPs but at the connections individually, that is when we are using virtual servers or virtual network routes for load distribution and there are a significant number of connections coming from only a few IPs, maybe because the IPs belong to big servers that open many connections. In this case when only the IP is examined load distribution will not fully work, because the traffic generated by an individual IP can than not be divided any further. When we look at the (TCP,UDP) ports in addition to the IPs, we can distribute the load more equally by remapping individual connections rather than individual IPs, as the following picture illustrates.

[state information example]

Fragmentation

Closely related with the above problem of keeping state information about TCP and possibly UDP connections is the problem of IP fragments. It is often desirable to base the decision whether a packet should be translated not just on the IP addresses, but also on the TCP/UDP addresses, the ports. This way telnet packets can be treated different compared to http packets. An example for a use of it is to have just one (virtual) IP or DNS name for all services, which will then be remapped to different hosts providing the service. Such services might even be provided a virtual host. A firewall with application level gateways does the same to a certain degree, but it can only do this for services where a gateway exists and mostly these gateways are not transparent. Besides, this is just an example for why it might be of use to look at the ports of packets for NAT.
The problem is that as soon as a packet has been fragmented the NAT router cannot tell the port except of the first fragment containing the TCP header. That is why we must also keep state information about fragments. We must store all data of the first fragment including its TCP or UDP port, of course, in order to be able to know the port the other fragments are going to. Even this measure might not be sufficient since IP does not guarantee that packets arrive with the correct sequence, i.e. the third fragment of a fragmented packet might pass through the NAT router first, before the first fragment still carrying the port information. In this case all we can do is to hold back all non-first fragments of a fragmented packet until the first one arrives, so that we know if we have to translate the packet or not. See also page [*].

When we have to do that much just to be able to use the TCP or UDP addresses for our to-NAT-or-not decision the idea to use NAT to also rewrite these addresses is almost obvious. This way we have not just IP address translation but also UDP/TCP address translation. It may be less significant but it certainly is a useful extension. An example for its use are virtual servers: Let us assume we want to create a virtual webserver. Let us further assume that the real webserver daemons running on different machines listen on different ports for some reason. When we do not rewrite the destination port in packets to the virtual server (and insert the original port on answer packets) this setup is impossible, then all webservers must listen on the same port where the virtual server provides its web service.

Protocol Specific Issues

Network Address Translation is not always as transparent a process as it should be. Everything would be fine if IP was the only protocol carrying IP address information. There are some protocols that send IPs as part of the data they transmit, and if this is a translated IP that is sent to a receiver behind our NAT-router we are going to have a problem. This means the receiver will have a problem, since he cannot reach the host the IP transmitted has been meant to address. The only way to solve this issue is to look at the data transmitted by certain protocols known to include IP information, which of course means additional overhead and complication.

Some examples for such protocols:

FTP [8]

The FTP-commands PORT and the response to a PASV both send an IP and a port to the other party. For FTP to work over a translated connection we have to replace the IP in the message. The most complicated part of this is that IP and port are transmitted as their(decimal) ASCII representation, i.e. each single number of the decimal representation of the IP is a byte in the packet. For this reason the IP does not have a fixed length in such FTP-packets. When we now try to replace the IP by another one that has more (less) digits in its decimal representation the packet gets larger (smaller). This in turn makes it necessary to adjust the TCP-sequence numbers accordingly, so that we have to keep some more information about these connections in order to adjust the numbers in each subsequent packet of that connection. This is not just a problem of FTP, but of all protocols where exchanging the IP changes the packets length.

ICMP [9]

Some ICMP messages, depending on the type of the message, include a part of the header of the original packet that caused this ICMP message to be generated, including the entire IP header of that packet. If the packet had been translated, this header will contain the NAT-IP rather than the real local IP of the host that gets this ICMP message. Depending on if and how this extra header information is used this may present a problem or not.

DNS

Obviously, this service is a major problem if nameservice for internal IPs shall be provided outside the NAT-domain. A solution would be to have two DNS-services, one with internal IPs for internal address resolution and an external one with NAT-IPs. Of course, the IPs resolved by the external server should not be part of a pool of addresses for dynamic NAT, as one can easily see. Since NAT-routers are mostly placed on the borderlines of networks separating internal and external DNS data makes sense anyway and is widely used for security reasons. If the far more complicated approach of rewriting all DNS data relayed by the NAT router is used I would suggest an application level gateway rather than an implementation inside NAT, because DNS is well suited for being ``gatewayed'' and we should only put code into the kernel that is really necessary there.

BOOTP

BOOTP should be no problem most times, because it is very unlikely that this protocol ever has to cross the border of a NATed network.

Routing-Protocols (RIP, EGP,...)

I do not need to explain why routing protocols are a problem. That there are a lot of different routing protocols doesnot make it any easier. The three solution are, again,

next up previous contents
Next: Virtualizing the Network Up: Title Previous: History
Michael Hasenstein