One embodiment of the present invention is directed to a customer-edge-discovery subsystem, within a VPN-provider system interconnected with a public communications network, that automatically generates a data representation of a VPN-provider view of the network by: initializing the data representation; accessing tools and protocols available within the VPN-provider system to discover elements, connections, interfaces, VPNs, and other components and characteristics of the public communications network and include representations of the discovered elements, connections, interfaces, VPNs, and other components and characteristics of the public communications network in the data representation; and finding customer-edge devices for each provider-edge device to include in the data representation using broadcast domains or address-resolution-protocol caches.