This thesis focuses on efficient provisioning of resilient Virtual Private Network (VPN) services. It first confirms the intuition that network resources can be more efficiently utilized when resilience mechanisms are implemented by a network provider in the physical network than by its VPN customers in their VPNs. Next, a Multiprotocol Label Switching-based programmable VPN architecture is presented that delivers virtual links as resilient quality of service (QoS) connections and virtual sites. Virtual sites allow customers to implement functionality like customized routing and content adaptation ???in the cloud???, as opposed to the current network model where all functionality is implemented at the network edge. To provision a resilient QoS connection, two paths need to be computed from the ingress to the egress nodes, such that both paths meet the given QoS constraints. Two different frameworks have been proposed in the literature to compute resilient QoS connections when the QoS constraints are bandwidth and end-to-end delay. They both use a preprocessing step whereby either all links with less residual capacity than the given bandwidth constraint are pruned, or the given end-to-end delay is converted to an effective bandwidth. The frameworks thus reduce the problem to one with only a single constraint. We argue in this thesis that these frameworks individually lead to poor network utilization and propose a new framework where both constraints are considered simultaneously. Our framework exploits the dependency between endto- end delay, provisioned bandwidth and chosen path through using the provisioned bandwidth as a variable. Here, two link-disjoint paths are computed together with their respective minimum bandwidths such that both the bandwidth and end-to-end delay constraints are satisfied. Given our framework we first propose a new generic algorithm that decomposes the problem into subproblems where known algorithms can be applied. Then we propose two new linear programming (LP) formulations that return the two paths and their respective bandwidths such that they have the minimum combined cost. To make our framework applicable in a production environment, we develop two new algorithms with low run times that achieve even higher network performance than their LP formulation counterpart. These algorithms systematically use an algorithm that computes non-resilient QoS connections. As no algorithm for computing nonresilient QoS connections with sufficiently low run time has been proposed in the current literature we develop two new algorithms and their respective heuristics with a run time comparable to Dijkstra???s shortest-path algorithm. Our simulations show that exploiting the dependency between end-to-end delay, provisioned bandwidth and chosen path can significantly improve the network performance.
| Identifer | oai:union.ndltd.org:ADTP/257189 |
| Date | January 2005 |
| Creators | Rosenbaum, Gustav Filip, Computer Science & Engineering, Faculty of Engineering, UNSW |
| Publisher | Awarded by:University of New South Wales. School of Computer Science and Engineering |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Copyright Gustav Filip Rosenbaum, http://unsworks.unsw.edu.au/copyright |
Page generated in 0.0022 seconds