Telecommun SystDOI 10.1007/s1123501397105
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 optimizing the Internet Service Provider (ISP) proﬁt by providinga periodic Dynamic Partitioning (DP) model for utilizingnetwork resources in the context of Virtual Private Networks (VPN). In literature, Complete Sharing (CS), Complete Partitioning (CP), and Bandwidth Borrowing (BR)techniques have been proposed for resource allocationwhere the following limitations can be noticed: VPN operators 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 different QoS classes through periodic auctions that can reducethe reasoning of exaggeration and maximize the ISP proﬁt.Thus, we formulate our problem based on the Integer Linear Programming (ILP) that allows us to maximize the ISPproﬁt and provides the optimal: (1) set of proﬁtable 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, Jordanemail: Quttoum@hu.edu.joA. Jarray
·
Z. DziongElectrical Engineering Dep., ETS, Université du Québec,Montréal, QC, CanadaA. Jarrayemail: Abdallah.Jarray.1@ens.etsmtl.caZ. Dziongemail: Zbigniew.Dziong@etsmtl.caH. OtrokDepartment of Computer Eng., Khalifa University of Science,Technology & Research, Abu Dhabi, UAEemail: Hadi.Otrok@kustar.ac.ae
demand. Furthermore, the proposed ILP model allows us tostudy the sensitivity of the ISP proﬁt 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 according 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 satisfaction conditions necessitate the ISPs to efﬁciently utilize theirbandwidth resources. Models to provide an efﬁcient and effectiveresourceallocationschemesareextremelyimportant.Relying on the current management models that attempt direct interactions with the ISPs is not satisfying anymore, asthey have many limitations that can be summarized as follows: (1) These models increase the management operationexpenses. (2) They provide slow response times. Such limitationscanleadtohighratesofusers’dissatisfaction.Consequently, the need is emerging to ﬁnd 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 allocation,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 ISPproﬁt.– In CP approach, resources can be underutilized which reduces ISPs proﬁts.– Due to the longterm SLA agreement, VPN operatorsmight exaggerate about their required resources to guarantee their QoS and to cope with any unpredicted variations in the network state. Such a behavior can affectthe ISP proﬁt, and maximize the VPN demands blocking 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 collecting the same proﬁts.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 trafﬁc, 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 viceversa), in such a case how the BR would work?To overcome the above limitations, we propose deployinga
periodicdynamicresourcepartitioningmodel
(DP)forallocating the network bandwidth resources to VPN operators. 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 network planning time is divided into a set of periods in order to reduce the reasoning of exaggeration and to eliminatethe needs for any borrowing technique. The length of thereoptimization period depends on the provided service duration. Demands with different service durations can be divided into groups, each with certain period length. At eachnew period, the proﬁtable VPN connections are selectedthrough an auction mechanism in order to maximize the ISPproﬁt. Therefore, we develop and implement an
Integer Linear Program
(ILP) solved using the ILOG CPLEX concerttechnology environment. The Proposed ILP maximizes theISP proﬁt and comesup with:– The optimal set of the proﬁtable VPN connections.– The optimal bandwidth division of each network linkamong different QoS classes.– The optimal routing scheme of the accepted VPN connections, with respect to their QoS speciﬁcations.Furthermore, the proposed ILP allows us to study thesensitivity of the ISP proﬁt to a targeted revenue objective represented by the Proﬁt Percentage Parameter (PPP).Through PPP, we are able to ﬁnd the optimal tradeoff setting that maximizes the ISP proﬁt while not breaking thedemands blocking constraint. Consequently, our contribution is a model that is able to:– Efﬁciently utilize the network bandwidth resources,where through the dynamic partitioning we are able toconsider the changes of trafﬁc demands.– Increase the VPN operators’ satisfaction rates, since resources are utilized efﬁciently and the allocation pricesare market competing.– Minimize the SLAs violations as exaggeration motivations 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 selection 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 autonomic management framework, where the whole networkresources are shared between all VPN operators, so eachof them can use any bandwidth available at any given moment. 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 ensure the delivery of services according to predeﬁned SLAs.These SLAs are constructed after negotiations between theISP and the VPN operators. From the ISP prospective, giving the VPN operators such a privilege can provide better 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 operators behave according to their declarations, deploying suchan approach can increase bandwidth utilization due to thestatistical multiplexing, which results in better satisfactionrates and higher proﬁts at the same time. However, in reality, 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 proﬁt 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 onetime 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 unpredictable 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 longterm 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 exaggeration behavior [19, 20].
To overcome the problem of resource underutilization,the
Bandwidth Borrowing
(BR) [6] technique has been proposed. The BR attempts the idea of borrowing the resourcesfrom the underloaded links and allocating them to the overloaded ones. Accordingly, the BR scheme can provide betterutilization of the network bandwidth resources, and betterSLAs guarantees. However, resources are utilized in a nonoptimal way that can reduce ISP proﬁt. Also, such behavior can entail a high management load to cope up with thechanges of trafﬁc 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 overcomes their limitations by virtually partitioning the networkbandwidth resources in an efﬁcient way based on
periodicauctions
, where resources are allocated to the best biddersproviding proﬁt maximization. In this context, we proposea resource management approach based on shortterm SLAsthat takes into account the desired ISP objectives over thetime.Toachievethis,VPNoperatorsareaskedtorevealtheirconnection demands in terms of: sourcedestination nodes,required QoS classes, and their offered prices (bids). Accordingly, 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 ﬁnd the optimal set of VPN connections;5:
Output:
the VPN connections that won the resource allocationsand the proﬁt collected from these connections;
3.1 DP approach
3.1.1 Algorithm
In our DP approach, resources are allocated based on
dynamic 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 representedintermsof
connectiondemands
.Thetermconnectionhere is deﬁned as a secure network tunnel that is layered ontop of a public network, such tunnel has some QoS parameters (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 optimal selection algorithm presented in Table 1. In which, ateach auction period
t
, the ISP broker ﬁrstly collects the newconnection demands received in the period of (
t
−
1,
t
] andform a new demandmatrix,thenfrom eachdemandmatrixitchooses the most proﬁtable 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 sellingprice thresholds, wheresuch thresholds depend on the ISP broker proﬁt objectives,the corresponding QoS classes, and demand blocking constraints. Demand blocking is mainly related to the numberof offered bids, and the bandwidth availability over the assigned 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 sudden 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 number of VPN operators
N
competing for bandwidth allocations over a network that is managed through an ISP broker.Bandwidth allocation requests are modeled through connection 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 rational, 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 proﬁt by accepting the maximumnumber of VPN operators while providing them with satisfactory QoS levels by competing prices. Accordingly; theISP broker proﬁt
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 connection 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 ﬁrst term of thefunction, and also, deploy an efﬁcient 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 received connection demands exceeds the available networkcapacity. Connection demands are also classiﬁed into set of different QoS classes summarized in Table 2, where for eachauction period
t
, the model receives a different set of connection demands’ patterns reﬂecting the diversity of the required services at the different auction periods. Periods canvary between day and night times, weekdays,and weekends.
Model parameters
The ISP network is basically deﬁned asa set of nodes
V
, connected by a set of bidirectional links
L
, where each physical link offers certain bandwidth capacity
b
l
. The requests of the VPN operators
N
form the shapeof the demands matrix
K
, where
K
represents all the connection 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 trafﬁc 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 admitted/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 considered 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 variables deﬁned 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 summation of the deﬁned class divisions over the networklinks must not exceed the total link capacity.
j
∈
J
α
lj
=
1
;
α
lj
∈ [
0
,
1
]
, l
∈
L
(7)– Minimum SellingPrice 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 ﬁnd the computational 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 simpliﬁed as:

K
×
π
K
+
L
×
J

– Number of constraints:

L
×
J
+
3

K
+
K
×
π
K

which can be simpliﬁed 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 efﬁcient solution to deal with high combinatorial problems.
3.1.3 Link bandwidth division scheme
To assign the VPN operators’ connection demands to themost proﬁtable 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 sourcedestination connection demand.– In oneshot scheme, the model chooses the most profitable 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 sourcedestination nodes, where the sum of bandwidthamountsoverthese candidatepathsis less than orequal to that required to satisfy the whole connections withthe same sourcedestination couples.The link bandwidth division among QoS classes schemeis mainly depend on the demands’ diversity, where suchdiversity reﬂects 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 timezones.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 Proﬁt 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 connection
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)