Virtual Private Networks provide secure and reliable communication between customer sites. With increase in number and size of VPNs, providers need efficient provisioning techniques that adapt to customer demand by leveraging a good understanding of VPN properties.In this paper we analyze two important properties of VPNs that impact provisioning - (a) structure of customer endpoint (CE) interactions and (b) temporal characteristics of CE-CE traffic. We deduce these properties by computing traffic matrices from SNMP measurements. We find that existing traffic matrix estimation techniques are not readily applicable to the VPN scenario due to the scale of the problem and limited measurement information. We begin by formulating a scalable technique that makes the most out of existing measurement information and provides good estimates for common VPN structures.We then use this technique to analyze SNMP measurement from a large IP VPN service provider. We find that even with limited measurement information we can realize adaptive provisioning for a significant fraction of VPNs, namely, those constituting the Hub-and-Spoke category. In addition, the ability to infer the structure of VPNs holds special significance for provisioning tasks arising from topology changes, link failures and maintenance. We are able to provide a classification of VPNs by structure and identify CEs that act as hubs of communication and hence require prioritized treatment during restoration and provisioning.