A computing device configured for Peer-to-Peer exchange of a control packet for a communication flow, comprising: a communication interface configured to couple the computing device to a network having a plurality of nodes; and a processor coupled to a non-transitory, computer-readable storage medium having stored thereon computer-executable instructions for a virtual network agent that routes data packets using a virtual network overlaying an underlying network, the virtual network agent, when executed by the processor, configure the processor to: pre-reserve blocks of ports in a shared database accessible by each of the plurality of nodes in order to create a pool of network address translation mappings locally available at a first node of the plurality of nodes; determine whether a communication flow associated with a data packet received at the communication interface is a new flow; generate state information for the communication flow when the communication flow is determined to be a new flow; and transmit the data packet to an egress node associated with the communication flow; and characterized in that the virtual network agent, when executed by the processor, further configures the processor to generate a control packet that includes the state information for the communication flow, the state information comprising a network address translation mapping of the pool of network address translation mappings locally available at the first node of the plurality of nodes; and tunnel the control packet to the egress node associated with the communication flow; and the determining step comprises determining the communication flow is a new flow by querying a local data store based on information extracted from the data packet, the extracted information including an ingress port at which the data packet is received, and the virtual network agent is further configured to, in response to determining that the communication flow is a new flow, write the state information generated to the local data store, the local data store comprising an associative data structure holding the local state for each node of the plurality of nodes and stored on the non-transitory, computer-readable storage medium. a communication interface configured to couple the computing device to a network having a plurality of nodes; and a processor coupled to a non-transitory, computer-readable storage medium having stored thereon computer-executable instructions for a virtual network agent that routes data packets using a virtual network overlaying an underlying network, the virtual network agent, when executed by the processor, configure the processor to: pre-reserve blocks of ports in a shared database accessible by each of the plurality of nodes in order to create a pool of network address translation mappings locally available at a first node of the plurality of nodes; determine whether a communication flow associated with a data packet received at the communication interface is a new flow; generate state information for the communication flow when the communication flow is determined to be a new flow; and transmit the data packet to an egress node associated with the communication flow; and characterized in that the virtual network agent, when executed by the processor, further configures the processor to generate a control packet that includes the state information for the communication flow, the state information comprising a network address translation mapping of the pool of network address translation mappings locally available at the first node of the plurality of nodes; and pre-reserve blocks of ports in a shared database accessible by each of the plurality of nodes in order to create a pool of network address translation mappings locally available at a first node of the plurality of nodes; determine whether a communication flow associated with a data packet received at the communication interface is a new flow; generate state information for the communication flow when the communication flow is determined to be a new flow; and transmit the data packet to an egress node associated with the communication flow; and characterized in that the virtual network agent, when executed by the processor, further configures the processor to generate a control packet that includes the state information for the communication flow, the state information comprising a network address translation mapping of the pool of network address translation mappings locally available at the first node of the plurality of nodes; and tunnel the control packet to the egress node associated with the communication flow; and the determining step comprises determining the communication flow is a new flow by querying a local data store based on information extracted from the data packet, the extracted information including an ingress port at which the data packet is received, and the virtual network agent is further configured to, in response to determining that the communication flow is a new flow, write the state information generated to the local data store, the local data store comprising an associative data structure holding the local state for each node of the plurality of nodes and stored on the non-transitory, computer-readable storage medium.