The State of NAT Traversal

This is a technical deep-dive post. If you aren’t interested in under-the-hood network geekery, you can safely skip it.

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.3 or 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.

UDP hole punching exploits this concept of a “conversation.” It works like this. (Slight variations on this procedure exist, but this is the basic idea.)

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