This paper describes VServ, a prototype architecture for a virtual private network (VPN) service, which builds and manages VPNs on demand. It allows each VPN to have guaranteed resources and customized control, and supports a highly dynamic VPN service where creation and modification operations can take place on fast timescales. These features are contingent on the automated establishment and maintenance of VPNs. A design process is described that attempts to satisfy the goals of both customer and VPN service provider (VSP). A pruned topology graph and tailored search algorithm are derived from the characteristics of the desired VPN. Although the searching procedure is theoretically intractable, it is shown that the complexity can be mitigated by a multitude of factors, VServ is built over the Tempest, a network control framework that partitions network resources into VPNs. An IP implementation of the Tempest is presented. Resource revocation is a mechanism that the VSP can use to react to violations of service level agreements-a protocol is described to enable graceful adaptation in the control plane to resource revocation events.