home • blog • mastodon • thingiverse

NAT stands for "Network Adress Translation" and is a deeply broken kludge to get around the shortage of IP addresses. A NATed network looks to the rest of the internet like a single computer. Packets passing through a NAT firewall have their port numbers and IP addresses rewritten to achieve this deception. Computers on a NAT network can not receive incoming connections, only initiate them. They can only be clients, and never servers. NAT implementations, for extra fun, differ wildly in how they go about their packet rewriting, which ports map to which, how long a port stays allocated for, and so on.

NAT is one of the banes of Peer-To-Peer networks. P2P nodes have to be both client and server. So a P2P network can't consist of entirely NAT machines, and the NAT machines are somewhat second class citizens.

Consider a typical scenario: two home networks, both with NAT routers attached to cable modems. Someone on one network wants to get a file from someone on the other network. If the file is to be transferred, it will have to go through a third party (or more likely, won't happen at all and the RIAA will be very happy).

Or so i thought. Then this page was posted to the p2p-hackers list. In it, Dan Kegel describes a method for connecting two NATed computers, with the help of a third party. It's compatible with some but not all NAT networks.

Which got me thinking. Not only are IP addresses limited (they are 32 bits, and some of that is routing information), so are port numbers. The port number in a UDP packet is only 16 bits long, so there are only 65536 UDP ports per computer. UDP is an alternative to TCP that works on the basis of data packets rather than data streams. Since UDP doesn't establish a "connection", NAT simply assumes that an outgoing UDP packet will result in a reply packet some time later. This is the most common way of using UDP, but certainly not the only way (see, for example, the Circle). As i said, NAT is broken. Anyway, when the NAT router gets a reply, it can match the IP address and port number with a table of sent UDP packets that it's expecting replies to and route it through the local network appropriately.

Ok, that was all just warming up, here's the fun part...

Suppose two NATed machines both want to communicate. If machine A sends 256 UDP packets (each from a different port) to machine B, that means there will be 256 holes in his NAT that machine B could get a packet through (256 entries in the NAT's UDP routing table). The NAT must allocate 256 different ports: since each packet was sent to the same IP, the port number is the only way for the NAT to distinguish each possible reply.

It will then take machine B about 256 tries to get a packet through to A. This is because each time B sends a packet it has about a 256/65536 = 1/256 chance of getting through. Once one packet gets through, you have a connection and can get on with transferring data.

Some knowledge about how different NAT implementation work could speed this up, but even with no knowledge, 512 small packets is pretty reasonable. Machine A can also keep network traffic down by setting the time-to-live of its packets fairly low.

Once you have NAT-2-NAT you can do all sorts of fun stuff. File transfers. Voice-over-IP. Instant messaging. And it works for absolutely everyone, even the downtrodden NATed masses (until we find some new and interesting way of breaking IP).

Isn't network programming fun!

Correction (12/12/03): The NATs can use both the source and destination ports to distinguish replies. So we may need an average of 65536 packets to connect between some (most?) NAT networks. This adds up to maybe 10Mb to establish a connection, not such a big deal on a cable modem, though not something one would do entirely casually.

[æ]