Topological design of multiple VPNs over MPLS network

With the deployment of MPLS over a core IP backbone, it is possible for a service provider to build virtual private networks (VPNs) supporting various classes of services with QoS guarantees. Efficiently mapping the logical layout of multiple VPNs over a service provider network is an important and challenging traffic engineering procedure. The use of sink-tree (multipoint-to-point) routing paths in an MPLS network makes the VPN design problem different from traditional design approaches where a full-mesh of point-to-point paths is often the choice. The clear benefits of using sink-tree paths are the reduction in the number of label switch paths and the bandwidth saving due to the larger granularity of bandwidth aggregation within the network. The design of multiple VPNs over MPLS, using sink-tree routing, is formulated as a mixed integer programming problem to find simultaneously VPN logical topologies and their dimensions to carry multi-service, multi-hour VPN traffic from various customers. Such a problem formulation yields an NP-hard complexity. We propose a heuristic aiming to scale the VPN design problem by choosing a small-but-good candidate set of feasible sink-tree paths to solve the optimization problem. Numerical results are given showing the advantages of the proposed approach.