In one embodiment, a method includes receiving at a first network device in a first virtual private network, a packet destined for a second network device in communication with a second virtual private network, and transmitting the packet over the second network, wherein the packet is encapsulated for transmittal on a tunnel extending from the first network device to the second network device. The first network device is in communication with a system operable to map and encapsulate the packet and provide an overlay that traverses over the second virtual private network. An apparatus and logic are also disclosed herein.