The technology disclosed addresses initiation of peer-to-peer media exchange sessions, with traversal of NAT and firewall devices, in a manner adapted to roaming. In particular, involves preliminary determination of NAT/firewall topology, which reduces latency at initiation, and hole punching technologies to select a routing and traversal strategy that reduce reliance on external media relay devices.