How NAT Traversal Works
Author: Tailscale Engineering
Prerequisites for NAT Traversal
Two requirements before anything works:
- UDP-based protocol — TCP adds too much complexity; use QUIC if you need streams
- Direct socket control — you must send/receive packets outside the main protocol
Stateful Firewalls
Inbound UDP is only allowed after matching outbound traffic has been seen. To punch through two firewalls simultaneously, both peers transmit at the same time:
- A sends to B’s address → A’s firewall logs outbound, allows return
- B sends to A’s address → B’s firewall logs outbound, allows return
- Each side’s packets arrive as apparent “responses” — both firewalls open
This works regardless of how many stateful firewall layers are stacked.
NAT Devices and STUN
NATs rewrite source IP/port (e.g., 192.168.0.20:1234 → 2.2.2.2:4242). The problem: you don’t know what your public endpoint looks like from outside.
STUN solves this: send a “what’s my endpoint from your point of view?” request to a STUN server. The response tells you your public IP:port.
NAT Type Classification (RFC 4787)
| Type | Behavior | Traversal |
|---|---|---|
| Endpoint-Independent Mapping (EIM) | Same public port for all destinations | Easy |
| Endpoint-Dependent Mapping (EDM) | Different public port per destination | Hard |
Tailscale calls these “Easy NAT” and “Hard NAT.”
Hard NAT: Birthday Paradox Port Probing
When both peers are behind hard NATs, ports are unpredictable. Solution: open many ports simultaneously and probe randomly.
- 256 sockets open + random probing
- 174 probes → 50% success
- 1,024 probes → 98% success
Two consecutive hard NATs raises the bar exponentially: ~170,000 probes for equivalent success. This is where relay fallback becomes important.
Port Mapping Protocols
Allow apps to request explicit port forwarding from the router, effectively removing one NAT layer:
- UPnP IGD — complex, widely supported (late 1990s)
- NAT-PMP — Apple’s simpler protocol
- PCP (Port Control Protocol) — NAT-PMP v2 successor
These fail under CGNAT (carrier-grade NAT) since you only control your home router, not the ISP-level NAT.
Hairpinning
When two peers are behind the same NAT, packets can “loop back” inside the router rather than going out to the internet. Many NATs don’t support this — requiring relay fallback for same-NAT peers.
NAT64
IPv6-only networks use NAT64 to reach IPv4. Detection: send a DNS request to ipv4only.arpa, which resolves to known IPv4 addresses — if you get an IPv6 response, you’re behind NAT64.
DERP: Relay Fallback
When all traversal fails, Tailscale uses DERP (Detoured Encrypted Routing Protocol) as a relay. DERP serves two purposes:
- Side-channel for signaling during connection setup
- Last-resort encrypted data relay
ICE Protocol
ICE (Interactive Connectivity Establishment) tries everything at once and uses the best path:
- Enumerate all local endpoints
- Query STUN servers and port mapping protocols
- Exchange candidate lists with peer (via side channel)
- Probe all remote candidates simultaneously
- Transparently upgrade to best working path
Implementation Checklist
- UDP foundation
- Direct socket access
- Peer side-channel (for exchanging candidates)
- STUN server infrastructure
- Relay network fallback
Steps: enumerate locals → STUN → port mapping → exchange candidates → probe all paths → maintain bidirectional keepalives → end-to-end encrypt → upgrade paths transparently