Over the years I've done a lot of work on P2P protocols. One challenge which consistently arises is devising a good P2P NAT traversal strategy, i.e. one which doesn't require all data between clients be relayed through a server.

Common wisdom divides NAT's into several categories, depending upon how they map internal to external endpoints, and what traffic is allowed into the private network. For example, 'cone', 'restricted', and 'symmetric.' Several strategies are specified to allow connections with one or more endpoints behind one of these NAT's to succeed and persist.

Based on these categories (and a few additional heuristics), there's are several well-researched and tested work to choose from. STUN (UDP NAT traversal) and STUNT (TCP NAT traversal) both provide good behavioral guidelines for NAT traversal, and there are several third party implementatoins of each. Not to be left out, Microsoft's own Teredo protocol is a NAT traversal strategy similar to IP tunneling over STUN, and is built into Windows XPSP2 and later.

Unfortunately, nothing's ever as easy as you'd hope. Within each of the NAT categories mentioned earlier there is a huge variety of behavior. Some of a given NAT's behavior is intentional, some a resource-based compromise, and some can be chalked up to bugs. I don't believe any NAT-traversal strategy can succeed against the full set of intentional behaviors within a bucket (such as 'port restricted'), let alone the other kinds of challents. And so, there will always be machines behind NAT's for which all known P2P NAT traversal algorithms fail.

Still, it works well enough to be incorporated into your application. If you have a good success detection mechanism and a back-up data relay, you can ensure all of your clients can talk to each other.

Here's my (unsolicited) advice.

1. Don't trust the reliability claims of any NAT traversal mechanism unless you've seen good data on it based on wide (thousands of seats, at the least) deployment. Many people advertise success rates based on limited testing, because doing extensive testing is Hard.
2. Always have a fallback. If you really, truly need any arbitrary pair of machines to be able to talk to each other, you're going to have to have some sort of a data relay, for example a server which can relay data as well as NAT traversal signalling.
3. Don't try to invent a new NAT traversal mechanism yourself without knowing what else is out there. You might be the one person in a million who can do a better job, but there's a lot of great work which has already been done and tested. Make sure you read up on STUN, STUNT, and/or Teredo before you decide to roll your own. Trust me, making your own NAT traversal and having it work well isn't easy.

Good luck!