A method to provide address translation at a first customer edge router, the first customer edge router being one of a plurality of customer edge routers (104a, 104b, 106a, 106b), the method comprising: establishing, by the first customer edge router, a tunnel (112a, 112b) between the first customer edge router and each of a plurality of aggregation routers (102a, 102b); performing, by the first customer edge router, a Network Address Translation, NAT, on a first data packet to create a NAT'ed first data packet, the NAT being a translation of a private IP address to a public IP address; maintaining, by the first customer edge router, a record of the NAT in a NAT table, and creating an entry in the NAT table that identifies a virtual private network, VPN, associated with the first data packet; maintaining, by the first customer edge router, a virtual routing and forwarding, VRF, table for the VPN; selecting, by the first customer edge router, a first aggregation router from amongst the plurality of aggregation routers (102a, 102b) to send the NAT'ed first data packet to; encapsulating, by the first customer edge router, the NAT'ed first data packet with overlay information corresponding to a tunnel established between the first customer edge router and the first aggregation router; sending, by the first customer edge router, the encapsulated NAT'ed first data packet through the tunnel to the first aggregation router; receiving, by the first customer edge router, a return data packet from the first aggregation router through the tunnel; removing, by the first customer edge router, overlay information from the return data packet to de-encapsulate the return data packet; performing, by the first customer edge router, reverse NAT on the return data packet to translate a public IP address to a private IP address based on the NAT table; identifying, by the first customer edge router, a VPN associated with the private IP address of the return data packet based on the NAT table; identifying, by the first customer edge router, an interface of the first customer edge router through which the return data packet is to be routed based on the VRF table for the identified VPN; and routing, by the first customer edge router, the return data packet through the interface identified from VRF table. establishing, by the first customer edge router, a tunnel (112a, 112b) between the first customer edge router and each of a plurality of aggregation routers (102a, 102b); performing, by the first customer edge router, a Network Address Translation, NAT, on a first data packet to create a NAT'ed first data packet, the NAT being a translation of a private IP address to a public IP address; maintaining, by the first customer edge router, a record of the NAT in a NAT table, and creating an entry in the NAT table that identifies a virtual private network, VPN, associated with the first data packet; maintaining, by the first customer edge router, a virtual routing and forwarding, VRF, table for the VPN; selecting, by the first customer edge router, a first aggregation router from amongst the plurality of aggregation routers (102a, 102b) to send the NAT'ed first data packet to; encapsulating, by the first customer edge router, the NAT'ed first data packet with overlay information corresponding to a tunnel established between the first customer edge router and the first aggregation router; sending, by the first customer edge router, the encapsulated NAT'ed first data packet through the tunnel to the first aggregation router; receiving, by the first customer edge router, a return data packet from the first aggregation router through the tunnel; removing, by the first customer edge router, overlay information from the return data packet to de-encapsulate the return data packet; performing, by the first customer edge router, reverse NAT on the return data packet to translate a public IP address to a private IP address based on the NAT table; identifying, by the first customer edge router, a VPN associated with the private IP address of the return data packet based on the NAT table; identifying, by the first customer edge router, an interface of the first customer edge router through which the return data packet is to be routed based on the VRF table for the identified VPN; and routing, by the first customer edge router, the return data packet through the interface identified from VRF table.