Android P2P (direct-connection) over the Internet (behind NAT)

Question

I'm starting a small project, basically a multiplayer (as in more than two players) variation of the classic Battleship game.

One problem that I'm trying to resolve before I dive into coding is the problem of communication between the multiple players. A current possibility is to use a central HTTP server as the central hub for communication (coupled with the Android C2DM API to allow push communication from the HTTP server to the devices). This seems a nice solution, because in theory as long as you have access to the Internet it should work perfectly, whether you are behind a NAT or not.

However, the proposed solution has the disadvantage of existing one single point of failure/extra load (the webserver). So I'd like to try other options. I thought of making direct connections using Sockets between the clients (with the webserver just being used as an initial meeting point), however this would only work well if all the devices were in the same network. Considering that today we are almost always behind the NAT of a router how can I achieve direct communication? I've been reading about hole punching but I can't find any good library that is well documented (containing good examples of use) and that works on Android for sure. Also most (if not all) hole punching techniques (STUN, ICE, etc...) widely available only work with UDP, which is fine for audio/video and real time multiplayer games that can lose some messages, but for a multiplayer turn-based game it's important to guarantee the delivery of the data of each turn (something that it's not possible directly with UDP).

So any ideas how to achieve a reliable hole punching (preferably over TCP) between Android devices behind NAT? It doesn't have to work on 100% of the cases (some stranger NATs may not be supported) but it would be nice if it worked on most cases.

Solution

use xmpp via smack over gtalk. You don't have to worry about server and single point of failure. let google worry about that! I have written Tetris to make it play against two player using gtalk as a communication layer. http://code.google.com/p/tetrads-drop-lite/ You can try MUC if you want more player.