Connection tracking records for a very large scale NAT engine

A non-transitory machine readable medium storing a program which when executed by one or more processing units performs network address translation to share a smaller number of external source network addresses among a larger number of connections, the smaller number of external source network addresses used by a first network to communicate with one or more other networks, the program comprising sets of instructions for:

• receiving a first packet of a first packet flow comprising a header storing a first network address as an internal source address and a second network address as a particular destination address;
• from a pool of external source addresses available for the particular destination address, allocating a third network address as an external source address for the first flow, the pool of external source addresses including external source addresses available for packet flows to other destination addresses as well as the particular destination address;
• forwarding the received packet after replacing the first network address with the third network address as the source address stored in the header of the packet;
• and
• for a second packet flow that is received in response to the first packet flow, creating a connection-tracking record that is stored in a connection-tracking storage and that maps the second and third network addresses to the first network address, in order to translate the destination addresses of packets in the second packet flow to the first network address,
• wherein creating a connection-tracking record comprises (i) generating, from a set of header values in the packet header, a hash value that identifies a location in the connection-tracking storage and (ii) storing the connection-tracking record at the location in the storage identified by the hash value,
• wherein each hash-addressable location in the storage stores a linked list of zero or more connection-tracking records, with each connection-tracking record associated with a different packet flow to the destination second network address.