NAT penetration algorithm from iGlance, circa 2005

January 25, 2011

How's this for a blast from the past. I posted this to the iGlance
Yahoo group. You can read the original here, which has a couple
follow-up replies:

http://tech.groups.yahoo.com/group/iglance/message/52

But here's the text itself for your reading pleasure:
———————————————————————–
Hi, thanks for writing. NAT penetration is a very tricky subject, so
let me first give an overview of what the obstacles are, and then I'll
explain my approach for circumventing them.

(Note, the 'STUN' protocol I'm using is home-brewed — it's not not
truly compliant with RFC3489, for reasons I can get into if you care to
hear. However, it accomplishes the same thing.)

First, assume the following network:

+——–+ +—–+ +——–+
| Client | —> | NAT | —> | Server |
+——–+ +—–+ +——–+

The client is connected to the NAT, and the NAT is connected (via the
internet) to the server. The client is generally on some LAN, and thus
has a "private" IP address. However, the NAT is generally on the
internet, and thus has a "public" internet IP address. Thus while the
client cannot send packets directly to the server (because the client
isn't on the internet), the client can send it "through" the NAT.

Now, UDP packets indicate from which address they originated. But which
address does the packet appear to be from when the server receives it:
the client, or the NAT? The answer is the NAT — NAT stands for
"Network Address Translator" because it translates "private" addresses
(such as on a LAN) to "public" addresses (such as on the internet).

So the client sends a packet from the LAN address (call it privateIP)
but the server thinks it's coming from an internet address (call it
publicIP) due to the NAT's translation. So long as the client is
simply sending to the server, there's no problem — if the
server is only receiving, it doesn't care what address the packet comes
from. But the moment the server wants to reply, then things get tricky.

In the easy case when a server is replying to a client request, the
server just sends back to the address the request packet appeared to
come from (ie, the publicIP). And when the NAT receives it, it forwards
it back to the client. In this way, when a client establishes a
connection with a server, the client and server can talk back and forth
without trouble.

However, the reverse is not so easy. Now, when the client initiates a
connection with the server, it 'punches a hole' through the NAT. This
hole (also called a 'mapping') is what the server uses to talk back with
the client. However, if the client doesn't punch the hole to the server
first, the server can't contact the client. Indeed, if the server sends
a packet to 'publicIP' before the client punches the hole through the
NAT, the NAT will just silently disregard the message and it'll never
arrive.

Thus a NAT is a bit like a one-way mirror: a client behind a NAT can
contact servers without restriction, but servers can't do the same.
Many people like this behavior for security reasons. But obviously, in
a P2P network this is less desirable because if you're behind a NAT, a
remote client can't contact you until you contact it. But if it's also
behind a NAT, you can't contact it until it contacts you. A seemingly
intractable problem.

To solve this problem, iGlance uses a directory server that acts as an
intermediary to help clients behind NATs and firewalls connect directly.
The process works as follows:

1) Client A connects to the global server and registers its IP
2) Client B connects to the global server and asks for the IP for A
3) The server informs A that B is trying to contact it
4) Client A begins trying to contact B
5) Client B begins trying to contact A
6) Eventually a direct connection is established

As mentioned before, whether A tries to contact B or B tries to contact
A, both will fail independently. But when they both try to contact each
other simultaneously, they both "punch holes" through their NATs and
firewalls, and thus both let the other's communications through. This
technique of simultaneous hole punching is the essence of NAT-to-NAT
traversal.

However, recall that each client typically only knows its "private" IP
address — ie, the IP address on its private LAN. But just as the
server sees only a client's "public" IP address, so do peers only see
other peers' public IPs. Thus before client A can attempt to contact
client B, A needs to learn B's public IP.

This process of a client determining whether or not it is behind a NAT
(and if so, finding its public IP address) is called the 'STUN' process
— named after the IETF standard RFC3489. (iGlance doesn't use this
protocol, but is heavily influenced by it.) The precise technique
iGlance uses is as follows:

1) STUN server is assigned 3 IP addresses — STUN0-2

2) Client sends STUN request to STUN0

3) Client punches hole to STUN1

4) The STUN server attempts to contact the client *from* STUN0-2

Thus the STUN server sends *three* responses from *three* different
IP:port combinations, to the *same* IP:port from which the client
request originated. Depending on the NAT and firewall in place, the
client might successfully receive up to 3 responses, one each from a
different IP:port on the STUN server. Based on which requests succeed,
we can guess which type of NAT is between the client and the STUN
server. This is used to set the 'Connection_Class' as follows:

FIREWALL: (0 responses)
Something is blocking either all outbound or inbound UDP traffic.

SYMMETRIC: (1 response from STUN0)
The client can receive UDP only from the exact IP it sends to.

RESTRICTED: (2 responses, from STUN0 and STUN1)
The client can receive UDP only from remote IP:ports for which holes
have explicitly been punched.

UNRESTRICTED: (3 responses)
Once a hole is punched through the NAT, any remote IP:port can use it to
contact the client.

PUBLIC: (3 responses)
The client is not behind a NAT and thus can receive from any IP:port.

Furthermore, the server returns in the STUN response the apparent
IP:port from which the client's request appeared to originate. Recall,
the client sends from its 'private' address, while the server receives
from the client's 'public' address. If these are different, we know a
NAT must be in place. But if they are the same, then we can assume
there is no NAT in place and thus the client is connected to the
internet directly. (This is how iGlance distinguishes between the
UNRESTRICTED and PUBLIC states.)

(All this logic is contained in the file GDispatchService.cpp. The STUN
request is sent in the function GDispatchService::_requestStun( ), and
the responses are processed by GDispatchService::_onInput( ) in the
GDSS_STUN state.)

So clients with PUBLIC, UNRESTRICTED, or RESTRICTED NATs know they can
receive UDP directly from another peer. And clients behind SYMMETRIC
NATs or UDP-blocking FIREWALL know they can't (they must establish a
'TURN' connection with the server, which simply listens for UDP traffic
and sends back over HTTP). Armed with this information, clients can
ensure they are able to be contacted by remote peers, whether behind a
NAT or FIREWALL, or directly on the internet.

Does this answer your question?

-david

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: