sockets peer to - Android P2P (direct-connection) over the Internet (behind NAT)
You're pretty much forced to use an intermediary. You can look up Natblaster for a mechanism that will work for establishing TCP connections between some NATed devices, but it's not something that you can use in Android without rooting both devices. And even then, it's experimental.
The best is probably to use an existing federated messaging system like jabber.
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.