Srikitja, Anotai
(2011)
Topological Design of Multiple Virtual Private Networks UTILIZING SINK-TREE PATHS.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
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.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| 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: |
http://etd.library.pitt.edu/ETD/available/etd-08022004-103836/, etd-08022004-103836 |
| Date Deposited: |
10 Nov 2011 19:56 |
| Last Modified: |
15 Nov 2016 13:47 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/8814 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[img]](http://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}