IP-based VPN technology is considered an attractive cost-effective private network service for both customers and service providers. We focus our research on the design of a minimal cost routing policy to be used by network-based IP VPN. The interest in such solutions is generated by both customers seeking to reduce support costs and by Internet Service Providers (ISPs) seeking new revenue sources. Reducing the cost of operation would allow ISPs to define and deploy new VPN services. In particular, a Multi-commodity Min-Cost Flows (MMCF) formulation is applied to the resource allocation in network-based IP VPN in order to develop a cost-effective routing proposal. We compare our proposal with the IETF RFC 2676 enhancement: a QoS enhancement to the Open Shortest Path First (OSPF) algorithm. Our results show the benefits of our proposal by considering two different scenarios.