Port allocation at distributed network address translators

A system, comprising:

• a distributed network address translation appliance comprising a plurality of computing devices;
• wherein the plurality of computing devices include instructions that upon execution on or across one or more processors cause the distributed network address translation appliance to:
• in response to a determination that one or more flow state metadata entries corresponding to a first packet are to be generated:
• direct the first packet to a particular node of a plurality of state manager nodes of the distributed network address translation appliance, wherein the particular node is selected at random from the plurality of state manager nodes, and wherein the particular node is configured to store flow state metadata associated with network flows corresponding to a particular flow hash value range;
• apply, at the particular node, a hash function to a reverse-direction flow tuple of the first packet to obtain a first intermediate hash result, wherein the reverse-direction flow tuple comprises at least a source address, a source port, and a destination address, wherein the destination address is an address of a networking intermediary of the network flow, and wherein the reverse-direction flow tuple does not include a destination port;
• determine, at the particular node, using at least (a) the first intermediate hash result, (b) the particular flow hash value range, and (c) a lookup table, an unused port number to be assigned as the destination port for a reverse-direction flow of the first packet, wherein the lookup table comprises one or more entries including a first entry, wherein the first entry indicates a mapping between a port number and a second intermediate hash result;
• allocate, at the particular node, the unused port number determined using at least (a) the first intermediate hash result, (b) the particular flow hash value range, and (c) the lookup table as the destination port for the reverse-direction flow;
• and
• store, at the particular node, a reverse-direction flow metadata entry, wherein a key associated with the reverse-direction metadata entry is based at least in part on the assigned destination port;
• cause a re-written packet to be transmitted to a recipient indicated in the first packet, wherein, in the re-written packet, a source address is the address of the networking intermediary, and a source port is the assigned destination port;
• and
• utilize the reverse-direction flow metadata entry, that is associated with the key that is based at least in part on the assigned destination port, to route at least one packet originating at the recipient indicated in the first packet.