New Architecture and Algorithms for Fast Construction of Hose-Model VPNs

Hose-model virtual private networks (VPNs) provide customers with more flexibility in specifying bandwidth requirements than pipe-model VPNs. Many hose-model VPN provisioning algorithms have been proposed, and they focus on the bandwidth efficiency in the construction of a single hose-model VPN. In practice, however, VPNs come and go and the dynamics will affect the performance of these VPN provisioning algorithms. If the frequency of adding and deleting VPNs is high, these algorithms will have a scalability problem. We propose in this paper a new network architecture for dynamic VPN construction. In the proposed architecture, adding a new VPN is much simpler and faster, and all that is required is to check if the edge routers have enough bandwidth. There is no need to check the bandwidth left on each internal link because the architecture guarantees that as long as the edge routers have enough capacities to accept the VPN, the internal links will never experience overflow caused by adding the new VPN. We present a linear programming formulation for finding the optimal routing that maximizes the amount of admissible VPN traffic in the network. We then exploit the underlying network flow structure and convert the linear programming problem into a subgradient iterative search problem. The resulting solution is significantly faster than the linear programming approach.     

Algorithms for provisioning virtual private networks in the hose model

Virtual private networks (VPNs) provide customers with predictable and secure network connections over a shared network. The recently proposed hose model for VPNs allows for greater flexibility since it permits traffic to and from a hose endpoint to be arbitrarily distributed to other endpoints. We develop novel algorithms for provisioning VPNs in the hose model. We connect VPN endpoints using a tree structure and our algorithms attempt to optimize the total bandwidth reserved on edges of the VPN tree. We show that even for the simple scenario in which network links are assumed to have infinite capacity, the general problem of computing the optimal VPN tree is NP-hard. Fortunately, for the special case when the ingress and egress bandwidths for each VPN endpoint are equal, we can devise an algorithm for computing the optimal tree whose time complexity is O(mn), where m and n are the number of links and nodes in the network, respectively. We present a novel integer programming formulation for the general VPN tree computation problem (that is, when ingress and egress bandwidths of VPN endpoints are arbitrary) and develop an algorithm that is based on the primal-dual method. Our experimental results with synthetic network graphs indicate that the VPN trees constructed by our proposed algorithms dramatically reduce bandwidth requirements (in many instances, by more than a factor of 2) compared to scenarios in which Steiner trees are employed to connect VPN endpoints.     

Resource Management for Virtual Private Networks

Virtual private networks (VPNs) have rapidly emerged as a leading solution for multi-site enterprise communication needs. Provider-managed solutions modeled on RFC 2547 serve as a popular choice for layer 3 VPNs, and the hose model has emerged as a common and simple service specification. It offers a hose of a certain contracted bandwidth to customers. With the growth in size and number of VPNs and the uncertainties in the traffic patterns of customers, providers are faced with new challenges in efficient provisioning and capacity planning for these networks and satisfying customer service level agreements (SLA). We suggest that a set of techniques can be used to help the provider build an adaptively provisioned network. These techniques involve continually processing measurement information, building inferences regarding VPN characteristics, and leveraging them for adaptive resource provisioning. We developed scalable techniques to infer VPN characteristics that are important for provisioning tasks. We demonstrated the feasibility of such provisioning techniques with existing measurement obtained using SNMP infrastructure from a large IP/VPN service provider. Our examination of measurement data yielded interesting new insights into VPN structure and properties. Building on our experience with analyzing VPN characteristics, we articulate an adaptive provisioning architecture that enables providers to effectively deal with the dynamic nature of customer traffic     

Managing Layer 1 VPN services

Control Plane architectures enhance transport networks with distributed signaling and routing mechanisms which allow dynamic connection control. As a result, layer 1 switching networks enabled with a distributed control plane can support the provisioning of advanced connectivity services like Virtual Private Networks (VPNs). Such Layer 1 VPN (L1VPN) service allows multiple customer networks to share a single transport network in a cost-effective way. However, L1VPN deployment still faces many challenges.In this work, we are concerned on configuration management and interdomain provisioning of L1VPN services. We propose an L1VPN management architecture based on the Policy-Based Management (PBM) approach. First, we describe the architecture and how it allows a single service provider to support multiple L1VPNs while providing customers with some level of control over their respective service. Then we explain how the architecture was extended to support interdomain L1VPNs by using the Virtual Topology approach. We also discuss the prototype implementation and evaluation of the proposed architecture. Moreover, this work is a tentative note before raising a more deep discussion related to interdomain provisioning of L1VPN services and implications of a policy-based approach for L1VPN configuration management.     

CATZ: Time-Zone-Aware Bandwidth Allocation in Layer 1 VPNs

The layer 1 virtual private network framework has emerged from the need to enable the dynamic coexistence of multiple circuit-switched client networks over a common physical network infrastructure. Such a VPN could be set up for an enterprise with offices across a wide geographical area (e.g., around the world or by a global ISP). Additionally, emerging IP over optical WDM technologies let IP traffic be carried directly over the optical WDM layer. Thus, different VPNs can share a common optical WDM core, and may demand different amounts of bandwidth at different time periods. This type of operation would require dynamic and reconfigurable allocation of bandwidth. This article evaluates the state of the art in layer 1 VPNs in the context of globally deployable optical networks and cost-efficient dynamic bandwidth usage. While exploiting the dynamism of IP traffic in a global network in which the nodes are located in different time zones, we study different bandwidth allocation methods for setting up a worldwide layer 1 VPN. We propose and investigate the characteristics of a cost-efficient bandwidth provisioning and reconfiguration algorithm, called capacity allocation using time zones (CATZ)     

An Overview of Virtual Private Network (VPN): IP VPN and Optical VPN

Recently, there has been rapid development and deployment of virtual private network (VPN) services. There are wide varieties of IP-based VPNs and optical VPNs (OVPNs) proposed in the literature and readers could easily get confused with so many different types of VPNs. The purpose of this paper is to present a comprehensive overview of the VPN and discuss the main issues associated with the design of IP VPN and OVPN. We first present a classification of the VPNs including CE-based, network based, customers provisioned, provider provisioned, connection oriented, connectionless oriented, port based, connection based, layer 1 VPN, layer 2 VPN, and layer 3 VPN, and describe different VPN protocols such as IPSec, GRE and MPLS. We then review the recent work on OVPN by different standard bodies, and outline the key requirements for OVPN service providers and customers. Finally, we describe several OVPN architectures appeared in the literature, highlight the future work in OVPN.     

Measurement-Based Characterization of IP VPNs

Virtual private networks (VPNs) provide secure and reliable communication between customer sites. With the increase in number and size of VPNs, providers need efficient provisioning techniques that adapt to customer demand by leveraging a good understanding of VPN properties. In this paper, we analyze two important properties of VPNs that impact provisioning: (1) structure of customer endpoint (CE) interactions and (2) temporal characteristics of CE-CE traffic. We deduce these properties by computing traffic matrices from SNMP measurements. We find that existing traffic matrix estimation techniques are not readily applicable to the VPN scenario due to the scale of the problem and limited measurement information. We begin by formulating a scalable technique that makes the most out of existing measurement information and provides good estimates for common VPN structures. We then use this technique to analyze SNMP measurement information from a large IP VPN service provider. We find that even with limited measurement information (no per-VPN data for the core) we can estimate traffic matrices for a significant fraction of VPNs, namely, those constituting the ldquoHub-and-Spokerdquo category. In addition, the ability to infer the structure of VPNs holds special significance for provisioning tasks arising from topology changes, link failures and maintenance. We are able to provide a classification of VPNs by structure and identify CEs that act as hubs of communication and hence require prioritized treatment during restoration and provisioning.     

Layer 1 virtual private networks: driving forces and realization by GMPLS

This article describes an emerging service for next-generation networks, layer 1 virtual private networks. L1VPNs allow customers desiring to connect multiple sites to be supported over a single shared layer 1 network. In the article we first describe the transport network's evolution and the shift in expectations of both service providers and customers. We provide an overview of the motivation for L1VPNs and examples of network usage. We follow by reviewing existing GMPLS mechanisms (addressing, discovery, and signaling) for realizing L1VPN functionality and identifying other work areas.     

Layer 1 virtual private network management by users

The layer 1 virtual private network (LlVPN) technology supports multiple user networks over a common carrier transport network. Emerging L1VPN services allow: L1VPNs to be built over multiple carrier networks; L1VPNs to lease or trade resources with each other; and users to reconfigure an L1VPN topology, and add or remove bandwidth. The trend is to offer increased flexibility and provide management functions as close to users as possible, while maintaining proper resource access right control. In this article two aspects of the L1VPN service and management architectures are discussed: management of carrier network partitions for L1VPNs, and L1VPN management by users. We present the carrier network partitioning at the network element (NE) and L1VPN levels. As an example, a transaction language one (TL1) proxy is developed to achieve carrier network partitioning at the NE level. The TL1 proxy is implemented without any modifications to the existing NE management system. On top of the TL1 proxy, a Web services (WS)-based L1VPN management tool is implemented. Carriers use the tool to partition resources at the L1VPN level by assigning resources, together with the WS-based management services for the resources, to L1VPNs. L1VPN administrators use the tool to receive resource partitions from multiple carriers and partner L1VPNs. Further resource partitioning or regrouping can be conducted on the received resources, and leasing or trading resources with partner LlVPNs is supported. These services offer a potential business model for a physical network broker. After the L1VPN administrators compose the use scenarios of resources, and make the use scenarios available to the L1VPN end users as WS, the end users reconfigure the L1VPN without intervention from the administrator. The tool accomplishes LlVPN management by users     

Optimal Link Weights for IP-Based Networks Supporting Hose-Model VPNs

From traffic engineering point of view, hose-model VPNs are much easier to use for customers than pipe-model VPNs. In this paper we explore the optimal weight setting to support hose-model VPN traffic in an IP-based hop-by-hop routing network. We try to answer the following questions: (1) What is the maximum amount of hose-model VPN traffic with bandwidth guarantees that can be admitted to an IP-based hop-by-hop routing network (as opposed to an MPLS-based network), and (2) what is the optimal link weight setting that can achieve that? We first present a mixed-integer programming formulation to compute the optimal link weights that can maximize the ingress and egress VPN traffic admissible to a hop-by-hop routing network. We also present a heuristic algorithm for solving the link weight searching problem for large networks. We show simulation results to demonstrate the effectiveness of the search algorithm.