NAT, Port Overloading, and the Address Exhaustion Boundary

IPv4 provides 32 bits of address, and the original allocation handed them out in blocks large enough that the supply ran out decades before the protocol did. The response that kept the network growing was not a new protocol but a translator: a box at the boundary of a site that rewrites the addresses in packets as they cross, so that many hosts behind it share one address on the outside. The technique is old enough to predate the exhaustion it was adopted to postpone, and its costs are specific enough to be listed.

A translator is not a router. A router forwards a packet with the addresses untouched and keeps no record of it. A translator modifies the header and, for anything with a port, the transport header too, and it must keep a record of each modification so that the reply can be reversed. That record is state, and the state is per conversation rather than per site, which is the source of nearly every property and every failure of the design. The router’s statelessness is what lets it be replicated per interface and sized by table lookup; the translator’s state is what makes it a chokepoint, and it is the same per-conversation state that the transport already keeps at the endpoints under the argument in The TCP/IP Split and the End-to-End Argument, duplicated once more in the middle of the path.

What the translation must remember

Consider a host at 192.168.1.10 sending a TCP segment from source port 49152 to 198.51.100.7 port 443. The translator owns one public address, say 203.0.113.5, and it must choose a source port on that address so that the reply can be demultiplexed. If it chose 49152 and another internal host was already using 49152 toward the same destination, the two conversations would be indistinguishable on the return path. So the translator allocates a port and records the tuple.

Internal side                     External side
192.168.1.10:49152  <->  203.0.113.5:40001   to 198.51.100.7:443
192.168.1.11:49152  <->  203.0.113.5:40002   to 198.51.100.7:443
192.168.1.10:49153  <->  203.0.113.5:40003   to 198.51.100.7:443

The record is keyed on the full five-tuple, not on the internal address alone, which is what allows two hosts to use the same source port simultaneously. The external port is the only field the translator is free to choose, and it is the field that makes overloading possible: one address has 65,535 ports, and each conversation consumes one. The theoretical ceiling on concurrent conversations through one public address is therefore bounded by the port space, not by the number of internal hosts, and in practice it is lower because some ports are reserved and because a port cannot be reused while a binding in the same four-tuple pair is live.

That ceiling is the reason a single address can serve a household but not a large office, and why the exhaustion argument is about concurrency rather than about address count alone. A site with thousands of clients holding connections open to the same service will exhaust the external port space long before it exhausts anything else, and the symptom is a failure to allocate a mapping rather than a failure to route.

The two directions of the binding

An outbound binding is created by the first packet from inside, and it is what makes the return path possible. An inbound packet with no matching binding is dropped, because the translator has no way to know which internal host should receive it. This asymmetry is the security property that made NAT popular long before the address shortage was acute: an unsolicited connection from outside cannot reach an internal host unless a mapping exists or a static rule has been configured.

A static rule, sometimes called a port forward, is a binding created by configuration rather than by traffic. It maps a fixed external port to a fixed internal address and port, and it exists permanently. The difference between a static and a dynamic binding is only in who creates it and when it expires, but the consequences differ: a static binding is reachable from outside and a dynamic one is not, so the presence of a static rule is what makes an internal service a public service.

The lifetime of a dynamic binding is a timer. For TCP, the binding can be released when both sides have closed the connection, because the translator can observe the FIN and the final acknowledgement. For UDP there is no close, so the binding expires after an idle period, and the length of that period determines both how long a reply is still accepted and how quickly the port is returned to the pool. A binding that expires while a peer still believes the conversation is alive produces a reply that the translator drops as unmatchable, and the peer sees silence rather than an error.

import time

class BindingTable:
    """Five-tuple bindings with idle expiry; the external port is the
    scarce resource, so allocation failures are the interesting case."""

    def __init__(self, external_ip, port_range=range(40000, 41000)):
        self.external_ip = external_ip
        self.free = list(port_range)
        self.table = {}          # (proto, ext_port, remote_ip, remote_port) -> entry

    def create(self, proto, src, remote):
        if not self.free:
            return None          # port space exhausted: this is the real limit
        ext_port = self.free.pop()
        key = (proto, ext_port, remote[0], remote[1])
        self.table[key] = {"internal": src, "expires": time.monotonic() + 120}
        return (self.external_ip, ext_port)

    def lookup(self, proto, ext_port, remote):
        key = (proto, ext_port, remote[0], remote[1])
        entry = self.table.get(key)
        if entry is None or entry["expires"] < time.monotonic():
            return None          # unsolicited, or expired while the peer still sends
        return entry["internal"]

The expiry check on lookup is the mechanism that makes an unsolicited packet indistinguishable from one whose binding has aged out. Both are dropped, and the internal host that expected the reply learns nothing about why.

What a translator cannot preserve

The header checksum covers the addresses, so a translation that changes an address must update the checksum. That is arithmetic and every implementation does it. The harder cases are the ones where an address is embedded in a payload the translator does not understand.

FTP’s active mode is the canonical example. The client sends a PORT command whose argument is its own address and port in a textual encoding, and the server is expected to connect back to that address. A translator that rewrites the packet header has no idea the payload contains an address, so the server receives an address it cannot reach. The fix requires a translator that parses the application protocol, which means it must know which protocols need it and how to find the field. The alternative, passive mode, moves the connection in the direction the translator already handles, which is why it became the default.

The same problem appears in any protocol that carries an address as data: session setup protocols for voice and video, some file transfer conventions, and any application that reports its own address to a peer for the peer to use. A translator that does not parse the protocol breaks the application silently, and a translator that does parse it becomes a participant in the protocol rather than a forwarding function.

The second class of breakage is the protocol that assumes it can receive. An internal host that listens on a port is unreachable from outside unless a static binding exists, so peer-to-peer topologies that depend on either party being able to accept a connection degrade to relay-based topologies. The relay exists precisely because the address a peer advertises is not the address a translator will accept traffic on, and the relay’s address is reachable by both sides.

The third is the protocol that embeds an address in a checksum. A transport checksum computed over a pseudo-header containing the source and destination addresses must be recomputed when either changes, and a translator that rewrites an address without recomputing the checksum produces a packet the receiver discards. Incremental update is possible because the checksum is a sum, so the difference between the old and new address can be folded in without re-reading the payload, but the implementation must know the transport’s checksum layout, including which transports have one at all.

The fragmentation trap

A translator that rewrites addresses must see the transport header to translate the port, and the port is not present in every fragment. A datagram fragmented by the sender has the transport header only in the first fragment, so the later fragments carry no port and cannot be matched to a binding. The options are to reassemble before translating, which requires buffering the whole datagram and defeats the point of fragmentation, or to key the binding on the identification field, which works only if the fragments can be associated reliably.

The practical consequence is that a datagram large enough to fragment is the case a translator handles worst, and the mitigation is to keep datagrams small enough that they do not fragment on the path. That is the same conclusion the transport reached for a different reason, and it is why path MTU discovery matters more on a translated path than on an untranslated one. A translator that silently drops fragments breaks the discovery, because the ICMP message that reports the smaller MTU is itself a datagram carrying the original header, and the translator must rewrite the embedded header to make the message meaningful to the internal host.

What the boundary actually cost

NAT preserved the address space at the price of the end-to-end model. A host behind a translator does not have an address that any other host can use to reach it, so the property that any host on the internet could address any other host was lost for the majority of endpoints. The functions that depended on that property, among them incoming connections, address-based authentication, and protocols that report their own address, either moved to a relay, moved to a protocol that establishes a mapping first, or stopped working.

The protocol designed to restore the property is IPv6, with 128-bit addresses and no need for translation at the boundary. Its deployment has been slow for reasons that have nothing to do with the address size, and during the transition the translator remains the mechanism that lets an IPv4 site connect to an IPv6 one. The translation between the two families is harder than translation within one, because the headers are different shapes and the addresses cannot be mapped one to one, so the boundary between the families needs a mechanism that terminates one protocol and originates the other rather than rewriting in place.

The translator also changed the economics of address allocation. A site that needs one public address for thousands of hosts no longer needs a block, so the demand for addresses fell and the pressure that was supposed to force the transition eased. That feedback is the reason the exhaustion date kept moving: each mitigation reduced the urgency of the replacement, and the replacement’s cost is paid by the parties who deploy it first rather than by the parties who benefit.

The routing side of the same boundary is described in Path Vectors, Policy, and Why BGP Does Not Minimize Anything: an address is announced by whoever holds it, and a translator lets a site hold one address while using many. The two mechanisms together are what allowed a 32-bit address space to carry a network orders of magnitude larger than its designers assumed, at a cost that is still being paid in every protocol that has to discover what lies between it and its peer.