I have pretty limited networking knowlegede, but based on what I've read on the forums, I don't think that the NAT negotiation server getting bogged down is the problem...I think the problem is that player connections to one another are being refused, either because the NAT traversal isn't working or because the socket connection is created incorrectly by the operating system.

This understanding has lead me to make my own uneducated guesses about solutions:

When I look at the connection information during games, I notice that when someone tries to join, he attempts a connection to everyone who is in the game, which is fine.  However, it also looks like he tries to connect to anyone else who is attempting to join, and sometimes even to people who have already left the game...I think that fixing this so that he only connects to people who are already in the game could help.

I had also thought that it would be interesting to allow players to join even if they can't connect to every other player, and asking a player who they can connect to to route their messages to the other players. The chain of players routing messages to one another could get out of control, but if we're just talking about one player routing messages to one target, then it wouldn't be too different from a client/server scenario where players send messages to a server and the server sends them to other players.

Like the first poster, I don't know whether these ideas are in any way correct or useful, but mentioning them can't hurt.

Heres some information on the NAT negotiation that they use -- RakNet

http://www.jenkinssoftware.com/raknet/manual/natpunchthrough.html

I'd be curious to know how often these connects are failing the original connection of exchanging IP/Port addresses between two clients, and then moving onto phase 2 where they are just brute force guessing which ports to use to communicate.  It seems to me that most of the communications aren't happening that quickly, and this phase 2 is a majority of the cases.

Then theres the separate issue - where some routers constantly renumber the port that they are forwarding,  making your original address exchange null and void.  RakNet's solution is then to provide a UDP-Proxy server to move the data, but I would doubt Stardock is providing server resources to construct these proxies.  I could be wrong though!

That was a bunch of nerd speak, I know.  For some reason this stuff got me very interested.

According to that link, the original attempt to connect the computers is:

"The server will find the external IP address of each client, and tell both clients to connect to that address at the same time."

Does that mean that the server is really just telling the clients to connect to each other at the same time?  That just sounds unreliable, doesn't it?

As for whether Stardock has the UDP Proxy servers, I'm not certain...I would guess that Stardock doesn't want to have proxy servers routing traffic from one player to another all the time, because wouldn't that be the same thing as using client/host instead of Peer-to-Peer?  But I also could be wrong.

As I understand it (not a dev) the issue is not so much at the OS level, but that some routers either reject the large number of socket attempts as an attack (strict security), or just panic/fail when faced with the simultaneous traffic (crappy hardware/firmware). Unfortunately you can't really tunnel past a router if it flips out at the mere sight of the traffic

Hmm, I should try sending Mr. Hankie an email and see if he knows how to do that.