next »

[Garthy]

I am working on a project that has a design aspect that requires an arbitrary number of client machines to be able to chat to each other directly via UDP. Generally, one will be acting as a server, the others as clients.

I have no difficulties in writing such a server- in fact, it's done. Easy stuff. However, issues start to come up with the problem of NAT traversal- ie. making sure a hole can be automatically punched into a NAT firewall on both sides of a connection to allow them to talk. The person running the server may not have the skill, knowledge, or inclination required to set up a router to port forward properly.

When I'd originally set out, I'd assumed that this hole punching wouldn't be overly difficult. Big mistake. I've dug into it a bit more recently, and one common theme I've seen is "don't try this yourself", as there are just too many combinations of NAT implementations and configurations to be viable. I believe these claims. I don't want to sink a whole lot of time into reinventing the wheel, poorly.

Digging, I started to run into things such as STUN and TURN. Now, I'm not looking for a TURN-based solution really, as it'd mean I'd need to supply a proxy capable of handling a whole lot of traffic. More digging shows up ICE, and from that, libnice. However, not a lot of applications seem to actually use it, the mailing list is mostly empty, and the documentation lacks examples or a tutorial. Also, I then enter the realm of possibly needing to set up a STUN and TURN server. I don't even know how to choose a good one, what is available, and what I'd need to do to maintain it. Things such as RakNet seem to handle some aspect of it too. There are various commercial solutions available all over the place, some public, some not.

At this point I'm not really sure what to do. I don't want to sink a lot of time into this. However, ripping out the bits of the design that require this is going to really hurt. Telling people they need to reconfigure their firewalls to use the app is going to make people say "pass" instantly. Most wouldn't have the first clue as to where to start, and I don't want to be left supporting this for arbitrary users and configurations. The cost required to host a server on a public IP to act as the server (bypassing the problem entirely) is going to be impractically expensive.

Basically, every option is extremely poor, and I lose out in some way, in every case.

The project is cross-platform Linux/Windows. I am just one person. I cannot stretch myself so thin on such an issue.

Thoughts? In particular, if you've run into this problem specifically, or you've got some experience in this particular field, *please* share your experiences.

[Lord Tim]

I had this exact problem a while ago trying to set up multiplayer in flash. Adobe just recently released the RTFMP stuff, and it is supposed to work all automagically and give you peer to peer around NAT by connecting though Adobe's own servers. It doesn't seem to work very well though, and I ran in to the same problems you are having. In researching it, I did find some cool stuff though...

NAT stuff checker:
http://cc.rtmfp.net/

Maybe this works? I don't know exactly:
http://numb.viagenie.ca/

[Garthy]

Cheers for the info Lord Tim.

The first link mentions RTFMP ( http://en.wikipedia.org/wiki/Real_Time_Media_Flow_Protocol ), which seems to be a Flash-centric Adobe protocol?

The second seems to be an implementation of STUN/TURN, might not be useful in general as a TURN server is basically a proxy (from what I can tell), and they're not going to like shifting volumes of traffic for someone else very long. :} But if someone (eg. myself) went that way, could be useful to test against a real server.

For my part, I am likely going to re-look at the design and see if I can change it around a fair bit to suit. I'm getting the feeling this could be nasty work, and I'm going to have to assume a decent number of setups will not be able to work properly with this sort of thing, even if I could get something like ICE working well in a decent time. ie. change the design assumption that clients will require this ability to one where they benefit from it, but do not require it.

Any further thoughts from people who have touched on this sort of problem before, what did you find, and what were your experiences?

[muku]

I feel a bit stupid to comment on this at all since I know virtually nothing about the topic. On the off chance that it might be helpful: have you looked into the UPnP support some routers/firewalls offer? Obviously this is Windows only, I don't know your platform requirements, and it only works if the player has a device which supports this protocol, but it might be a way to get automatic port forwarding for at least a subset of your player base.

[Garthy]

I feel a bit stupid to comment on this at all since I know virtually nothing about the topic. On the off chance that it might be helpful: have you looked into the UPnP support some routers/firewalls offer? Obviously this is Windows only, I don't know your platform requirements, and it only works if the player has a device which supports this protocol, but it might be a way to get automatic port forwarding for at least a subset of your player base.

Don't feel stupid. As far as I can tell, UPnP is part of the whole equation. My understanding is that some devices don't support it, it doesn't always work very well, has been plagued by security problems, a bundle of people turn it off, but those that don't are probably the sort of people who most need an automated solution anyway. Some part of it seems to be designed for explicitly allowing port forwarding, which is one way to solve the problem entirely. Having said that, this is just surface information, I fear that I don't know too much about it either.

Cheers for throwing that one in.

It's probably too early to come to a solid conclusion, but my guess at this point is that there are going to be a whole bunch of ways of getting it to work, each allowing a subset of the available computers to perform as needed, much like a gigantic Venn diagram. And much like a Venn diagram, there's always going to be some systems that just lie on the outside of it all. As such, any design that assumes that even a decent subset of people are going to be able to get it to work, short of sinking a lot of time into getting the percentage as high as possible, is going to be a poor one.

[blundis]

From my experience of playing multi-player on line games quite a lot, the only "bulletproof" method is some kind of proxy service, requiring you to set up a server to run all the traffic through.

I don't actually think this is a huge problem, most people should be capable of opening a port in their firewall or router and most of the time it's easy to explain how since routers differ only slightly in set-up (at least the consumer ones), and if someone can't figure it out they'll just have to play as a client. Of course, a central "lobby" or matchmaking type server just too connect people together would help this, it can be as simple as listing IP-addresses on a website.

[Garthy]

From my experience of playing multi-player on line games quite a lot, the only "bulletproof" method is some kind of proxy service, requiring you to set up a server to run all the traffic through.

What sort of games are we talking about here? I had guessed that the big players could dedicate a whole bunch of time into solving this, and that for "bigger" games it was less of a problem.

If you've played such games quite a lot, what would your assessment be in terms of the number of games that just needed this kind of manual configuration, versus the number that figured it out on their own? I'm very curious, please share.

I don't actually think this is a huge problem, most people should be capable of opening a port in their firewall or router and most of the time it's easy to explain how since routers differ only slightly in set-up (at least the consumer ones), and if someone can't figure it out they'll just have to play as a client. Of course, a central "lobby" or matchmaking type server just too connect people together would help this, it can be as simple as listing IP-addresses on a website.

Some people definitely have troubles with this. I've had to talk people through implementing similar things over the phone a few times, and you'd be surprised how hard it can be instructing someone to make their router-supplied IP static and forward ports when they've never had to learn anything more than plug-it-in-and-it-works! The target audience includes people who just will not be able to figure this out on their own, so sadly I have to remain aware of it.

Implementing matchmaking won't be a major problem for what I'm doing, though getting enough clients able to run as the server might be. Cheers for the hints on that subject.

[mewse]

Usually people do NAT hole-punching as part of the matchmaking process.  The matchmaking server tells each participant what address and port the other participants are at, and the participants can all then talk to each other (effectively, each participant "punches a hole" through their own NAT device, to allow the person on the other side to talk to them).  As long as everybody has a NAT device with conical connection mapping (or "Moderate" NAT type, as Microsoft calls it), that approach works pretty well.

Microsoft's XBox has really improved the NAT situation among game players;  my current numbers suggest that less than 10% of the game players out there still have NAT devices with parallel or random connection mapping (or "Strict" NAT type, in Microsoft words).

[Garthy]

Usually people do NAT hole-punching as part of the matchmaking process.  The matchmaking server tells each participant what address and port the other participants are at, and the participants can all then talk to each other (effectively, each participant "punches a hole" through their own NAT device, to allow the person on the other side to talk to them).

That is a rough summary of what I am trying to do at a higher level, with my post being an attempt to dig further into the bit you've sumarised as "effectively 'punches a hole'".

As long as everybody has a NAT device with conical connection mapping (or "Moderate" NAT type, as Microsoft calls it), that approach works pretty well.

I'm not sure what conical mapping or moderate NAT type map to exactly. Would they be equivalent to full cone as per:

http://en.wikipedia.org/wiki/Network_address_translation

and RFC 3489? Or does it perhaps map to multiple types? Either way, is assuming that everyone has such a conical mapping NAT device really feasible? I would imagine there are many types out there. Is there an indication that (say) most commercial home routers would be of this type?

Microsoft's XBox has really improved the NAT situation among game players;  my current numbers suggest that less than 10% of the game players out there still have NAT devices with parallel or random connection mapping (or "Strict" NAT type, in Microsoft words).

I think I'd read something along those lines. Not being familiar with XBox development, is there a standard interface/API that XBox developers have access to that handles the NAT traversal problem for them? Basically- when you want to do this, which API or similar do you actually use to do it? Or are most apps/games just sitting on the matchmaking server, waiting for an incoming packet, noting the source IP/port, and then relaying that to other clients and assuming it'll behave as per a full cone? Or something else?

Also, when you say 10%, what are these numbers based on? Experience with a particular type of game? Or a range of apps? Does it imply that the remaining 90% fall into the "conical" category you mentioned above?

[mewse]

I'm not sure what conical mapping or moderate NAT type map to exactly. Would they be equivalent to full cone as per:

http://en.wikipedia.org/wiki/Network_address_translation

I've had a look over the wikipedia article.  In the wikipedia article, what they call a "full cone" is what Microsoft calls "Open" NAT type, and what they call a "restricted cone" (address or port) is what Microsoft calls "Moderate" NAT, and what they call "Symmetric" is what Microsoft calls "Strict" NAT.

The thing you have to realise is that there are no "standards" with NAT;  NAT was basically invented independently by a lot of different companies, and every different device has a slightly different implementation.  These types that we talk about are just classification schemes, trying to roughly group together the most important types of behaviours of NAT devices that have been observed in the wild.  There are lots of subtle different behaviours, but as they were setting out XBox Live, they figured out that from the point of view of playing peer-to-peer networked games, their three "Open", "Moderate", and "Strict" NAT types were the only ones that mattered.  This made NAT a LOT easier to think about!

Most consoles have a built-in matchmaking service which will handle NAT traversal for you.  On PC, different games have different implementations, but many (most?) mainstream games use networking middleware to perform this function.  But at a basic level, here's how it works..  let's assume we have three players, Player A (hosting a game), Player B (playing the game), and Player C (who wants to join).

Here's how the exchange works:

Player C -> Matchmaker:  "I want to join Player A's game"

Matchmaker -> Player C:  "Okay, he's at this address:port"
Matchmaker -> Player A:  "Player C is about to join you.  He's at address:port"

Player C -> Player A:  "Hi, I'm player C!" \
Player A -> Player C:  "Hi, I'm player A!" /  sent repeatedly, until both can see each other's messages.  This is the hole-punching!

Now.  At this point, Player A and Player C are both sending messages to each other, using the address that the Matchmaker sees for them.  Let's consider just the message that player A is sending to player C.

If C has "Open" NAT, then everyone sees the same external address/port for him, and anybody can send a message there and he'll receive it.  This is basically like not having a NAT device at all, or just an explicitly forwarded port on the NAT device.  If this happens, then player C will receive player A's message.

If C has "Moderate" NAT, then everyone sees the same external address/port for him, but C will only actually receive the message from A if he's already sent a packet to A.  So if C has sent his message to A before A's message to C arrives, A's message will be received by C.  If not, then A's message will be discarded by the NAT device.  (This is why we send the "Hi!" message repeatedly, until both sides receive it;  depending on network lag, the first several packets may be silently dropped by the NAT device.)

If C has "Strict" NAT, then everyone sees a different external address/port for him, and A's message (addressed to the IP:port seen by the matchmaking server) ends up being sent to the wrong address;  C will never receive it, because C wants to talk to A from a different external IP/port.  This is the nasty case.

Let's assume that C has "strict" NAT.  In this case, we look at what A has.  If A also has "strict" NAT, then the two simply won't be able to talk to each other directly, since neither can find the right address to talk to the other, based upon the address that the matchmaker knows.  Moderate is a similar problem;  since A doesn't know the right address to send his "Hi!" packet to, he can't punch a hole for C to send his packet through.  But if A has "open" NAT, then A will receive a "Hi, I'm Player C!" message from an IP/Port different from the one that the matchmaker told him to expect.  If A accepts this different address/port, then he can successfully talk to C.

B has the same issue as A;  in order for C to fully join and talk to all members of the game, all those other members must be "Open", so that they can receive an arbitrary message from some unknown address claiming to be player C, and then send their packets to that address.


When I say that only about 10% of NAT devices are "strict", it's based on a console online game I worked on and administered for a while post-launch, a few years back.  One of the servers I wrote had clients self-diagnose their NAT types, and we used that information as part of matchmaking (that is, "strict"-type players weren't shown any game sessions which had non-"open" players in them, because we knew that they wouldn't be able to communicate with each other).  This was on PS2 and PSP, several years back;  about 20% open, 70% moderate, 10% strict.  I imagine that the numbers are even better for folks with "next-gen" consoles.  As I mentioned, Microsoft put a lot of pressure on the NAT market when they started their "XBox Live Certified" program, because those devices had to be at least "Moderate" in order to qualify for certification.

Hope I explained that okay?  I know it's kind of a TL;DR wall of text..  :/

[Garthy]

Thankyou for taking the time to make such a detailed post mewse, greatly appreciated.

The MS NAT categories now make sense to me, so thankyou for explaining the mapping. The categories in the wiki page appear to be based on the STUN RFC 3489, which has since been updated with RFC 5389, so it's hard to tell whether they're still accepted groups or not.

And yes, good point re the classifications being rough groupings. As you mention, a lot of the NAT tech in use was developed independently, meaning there are a whole bunch of subtleties in play, even with an ideal grouping.

The evening before I saw your post I'd put together a rough algorithm that would seem to work with what I have in most cases, based on the distribution of devices discussed. I feel a bit vindicated that the thing I came up with is reasonably similar to the process you've described and others I've seen online.

Re networking middleware that handles it, do you have any suggestions for things to look at? It appears RakNet handles it to a degree, but I'm not sure of other solutions?

Thanks for clarifying your example of the distribution of the different types of devices. One concern I had was whether your data may have been skewed by the nature of the service. For example, if users with symmetric (strict) NATs couldn't play, they would probably not be represented well.

I had found an RFC or similar that listed a small number of devices and their (rough) behaviour, but I can't find the rotten thing now. :} It had numbers quite similar to yours- namely, symmetric NATs on consumer devices were relatively uncommon (say, 5-10%), and the remaining split was between devices that were either open or restricted. At a guess, it would seem that the ratio of devices in use may be quite close to that which you observed. I haven't had any luck in finding a decent list online beyond that one though.

There are also things such as:

http://tools.ietf.org/html/draft-ietf-behave-nat-udp-08

along with the "XBox Live Certified" program that you mention, which strongly suggests to me that symmetric NATs on such devices are going to be dying out, except perhaps with the tech-friendly crowd, who are going to know how to set up port forwarding anyway, or environments where port traversal is not wanted (eg. businesses, etc), which I'm not as interested in.

And no problems re wall-of-text! There's no practical way to explain a complex and detailed topic without one.

Cheers again for your insight and the time you have taken to explain it all.

[mewse]

I only have personal experience with professional networking middleware, unfortunately.. and I can't really recommend any particular libraries very highly.  It's really just as easy to do the whole thing yourself.  Some middleware tries to make clever guesses to make strict NAT types behave like moderate ones (some technically 'strict' devices have predictable patterns for how they allocate external ports, for example.  If you can guess the correct port to connect to, a moderate client CAN connect to a strict one.  But honestly, I don't think this is worth the bother.)


I'll also note that every company uses different terminology for this stuff.  Microsoft is the only company who calls NAT types "Open", "Moderate", and "Strict".  Most companies talk about "conical" and "parallel" or "symmetric", referring to the external port allocation strategy.  But I think that Microsoft's is the best classification system I've seen, for the purpose of explaining the end-users what's going on.  But if you ever want to make a Sony rep uncomfortable, ask him about how PSN copes with clients who are behind "strict" NAT devices.  He'll spend several awkward seconds pretending not to know what you mean, because he's apparently not allowed to acknowledge Microsoft's terms. 

[Garthy]

I'll probably give it a crack myself based on a revised design that wouldn't require it to be able to succeed all the time. In my particular case, a basic attempt is probably enough. Port prediction is no doubt a fascinating technical problem to solve, but I might leave that one for now.

Whilst I probably won't get the chance to do so, should I run into appropriate Sony/MS reps, I'll be sure to drop the other's terminology into conversation somehow.