An optimal dynamic resources partitioning auction model for virtual private networks

Please download to get full document.

View again

of 14
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Mental Health

Published:

Views: 0 | Pages: 14

Extension: PDF | Download: 0

Share
Related documents
Description
An optimal dynamic resources partitioning auction model for virtual private networks
Tags
Transcript
  Telecommun SystDOI 10.1007/s11235-013-9710-5 An optimal dynamic resources partitioning auction modelfor virtual private networks Ahmad Nahar Quttoum  · Abdallah Jarray  · Hadi Otrok  · Zbigniew Dziong © Springer Science+Business Media New York 2013 Abstract  In this paper, we consider the problem of optimiz-ing the Internet Service Provider (ISP) profit by providinga periodic Dynamic Partitioning (DP) model for utilizingnetwork resources in the context of Virtual Private Net-works (VPN). In literature, Complete Sharing (CS), Com-plete Partitioning (CP), and Bandwidth Borrowing (BR)techniques have been proposed for resource allocationwhere the following limitations can be noticed: VPN opera-tors can exaggerate about their required resources, resourcesmight be underutilized, and optimal bandwidth utilizationis not guaranteed. To overcome the above limitations, wepropose to dynamically partition the resources over differ-ent QoS classes through periodic auctions that can reducethe reasoning of exaggeration and maximize the ISP profit.Thus, we formulate our problem based on the Integer Lin-ear Programming (ILP) that allows us to maximize the ISPprofit and provides the optimal: (1) set of profitable VPNconnections, (2) bandwidth division of each network linkamong QoS classes, and (3) routing scheme for the accepted A.N. Quttoum (  )Computer Engineering Department, The Hashemite University,P.O. Box 150459, Zarqa, Jordane-mail: Quttoum@hu.edu.joA. Jarray  ·  Z. DziongElectrical Engineering Dep., ETS, Université du Québec,Montréal, QC, CanadaA. Jarraye-mail: Abdallah.Jarray.1@ens.etsmtl.caZ. Dzionge-mail: Zbigniew.Dziong@etsmtl.caH. OtrokDepartment of Computer Eng., Khalifa University of Science,Technology & Research, Abu Dhabi, UAEe-mail: Hadi.Otrok@kustar.ac.ae demand. Furthermore, the proposed ILP model allows us tostudy the sensitivity of the ISP profit to a targeted revenueobjective. Keywords  Virtual Private Network (VPN)  ·  Resourceallocation  ·  Dynamic partitioning  ·  Periodical auction  · Linear programming 1 Introduction We are witnessing an unprecedented demand for InternetService Providers (ISPs) to support a wide variety of VirtualPrivate Networks (VPNs). These VPNs use the ISPs’ publicinfrastructure to establish secure and reliable services ac-cording to contracted Service Level Agreements (SLA) [9].Resource management is one of the main challenges facingISPs, where each VPN may have different requirements andrequired Quality of Service (QoS) guarantees. The growingdemands for such VPN services with certain QoS satisfac-tion conditions necessitate the ISPs to efficiently utilize theirbandwidth resources. Models to provide an efficient and ef-fectiveresourceallocationschemesareextremelyimportant.Relying on the current management models that attempt di-rect interactions with the ISPs is not satisfying anymore, asthey have many limitations that can be summarized as fol-lows: (1) These models increase the management operationexpenses. (2) They provide slow response times. Such limi-tationscanleadtohighratesofusers’dissatisfaction.Conse-quently, the need is emerging to find an alternative resourcemanagement models that overcome the current limitations.Complete Sharing (CS) [14, 17] and Complete Partition- ing (CP) [5, 13, 14] models are proposed in the literature to cope with the above management problem by creatinga framework for automated management. In CS, network  A.N. Quttoum et al. resources are shared over all classes without any division.While, in CP, resources are statically divided among QoSclasses where each class uses its own allocated resources.Such approaches are able to automate the resources alloca-tion,whileatthesametimetheycreateseveralproblemsthatcan be summarized as follows:– In CS approach, resources are allocated in a First AskFirst Allocate (FAFA) scheme, where one QoS class canoverwhelm all other classes in a way that reduces the ISPprofit.– In CP approach, resources can be underutilized which re-duces ISPs profits.– Due to the long-term SLA agreement, VPN operatorsmight exaggerate about their required resources to guar-antee their QoS and to cope with any unpredicted vari-ations in the network state. Such a behavior can affectthe ISP profit, and maximize the VPN demands block-ing rates. Indeed, when demand for the resources exceedsthe capacity, avoiding exaggeration allows to admit moreVPN connections (using the same amount of bandwidthresources), which can reduce the blocking rates while col-lecting the same profits.To overcome the problem of underutilization in CP, theBandwidth Borrowing (BR) technique has been proposed,[6, 21], to enable the ISPs to provide better resource utiliza- tion that guarantees the QoS for all VPNs. According to thedynamicity of the traffic, the BR technique allows the ISPto borrow the extra resources of the underloaded links andreallocate them to the overloaded ones. While yet, as longas the CP attempts a static partitioning scheme, BR cannotprovide an optimal bandwidth utilization solution, where wemay have many underloaded links with no overloaded ones(or vice-versa), in such a case how the BR would work?To overcome the above limitations, we propose deploy-inga  periodic-dynamicresourcepartitioningmodel (DP)forallocating the network bandwidth resources to VPN oper-ators. In DP, the dynamic class division process will takeplace in a periodic auction manner, where VPN operatorswill be competing to win the resource allocations throughtheir submitted prices and connections’ demands. The net-work planning time is divided into a set of periods in or-der to reduce the reasoning of exaggeration and to eliminatethe needs for any borrowing technique. The length of there-optimization period depends on the provided service du-ration. Demands with different service durations can be di-vided into groups, each with certain period length. At eachnew period, the profitable VPN connections are selectedthrough an auction mechanism in order to maximize the ISPprofit. Therefore, we develop and implement an  Integer Lin-ear Program  (ILP) solved using the ILOG CPLEX concerttechnology environment. The Proposed ILP maximizes theISP profit and comes-up with:– The optimal set of the profitable VPN connections.– The optimal bandwidth division of each network linkamong different QoS classes.– The optimal routing scheme of the accepted VPN connec-tions, with respect to their QoS specifications.Furthermore, the proposed ILP allows us to study thesensitivity of the ISP profit to a targeted revenue objec-tive represented by the Profit Percentage Parameter (PPP).Through PPP, we are able to find the optimal tradeoff set-ting that maximizes the ISP profit while not breaking thedemands blocking constraint. Consequently, our contribu-tion is a model that is able to:– Efficiently utilize the network bandwidth resources,where through the dynamic partitioning we are able toconsider the changes of traffic demands.– Increase the VPN operators’ satisfaction rates, since re-sources are utilized efficiently and the allocation pricesare market competing.– Minimize the SLAs violations as exaggeration motiva-tions are reduced.The rest of the paper is organized as follows: Sect. 2presents the problem statement. Section 3 illustrates ourdynamic resource partitioning model and the proposed se-lection algorithm. Section 4 lists the proposed performancemetrics, followed by the computational results in Sect. 5. InSect. 6, we present the related work. Finally, Sect. 7 con- cludes the paper. 2 Problem statement The  Complete Sharing  (CS) approach proposes an auto-nomic management framework, where the whole networkresources are shared between all VPN operators, so eachof them can use any bandwidth available at any given mo-ment. With no link bandwidth division, in the CS approach,all QoS classes can share the network resources withoutdiscrimination. Through this, the model is supposed to en-sure the delivery of services according to predefined SLAs.These SLAs are constructed after negotiations between theISP and the VPN operators. From the ISP prospective, giv-ing the VPN operators such a privilege can provide bet-ter utilization of the network resources, assuming that theVPN operators know well their changing requirements, andaccordingly they can acquire the required resources basedon their actual needs. Naturally, as long as the VPN opera-tors behave according to their declarations, deploying suchan approach can increase bandwidth utilization due to thestatistical multiplexing, which results in better satisfactionrates and higher profits at the same time. However, in real-ity, VPNs can exceed their declarations as long as there isno link bandwidth division, and one class may overwhelm  An optimal dynamic resources partitioning auction model for virtual private networks all other classes which creates several problems like SLAsviolations, high blocking ratios, and low profit rates.In the  Complete Partitioning  (CP) approach, the scenariois somehow different. Here the resources are partitionedamong the provided service classes in a  static  way, based ona one-time bandwidth partition for all network links. Withsuch a static scheme, each class is allowed to exclusivelyuse its portion of the provided resources. This can solve theSLAs violation problem, but it may lead to low bandwidthutilization as resources might be underutilized.Exaggeration is considered as a common drawback of both CS and CP, where VPN operators might exaggeratetheir requirements in order to cope with any sudden or un-predictable changes in the network state and link conditions,so they tend to keep a spare amount of resources that enablesthem to overcome and cope with such situations. This is dueto the long-term SLA that does not allow users to changetheir resource requirements according to their needs. Such aproblem can be solved either through a short term resourcesharing model that reduces the reasoning of exaggeration orthrough a penalization model that penalizes any exaggera-tion behavior [19, 20]. To overcome the problem of resource underutilization,the  Bandwidth Borrowing  (BR) [6] technique has been pro-posed. The BR attempts the idea of borrowing the resourcesfrom the underloaded links and allocating them to the over-loaded ones. Accordingly, the BR scheme can provide betterutilization of the network bandwidth resources, and betterSLAs guarantees. However, resources are utilized in a non-optimal way that can reduce ISP profit. Also, such behav-ior can entail a high management load to cope up with thechanges of traffic load and utilize the unused resources inrealtime. 3 Dynamic resource partitioning approach In this section, we present our  Dynamic Partitioning  (DP)approach that improves the CS and CP techniques, and over-comes their limitations by virtually partitioning the networkbandwidth resources in an efficient way based on  periodicauctions , where resources are allocated to the best biddersproviding profit maximization. In this context, we proposea resource management approach based on short-term SLAsthat takes into account the desired ISP objectives over thetime.Toachievethis,VPNoperatorsareaskedtorevealtheirconnection demands in terms of: source-destination nodes,required QoS classes, and their offered prices (bids). Ac-cordingly, the DP algorithm presented in Table 1 is deployedto provide an optimal allocation mechanism. Table 1  DP selection algorithmAlgorithm2: Selecting the Winning VPN operators in DP1:  Input:  At each auction round  t  , the ISP broker  do ;2: Collect the VPN operators connection demands  K ( p k ,  QoS  k ,s k ,d  k ) received through time ( t   − 1 ,t  ];3: Formulate the problem as an ILP;4:  Solve  the ILP, and find the optimal set of VPN connections;5:  Output:  the VPN connections that won the resource allocationsand the profit collected from these connections; 3.1 DP approach 3.1.1 Algorithm In our DP approach, resources are allocated based on  dy-namic auctions  that are held in a periodic manner, withthe aim of selecting the best set of VPN operators from acompeting environment. VPN operators’ requests are repre-sentedintermsof  connectiondemands .Thetermconnectionhere is defined as a secure network tunnel that is layered ontop of a public network, such tunnel has some QoS param-eters (i.e. bandwidth capacity, maximum number of hops),and it is used to send data from a source node  s k  to anotherdestinationnode  d  k . The processof selectingthewinningsetof VPN connections for resource allocations deploy an op-timal selection algorithm presented in Table 1. In which, ateach auction period  t  , the ISP broker firstly collects the newconnection demands received in the period of ( t   −  1,  t  ] andform a new demandmatrix,thenfrom eachdemandmatrixitchooses the most profitable set of connections to accept. Todo so, using the Linear Programming Theory we developedan Integer Linear Program (ILP) to formulate the bandwidthallocation problem. By solving this ILP, we are showinghow it can choose the optimal set of bidding VPN operators,and provide the optimal bandwidth utilization rates. The ILPchecks the offered bids of the competing VPN operators if itis larger than or equal certain selling-price thresholds, wheresuch thresholds depend on the ISP broker profit objectives,the corresponding QoS classes, and demand blocking con-straints. Demand blocking is mainly related to the numberof offered bids, and the bandwidth availability over the as-signed candidate paths.To overcome the problem of exaggeration, we proposeperforming a dynamic partitions of resources over differentQoS classes through short periods of time comparing withthat of the static scenarios. This can reduce the motivationsof exaggeration actions, where bidding VPN operators willnot be motivated anymore to ask for more resources, as theydo not have to care about their future connections or the sud-den changes in the network state, at least at this stage, sincecurrent allocations are only valid for a short period of time,comparatively.  A.N. Quttoum et al. 3.1.2 Mathematical modeling We model the DP approach as an ILP model. Through thismodel, we study the case where we assume having a num-ber of VPN operators  N   competing for bandwidth alloca-tions over a network that is managed through an ISP broker.Bandwidth allocation requests are modeled through connec-tion demands, where each VPN operator  i ,  i  ∈  N  , has aset of connection demands  k  belonging to a set of serviceclasses  J  . Logically, VPN operators are assumed to be ratio-nal, and thus their aim is to have their connection demandsadmitted with the lowest possible prices, and at the sametime acquire satisfactory QoS levels. On the other side, theISP broker aims to utilize its network bandwidth resourcesbetter, and maximize its profit by accepting the maximumnumber of VPN operators while providing them with sat-isfactory QoS levels by competing prices. Accordingly; theISP broker profit  P  B  function can be expressed as: P  B  =  max  | K |  k = 1 p k  −  k ∈ K c k   (1)where the  P  B  equals the sum of bids  p k  collected from con-nection demands being admitted for allocation, reduced bythe total cost of the bandwidth resources required to satisfyeach connection demand  c k . Accordingly, to maximize the P  B ( ILP ) , the ISP broker has to choose the best set of VPNoperators’ connections that maximizes the first term of thefunction, and also, deploy an efficient bandwidth utilizationscheme in order to minimize the second term.Choosing the best set of VPN operators’ connections istypically done in accordance to their offered bids, wherehigher bids increases the chance for their correspondingdemands to be accepted. To create a form of competitionbetween the bidding VPN operators, we assume that theamount of bandwidth resources required to satisfy the re-ceived connection demands exceeds the available networkcapacity. Connection demands are also classified into set of different QoS classes summarized in Table 2, where for eachauction period  t  , the model receives a different set of con-nection demands’ patterns reflecting the diversity of the re-quired services at the different auction periods. Periods canvary between day and night times, weekdays,and weekends.  Model parameters  The ISP network is basically defined asa set of nodes  V  , connected by a set of bidirectional links L , where each physical link offers certain bandwidth capac-ity  b l . The requests of the VPN operators  N   form the shapeof the demands matrix  K , where  K  represents all the con-nection demands submitted by the bidding VPN operators,each demand consists of a VPN operator ID  i , connectionsource node  s k , destination node  d  k , and a class of service j  ,  j   ∈  J  . Henceforth, a connection demand  k  of class  j  , Table 2  QoS classesQoSclassConnections Quality of Service Bandwidth perConnectionMax.of Hops5 Golden Load ( < 100ms Latency) 5 Mbps 2 Hops4 Excellent Load (Business Critical) 4 Mbps 3 Hops3 Controlled Load (Streaming Video) 3 Mbps 4 Hops2 Standard (IP Packet Delivery) 2 Mbps 5 Hops1 Best Effort 1 Mbps 6 Hops consumes a bandwidth amount of   b j  . Dividing the links’bandwidth capacities among the set of connection demands K  and their corresponding service classes  J   highly dependson the period’s traffic pattern.  α lj   denotes the percentage of bandwidth capacity allocated to a connection of class  j   overthe network link  l , where  α lj   ≤  b l .  Model variables  To facilitate the process of measuring theISP broker utility presented in Eq. (1), we refer to the admit-ted/rejected connections using the variable  z k , where: z k  =  1 if connection demand  k  is admitted0 otherwise (2)and we also refer to the selected path that holds the consid-ered connection using the variable  x πk  , where: x πk  =  1 if connection demand  k  uses path  π 0 otherwise (3) Objective function  According to the parameters and vari-ables defined above, the objective function of Eq. (1) can bereformulated as: P  B  =  k ∈ K  p k z k  −  π ∈ π k x πk  l ∈ π c lk   (4)  Model constraints  For this objective function presented inEq. (4), we have the following constraints:– Link Capacity: For each link  l , the available bandwidthfor the admitted connection demands  k  of class  j   cannotexceed the total link capacity reserved for this class.  k ∈ K j   π ∈ π k η πl  x πk  b j   ≤  α lj  b l ;  l  ∈ L, j   ∈ J   (5)where the variable  η πl  refers to: η πl  =  1 if path  π  uses link  l 0 otherwise (6)and  K j   refers to the set connections belonging to QoSclass  j  .  An optimal dynamic resources partitioning auction model for virtual private networks – Link bandwidth Division among QoS classes: The sum-mation of the defined class divisions over the networklinks must not exceed the total link capacity.  j  ∈ J  α lj   =  1 ;  α lj   ∈ [ 0 , 1 ] , l  ∈  L  (7)– Minimum Selling-Price Threshold: To be considered as acompeting connection demand for the allocation process,the minimum offered bid  p k  for a connection demand  k of QoS class  j   must at least be higher than or equal toa certain threshold. The calculation of this threshold isderived in Sect. 3.1.4. p k  ≥  π ∈ π k x πk  l ∈ π p lth,j  ;  k  ∈  K j  , j   ∈ J   (8)– Routing Path Assignment: Only one routing path can beassigned to carry each connection.  π ∈ π k x πk  ≤  1 ;  x πk  ∈ { 0 , 1 } , k  ∈ K  (9)– Linking decision variables: If there is no way to route theconnection while the connection is rejected. z k  ≤  π ∈ π k x πk  ;  z k  ∈ { 0 , 1 } , k  ∈  K  (10) •  Routing Path Length: The length of the assigned path  l π for a connection demand  k  of QoS class  j   cannot exceed H  j   hops, one hop represents one physical link. l π  ≤ H  j  ;  π  ∈ π k , j   ∈ J   (11)  ILP complexity  However, it is worth to find the compu-tational complexity of the model. This can be measuredthrough the number of model variables and constraints, asfollows:– Number of variables: | K |+| K |×| π K |+| L |×| J  | which can be simplified as: | K |×| π K |+| L |×| J  | – Number of constraints: | L |×| J  |+ 3 | K |+| K |×| π K | which can be simplified as: | L |×| J  |+| K |×| π K | From this, we can conclude that the number of variablesequals the number of constraints, which is in the orderof   O(n 2 ) . Moreover, to deal with the complexity issues,if exist, in such a problem we can use the technology of  Cloud Computing  that is considered as an efficient solu-tion to deal with high combinatorial problems. 3.1.3 Link bandwidth division scheme To assign the VPN operators’ connection demands to themost profitable paths, the ILP do the following:– In accordance to the offered bid rates and the networklinks capacities, it generates a class division map thatshows the percentages of bandwidth capacities reservedfor each QoS class over the network links.– Based on this map, the model assigns different candidatepaths [11] to carry each source-destination connection de-mand.– In one-shot scheme, the model chooses the most prof-itable combinations of the VPN operators’ demands to becarried over the network links, and consequently assignthem to their routing paths.To create a form of competition, the assigned candidatepaths might be shared between various connection demandshaving the same source-destination nodes, where the sum of bandwidthamountsoverthese candidatepathsis less than orequal to that required to satisfy the whole connections withthe same source-destination couples.The link bandwidth division among QoS classes schemeis mainly depend on the demands’ diversity, where suchdiversity reflects the different VPN operators requirementsfrom time to time. Differences may appear between theday times (i.e. mornings, afternoons, evenings, and nights),weekdays (i.e. workings days, and weekends), or even itmight be affected by the different time-zones.Consequently, for each period of time we assume havingthe following demand matrix partition:–  γ  1  % connection demands of   QoS   1.–  γ  2  % connection demands of   QoS   2.–  γ  3  % connection demands of   QoS   3.–  γ  4  % connection demands of   QoS   4.–  γ  5  % connection demands of   QoS   5. 3.1.4 Profit percentage parameter  For each VPN connection  k  belonging to QoS class  j  , wecalculate the set of candidate paths  π k . Then, if at least onepath  π ,  π  ∈  π k , uses the link  l , then we add the VPN con-nection  k  to the set of candidate VPN connections that usethe class of service  j   over link  l . We denote by  K l  the set of candidate VPN connections to use the link  l : K l  =  j  ∈ J  K j l  (12)
Recommended
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks