Just to make sure we're all on the same page in terms of terminology:
What is NAT?
NAT is an acronym for "Network Address Translation". It's a system designed to allow a router to allow a whole private network of arbitrary size to appear to be a single device, from the point of view of the outside world. And the magic is that it does this completely transparently, without the clients on either the private or the public network ever needing to know it's happening.
In effect, it takes outgoing requests from the private network and rewrites them to appear to be coming from its single public address and some public port number, and then when it receives a response, it rewrites the response to forward it back into the private network, to whatever device sent the original request.
This was primarily needed because of the rapidly depleting supply of public IPv4 addresses as the Internet's popularity was taking off, but also brought some moderate security benefits by putting a largely one-way barrier between potentially unsecured consumer devices and the public internet. (It also dramatically slowed adoption of IPv6, but that's a topic for another day)
This particular classification of NAT types appears to have originated with Microsoft, where it was identified as useful during development of the original XBox game console, since it classed different NAT types into a useful way to determine which clients would be able to directly communicate with which other clients.
Sony uses essentially the same classification system, but uses different terms. In the discussion that follows, I'll mention both company's terms, and then use them interchangeably. But almost everybody has settled on using Microsoft's more human-readable terms for these NAT types; even Nintendo uses Microsoft's terms, now. The only holdout I'm aware of is Sony, who still use their own terms. (I once spent an enjoyable afternoon with a Sony dev rep, trying to make him slip up and use Microsoft's terms for NAT types. I think he figured out what I was doing, and I never managed it. But I did get him to actually say 'Xbox' once, which got him a stern look from his manager. That was a good day. I am a simple man of simple pleasures.)
"Open" NAT (Microsoft's term) or "Type 1" NAT (Sony's term) describes NAT behaviour where a particular private IP address and port behind the NAT device gets mapped to a single public address and port on the outside network. That is, anybody anywhere on the outside who sends a packet to that public address and port will have it successfully delivered to the inside, no matter what. This means that not having a NAT device gets categorised as "Open" NAT. Alternately, setting up a NAT device to forward the correct ports can also achieve this same result.
"Moderate" NAT (Microsoft's term) or "Type 2" NAT (Sony's term) describes NAT behaviour where a particular private IP address and port behind the NAT device gets mapped to a single public address and port on the outside, exactly the same as in "Open" NAT, except that incoming packets to that public IP address and port will only be delivered if we've already recently sent a packet OUT on that port, to the person who is now trying to send a packet IN. That is, people are allowed to respond to us, but not to initiate communication. (This is the most common sort of NAT). We use hole-punching to get through this; a central server tells both of us the other person's public address and port, and we then spam messages to each other, so both of us pretend that we're initiating the conversation, and our NAT devices let both sets of messages get through, thinking that they're "responses".
"Strict" NAT (Microsoft's term) or "Type 3" NAT (Sony's term) describes NAT behaviour which doesn't meet the requirements of Type 1 or Type 2. That is, a single private address and port sometimes get mapped to different public addresses and/or ports, most commonly based upon who the packets are being sent to. For example, if I send a packet from private port 80/UDP to person A and a packet from that same private port 80/UDP to a different person B, then A and B will see those packets as having come from different public port numbers on the NAT device. This means that A and B can't tell each other how to contact me, because my NAT device is going to be requiring that they each only reply to me using the special public port which it allocated for communication to each of them independently; any packets that A might send to the port which was allocated for talking with B won't get through, and vice-versa.
NAT types are broad generalisations
As mentioned above, there are far more types of NAT than just these three, and many more ways to classify them. Sometimes they're classed as "symmetric", or "conical", or in other ways.
One particularly relevant difference, even inside this classification: Moderate/Type 2 NAT devices often differ in terms of how recently we have to have sent an outgoing packet, in order to accept incoming responses. If there's a long delay between our last packet out and someone's response to us, an otherwise Type 2 NAT device may appear to occasionally behave like a Type 3 NAT device.
Another common gotcha is that some routers which behave as Type 2 when there's just one client using the private network begin to behave as Type 3 when there are two clients both using the same private port numbers on that private network.
There is no "standard" implementation of NAT; everybody started from the basic concept for what a NAT device should do, but implemented it separately, so the little details are typically different in every device, and our "NAT types" discussion is just a useful classification system for carving useful information out of a broad spectrum, for the purposes of establishing peer to peer communication when both peers are behind different NAT devices.
Just something to bear in mind.
On the technical support query in the comment
On the PlayStation, NAT type 2 is "moderate", not "restricted" (not sure where you got that term from). It should work perfectly well, since all modern game services are built to perform standard hole-punching to allow clients to communicate with each other.
How to classify a NAT device's behaviour, yourself
To classify a router between the three types we're discussing here, all you need is a server with three different public IP addresses. We'll call these IP addresses 'A', 'B', and 'C'. Follow these steps:
- Client sends a packet to A, and a packet to B.
- Server compares the packets it received on its A and B addresses, and checks to see if the public IP address and port numbers it sees as the source of those two packets match each other. If not, the client is Type 3 (Strict).
- If the packets did both show the same public source IP address and port, then the server sends a packet from C to that IP address and port. Remember that the client has never sent a packet to C, so if the client successfully receives that packet, then we know it's Type 1 (Open). If it fails to receive the packet, it's Type 2 (Moderate).
That's all it takes!
Why any of this matters
Fundamentally, any number of Type 1 and Type 2 clients can successfully talk to each other; the Type 1 clients because anybody can talk to them on their public address/port, and the Type 2 clients because they can hole-punch out, as long as they know the public address/port that is going to be contacting them.
Type 3 clients, on the other hand, can only talk to Type 1 clients, and they require the Type 1 client to have special NAT traversal code to do that successfully; (the program has to be smart enough for the Type 1 client to receive a packet it wasn't expecting from an unknown address/port, and realise that it must actually be the true address/port from the Type 3 client, and redirect itself to talk to that address, instead of the one it had been expecting to hear from. I would be surprised if many folks actually write that sort of code any more; the vast majority of people are using Type 2 NAT devices, these days, so it'd be hard to test and few folks would get any benefit from this work).
Anyhow, Type 3 clients can't talk to Type 2 clients, because the Type 2 clients don't know the correct address/port to send packets to in order to hole-punch through their own NAT device. And obviously two Type 3 clients will likely never manage to reach each other at all, since neither actually knows the correct address/port for talking to the other.
If you're making a multiplayer game, it can be useful to know which NAT type each player is; for example, knowing that Type 3 players will only be able to talk to Type 1 players, you immediately know not to even bother suggesting that they join a game session which includes any Type 2 or Type 3 players; you already know they won't be able to connect to each other!
And similarly, you know not to send Type 2 players to join a game session which includes any Type 3 players; you know they won't be able to connect. All this logic lets you reduce frustrating "trying to connect to game session" processes which will never complete.
And that's pretty much all there is to it!