Scaling network address translation (NAT) and firewall functionality to support public cloud networks

A computerized method conducted by logic deployed within a network device implemented within a virtual private cloud network for supporting network address translations within a public cloud network, the method comprising:

• receiving a message;
• based on content within the message, selecting a network address translation (NAT) control logic unit from a plurality of NAT control logic units, wherein the selecting of the NAT control logic unit comprises conducting one or more hash-type functions on at least a source private Internet Protocol (IP) address or a source port of a header section of the message to produce a result for use in determining the selected NAT control logic unit and the selected NAT control logic unit to perform address translations on information within the message to produce a translated message;
• and
• routing the translated message to a destination network device located on the public network.