This paper describes a proposal for the support of Quality of Service over Virtual Private Networks (VPNs). We combine DiffServ, MPLS and a dynamic resource allocation technique in order to provide a QoS-enabled VPN. We apply dynamic resource allocation using traffic predictors. Our predictor assumes that the statistical behavior of aggregate traffic streams is statistically described through α-stable long-rage dependent stochastic processes. This is a valid assumption, since some of the authors of this work proved in the past that such distributions more accurately describe aggregate traffic passing through modern networks as compared to earlier models. In our work, we investigate a scenario in which the service provider establishes Service Level Agreements (SLAs) with the customers, where the resources and QoS requirements are defined. When operating the network, the provider uses dynamic resource allocation algorithms to pace and forward traffic while optimizing the resource utilization. The conceptual architecture of this technology is provided along with a description of our Linux-based experimental testbed. We also discuss some important performance considerations obtained through extensive computer simulations.