How Does NAT Traversal Really Work? A Deep Dive into Modern Techniques

Translator's Preface

This article is translated from the 2020 English blog "How NAT traversal works".

Imagine two machines in Beijing and Shanghai, each behind a private LAN (e.g., a home desktop and a laptop on Starbucks Wi‑Fi). Both have private IPs but can reach the public Internet. How can they communicate directly?

The simplest solution is a public relay server, but that adds latency and becomes a bottleneck.

Can we achieve direct communication without a relay? With enough networking knowledge, the answer is yes. Tailscale’s epic article demonstrates this possibility, and fully implementing the techniques described yields an enterprise‑grade NAT/firewall traversal tool. Moreover, many ideas in the decentralized software space reduce to the problem of crossing the public Internet for end‑to‑end direct connections.

1 Introduction

1.1 Background: IPv4 address shortage and NAT

IPv4 addresses are exhausted, so NAT (Network Address Translation) was invented to mitigate the problem.

Most machines use private IP addresses; when they need to access public services, their traffic must pass through a NAT device, which performs SNAT (Source NAT) to replace the private srcIP:Port with the NAT’s public IP:Port, allowing return traffic.

For more on NAT, see "(译) NAT - 网络地址转换（2016）".

1.2 Requirement: Point‑to‑point connection between two NATed machines

Two machines behind NAT cannot directly use each other’s private IPs (e.g., 192.168.1.x). Tailscale creates a WireGuard® tunnel to solve this, but the underlying techniques apply to many scenarios such as WebRTC, VoIP, and online games.

1.3 Solution: NAT traversal

1.3.1 Two prerequisites: UDP + direct socket control

To design your own NAT traversal protocol you must:

Base the protocol on UDP (TCP adds unnecessary complexity; QUIC can be used if a stream‑oriented connection is needed).

Have direct control over the socket to send and receive extra packets outside the main protocol.

1.3.2 Backup: Relay

If direct socket control is impossible, a local proxy (relay) can be used, adding an extra layer but requiring no changes to existing applications.

1.4 Challenge: Stateful firewalls and NAT devices

We now need to build a bidirectional UDP connection despite stateful firewalls and NAT mapping.

2 Traversing Firewalls

Most stateful firewalls allow all outbound traffic and block inbound traffic by default. They track each packet and allow the corresponding inbound packet if they have seen the outbound one.

For UDP, the rule is simple: if the firewall has seen an outbound packet, the matching inbound packet is allowed.

Some very relaxed firewalls allow any inbound packet matching the source IP and port, but these are rare.

2.1 Default behavior (policy)

Allow all outbound connections.

Block all inbound connections.

2.2 Distinguishing inbound and outbound packets

Stateful firewalls record each packet; when a response arrives, they check the recorded state to decide whether to allow it.

2.3 Firewall orientation scenarios

2.3.1 Same orientation (server reachable)

If the server’s IP is directly reachable, a client‑to‑server direct connection or hub‑and‑spoke topology works.

2.3.2 Different orientation (both sides behind firewalls)

Both sides must initiate connections simultaneously; otherwise the firewall will drop packets. Options include reconfiguring firewalls or using side channels.

2.4 Side channels for coordination

Side channels (e.g., XMPP, WebRTC signalling, Tailscale’s coordination server, or DERP) provide a low‑bandwidth, tolerant link to exchange IP:Port information.

2.5 Firewall state cleanup

Stateful firewalls often expire idle UDP sessions (e.g., after 30 seconds). Keepalive packets or out‑of‑band reconnection are needed.

3 The Essence of NAT

3.1 NAT devices vs. stateful firewalls

NAT devices are enhanced firewalls that also modify packet addresses.

3.2 NAT traversal and SNAT/DNAT

We mainly deal with Source NAT (SNAT); Destination NAT (DNAT) does not affect traversal.

3.3 SNAT purpose: address shortage

SNAT lets many private devices share a few public IPs, enabling continued Internet growth despite IPv4 scarcity.

3.4 SNAT process (home router example)

Device sends UDP packet 192.168.0.20:1234 → 7.7.7.7:5678.

Router performs SNAT, picking a public port (e.g., 2.2.2.2:4242) and creates a mapping.

Packet leaves with source 2.2.2.2:4242.

Responses are reverse‑translated back to the private address.

3.5 SNAT challenges for traversal

Both sides need to know each other’s public IP:Port before they can initiate communication, which is impossible until an outbound packet creates the mapping.

3.6 STUN (Session Traversal Utilities for NAT)

STUN servers tell a client the public IP:Port they appear to come from. Sharing this information with the peer reduces the problem to firewall traversal.

The STUN protocol includes additional features (obfuscation, authentication) that are irrelevant for simple address discovery.

4 Traversing NAT+Firewall: STUN

STUN works well for many home routers but fails with enterprise‑grade NATs that are more restrictive.

4.1 Why STUN may not work

Some NAT devices are very strict and will not allow inbound packets unless they match the exact destination address used for the outbound packet.

4.2 When STUN fails, fallback to relays (TURN, DERP)

TURN is a classic relay protocol but is rarely used by Tailscale. Instead, Tailscale uses DERP (Detour Encrypted Routing Protocol), an HTTP‑based encrypted relay.

4.3 Summary of STUN + fallback

With STUN you can achieve direct connections in ~90 % of cases; the remaining ~10 % fall back to relays.

5 Midway Lesson: NAT Terminology

5.1 Early terms

Full Cone

Restricted Cone

Port‑Restricted Cone

Symmetric NAT

5.2 Recent research and new terms

RFC 4787 defines Endpoint‑Independent Mapping (EIM) and Endpoint‑Dependent Mapping (EDM). The “easy” NATs are EIM; “hard” NATs are EDM.

5.3 Cone types revisited

Cone types combine NAT mapping behavior and firewall behavior, resulting in a matrix of Full Cone, Restricted Cone, Port‑Restricted Cone, and Symmetric NAT.

5.4 Simplified NAT classification for traversal

Endpoint‑Independent NAT mapping (easy NAT)

Endpoint‑Dependent NAT mapping (hard NAT)

5.5 Additional NAT specifications

RFC 4787 (UDP)

RFC 5382 (TCP)

RFC 5508 (ICMP)

6 Fallback to Relay: TURN, DERP

6.1 Problem recap and backup (relay)

If direct traversal fails, a relay provides a guaranteed but higher‑latency path.

6.2 Relay protocols

TURN – classic but rarely used by Tailscale.

DERP – Tailscale’s own HTTP‑based encrypted relay, also used for connection upgrades.

6.3 Summary

With relays, success rate approaches 100 % even in the worst cases.

7 Enterprise‑grade Improvements

7.1 Brute‑force port scanning for hard NAT

When STUN fails, one side can scan all 65 535 ports on the other side’s public address. At 100 pps this takes ~10 minutes.

7.2 Birthday‑paradox optimization

Open multiple ports on the hard side (e.g., 256) and have the easy side probe randomly. This gives a 50 % success chance in ~2 seconds and >99 % in ~20 seconds.

7.3 Dual hard NAT scenario

When both sides are hard NATs, the search space becomes two‑dimensional (src port, dst port). Achieving 99.9 % success may require ~170 000 probes per side (~28 minutes at 100 pps).

7.4 Port‑mapping protocols (UPnP IGD, NAT‑PMP, PCP)

If the local gateway supports any of these, you can request a public port mapping, effectively turning the NAT into an “easy” NAT.

7.5 Multiple NATs

In multi‑NAT topologies, only the outermost NAT matters for traversal; inner NATs are transparent.

7.6 Carrier‑grade NAT (CGNAT)

CGNAT adds another NAT layer beyond the home router, making port‑mapping harder. Hairpinning (NAT loopback) can help when both peers are behind the same CGNAT.

7.7 IPv6

IPv6 eliminates NAT but stateful firewalls still exist. Side channels and relays remain useful. IPv4‑only peers behind NAT64/DNS64 need CLAT or manual handling.

7.8 Integrating everything with ICE

ICE (Interactive Connectivity Establishment) gathers all possible candidate addresses (LAN, STUN, port‑mapped, relay) and probes them in parallel, selecting the best reachable path. Tailscale starts with DERP (relay) for immediate connectivity, then upgrades to a better path when discovered.

7.9 Security

All upper‑layer protocols must provide end‑to‑end authentication and encryption (e.g., TLS for QUIC, WireGuard keys). Path‑discovery packets should also be authenticated.

8 Conclusion

Implementing robust NAT traversal requires:

A UDP‑based protocol with direct socket access.

A side channel to exchange candidate addresses.

STUN servers for public address discovery.

A fallback relay network (DERP).

Then you must:

Enumerate all local IP:Port candidates.

Query STUN to learn your public address and NAT difficulty.

Use port‑mapping protocols to obtain additional public ports.

Detect and handle NAT64/CLAT if present.

Exchange all candidates with the peer via the side channel.

Optionally start communication over a relay.

Probe all candidates (including birthday‑paradox scans for hard NATs).

Upgrade to the best path when found.

Fallback to other candidates or the relay if the current path fails.

Ensure all traffic is encrypted and authenticated.

With these techniques you can achieve reliable, low‑latency, peer‑to‑peer connections in virtually any network environment.