In this paper the authors propose a theoretic framework to design the Virtual Private Network (VPN) via which the Quality of Services (QoSs) are guaranteed over IP networks. The required QoS is a very strict packet loss probability or a probability that packet delay does not exceed a certain target value in a statistical manner. QoSs are guaranteed by providing a statistical bandwidth similar to equivalent bandwidth, which is computed so that the provided bandwidth is sufficient to guarantee those requirements. Two typical network architectures are considered in constructing VPN, the customer pipe scheme and the Hose scheme, and we propose a method to compute the amount of the required bandwidth for the two schemes. Finally, we investigate the implication of the scheme via numerical experiments.