Here's a message I wrote on the GD-Windows mailing list about how NAT works, and how it gets in the way of setting up game servers:

> What kind of firewalling/NAT/proxies are typical with ADSL
> providers? ADSL is not offered in our corner of Europe
> and thus it caught us entirely by surprise.

Many ADSL set-ups use NAT. Problems with NAT come when you 
need to send packets "in" to the user, who are not "replies" 
to packets going "out" from the user.

If you have this situation:

Server <---> NAT <---> User

NAT is the gateway for the User. The User creates and binds 
a socket, which gets a local port number Pu on the User machine 
with address Au. He then uses this socket to sendto() some 
remote port number Ps.

NAT will re-write the "source" address/port field to some 
NAT-local port Pn, and using the external NAT gateway address 
An. NAT remembers the tuple Pn->Au/Pu.

The Server gets a packet, and looks at the recvfrom() address 
to figure out the return address: the server sees An/Pn. 
Server figures out what data to send to the User, and sends it 
back to An/Pn.

NAT box sees a packet arriving at Pn, and looks up Pn in his 
translation table. If found, he forwards it to Au/Pu, re-writing 
the "destination" header, and the User sees the packet as if 
nothing had happened.

The problem comes if you send or use IP addresses or ports that 
are not part of the headers that get correctly re-written by 
NAT. If you have a field in your packet that says "IP address" 
or "IP port", then your protocol is fundamentally broken from 
the point of view of NAT. Some famous fundamentally broken 
protocols include FTP and H.320, so you'd be in good company :-) 
Part of NAT friendly protocol design is to only use the addresses 
as seen by sendto() and recvfrom(), and not put addressing data 
in your data packet.

If you're using peer-to-peer networking, it gets even more 
exciting, because some "server" may tell a "user" about some 
other "user" he's supposed to communicate to. This counts as 
"IP/port" data which is part of your packet, and thus won't get 
properly re-written by NAT.

As you can see, nobody who "listens" for "remote" connections, as 
opposed to "initiating" them, can sit behind NAT, unless you make 
the NAT explicitly aware of this port and forwards the port 
traffic to some specific listener inside the translated network.

If you're trying to get peer-to-peer working when both peers are 
behind one NAT box each, and the NAT boxes don't support custom 
port forwarding (or the users don't set it up) you're never going 
to get it to work, unless you use some external third server 
which sends packets to introduce the two sites to each other.
More on that can be found in this article.