Title: Topological Design of Multiple Virtual Private Networks Utilizing Sink-Tree Paths

When: Wednesday, July 28, 2004, 10:30-11:30 AM

Where: Room 503 IS Building

Who: Anotai Srikitja

Committee: Dr. David Tipper, University of Pittsburgh , Committee Chair; Dr. Richard Thompson, University of Pittsburgh Committee Member ; Dr. Prashant Krishnamurthy, University of Pittsburgh Committee Member; Dr. Bryan Norman, University of Pittsburgh Committee Member; Dr. Peter Steenkiste, Carnegie Mellon University Committee Member

Abstract: With the deployment of MPLS over a core IP backbone, it is possible for a service provider to built 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 a challenging traffic engineering procedure. The use of sink-tree (multipoint-to-point) routing paths in a 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 bandwidth saving due to larger granularities of bandwidth aggregation within the network.

In this thesis, the design of multiple VPNs over MPLS-like infrastructure network, using sink-tree routing, is formulated as a mixed integer programming problem to simultaneously find VPNs logical topologies and their dimensions to carry multi-service, multi-hour VPNs traffic from various customers. Such a problem formulation yields a NP-hard complexity. A heuristic path selection algorithm is proposed here to scale the VPN design problem by choosing a small-but-good candidate set of feasible sink-tree paths over which the optimal routes and capacity assignments are determined. The proposed heuristic has clearly shown to speed up an optimization process and the optimal solution can be obtained within a reasonable time for a realistic-size network.

Nevertheless, when a large number of VPNs are being layout simultaneously, a standard optimization approach has a limited applicability in practice. The Minimum-Capacity Sink-Tree Assignment (MCSTA) algorithm is, therefore, proposed to approximate optimal bandwidth and sink-tree route assignment for multiple VPNs within a polynomial computational time. The MCSTA algorithm is demonstrated to give a good approximation within a small error bound and sometimes yields the exact solution. Lastly, the proposed VPN design models and solution algorithms are extended for multipoint traffic demand including multipoint-to-point and broadcasting connections.