A redirector within an Autonomous System (AS) is configured to access a set of Routing and Forwarding (RF) tables associated with a respective set of tenants. A current packet, addressed to a private IP address of a private tenant network outside the AS, is received by the redirector. The redirector executes a look up of the private IP address in a RF table, from the set of RF tables, that corresponds to the tenant associated with the packet. The redirector selects an egress interface of a egress gateway of the AS based on the look up. The redirector encapsulates the current packet and an identifier of the egress interface within an outer packet and transmits the outer packet to the egress gateway. The egress gateway transmits the packet toward the private IP address of the private tenant network using the egress gateway selected by the redirector.