A method includes a proxy device receiving from a source device a request to establish a flow to a destination device; generating, based on the request, a meta-packet that indicates that the flow to the destination device is to be proxied; determining whether a pre-established flow connecting the proxy device to another proxy device that leads toward the destination device exists; sending the meta-packet on the pre-established flow, when it is determined that the pre-established flow exists; receiving by the other proxy device, the meta-packet, and establishing the flow to the destination device based on the meta-packet, where the proxy devices assign one or more of a source address, a source port, a destination address, or a destination port, associated with the source device and the destination device, to the pre-established flow.