According to:
https://en.wikipedia.org/wiki/Network_address_translation
there are 4 types of NAT configurations:
Full-cone, Address restricted, Port restricted, and Symmetric.
Now, suppose we have client A and client B on separate networks and are hidden behind their own separate NATs.
What combinations of "client A NAT type" + "client B NAT type" would require a TURN server to be involved (i.e. not solvable by the STUN protocol) if they want to p2p communicate?
For example, I would suspect:
" client A NAT = Symmetric + client B NAT = Symmetric " would require a TURN server.
What are the rest of the combinations?
Symmetric to Symmetric : TURN
Symmetric to Port Restricted : TURN
Symmetric to Address Restricted: STUN (but probably not reliable)
Symmetric to Cone: STUN
Everything else can be through STUN.
There are known techniques whereby the port allocation algorithm can be guessed for a Symmetric NAT (typically a symmetric NAT just keeps using the next incremental port number). Thus, if you know through STUN that the NAT is symmetric and observe through STUN tests that the port mapping for two different addresses is only off by one, then the next port allocation can be guessed and used as an address candidate.
Even for the NAT pairings listed as STUN above, STUN isn't 100% reliable and is less reliable for TCP than it is for UDP. Relays in the cloud get you closer to 100% traversal.