WIXLIB

Path SelectionProcedure- Networktopology andnode locationsCandidate TreesGeneration- QoS constriants(Maximum delayrequirement)Feasible TreesSelectionnOff-line GlobalOptimizationProcedure13VPN nDepth n-1VPN 1Virtual NetworkDimensioning- GoS- Packet l LinkDimensioningNetwork RouteOptimizationDepth 1- Trafficdemand matrix- Qos- Link costmatrix234n(a) Sink-tree with 1-hop depthChange innetwork topologyVPNs optimal routing planandVirtual link dimensionChange inlink costChange intraffic demandOn-line Traffic Optimizationand MonitoringFigure 2 : VPN traffic engineering procedureconstraints at the traffic layer such as packet loss rate anddelay. In addition, considering the effects of statisticalmultiplexing among different connections (when possible),bandwidth allocation can be reduced. Here, we use theconcept of “effective bandwidth” to represent service ratesrequired by each traffic connection belonging to differentservice classes. Effective bandwidth calculations willencapsulate the QoS requirements in term of packet loss rateand delay. Thus, by using the concept of effective bandwidth,traffic flows with different characteristics and QoSrequirements can be represented as being steady with adeterministic bandwidth requirement. This simplifies ouroptimization model. Lastly, the routing optimization willoptimally assign a route to a traffic demand, given a set ofcandidate routes and link capacities. Other than minimizingcost of laying out a given traffic, a route assignment may alsoaim to balance the load across the network such that thenumber of over-utilized links and under-utilized link isreduced.IV. TREE SELECTIONThe choice of a tree is important as it affects the goodnessof the solution obtained and the computation time. To reducethe problem size (and thus computation time) for a largenetwork, a precomputed candidate set of trees will be used inthe model over which the optimal routes and capacityrequirements are determined. A path set will be generated foreach source and its destinations given the physical networktopology. This set will be limited by a maximum hop-countallowed between each source-destination pair such that themaximum end-to-end delay is bounded. The choice of arouting tree also affects the capacity required and ifbandwidth of traffic flows is aggregated and multiplexed21(b) Sink-tree with (n-1)-hop depthFigure 3 : Sink-tree routing paths for n nodeswhen they are merged at one node. For connections withinthe same class of service, in which a statistical multiplexingcan be achieved, a certain part of allocated bandwidth can beshared among them.Hence, in tree selection, there is a trade off, betweenminimizing an end-to-end delay requirement versusminimizing cost of link capacity. Shown in Figure 3 are twodifferent choices of a sink-tree for n nodes. The depth of atree is defined as the distance between the root node and aleave node. Figure 3(a) show a sink-tree of 1-hop paths with amaximum depth of 1. This choice of a tree yields a minimumdelay between demand node-pairs, but, since 1-hop pathsmerge at the root node, no bandwidth aggregation is possible.Oppositely, the tree in Figure 3(b) with a depth of (n-1)yields a maximum bandwidth gain due to statisticalmultiplexing at all links after the merge points. Differenttypes of trees including spanning trees, shortest (distance)path trees and Steiner trees (minimum-cost trees) are amongpotential choices.V. MPLS-VPN DESIGN FORMULATIONSGiven a network topology, node location and link capacity,an optimization model is formulated for VPN design. Aphysical network is represented by a graph G (N , L, C ) whereN , L , C is a set of nodes, links and link capacities of thenetwork respectively. M ( M N ) is a set of edge nodes(edge routers) where there is a demand traffic entering orexiting. Thus, N M represents a set of core nodes (corerouters). The complete notation of the formulation is givenbelow. For each link l L , utilization factor α l limits theproportion of the link capacityClto be allocated for VPNtraffic. This utilization factor may be used to protect certainlinks from being overly subscribed or subjected to potentialcongestion. For example, a smaller value of α l may beassigned to links connecting to core-routers than onesconnecting to edge-routers. This factor is assumed to beknown.

A. NotationαlMaximum utilization factor of linkC. Selection of Candidate PathsFeasible sink-trees or multipoint-to-point paths are used inthe optimization model where a traffic demand may beassigned. The feasible path set Pkν , s can be pre-computed forl LPν , sDemand set index, K MSet of feasible sink-trees ending at nodeDν , s, kspanning all nodes m M of service class s S ofVPN ν VSet of point-to-point demand pairs in demand setKkk KBνd, h, s, kof service classs Sof VPN ν VBandwidth requirement of demand pairservice classs Sk Nd Dν , s, kofof VPN ν V during hour-periodh HYlSizing (topology) variables, capacity assigned toψlVPN traffic on link l LCost of a capacity on linklCapacity at linkUν , hhour-periodpX ν , h, s , kl Ll Lallocated to VPN ν V duringh HDemand-path routing decision variables 1γ lp, dif pathp Pkν , sk Kof service class s S of VPN ν V duringhour period h H 0 otherwiseLink path incidence matrix 1if demand pairuses pathEBνl , h, s, kis used for demand setd Dν , s, kp Pkν , sof setk Kthatis directed using linkl L 0otherwiseEstimated BW requirement of all demand typeVPN ν and service class s having different QoSrequirements (i.e., maximum end-to-end delay requirement).A path p Pkν , s is selected from candidate sink-tree pathswhich are spanning trees rooted at egress node k K andspanning over all the edge nodes m M or a subset of theedge nodes. Set of candidate paths can be generated byenumerating all distinctive spanning trees. Algorithms todetermine these trees can be found in previous worksincluding [7]. The maximum end-to-end delay requirement istranslated in to the hop-count limitation constraint. Thisconstraint will limit the path set where only feasible paths areselected from all candidate paths.D. Bandwidth CalculationThe bandwidth requirements at each link will be estimatedbased on an effective bandwidth calculation [8] where thetraffic parameters such as connection peak rate and itsburstiness are taken into account. Two classes of services in adifferentiated service model are considered includingpremium/guarantee service and assured services.( i ) Premium ServiceIn the premium service class, packet loss, delay and delayjitter must be bounded. The traffic of this class requires anabsolute bandwidth guarantee. Thus each traffic connectionin this class is allocated a bandwidth equal to a source peakrate R peak . Assuming that η connections are multiplexedwithin one link, total allocated bandwidth ( Eqv )on link l L of service class s S ofVPN ν V during hour-period h H) Equivalent bandwidth calculation function fortraffic in service class s S with requirement ofbandwidth amount B ( with traffic descriptor Tsand quality of service requirement Qs )where η is derived from an inverse Erlang formulation suchthat a grade of service constraint (GoS) of a connection (i.e.,connection blocking probability - P b ) is met.B. Traffic DemandThe complete matrix of VPNs traffic demand is assumed tobe given. It can be derived from all SLAs (Service LevelAgreements), between customers and service providers.SLAs typically specify various classes of service and howmuch traffic in each service class a user is allowed to send. Inmore detail, for each source-destination (ingress-egress)node-pair, the matrix of each VPN specifies the requiredbandwidth and its QoS parameters (i.e., end-to-end delayrequirement, delay jitter). Traffic demand Dν , s, k will be( ii ) Assured ServiceIn the assured service class, applications are expected tohave the ability to tolerate a certain amount of delay and loss.For this traffic class, a mean bandwidth guarantee is onlyneeded along with a statistical delay bound. In bandwidthcalculation, source traffic in the assured service class isassumed to be characterized by its source peak rate - R peak ,k KEqv(B, Ts , Qsassigned a route based on its egress nodewhere K M , called the demand set index.k K,Eqv(1) η R peak(2)η InvErlang ( a, Pb )where a is the source utilization or an offered load of aconnection.utilization factor - ρ , and mean burst period - b . In this case,the allocated bandwidth ( Eqv ) is less than η R peak .{Eqv min η m α ′σ ,η cˆi}(3)

where α ′ 2 ln(ε ) ln(2π ) given m a mean bit rate, σ a variance bit rate, and ε buffer overflow probability.Equivalent capacity estimation for each source ĉi iscˆi R peak(a 1)2 4 ρ aa 1 (4)2a traffic demand pairDν , s, kand bandwidth requirement, (iii) a precomputed sink-tree path setcorresponding link path incidence matrixν,sand aγ lp, d .ThePkformulation seeks to find VPN link capacity allocationand its routepX ν , h, s , kUνl , hfor all VPNs in each hour period.Formulation-I shows the case where there is no bandwidthaggregation. The objective of the formulation is to minimizethe total capacity cost in providing service to all VPNs. Foreach VPN, service class, and hour period, constraint (5)selects only one path from a pre-computed set of feasiblesink-tree paths ending at egress node Pk for each demand setk . Constraints (6) (9) imposes that capacity assigned ateach link must not be greater than a utilization limit of linkcapacity ( α l Cl ). Note that, in constraint (6), the capacitycalculation is done separately for each traffic demand-pair.Constraints (10) and (11) require that routing variables andcapacity assignment variables must be positive. Thisformulation yields different route assignment and capacityallocation at different hour-periods.Formulation-IMinimize ψ l Yl EBν , h, s, k ν V,s Sh H,l LXνp, h, s, k,l L(6)(7)l L; : l L(8)(9){0, 1}; : ν V ,h H,s S,k K,p Pkν , s; : l L 0Ylk K; : h H , Yl , Uν , h α l ClYl(10)(11)F. General Case with Bandwidth Aggregation.Here, we introduce a case where bandwidth of varioustraffic demand is aggregated at links where possible. Theaggregation only occurs within a demand set destined to thesame egress node of a VPN. In this case, the objectivefunction and constraints are similar to previous case exceptfor constraint (6) is replaced by (12). The total traffic demandrouted on one link is aggregated and bandwidth allocation isdone together.Formulation-IIMinimize ψ l Yll LSubject to :(5), (7), (8), (9), (10), (11), and EBνl , h, s, k Eqv Bνd, h, s, k γ lp, d Xνp, h, s, k , Ts , Qs d D p Pν , sν , s, kk : ν V , h H , s S , k K , l L(12)PRELIMINARY NUMERICAL STUDYThe mixed-integer formulations for the VPN designproblem, shown previously, have a NP-hard complexity. Asimplified version of these formulations can be derived whenwe only consider traffic demand of VPNs having one serviceclass and hour-period. Thus, the formulation-I can be reducedto:VI.Formulation-IIIMinimize p Pk 1; : ν V ,Uνl , hh Hl ψ l YlSubject to :Subject to : ; : ν V ,l Ll LpX ν , h, s , k ; : ν V ,E. General Case without Bandwidth AggregationUsing a sink-tree routing path, traffic demand can bemerged within the network, thus the required bandwidth afterthe merged point can be allocated separately for eachdemand-pair or multiplexed together within the same serviceclass. The latter yields a reduction in bandwidth requirementsespecially for traffic in the assured service class, due to astatistical multiplexing gain. The basic formulations are givenbelow. The model assumes that the followings are given: (i)link utilization factor α l and the link capacity Cl , (ii) set ofp Pν , sk lb(1 ρ ) ln εBassume that B buffer size and ε packet loss ratio areknown. The number of connections η multiplexed can befound as before from an inverse Erlang formulation.Bνd, h, s, k pdl Eqv Bν,,T,QγX h, s, ks s p, dν, h, s, k p Pν,sd Dν, s, kk s S k KwherealEBν, h, s, kh H,s S,k K(5)X kp 1; : k K(13)

Eqv Bkd , T , Q γ lp, d X kp Yl k K d Dk p Pk ) α l ClYlpXkYl( {0, 1} 0; : l L; : l L(14)(15); : k K , p Pk(16); : l L(17)(a) 8-node networkIn the same manner, the formulation-II can be reduced to :Formulation-IVMinimize ψ l Yll LSubject to :(13), (15), (16), (17), and dlp EqvB γ X,T,Q p, d k Ylk d Dk k Kp Pk ; : l L(18)Obtaining a solution to problems stated in formulation-IIIand IV is easier than ones in formulation-I and II. A pilotstudy was conducted by translating formulation-III and IVusing the AMPL model description language and solution isobtained using CPLEX 6.6 optimization solver implementinga branch and bound solution technique. The networks studiedwere small networks with 8 and 10 nodes, with equalcapacity link-cost, shown in Figure 4. The capacity of eachlink Cl was set to Cl 1000 ; l L , so that capacity was not alimiting factor. Different cases are shown in Table 1. Forcase-I, asymmetric load of fixed demands was studied that isthere was one unit of demand from each node to every othernode. For case-II, a symmetric load of demand wasconsidered with the demand generated from a Uniform(1,5)distribution. For case-III, an asymmetric load of demand wasstudied with nonzero demand only from a subset of networknodes. The nodes with nonzero demand were randomlyselected with a random load drawn from a Uniform(1,5)distribution.From Table 1, one can see that the optimal solutionsobtained from a sink-tree design with no bandwidthaggregation are not different from ones obtained from a fullmesh design. It is observed that a path used in a sink-treedesign (with no bandwidth aggregation) is simply a shortestpath tree. This is similar to a full-mesh design where ademand is routed along a shortest path. In terms of cost, whenbandwidth aggregation is considered in a sink-tree design, acost reduction is realized approximately by 30-40 percent inall cases. This is because traffic demand may be routed usinga sink-tree path that is different from a shortest path tree.Note that there is a huge difference in the number of LSPsused between the sink-tree and full-mesh design approaches.In order to obtain a solution to general case problem,where multi-service and multi-hour period are considered,and where multiple VPNs layouts are simultaneously(b) 10-node networkFigure 4 : Networks under studyoptimized, one seeks to find more efficient solution methoddue to the problem complexity. Results from the pilot studysuggest that a heuristics method may start out its search froma so-called near-optimal solution obtained by routing demandtraffic using shortest-path trees, then seek out a bettersolution as it moves along a projected direction within afeasible search space. One may apply various heuristicstechniques explored in the literature, such as greedyalgorithm, simulated annealing, or genetic algorithm, to solvethis problem.VII. CONCLUSIONIn this paper we have formulated the MPLS based multihour VPN design problem with and without bandwidthaggregation. We modeled a VPN as multiple logical sinktrees which reduces the number of label switch paths andallows the possibility of bandwidth savings. Samplenumerical results for different studied cases shows that asink-tree design with no bandwidth aggregation yields thesame solution as a full-mesh design where demand wasrouted along a shortest-path. However, when bandwidthaggregation is considered in a sink-tree design, demand wasrouted along a tree that is different from a shortest-path treesuch that a link capacity assignment can be smaller and thetotal capacity cost reduction is realized.[1][2][3][4][5]REFERENCESE. Rosen, A. Viswanathan, and R. Callon,"Multiprotocol Label Switching Architecture," RFC3031, January, 2001.B. Davie and Y. Rekhter, MPLS : technology andapplications,San Francisco: Morgan KaufmannPublishers, 2000.D. Awduche, et al., "Requirements for TrafficEngineering Over MPLS," RFC 2702, September, 1999.S. Kent and R. Atkinson, "Security architecture for theInternet Protocol," RFC 2401, November, 1998.K. M. Girish, B. Zhou, and J.-Q. Hu, "Formulation of theTraffic Engineering Problems in MPLS based IPNetworks," Proceedings ISCC 2000. Fifth IEEESymposium on Computers and Communications. , LosAlamitos, CA, USA, pp. 214-219, 2000.

[6] H. Saito, Y. Miyao, and M. Yoshida, "TrafficEngineering using Multiple multipoint-to-point LSPs,"IEEE INFOCOM 2000, pp. 894-901, March, 2000.[7] N. Christofides, Graph Theory and AlgorithmicApproach, London: Academic Press Inc., 1986.Full-Mesh DesignTopologyOptimalCostSimplexIterationsNo. ofLSPs[8] R. Guerin, H. Ahmadi, and M. Naghshineh, "EquivalentCapacity and Its Application to Bandwidth AllocationinHigh-Speed Networks," 7th ITC Seminar, Morristown,NJ, October, 1990.Sink-Tree(s) Design(w/o BW aggregation)OptimalSimplexNo. ofCostIterationsLSPsSink-Tree(s) Design(with BW aggregation)OptimalSimplexNo. ofCostIterationsLSPsCase I : Symmetric 0174308109092510Case II : Symmetric 211290562242104104,23910Case III : Asymmetric 763521221671295657Table 1 : Comparison for different design cases

VPN over an 8-node MPLS network. Assume that there is a directional demand of one unit between 3-node pairs in VPN network and each link in the MPLS network has one unit cost. A full-mesh design requires 6 LSPs compared to 3 LSPs in sink-tree design. Both designs use the same links in MPLS network. However, the first yields 14 unit cost while .