Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Topological Design of Multiple Virtual Private Networks UTILIZING SINK-TREE PATHS

Srikitja, Anotai (2011) Topological Design of Multiple Virtual Private Networks UTILIZING SINK-TREE PATHS. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

[img] PDF
Primary Text

Download (2MB)


With the deployment of MultiProtocol Label Switching (MPLS) over a core backbone networks, 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 problem. 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 savings due to larger granularities of bandwidth aggregation within the network. In this thesis, the design of multiple VPNs over a MPLS-like infrastructure network, using sink-tree routing, is formulated as a mixed integer programming problem to simultaneously find a set of VPN logical topologies and their dimensions to carry multi-service, multi-hour 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 the optimization process and the 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 scalability. Here, the heuristics termed the Minimum-Capacity Sink-Tree Assignment (MCSTA) algorithm proposed to approximate the optimal bandwidth and sink-tree route assignment for multiple VPNs within a polynomial computational time. Numerical results demonstrate the MCSTA algorithm yields a good solution within a small error 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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairTipper, Daviddtipper@mail.sis.pitt.eduDTIPPER
Committee MemberNorman,
Committee MemberSteenkiste,
Committee MemberKrishnamurthy, Prashantprashant@mail.sis.pitt.eduPRASHK
Committee MemberThompson, Richardthompson@mail.sis.pitt.eduRTHOMPSO
Committee Member,
Date: 17 February 2011
Date Type: Completion
Defense Date: 28 July 2004
Approval Date: 17 February 2011
Submission Date: 2 August 2004
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Institution: University of Pittsburgh
Schools and Programs: School of Information Sciences > Information Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Approximation; Capacity Assignment; Heuristics; Mathematical Optimization; Multipoint-to-point path; Network Design; Route Optimization; Tree Generation
Other ID:, etd-08022004-103836
Date Deposited: 10 Nov 2011 19:56
Last Modified: 15 Nov 2016 13:47


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item