NAT Traversal Deep Dive
How direct connections happen through NATs — based on Tailscale's "How NAT Traversal Works"
The Fundamental Problem
Devices behind NAT lack direct internet reachability. The core challenge: two firewalled peers cannot establish bidirectional communication when both must initiate contact simultaneously — a logical impossibility without external assistance.
Why It's Hard
- Stateful firewalls only allow inbound UDP if a matching outbound was previously seen
- Both peers need to send first — but neither can receive until they do
- NAT rewrites source addresses, so peers don't know each other's real endpoints
- Different NAT devices behave differently — no single solution works everywhere
What We Need
- A way to discover our own public endpoint
- A side channel to exchange endpoint info with peers
- A trick to make both firewalls open simultaneously
- A fallback relay for when direct connection is impossible
Prerequisites for NAT Traversal
1. UDP-Based Protocol
TCP adds another layer of complexity — the TCP handshake requires synchronized state and may need kernel modifications. Use UDP as the transport, or QUIC (stream-oriented protocol built on UDP) for reliability.
2. Direct Socket Control
You cannot retrofit NAT traversal onto existing network libraries. The traversal mechanism must share the socket with your primary protocol — each socket gets a different NAT mapping.
STUN: Discovering Your Public Endpoint
STUN (Session Traversal Utilities for NAT) solves the information asymmetry problem — you don't know what public ip:port your NAT assigned to you.
Warning
Critical: STUN packets must originate from the same socket that will carry actual data traffic. Each socket gets a different mapping on the NAT device — discovering the mapping for one socket tells you nothing about another.
Why STUN Alone Isn't Enough
STUN works perfectly for endpoint-independent mapping NATs (the same external port regardless of destination). But for endpoint-dependent mapping (symmetric) NATs, the port STUN discovers will be different from the port assigned for peer communication.
NAT Behavior Types
Same socket → same external port regardless of destination.
- Send to 5.5.5.5:1234 → NAT assigns port 54321
- Send to 7.7.7.7:2345 → NAT reuses port 54321
STUN discovers the port once, share it with peers — done.
~85-90% of consumer NATs
Each destination gets a different random port.
- Send to 5.5.5.5:1234 → NAT assigns port 54321
- Send to 7.7.7.7:2345 → NAT assigns port 62847
STUN discovers 54321, but peer will trigger a different port — must predict.
~10-15% (enterprise, CGNAT)
Note
Cross-reference: For the full taxonomy of NAT types and filtering behaviors, see NAT Types & Behavior.
UDP Hole Punching Walkthrough
The key insight: nothing says the packets must be related beyond the IPs and ports lining up. Both peers send packets at nearly the same time — both firewalls see outbound traffic and allow return packets.
- Both peers register with a coordination server (DERP, XMPP, SIP, etc.) and perform STUN to discover their public endpoints.
- Coordination server tells Peer A: "Peer B is at 72.5.6.7:39182" and Peer B: "Peer A is at 72.1.2.3:54321"
- Both peers start sending packets simultaneously to each other's known endpoints.
- Peer A sends to 72.5.6.7:39182 → A's NAT creates outbound state. Packet arrives at B's NAT, but is dropped (no matching outbound yet).
- Peer B sends to 72.1.2.3:54321 → B's NAT creates outbound state. Packet arrives at A's NAT — matches A's outbound state → allowed through!
- A's reply now reaches B — matches B's outbound state → allowed through. Bidirectional channel established.
Tip
Timing: The packets don't need to cross in flight. As long as both NATs have created outbound state before the other side's packet arrives, it works. A few hundred milliseconds of overlap is sufficient.
Birthday Paradox Port Prediction
When one or both peers are behind symmetric (endpoint-dependent) NATs, the port assigned for peer communication is unpredictable. STUN discovers a port, but the NAT will assign a different port for a different destination.
The Strategy
Open many ports on one side and probe randomly from the other. Like the birthday paradox — you don't need to guess the exact port, just find a collision in the port space.
| Scenario | Ports Open (One Side) | Probes Needed (Other Side) | Success Rate |
|---|---|---|---|
| One hard NAT | 256 | 174 | 50% |
| One hard NAT | 256 | 1,024 | 98% |
| One hard NAT | 256 | 2,048 | 99.9% |
| Two hard NATs | Random both sides | ~170,000 each | 99.9% |
Warning
Two hard NATs: Both sides probing randomly requires ~170,000 probes each for 99.9% success — approximately 28 minutes at 100 packets/second. This is why relays exist as fallback.
Port Mapping Protocols
Instead of guessing, ask the NAT directly to create a mapping. Three protocols can do this:
| Protocol | Mechanism | Status |
|---|---|---|
| UPnP IGD | XML/SOAP over HTTP — request port forwarding from the gateway | Widely implemented, but security concerns led to widespread disabling |
| NAT-PMP | Apple's simpler binary protocol — lightweight, fewer security issues | Apple ecosystem, some consumer routers |
| PCP | NAT-PMP v2, RFC 6887 — adds IPv6 support, third-party mappings | RFC standard, growing adoption |
Effect: these protocols effectively "make one NAT vanish from the data path" by requesting the device to forward an external port to your internal address. If available, this eliminates the need for hole punching on that side.
Hardware NAT Behavior Quirks
Mapping Timeouts
Stateful firewalls time out mappings after ~30 seconds of inactivity. You must send keepalive packets at ~25 second intervals to maintain the NAT state.
Different NATs have different timeouts — some as short as 20s, some up to 5 minutes. The safe default is 25s.
Filtering Inconsistencies
Some NATs filter on source port, some don't, some partially. RFC-defined behaviors (endpoint-independent, address-dependent, address+port-dependent filtering) are often implemented inconsistently.
Hairpinning
When two peers are behind the same NAT, they try to reach each other via their external addresses. The router should recognize this and internally rewrite (hairpin), but many routers fail — routing assumptions baked into silicon don't handle this case.
Note
Hairpinning failure means two devices on the same LAN can't connect directly via their public IPs. Traversal systems must detect this and fall back to using LAN IPs or a relay.
Double NAT & CGNAT
Carrier-grade NAT (CGNAT) stacking creates the worst scenarios:
- Home NAT behind ISP NAT — two layers of address translation
- Two peers behind the same CGNAT but different home NATs — hairpinning problems compound
- Each NAT layer adds its own mapping — STUN only sees the outermost
- Port mapping protocols (UPnP) only work on the innermost NAT
NAT64 Considerations
IPv6-only networks using NAT64 translators add another dimension:
- Detect the NAT64 prefix via DNS queries to
ipv4only.arpa - Calculate the NAT64 prefix from the response
- Communicate with IPv4 peers by targeting
{NAT64 prefix + IPv4 address} - The NAT64 translator handles the v6↔v4 conversion
ICE: Try Everything At Once
Interactive Connectivity Establishment elegantly sidesteps the classification problem: "try everything at once, and pick the best thing that works."
Gather Candidates
LAN IPs, STUN WAN IPs, port-mapped addresses, IPv6, relay
Exchange Lists
Share all candidates with peer via side channel
Probe All
Simultaneously probe every peer candidate
Select Best
Pick lowest latency working path
Upgrade
Transparently switch to better paths as they appear
ICE eliminates guesswork about NAT type and network topology. It doesn't classify — it experiments.
Note
Cross-reference: For the ICE protocol details, candidate types, and Trickle ICE, see STUN, TURN & ICE.
Relay Fallback: TURN & DERP
When all direct traversal methods fail (~5-10% of connections), relay through an intermediary:
- Standardized relay protocol (RFC 5766)
- Allocates a public relay address for each client
- Supports both UDP and TCP relay
- Typically used with ICE as last resort
- Higher latency (extra hop) but guaranteed connectivity
- Detoured Encrypted Routing Protocol
- Runs over HTTP/HTTPS — works through restrictive firewalls that block all UDP
- Positioned near the network path direct connection would take
- Dual purpose: relay AND side-channel signaling
- Data is end-to-end encrypted (WireGuard) — relay can't read it
Note
Cross-reference: For Tailscale's DERP relay network and architecture, see Tailscale Architecture.
Security Implications
Warning
End-to-end authentication is mandatory. Once NAT traversal enables dynamic path switching, IP-based security becomes meaningless. Paths can change at runtime — security must be at the transport level (e.g., WireGuard's Noise protocol).
- Packets may arrive from different source IPs as paths change
- A relay sees encrypted blobs — but only if you actually encrypt
- The coordination server knows peer endpoints — compromise = metadata leak
- Keepalive packets reveal connection patterns even when idle
The Complete NAT Traversal Strategy
A robust NAT traversal system combines all techniques in order of preference:
- Try port mapping protocols (UPnP IGD, NAT-PMP, PCP) — if available, eliminates one NAT from the equation
- Use STUN to discover public endpoints on each side
- Exchange candidates via coordination server (all LAN IPs, WAN IPs, port-mapped IPs, IPv6 addresses)
- Attempt direct hole punching — probe all candidates simultaneously (ICE-style)
- If symmetric NAT detected — birthday paradox probing (256+ ports, 1000+ probes)
- If all direct methods fail — fall back to relay (TURN/DERP)
- Send keepalives at ~25 second intervals to maintain NAT state
- Periodically re-evaluate — try to upgrade from relay to direct as network conditions change
Tip
In practice: Tailscale reports that direct connections succeed ~90-95% of the time using this approach. The remaining 5-10% use DERP relays, which are fast enough that most users don't notice.
Quick Reference
| Technique | Solves | Limitations | When Used |
|---|---|---|---|
| STUN | Endpoint discovery | Only works for endpoint-independent NATs | Always (first step) |
| Hole punching | Firewall traversal | Needs coordination, timing | When STUN succeeds |
| Birthday probing | Symmetric NAT | Slow with two hard NATs | When STUN port doesn't match |
| UPnP/NAT-PMP/PCP | Explicit port mapping | Often disabled, only inner NAT | Opportunistically |
| ICE | Path selection | Complexity | Orchestrates all of the above |
| TURN/DERP relay | Guaranteed connectivity | Higher latency, bandwidth cost | Last resort (~5-10%) |
| Keepalives | Mapping persistence | Battery/bandwidth cost | Always (every ~25s) |
