The State of NAT Traversal

For those who don’t know, NAT stands for Network Address Translation. If you’re on a typical network, your system probably has an IP address like 10.1.2.3or 192.168.0.66. These are private IPs. They are not your real Internet IP address. Between you and the network there is a device called a “NAT router” that performs intelligent address translation back and forth.

NAT was invented because IPv4, the IP scheme that still runs most Internet sites, has an address space that is too small to allow all devices to have “real” addresses. Its successor, known as IPv6, does not have this limitation but is still fairly early in its adoption curve. Migrating a system as huge as the Internet to a new protocol version takes a very long time.

ZeroTier One runs over a peer to peer network, which means that allowing devices to communicate directly is central to how it operates (at scale and with acceptable performance). Since most users are behind NAT devices, people often wonder how exactly peer to peer connectivity is established.

NAT is Traversable

In reading the Internet chatter on this subject I’ve been shocked by how many people don’t really understand this, hence the reason this post was written. Lots of people think NAT is a show-stopper for peer to peer communication, but it isn’t. More than 90% of NATs can be traversed, with most being traversable in reliable and deterministic ways.

At the end of the day anywhere from 4% (our numbers) to 8% (an older number from Google) of all traffic over a peer to peer network must be relayed to provide reliable service. Providing relaying for that small a number is fairly inexpensive, making reliable and scalable P2P networking that always works quite achievable.

UDP Hole Punching

The most common and effective technique for NAT traversal is known as UDP hole punching.

UDP stands for User Datagram Protocol. It’s sort of TCP’s smaller and simpler cousin, a protocol that allows a piece of software to send a single discrete packet from its own address to another IP and port.

A number of Internet protocols use UDP such as DNS, many games, media streaming protocols, etc. For these to be usable behind NAT, NAT routers must implement a concept of “UDP connections.” They do this by listening for outgoing UDP packets and when one is seen creating a mapping that says “private IP:port UDP <-> public IP:port UDP.” Any further packets leaving the private network will be remapped in the same way, and replies from the external system contacted will be remapped in the opposite direction. This allows a two-way UDP conversation to be initiated by a device behind NAT.

1. Alice and Bob are both behind NAT. They both know about a third party — let’s call him Ziggy — that is not behind NAT. Alice and Bob periodically send UDP messages to Ziggy, who records their existence and their public (Internet-side of NAT) IP addresses and ports.

2. When Alice wants to talk to Bob, she sends a message to Ziggy that says “hey I want to call Bob.” Ziggy then sends a message to both Alice and Bob. The message to Alice contains Bob’s public IP and port, and the message to Bob contains Alice’s.

3. Alice and Bob simultaneously (upon receipt) send messages to each other. Alice’s NAT router sees a message leave Alice for Bob’s public IP and port, while Bob’s sees the same thing in the direction of Alice. Both NAT routers create a mapping entry as described above. Each NAT router then interprets the other party’s initialization packet as a reply in a two-way UDP “connection,” and interprets further packets likewise. As long as Alice and Bob send keepalive messages to one another frequently enough (about every 120 seconds for typical routers), this conversation can be kept going indefinitely.

Two points about this. First, the folks who say NAT makes P2P impossible are almost right. NAT does make true serverless peer to peer virtually impossible without incredibly difficult and often unreliable methods. But in practice setting up a triangle relationship like the one above is easy, and since the messages are small the server’s bandwidth requirements are not large. A single relatively inexpensive cloud server instance can easily provide NAT traversal services for millions of devices. Second, if you’re thinking “wow that’s an ugly hack” you are correct. It is indeed ugly and a hack, but so is NAT.

The scenario above is exactly how ZeroTier works except for one minor wrinkle: the message from Alice to Ziggy that says “I want to call Bob” is her first message to Bob. ZeroTier’s servers also act as relays. When they see traffic being sent from one peer to another, they relay it and periodically send a message called VERB_RENDEZVOUS that tells each party to attempt NAT traversal. If it works, they stop relaying and start talking directly. But if NAT traversal never works, both peers can just keep relaying forever. This provides connections that start working instantly and always work for everyone. In common programming parlance we can call this “lazy NAT traversal.” It’s the secret to how ZeroTier One provisions connections so quickly.

Lazy traversal also simplifies things. Most peer to peer protocols perform a complicated endpoint characterization step prior to initiating connectivity. That requires a complicated state machine and a lot of state transitions that must be coordinated to determine things like “am I behind NAT” and “what kind of NAT am I behind?” The lazy method just skips all that. Connection setup is stateless.

Types of NAT

There are four major types of NAT encountered in the field. The terminology used is somewhat confusing… I’m not really sure what is meant by a “cone.” But here they are. The important thing here is that the UDP hole punching technique works for only the first three. The fourth type, known as symmetric NAT, is problematic.

If one host is behind symmetric NAT, traversal can still occur. That’s because the host that isn’t restricted in this manner can reply to the initial packet from the host that is and in so doing “learn” its per-destination IP and port mapping. But if both hosts are behind symmetric NAT, hole punching can’t work… at least not reliably.

Traversing Between Two-Party Symmetric NATs

There is one even scarier hack technique that can occasionally work even if both parties are behind symmetric NAT. Many symmetric NATs assign port numbers sequentially. So in addition to trying Alice’s first IP and port, Bob can also try Alice at IP:port+1 and possibly also IP:port+2.

ZeroTier doesn’t do this yet, but it probably will in a future release. Before enabling it we’d like to do a little more field testing and try to figure out just how often this works and whether it’s worth the trouble and small amount of overhead.

But returning to the numbers cited above: only 4-8% of users cannot establish direct links even though as many as 99% are behind NAT. The situation for a peer to peer protocol in the wild is far from hopeless.

The Same Network Problem

Another difficult situation arises if two peers are actually on the same local network behind the same NAT router.

If that NAT router is traversable, NAT-traversal will almost always work as-usual. But this isn’t optimal. It imposes a small performance penalty, as traffic must now pop its head out of the LAN and back into it and traverse the router twice. What we’d ideally want is for traffic on the same LAN to simply go directly from host A to B.

The simplest solution is to use UDP broadcasts. This is what many applications including ZeroTier do. A packet is sent to broadcast every 60 seconds or so that says “here I am.” Other peers see it and after a proper cryptographic handshake to verify identity establish a direct connection over LAN.

It might be tempting for peers to encode their private IP address and send it to the intermediate server and/or to the other peer. I thought about this when writing ZeroTier. On the plus side, this would work even on large segmented networks where UDP broadcasts don’t make it everywhere. But the problem is that this exposes internal configuration details about the network to potentially random external peers. Many network security administrators are not going to like that, so I decided against it. I tried to think of a way to anonymize the data but couldn’t, since the IPv4 private address space is so small that no form of hashing will adequately protect against exhaustive search.

UPnP and Other Semi-Standards

Some NAT devices support various methods of intentionally opening ports from the inside. The most common of these is called Universal Plug-and-Play(UPnP).

ZeroTier doesn’t support it since typically it’s only found in small router devices such as home routers. These usually implement some form of “full-cone” NAT that can be traversed using ordinary hole punching, rendering UPnP unnecessary for our use case. It’ll probably be supported eventually, since there are sure to be a few exceptions to that rule and the goal is to support traversal in as many scenarios as can possibly be achieved.

UPnP is a fairly ugly semi-standard. It’s not likely to be supported any more widely than it is already.

NAT Murders Kittens

Due to IPv4 limitations, NAT is deployed on most networks. IPv6 is really the only way around this. Yet most don’t realize the cost in kittens. Every time a NAT device remaps an IP address, a kitten dies. This amounts to trillions upon trillions of needless kitten fatalities every day. NAT traversal techniques do not avoid the carnage. They only hide it from the user.

In all seriousness though: NAT is an awful thing. It’s an ugly workaround to a fundamental limitation, and the sooner it’s rendered obsolete by IPv6 the sooner we can start really deploying a whole new generation of Internet protocols.

Other than the obvious downside of increased software complexity, the worst thing about NAT is the inherent resource overhead it imposes on protocols. This is true even in conventional client-server protocol designs. Because NAT is almost always stateful, frequent keepalive packets are required to hold all connections open. This is true for TCP as well as UDP. If you don’t send a packet about once every 120 seconds (for typical NATs), your connection will be forgotten and will reset. Users behind NATs who use SSH have likely discovered this when attempting to leave SSH sessions open for a long time, and SSH (like most protocols) has a protocol keepalive option available as a workaround.

For desktop/laptop and server systems these tiny messages don’t matter much, but for small mobile devices they’re a battery life killer. They also make implementing peer to peer anything on a mobile device very difficult. In the near term, porting ZeroTier’s protocol to mobile without significantly impacting battery life will require some fairly heroic hacks around using platform-provided “push” notifications and other cleverness. None of that would be necessary without NAT, as peers could simply notify one another of their new IP:port locations whenever those locations changed. Usually that’s not very frequent, maybe once or twice a day at maximum, and would not impose much overhead.

So if you want to see truly efficient, scalable, and simple Internet protocols in the future, by all means use IPv6 and encourage others to do the same. It’s not just about IPv4 address exhaustion. It’s also about fundamentally sound protocol design that dispenses with the need for any number of awful hacks like the ones discussed in this post.

… not to mention the kittens.