Techniques for performing NAT operations to send packets between networks are described. In an example, a network device receives a packet that comprises a header. The header indicates a source address of a first computing resource in a first network and a destination address of a second computing resource in a second network. The network device determines a pool of identifiers allocated for the first network and the second computing resource and identifies a packet flow based on the header. The network device also determines that no identifier from the pool of identifiers has been allocated for the packet flow and determines an identifier available to allocate for the packet flow from the pool of identifiers. The network device performs a NAT operation on the packet based on the identifier.