Communications of the ACM
Communications of the ACM
Networks New Economical Virtual Private
Telecommunication operators can use our newly developed telecommunication design methodology to account for the uncertainty of traffic among corporate sites and develop economical virtual private networks (VPNs) for their prospective corporate customers.
Following the mass-market popularity and technical achievement of the Internet and the diversity of its communication applications, including the Web, email, phone, fax, file transfer, and video, businesses are increasing their use of telecommunication services. To minimize the related costs, they increasingly build and manage their own networks. However, these solutions are generally suitable only if the traffic is of sufficient volume. In most cases, they use VPNs based on the public infrastructures of their contracted telecommunication operators.
A VPN is a general-purpose communication environment allowing user organizations to communicate privately, securely, and transparently through shared resources provided by telecommunication operators, including AT&T and France Télécom [9], that is, it emulates a private wide area network (see Figure 1).
VPNs are one of the most profitable services for long-distance carriers. Infonetics Research, a market research and consulting firm (infonetics.com), projects the worldwide market for VPN and firewall hardware and software to reach $5 billion by 2006. This growing market involves aggressive international competition among telecommunication operators and equipment manufacturers.
Operators differentiate their VPN services along several key parameters, including: networking technology (such as Synchronous Optical Network/Synchronous Digital Hierarchy rings, Asynchronous Transfer Mode, Frame Relay, Internet Protocol, the Multiprotocol Label Switching Standard, and tunneling techniques); quality of service (QoS) (such as guaranteed constant bit rate, variable bit rate with guaranteed minimum rate, and best-effort service); and pricing strategy (such as flat rate, volume, time, and distance-based).
A user company can have difficulty deciding which VPN offer is best for its purposes; a high level of expertise is needed just to be able to compare offers. Moreover, traffic patterns are increasingly difficult to forecast in light of the recent development of so many network applications and the explosion in the number of corporate sites; variations over even a day can be critical to forecasting future traffic patterns, as well as the capacity needed to provide the contracted QoS.
Most proposed VPN offers claiming a particular level of QoS are based on static resource reservation, so it is generally impossible for a user company to reserve resources for only the time it actually needs them. Before selecting, installing, or using VPNs, a user company must consider the worst case in terms of traffic volume between any pair of its sites. The related restrictions can lead to classical VPNs, which can be prohibitively costly.
The aim of our new economical VPN concept developed at France Télécom over the past three years is to reduce costs without undermining QoS. It is independent of the technology used by a particular VPN service. The service is able to account for imprecision in traffic forecasts. Henceforth, instead of defining a traffic demand matrix among corporate sites, the traffic domain weighs the relationships among traffic components before resource reservation takes place. Resources are reserved in a static yet optimal way for routing corporate traffic. Some technical constraints, including stability and path length, may be imposed on the routing strategy. We also devised pricing models that adapt to their counterparts used in the context of classical VPNs.
Defining a Traffic Domain
Service level agreements (SLAs) are contracts between customers and network operators that depend on the traffic characteristics of a user company's operations, including user demand, as well as technology and competition. In most communications networks, traffic is described by an origin node (source), a destination node (sink), and a specific bandwidth. The most natural method to predict the traffic volume that must be carried in a VPN specifies the traffic matrix in which the entries give the required bandwidth between all source-sink pairs. Knowledge collected by network administrators and built into networking technology of the traffic matrix is valuable for network planning and optimization problems, including dimensioning, routing, and pricing.
Ensuring an operator can handle an SLA requires a description of the user company's traffic characteristics. However, due to the success of the Internet and the diversity of the related communication applications, it is increasingly difficult, indeed even impossible, to specify traffic in terms of required bandwidth between all source-sink pairs. Therefore, because operators can consider a specific traffic matrix, they must also employ a new model for describing traffic among a VPN's member sites when designing and evaluating a new VPN.
Assume that all traffic flowing through the network at a given time is represented by a traffic matrix, even though it may be variable and imprecise. The user company must specify a set of sites to be connected through the network, as well as its QoS requirements. This combined specification leads to the definition of a traffic domain containing all relevant traffic matrices.
More precisely, the relationships between the entries in a traffic matrix can be given by some linear inequalities, including limits on the incoming traffic into some VPN sites. More generally, we devised and now endorse the concept of "polytopes" to define a traffic domain. A polyhedron is a tool derived from polyhedral theory [8] corresponding to the solution set of a finite system of linear inequalities; a bounded polyhedron is called a polytope.
The traffic demand is said to be polyhedral if the traffic matrix is located at any point of a given polytope designated P. This polytope is the traffic polytope, specified either by a user company wishing to set up a VPN or by an operator designing a network for a customer. Figure 2 outlines an example of the use of a polyhedral model. Consider, for example, four VPN sitesA, B, C, and Dwith two kinds of traffic, one from A to B, the other from C to D. The user company specifies three QoS constraints involving these two traffic flows. Each QoS requirement provides a linear inequality separating admissible traffic matrices from the others. The intersection of these three admissible sets yields the traffic domain shown in Figure 2.
Operators must employ a new model for describing traffic among a VPN's member sites when designing and evaluating a new VPN.
Until now, there were mainly two service models for any VPN under consideration. The first, or pipe, model is a classical point-to-point architecture in which the traffic parameters, as well as the QoS commitment, are specified on the basis of traffic exchanged between two VPN sites. In the late 1990s, researchers at AT&T [6] introduced the second, or hose, modela point-to-cloud model in which traffic and QoS requirements are based on the traffic exchanged between a VPN site and the network. Both models are polyhedral. Moreover, the use of the polyhedral model can be fully justified through a number of examples.
The specification of the traffic polytope P is the most important issue for both the operator and the user company. It must be large enough to allow traffic flexibility but not excessively large to cause the wasting of network resources. To illustrate the problem, assume the user company or the operator has performed some periodic measurements of the variable traffic matrix. The convex hull of these matrices, that is, the smallest convex set enclosing all matrices, is the smallest polytope that can contain them. However, this traffic domain might be considered restrictive. It is possible for either the user company or the operator to define a traffic polytope containing all the measurements and satisfying any other linear properties; for example, the VPN sites may be located in two distant areasA and Band the links between them may be costly to design and install. It may thus be useful to give an upper bound (A/B)max for the traffic going from A to B. The linear inequality that expresses the fact that the sum of the entries of the traffic matrix corresponding to traffic from A to B is equal to or less than (A/B)max can be useful in specifying the traffic polytope P. Several polyhedral models either provide some guarantees about the routing cost of each traffic matrix belonging to the traffic polytope P or account for time differences between distant areas if the focus is on, say, international corporations [2].
Another issue that must be addressed is how a network operator might verify that the current traffic matrix is in the polytope Pa process that can be viewed as traffic conformance testing. In some cases, the test can be performed at the access nodes. Some periodic measurements can also be made to check conformance. Moreover, as resources are reserved for every VPN and if the traffic is not consistent with the polyhedral model, the QoS of the VPN may be degraded. That is, the operator may not need to check the conformance of the traffic, as a VPN cannot use more resources than those reserved for it.
Note that one or several VPN sites can be considered access points to the public Interneta common assumption in the VPN context where, for security reasons, user companies prefer a limited number of public access points [7]. This assumption can be integrated into our VPN model.
Routing and Provisioning
To rigorously guarantee QoS, resources must be reserved for VPNs. We assume this can be done on any link in the operator's network. No other special assumptions are made about the architecture and the operator's network. The polyhedral traffic of a VPN has to be routed through the operator's network using the reserved resources. Thus, some routing paths have to be determined between the VPN's sites; they depend on three factors: user-company traffic demand, the operator's network, and the routing strategy.
The routing strategies used in telecommunication networks [1, 5] can be classified in various ways depending on a number of parameters, including:
- The routes (such as centralized and distributed);
- The frequency these routes are computed or changed (such as static, period-dependent, dynamic, and adaptive);
- The required QoS (such as best effort, bounded end-to-end delay, low loss probability, and limited delay variations) [4, 5];
- The kind of network paths used for routing, including multi-path (traffic split through many paths), single-path (only one path between each pair of VPN sites), and shortest-path (classical Internet routing) [3, 5]; and
- The criteria to be optimized when the routing paths are computed (such as maximize throughput, maximize revenue, minimize mean delay, minimize maximum load, and minimize routing cost).
The strategy chosen by the operator for economical VPNs is either multi-path or single-path, computed in a centralized and static way. A number of QoS policies can be considered, and several performance criteria can be taken into account to compute the routing paths.
Routing is computed in a centralized way because VPN sites should not participate in routing decisions when their traffic is moving through the telecommunication operator's network. Moreover, the routing has to be simple enough for the operator to implement and static to guarantee the QoS; the paths used for routing do not depend on the current traffic matrix. Note that this kind of routing provides some stability and is easy to implement because real-time computation helps find optimal routing paths; these paths are optimally computed by accounting for these traffic domain and the network capacities.
Splitting the traffic over many paths leads to efficient use of network resources. Assume, for example, that two pathsP1 and P2are used between two VPN sites. The traffic demand between them is split according to some optimal splitting coefficients computed by the algorithm described in [2]; for example, 70% of the traffic is carried on P1 and 30% on P2. These coefficients should not change, but the amount of traffic carried on the two paths depends on the current traffic matrix.
Given the costs wl induced by the reservation of one unit of capacity on any network link l, the whole VPN provisioning cost is computed by the operator using an efficient algorithm [2] that gives the minimum capacities that have to be reserved to carry the user company's polyhedral traffic demand.
In Figure 2, the network link R1-R2 can aggregate the traffic going from A to B and from C to D. For any traffic matrix inside the polyhedral domain, the sum of the two traffic components is always less than approximately 10.5 units of capacity. Therefore, the network designers can reserve a capacity of 10.5 for this VPN to carry any traffic configuration. On the other hand, if they consider a classical traffic model, then 20 units of capacity have to be reserved10 units for demand A
B, 10 units for demand CD. With the polyhedral model, the cost is thus approximately half.
More generally, let S be the number of VPN sites. We showed in [2] that the provisioning cost of an economical VPN can be S(S-1) less than the cost of a classical VPN. This bound is achieved by some networks, including the star configuration [2].
Note that it is also possible for the operator to consider dynamic routing, depending on the current traffic matrix. The optimization problem (routing and provisioning) can be solved through bilinear programming (much more difficult than linear programming). However, such optimal fully dynamic routing cannot be implemented on networks. Nonetheless, it may be possible to define many polyhedral traffic domains (such as one for the morning, another for the evening). A routing strategy is associated with each polyhedral domain. The routing patterns can be different to minimize the resources used by the VPN. Because such period-dependent routing is an intermediate strategy between static routing and fully dynamic routing, its complexity is somewhere between the complexities of the routing strategies.
Pricing Strategy
An economical VPN architecture can be configured and provided by many telecommunication operators. One of the most important issues to be studied by them is the pricing of the service. Three important properties introduced in [2] help operators propose pricing models:
Profit. The profit condition is the easiest to understand. The price to be paid by a user company for an economical VPN must be greater than the provisioning cost of the VPN. Even if this condition is relaxed during the service launch phase to attract new customers, it is a mandatory condition for any successful business.
Simplicity. Corporate customers appreciate the simplicity and transparency of pricing models, allowing them to predict the price they will pay and adjust their demands accordingly. A pricing model can sometimes be represented through a simple mathematical model devised by operators and shared with prospective customers. Another solution available to operators involves a simple pricing application that can help analyze a particular company wishing to estimate the price of an economical VPN.
Coherence. A telecommunication operator proposing an economical VPN service (polyhedral model) is likely to also propose a classical VPN service (pipe model). Thus, the two services should be priced to account for the technical differences between them.
Now suppose a traffic matrix belongs to the polyhedral domain of an economical VPN; the price paid by a user company to route only this matrix (classical VPN service) should therefore be lower than the price of our economical VPN service. Suppose, too, a user company generates a polyhedral demand using a pipe model. This can occur if the components of the traffic matrix corresponding to the pipe model are sufficiently large ([2] includes a precise mathematical definition of this concept). The price of the corresponding classical VPN service should therefore be greater than the price of the economical VPN service.
Some simple pricing models satisfying all three conditionsprofit, simplicity, and coherenceare also described in [2]. Note that the definition of the traffic domain can be reexamined by either the operator or the customer after the price estimation.
Conclusion
Following deregulation of the telecom markets in many countries worldwide over the past 10 years, many network operators began to offer competitively priced VPN services. Therefore, they've sought innovation in VPN architecture, design, and management in order to claim a larger share of the VPN market. The new economical VPNs now herald the field's next generation. The cost of an economical VPN can be much lower than the cost of a classical VPN, and the traffic variations can be more easily taken into account.
Figure 3 outlines the main steps needed by operators to design and install proposed economical VPN systems. First, a traffic domain (a polytope) has to be specified on the basis of some traffic measurements or user company specifications. The operator then computes an optimal static multi-path/single-path routing scheme using the algorithm in [2] while accounting for network resources and costs. Finally, the operator proposes a price based on models reflecting the competition, as well as classical VPN services.
References
1. Ash, G. Dynamic Routing in Telecommunications Networks. McGraw-Hill, New York, 1998.
2. Ben-Ameur, W. and Kerivin, H. Flexible VPN Framework. Tech. Rep. NT/DAC/OAT/04.25, France Télécom R&D, 2002.
3. Ben-Ameur, W., Michel, N., and Liau, B. Routing strategies for IP networks. Telektronikk Magazine 2, 3 (2001).
4. Crawly, E., Nair, R., Rajagopalan, R., and Sandick, H. A Framework for QoS-Based Routing in the Internet. IETF RFC 2386, 1998.
5. Davie, B. and Peterson, L. Computer Networks: A Systems Approach. Morgan Kaufmann, San Francisco, 2000.
6. Duffield, N., Goyal, P., Greenberg, A., Mishra, P., Ramakrishnan, K., and van der Merive, J. A flexible model for resource management in virtual private networks. In Proceedings of ACM SIGCOMM (Cambridge, MA, Aug. 30Sept. 3). ACM Press, New York, 1999, 95108.
7. Huston, G. ISP Survival Guide. John Wiley & Sons, New York, 1998.
8. Nemhauser, G. and Wolsey, L. Integer and Combinatorial Optimization. John Wiley & Sons, New York, 1988.
9. Yan, R. and Strayer, T. Virtual Private Networks: Technologies and Solutions. Addison-Wesley, Reading, MA, 2001.
Figures
Figure 1. Corporate sites connected through a public infrastructure.
©2003 ACM 0002-0782/03/0600 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2003 ACM, Inc.
No entries found