NAT traversal (STUN, ICE, TURN)

Deep dive

How it works

Parts

• NAT behaviour (RFC 4787) — mapping and filtering are each endpoint-independent, address-dependent or address-and-port-dependent. The old full-cone/symmetric labels are called inadequate there; "symmetric" survives for destination-dependent mapping.
• STUN server — answers a Binding request with the source address it saw (server-reflexive address).
• Signalling channel — any path between peers (for example SDP offer/answer) for candidates and credentials.
• ICE agent — gathers, orders pairs, checks, nominates, keeps alive.
• TURN server — allocates a relayed address and forwards between client and peer.

Operations

1. Gather candidates: host (local interfaces), server-reflexive (STUN Binding), relayed (TURN Allocate).
2. Exchange candidates, a username fragment and a password via signalling. Trickle ICE (RFC 8838) sends candidates as found and starts checks at once; end-of-candidates closes the list.
3. Pair local x remote, replace reflexive locals by their base, prune duplicates, sort by pair priority; default limit 100 pairs.
4. Run checks: STUN Binding requests with PRIORITY, short-term credentials (MESSAGE-INTEGRITY), a role (ICE-CONTROLLING or -CONTROLLED) and a tiebreaker. One check per Ta (50 ms default); RTO at least 500 ms.
5. A request from an unknown source yields a peer-reflexive candidate. A received check triggers an immediate check back on that pair.
6. The controlling agent sends USE-CANDIDATE on a valid pair (regular nomination; aggressive nomination is gone). That pair is selected.
7. Keep alive: a keepalive after 15 s idle (Tr), plus consent freshness (RFC 7675): Binding requests about every 5 s (jitter 0.8-1.2, never below 4 s); after 30 s without a valid response the sender must stop.
8. No direct pair: use the relayed pair. TURN allocations last 10 minutes by default, permissions 5, channel bindings 10, unless refreshed.

 A --Binding--> [NAT A] --> STUN S <-- [NAT B] <--Binding-- B   (learn A_pub, B_pub)
 A <======= candidates + ufrag/pwd via signalling =======> B
 A --check--> NAT B drops it (no state yet);  B --check--> NAT A admits it
 A <== triggered check ok, USE-CANDIDATE ==> B      direct path
 no pair validates:  A <-> TURN relay <-> B

Priorities. Candidate priority = (2^24)(type preference) + (2^8)(local preference) + (256 - component ID); type preference 0-126 (recommended 126 host, 110 peer-reflexive, 100 server-reflexive, 0 relayed), local preference 0-65535 (unique per candidate of one type). Pair priority = 2^32MIN(G,D) + 2MAX(G,D) + (G>D?1:0), G from the controlling agent's candidate, D from the controlled agent's. MIN dominates, so a pair ranks by its weaker end: with the recommended preferences any pair with a relay sorts after every pair without one.

NAT behaviour decides success. With endpoint-independent mapping the STUN-reported address is the one the peer must hit, whatever the filtering. With destination-dependent mapping the NAT picks a new port per destination, the reported port is wrong for the peer, and the relay is needed. RFC 4787 REQ-1 requires endpoint-independent mapping; not every device complies.

Timing. A first check is often dropped (the other NAT has no state yet); retransmits and the triggered check cover it, so both sides must check at about the same time (Ford et al.). RFC 4787 REQ-5: a UDP mapping timer must not expire in under two minutes (five or more recommended), so 15 s keepalives stay inside.

TCP and IPv6. ICE-TCP (RFC 6544) adds TCP candidates; TURN also runs over TCP, TLS or DTLS, passing UDP-blocking networks. IPv6 needs no NAT, but stateful gateways still drop unsolicited inbound packets (RFC 6092); checks from both sides open the pinhole, so ICE remains.

Code

Rust, std only: RFC 8445 candidate and pair priorities with checklist ordering, plus a STUN Binding request encoder and XOR-MAPPED-ADDRESS decoder (RFC 8489, cookie 0x2112A442), round-tripped on a constructed response; no network.

use std::net::{IpAddr, Ipv4Addr, Ipv6Addr, SocketAddr};
// RFC 8445 5.1.2 candidate priority, 6.1.2.3 pair priority
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Kind { Host, Prflx, Srflx, Relay }

fn type_pref(k: Kind) -> u32 {
    match k { Kind::Host => 126, Kind::Prflx => 110, Kind::Srflx => 100, Kind::Relay => 0 }
}
/// 2^24*type pref + 2^8*local pref (0..=65535) + (256 - component ID 1..=256)
pub fn candidate_priority(k: Kind, local_pref: u32, component: u32) -> u32 {
    (type_pref(k) << 24) + (local_pref << 8) + (256 - component)
}
/// G = controlling agent's candidate priority, D = controlled agent's.
pub fn pair_priority(g: u32, d: u32) -> u64 {
    ((g.min(d) as u64) << 32) + 2 * g.max(d) as u64 + (g > d) as u64
}
pub struct Pair { pub local: u32, pub remote: u32, pub prio: u64 }
/// All local x remote pairs, highest priority first.
pub fn checklist(local: &[u32], remote: &[u32], controlling: bool) -> Vec<Pair> {
    let mut v = Vec::with_capacity(local.len() * remote.len());
    for &l in local { for &r in remote {
        let (g, d) = if controlling { (l, r) } else { (r, l) };
        v.push(Pair { local: l, remote: r, prio: pair_priority(g, d) });
    } }
    v.sort_by(|a, b| b.prio.cmp(&a.prio));
    v
}
// RFC 8489 STUN: Binding request, XOR-MAPPED-ADDRESS
const COOKIE: u32 = 0x2112_A442;

/// Header only: type 0x0001, length 0, cookie, 96-bit transaction ID.
pub fn binding_request(txid: [u8; 12]) -> [u8; 20] {
    let mut m = [0u8; 20];
    m[0..2].copy_from_slice(&0x0001u16.to_be_bytes());
    m[4..8].copy_from_slice(&COOKIE.to_be_bytes());
    m[8..].copy_from_slice(&txid);
    m
}
fn xor_mask(txid: &[u8; 12]) -> Vec<u8> { // cookie || txid, applied in network byte order
    [&COOKIE.to_be_bytes()[..], &txid[..]].concat()
}
/// Server side, for the test: success response 0x0101 with XOR-MAPPED-ADDRESS 0x0020.
pub fn binding_response(txid: [u8; 12], a: SocketAddr) -> Vec<u8> {
    let k = xor_mask(&txid);
    let mut attr = vec![0u8, if a.is_ipv4() { 1 } else { 2 }];
    attr.extend((a.port() ^ (COOKIE >> 16) as u16).to_be_bytes());
    let ip = match a.ip() { IpAddr::V4(v) => v.octets().to_vec(), IpAddr::V6(v) => v.octets().to_vec() };
    attr.extend(ip.iter().zip(k.iter()).map(|(x, m)| x ^ m));
    let mut m = Vec::new();
    m.extend(0x0101u16.to_be_bytes());
    m.extend((4 + attr.len() as u16).to_be_bytes()); // attribute value lengths here are multiples of 4
    m.extend(COOKIE.to_be_bytes());
    m.extend(txid);
    m.extend(0x0020u16.to_be_bytes());
    m.extend((attr.len() as u16).to_be_bytes());
    m.extend(attr);
    m
}
/// Client side: check cookie and transaction ID, walk attributes, XOR-decode.
pub fn parse_xor_mapped(msg: &[u8], txid: &[u8; 12]) -> Option<SocketAddr> {
    if msg.len() < 20 || msg[0..2] != [0x01, 0x01] || msg[4..8] != COOKIE.to_be_bytes() || msg[8..20] != txid[..] { return None; }
    let end = (20 + u16::from_be_bytes([msg[2], msg[3]]) as usize).min(msg.len());
    let (mut i, k) = (20, xor_mask(txid));
    while i + 4 <= end {
        let (t, l) = (u16::from_be_bytes([msg[i], msg[i + 1]]), u16::from_be_bytes([msg[i + 2], msg[i + 3]]) as usize);
        let v = msg.get(i + 4..i + 4 + l)?;
        if t == 0x0020 && l >= 8 {
            let port = u16::from_be_bytes([v[2], v[3]]) ^ (COOKIE >> 16) as u16;
            let x: Vec<u8> = v[4..].iter().zip(k.iter()).map(|(b, m)| b ^ m).collect();
            let ip = match (v[1], x.len()) {
                (1, 4) => IpAddr::V4(Ipv4Addr::new(x[0], x[1], x[2], x[3])),
                (2, 16) => IpAddr::V6(Ipv6Addr::from(<[u8; 16]>::try_from(&x[..]).ok()?)),
                _ => return None,
            };
            return Some(SocketAddr::new(ip, port));
        }
        i += 4 + ((l + 3) & !3); // attributes are padded to 4 bytes
    }
    None
}
fn main() {
    let host = candidate_priority(Kind::Host, 65535, 1);
    let srflx = candidate_priority(Kind::Srflx, 65535, 1);
    let relay = candidate_priority(Kind::Relay, 65535, 1);
    assert_eq!((host, srflx, relay), (2_130_706_431, 1_694_498_815, 16_777_215));
    assert_eq!(pair_priority(host, srflx), (1_694_498_815u64 << 32) + 2 * 2_130_706_431 + 1);
    assert_eq!(pair_priority(srflx, host), pair_priority(host, srflx) - 1); // G>D tie-break bit
    // MIN(G,D) dominates: pairs with a relay candidate sort after all pairs without.
    let pairs = checklist(&[host, srflx, relay], &[host, relay], true);
    let order: Vec<(u32, u32)> = pairs.iter().map(|p| (p.local, p.remote)).collect();
    assert_eq!(order, [(host, host), (srflx, host), (host, relay), (relay, host), (srflx, relay), (relay, relay)]);
    // STUN: request bytes; response round trip for an IPv4 and an IPv6 address.
    let tx = [7u8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
    assert_eq!(&binding_request(tx)[..8], &[0, 1, 0, 0, 0x21, 0x12, 0xA4, 0x42]);
    for a in ["203.0.113.9:54321", "[2001:db8::7]:40000"] {
        let a: SocketAddr = a.parse().unwrap();
        let resp = binding_response(tx, a);
        assert_eq!(parse_xor_mapped(&resp, &tx), Some(a));
        assert_eq!(parse_xor_mapped(&resp, &[0; 12]), None); // wrong transaction ID
    }
    let wire = binding_response(tx, "203.0.113.9:54321".parse().unwrap());
    assert_eq!(wire[26..28], (54321u16 ^ 0x2112).to_be_bytes()); // port XOR cookie high 16 bits
    // Measure: 16 x 16 pairs built, prioritised, sorted.
    let cands: Vec<u32> = (0..16u32).map(|i| candidate_priority([Kind::Host, Kind::Srflx, Kind::Relay, Kind::Prflx][i as usize % 4], 65535 - i, 1)).collect();
    let (n, t0, mut sink) = (20_000, std::time::Instant::now(), 0u64);
    for _ in 0..n { sink = sink.wrapping_add(std::hint::black_box(checklist(&cands, &cands, true))[0].prio); }
    let dt = t0.elapsed().as_secs_f64();
    println!("{:.1} us per 256-pair checklist, {:.1} M pairs/s (sink {})", dt / n as f64 * 1e6, 256.0 * n as f64 / dt / 1e6, sink);
}

Compiled and run on this Mac (Apple M4 Pro), all asserts pass (priorities 2130706431, 1694498815, 16777215 for host, server-reflexive, relayed). Measured on this Mac (Apple M4 Pro, release build, 20,000 runs): about 1.3 us per 256-pair checklist (build, priority, sort), about 200 M pairs/s.

Complexity and constants

• Pairs |L| x |R|, sorted O(n log n), pruned to 100; CPU is microseconds, network time dominates.
• Pacing: 100 checks at Ta = 50 ms take on the order of 5 s if all run (arithmetic); pair order matters.
• STUN: 20-byte request, 32-byte IPv4 response (arithmetic); UDP up to Rc = 7 sends, failed after 39.5 s by default.
• TURN header: ChannelData 4 bytes, Send/Data indications 36 (RFC 8656).

Efficiency

• Cost: setup is a few STUN round trips plus one check wave, bound by RTT and signalling delay, not CPU. A direct path adds no bytes; a relayed one passes each stream through the server twice, a cost RFC 8656 names.
• Levers:
  • Trickle ICE — checks overlap gathering, faster setup (RFC 8838, no figure) — fast signalling.
  • Priorities and pruning — fewer checks before a direct hit (RFC 8445) — always.
  • ChannelData instead of Send indications — 4 instead of 36 bytes per packet (RFC 8656) — small relayed packets such as audio.
• Naive → standard → state of the art:
  • Always relay · simplest, highest operator cost and latency
  • STUN plus ICE, direct first, relay fallback · one check wave
  • Trickle ICE, relay live at once, upgraded to direct when found · fastest start

Implementation notes

• Check from the socket that learned the mapping; STUN's two zero top bits tell it from data (RFC 8489).
• Reject checks without valid MESSAGE-INTEGRITY.
• Prefer XOR-MAPPED-ADDRESS: some NATs rewrite payload bytes that look like their address.
• Refresh TURN allocation, permissions and channels in time.

Pitfalls

• Using the STUN-reported port for every peer despite destination-dependent mapping.
• Ignoring consent expiry (30 s); leaving TURN open without credentials and quotas; relying on NAT loop-back between two peers behind one NAT instead of host candidates.

Variants and alternatives

In production

• Browser calls (WebRTC) run ICE per call; RTP under SRTP uses the selected pair.
• Tailscale uses DERP relays as fallback and side channel, then upgrades to direct paths (its blog).
• Valve's GameNetworkingSockets lists ICE-based NAT traversal for peer-to-peer game links.
• WireGuard-style meshes, IoT remote access and torrent clients (swarming) follow it.

Implementations

Sources

• A. Keranen et al., Interactive Connectivity Establishment (ICE), RFC 8445, 2018. RFC
• M. Petit-Huguenin et al., STUN, RFC 8489, 2020. RFC
• T. Reddy et al., TURN, RFC 8656, 2020. RFC
• F. Audet, C. Jennings, NAT Behavioral Requirements for UDP, RFC 4787, 2007. RFC
• STUN Usage for Consent Freshness, RFC 7675, 2015. RFC; Trickle ICE, RFC 8838, 2021. RFC
• B. Ford, P. Srisuresh, D. Kegel, Peer-to-Peer Communication Across Network Address Translators, USENIX ATC 2005. paper
• Tailscale, How NAT traversal works (blog). post