This paper proposes a network design scheme for Virtual Private Network (VPN) services. Traditionally, network design to compute required amount of resource is based on static point-to-point resource demand. This scheme is effective for traditional private line services. However, since VPN services allow multi-site connectivity for customers, it may not be appropriate to design a network based on static point-to-point resource demand. In particular, this scheme is not effective when the traffic pattern changes over time. Therefore, network design for VPN services introduces a new challenge in order to comply with traffic flexibility. There are conventional studies tackling this issue. In those studies, by defining a resource demand model considering flexibility, and designing the network based on this model, amount of resource required can be computed. However, there are some deficiencies in those studies. This paper proposes a new network design scheme, consisting of two components. The first one is a new resource demand model, created by extending conventional resource demand models, that can specify resource demand more precisely. The second one is a new network design algorithm for this resource demand model. Simulations are conducted to evaluate the performance of the proposed network design scheme, and the results show significant performance improvement against conventional schemes. In addition, deployment considerations of the proposed scheme are analyzed.