A method is provided in one example embodiment and includes configuring on a network element a first tunnel from the network element to a first network, wherein the configuring comprises mapping a nexthop address of the local network element to a transport address of the tunnel on the network to create a first nexthop-to-transport mapping for the network element; and advertising the first nexthop-to-transport mapping along with routing information for the network element to remote network elements.