Edge Provisioning and Fairness in VPN-DiffServ Networks.
Customers of Virtual Private Networks (VPNs) over Differentiated Services (DiffServ) infrastructure are most likely to demand not only security but also guaranteed Quality-of-Service (QoS) in pursuance of their desire to have leased-line-like services. However, expectedly they will be unable or unwilling to predict the load between VPN endpoints. This paper proposes that customers specify their requirements as a range of quantitative services in the Service Level Agreements (SLAs). To support such services Internet Service Providers (ISPs) would need an automated provisioning system that can logically partition the capacity at the edges to various classes (or groups) of VPN connections and manage them efficiently to allow resource sharing among the groups in a dynamic and fair manner. While with edge provisioning a certain amount of resources based on SLAs (traffic contract at edge) are allocated to VPN connections, we also need to provision the interior nodes of a transit network to meet the assurances offered at the boundaries of the network. We, therefore, propose a two-layered model to provision such VPN-DiffServ networks where the top layer is responsible for edge provisioning, and drives the lower layer in charge of interior resource provisioning with the help of a Bandwidth Broker (BB). Various algorithms with examples and analyses are presented to provision and allocate resources dynamically at the edges for VPN connections. We have developed a prototype BB performing the required provisioning and connection admission.
INTRODUCTION
There is a growing demand that since private networks built on using
dedicated lines offer guaranteed bandwidth and latency, similar guarantees
be provided in IP based Virtual Private Networks (VPNs) [9], [14].
While the internet has not been designed to deliver performance guar-
antees, with the advent of differentiated services [3], [2], IP backbones
can now provide various levels of quality of service.Recently proposed
Expedited Forwarding (EF) [10] Per Hop Behaviour (PHB) is the recommended
method of build such an Virtual Leased Line Line (VLL)
type point-to-point connection for VPN.
To provide such service we have (and others, for example [16],[17])
recently implemented [12], [13] a Bandwidth Broker [15] that allows
an user to specify a single quantitative value (i.e 1 Mbps or 2 Mbps
etc.) and based on this specification the edge routers establish VPN
connections dynamically. However, it is expected that users will be unable
or unwilling to predict load between VPN endpoints [7]. From the
provider's point of view also, guaranteeing exact quantitative service
might be a difficult job at the beginning of VPN-Diffserv deployment
[2]. We, therefore, propose that users specify their requirements as a
range of quantitative service. For example, a user who wants to establish
a VPN between stub Networks A and B (Figure 1), and is not sure
whether he needs 0.5 Mbps or 0.6 Mbps or 1 Mbps, and only knows
the lower and upper bounds of his requirements approximately, can
specify a range 0.5- 1 Mbps as his requirement from the ISP when he
outsources his service to the latter. An ISP can offer multiple such options
via a website (Figure 6) to help customers to select any suitable
option to activate services dynamically on the fly.
This has several advantages: Users do not need to specify the exact
capacity but it gives the flexibility to specify only a range. The price
that customers have to pay is higher than one pays for the lower bound
capacity but lower than what is normally needed to be paid for upper
bound capacity. During low load it is possible that users might enjoy the
upper bound rate (say 1 Mbps in the example) without paying anything
extra. This kind of pricing might be attractive to users and ISPs can
take advantage of that to attract more customers without breaking the
commitment.
This, however, poses significant challenge to the ISPs as they would
need to deploy automated provisioning system that are able to logically
partition the capacity at the edges to various classes (or groups where
each group is identified from it's offer, for example 0.5- 1 Mbps could
represent one group, 1-2 Mbps could represent another) of VPNs and
manage them efficiently to allow resource sharing among the groups
in a dynamic and fair manner.Also, they must provision the interior
nodes in the network to meet the assurance offered at the boundaries
of the network We have, therefore, proposed a two-layered model in
section II to provision such VPN-Diffserv Networks where the top
layer is responsible for edge provisioning and drives the lower layer in
charge of interior resource provisioning with the help of a Bandwidth
Broker (BB).
We have restricted this paper to edge provisioning only considering
the fact that most of complexities lie at the boundaries of the network
and is the main driving force for overall provisioning. In section III
various algorithms with examples and analysis have been presented to
provision and allocate resources dynamically at the edges. Fairness issues
while allocating unused resources have been addressed in section
III-D. A prototype BB performing the required provisioning and connection
admission has been described in section IV. Section V concludes
the paper with a summary of our contributions and a discussion
of future research directions.
Edge
Router 3
Interior
Router 1
Interior
Interior
Edge
Router 1
Edge
Router 3
Edge
Router 5
Edge
Router 4
ISP
Stub
Network
Customer
Customer
Stub
Network
A 1A
Network Stub
Customer
Customer
Stub
Network C 1C
Fig. 1. VPN Diffserv deployment scenario
II. PROVISIONING REQUIREMENTS FOR VPN-DIFFSERV
NETWORKS: A MODEL
Provisioning in Diffserv Networks does not only mean determination
and allocation of resources necessary at various points in the network,
but also modification of existing resources to be shared dynamically
among various VPN classes (i.e. groups). Both quantitative, as it is
the case with VPNs, and qualitative traffic (some assured service) are
required to be provisioned at the network boundaries and in the network
interior.
Determination of resources required at each node for quantitative
traffic needs the estimation of volume of traffic that will traverse each
network node. While an ISP naturally knows from the SLA the amount
of VPN quantitative traffic that will enter the transit network through
a specific edge node, this volume cannot be estimated with exact accuracy
at various interior nodes that will be traversed by VPN connections
if we do not know the path of such connections [1]. However,
if the routing topology is known, this figure can be almost accurately
estimated. If the default path doesn't meet the requirements of an in-coming
connection, alternate and various QoS routing [6], [5] can also
be used to find a suitable path and enforced by MPLS techniques [8].
A. Role of Bandwidth Broker for Automated Provisioning
Based on the basic needs of provisioning a VPN-Diffserv network to
support quantitative service we consider the provisioning as a two layered
model - the top layer responsible for edge provisioning and driving
the bottom layer which is in charge of interior provisioning (Figure 2).
As we seek to provide a system where VPN services are available on
demand, we find that Bandwidth Broker [15],[17] is the right choice,
because it is not only capable of performing dynamic end-to-end admission
control to setup a leased line like VPN by maintaining the topology
as well as policies and states of all nodes in the network, but also capable
of managing and provisioning network resources of a separately
administered DS domain and cooperating with other similar domains.
Edge Provisioning
Interior Provisioning
Bandwidth Broker
CR CR CR
ER
CR
CR
CR
ER
Fig. 2. Layered Provisioning view of VPN-Diffserv Networks
B. A Novel Bandwidth Specified as an Interval
To overcome users' difficulty in specifying the exact amount of quantitative
bandwidth required while outsourcing the VPN service to ISP
our model supports a flexible way to express SLAs where users specify
a range of quantitative amounts rather than a single value. Although
it has several advantages, this also makes the edge and interior provisioning
difficult. This complexity can be explained with a simple ex-
ample. Referring to Figure 1 once again, assume that edge router 1 has
been provisioned to provide 20 Mbps quantitative resources to establish
VPN connections elsewhere in the network and ISP has provided
two options via a web interface to the VPN customers to select the rate
of the connections dynamically: 1 Mbps or 2 Mbps. It is easy to see
that at any time there can be 20 connections each having 1 Mbps, or 10
connections each enjoying 2 Mbps, or even a mixture of the two (e.g. 5
connections with connections with 1 Mbps). When a new
connection is accepted or an active connection terminates, maintaining
the network state is simple and doesn't cause either reductions or
forces re-negotiations to existing connections. If there are 20 connections
of 1 Mbps, and one connection leaves then there will be simply
19 connections of 1 Mbps. Admission process is equally simple.
Now if the ISP provides a new option ( for example, as shown in Figure
6(b)) by which users can select a range 1Mbps - 2 Mbps (where 1
and 2 are the minimum and maximum offered guaranteed bandwidth),
maintaining the state and admission control can be difficult. A detailed
example can be found in section III-B.When there are up to 10 users
each connection would get the maximum rate of 2 Mbps, but as new
connections start arriving, the rate of existing connections would de-
crease. For example, when there are 20 connections this rate would and then at that stage if an active connection terminates
the rate of every single connection would be expanded from 1 Mbps Mbps. This is a simple case when we have a single resource
group supporting a range 1Mbps-2 Mbps. In reality, we might have several
such groups as shown in Figure 6(b). In such cases, renegotiation
for possible expansion of existing connections, admission control and
maintenance of network states will not be simple. The idea presented
here is illustrated in figure 3.
BE traffic
EF traffic
C user_max(i)
C user_min(i)
user(i)
user(i)
VPN Pipe
VPN connection demand
(a) (b)
Fig. 3. The SLA (a) Bandwidth is specified as an interval of C user min(i)
and C user min(i) for any group i. Actual rate of a VPN connection C user(i) varies
between this range but never gets below C user min(i) . (b) C user(i) is the rate that
is configured in the edge router as the policing rate. Traffic submitted at a rate higher
than this rate is marked as best effort traffic or dropped depending on the policy
C. The Model and Notations
In our model, we address this novel approach to SLA and provide
policies and algorithms for automated resource provisioning and admission
control. However, to support such provisioning, we first start
by allocating a certain percentage of resources at each node (edge and
interior) to accommodate quantitative traffic. At the edge this quantitative
portion is further logically divided between dedicated VPN tunnels
(i.e. require 1Mbps or 2 Mbps explicitly) and those connections that
wish to have rates defined by a range (i.e 0.5-1 Mbps or 1-2 Mbps etc.
This top level bandwidth apportionment is shown in Figure 4. The
notations are :
ffl CT is the total capacity of a node interface.
ffl Cded is the capacity to be allocated to VPN connections requiring
absolute dedicated service
ffl Cshared is the capacity apportioned for those VPN connections who
describe their requirement as a range.
ffl C qual is the remaining capacity for qualitative traffic.
ffl Cquan is the capacity provisioned for quantitative traffic and is equal
to (Cded+ Cshared ).
C quan
C quan shared
ded
C qual
z.
shared
y.
a.
C qual
C qual
(b)
(a)
b.
Fig. 4. Top level Bandwidth Apportionment: (a) logical partitioning at the edge, (b) logical
partitioning at an interior
While at the edge Cquan is rate controlled by policing or shaping,
at the interior this Cquan indicates that this amount of capacity will
be allocated (actually protected) to quantitative traffic if need arises.
All the values can be different at different nodes. This kind of logical
partitioning is helpful because capacity is never wasted even if portions
of resources allocated to quantitative traffic are not used by VPN
connections. Unused capacity naturally goes to qualitative portion and
enhances the best effort and other qualitative service. This is true both
at the edge and in the interiors. Cshared , as shown in Figure 4, can
be logically divided to multiple groups where each group supports a
different range (Figure 5). As there might be multiple of such groups,
for any group i we define the following notations:
ffl C base(i) is the the base capacity for group i which is shared by the
VPN connections belonging to that group.
ffl C user min(i) is the ISP offered minimum guaranteed bandwidth that
a user can have for a VPN connection.
ffl C user max(i) is the ISP offered maximum guaranteed bandwidth that
a user can have for a VPN connection.
ffl N shared(i) is the current number of shared VPN connections in
ffl C shared(i) is the amount of capacity currently used by group i.
ffl C user(i) is the actual rate of active connections in group i and is
equal to C shared(i)
(in section 3).
Cshared unused is the total unused bandwidth from all shared service
groups.
shared-unused C base(i)
ded
shared
shared
qual
C00000000000000000001111111111111111111Unused
Fig. 5. Microscopic View of Bandwidth Apportionment at Edge
There are numerous sharing policies that we can apply to these
shared service groups. We call them shared service groups because
in reality the base capacity is shared by a certain number of VPN connections
and sharing policy might allow a group to share it's resources
not only among it's own connections, but also share with other groups'
VPN connections in case there is some unused capacity. This may also
apply to dedicated capacity. Priority can be given to certain groups
while allocating unused resources. Actually, fair sharing is a challenging
problem, and we will address all these issues in the following sections
while developing provisioning mechanisms.
III. EDGE PROVISIONING POLICIES: ANALYSIS AND
ALGORITHMS
Based on the model described in section II, various allocation policies
could be adopted by the ISPs at the ingress point to allocate capacity
dynamically to maintain and guarantee the quality of service of various
types of incoming and existing VPN connections as we will have
multiple classes of VPNs each supporting different bandwidth specifi-
cations. Some suitable policies are :
ffl Policy I: Capacity unused by one group cannot be used by any other
groups. This means that if we have multiple shared service groups, one
group whose resources have been exhausted while supporting numerous
connections doesn't borrow resources from others even when those
groups have unused capacity.Also, none of the groups are allowed to
use unused capacity of dedicated service group.
ffl Policy II: Capacity unused by one shared service group can be borrowed
by another shared service group. However, like the previous pol-
icy, they are not supposed to borrow from the dedicated service group.
ffl Policy III: Capacity unused by dedicated service group can be borrowed
by tunnels of shared service groups. Also, these groups can share
resources among themselves.
In this section, we will start with VPN Connection Acceptance algorithms
at Ingress point where all admission complexities lie. This
complexities are introduced because of the need to partition and share
resources to support our model and policies presented above. Further
analysis with examples of algorithms for Policy I,II and III clarify those
in detail.
A. VPN Call Acceptance at Ingress
The job of admission control is to determine whether a VPN connection
request is accepted or rejected. If the request is accepted,
the required resources must be guaranteed. For any group i a new
VPN establishment request is admitted only if at least the minimum
bandwidth as stated in the offer can be satisfied while also retaining
at least the minimum requirements for the existing users, i.e. if
C user min(i)
a new VPN connection request can be
accepted. This ensures that, an admitted VPN connection will always
receive at least the minimum offered bandwidth C user min(i) in group
by restricting the number of maximum connections that can join the
group. How much capacity the accepted connection will actually have
is decided by connection state in that group and sharing policies that
we are going to discuss in the next subsections.
B. Capacity Allocation with no sharing among groups: Policy I
The base capacity allocated to a group is solely used by the VPN
connections belonging to that group only. Under no circumstance resources
assigned to one group can be borrowed by others, even if that
capacity is unused. This makes allocation simple not only at the edges,
but also in the interior and from an implementation point of view it
is simple. Since the unused capacity is not used by any other groups,
qualitative services, as we mentioned earlier, are also enhanced.
If a VPN connection is accepted the system checks if that connection
can be allocated the maximum rate. This is possible if
the base capacity C base(i) is enough to assign all the existing connections
the maximum rate C user max(i) . Otherwise, the base capacity
is shared among all the existing and new VPN connec-
tion. Therefore, we can express this admission policy as follows:
Example 1: For the following example assume that the total link
bandwidth Mbps and there
is only one ( shared user group .Also assume that ISP offers
this group as C user
Base capacity C base(1) allocated to this group is 20 Mbps.
Mbps
Calls are accepted as long as the condition
C user min(i)
of section III-A is met. When the number of calls exceed
C user min(i)
a new arriving call is rejected. For example, if the
21st call in the example were accepted then C user(1) would have been21 , and the minimum bandwidth could no longer be guaranteed. There-
fore, the call is rejected.
C. Capacity Allocation with sharing among groups: Policy II
If the capacity allocated to a group is not fully used by VPN con-
nections, then this capacity can be borrowed by connections of other
shared service groups if needed. However, borrowed capacity must
be relinquished when needed by the group from which capacity was
borrowed. Although this borrowing and deallocation adds some complexity
in edge provisioning, connections from various groups, how-
ever, have better chances of enjoying higher rates. In the following we
present algorithms regarding VPN connection arrival, termination and
possible expansion of existing connections as a result of the termination
of a connection from a shared service group.
C.1 VPN Connection Arrival
Like the previous case, VPN connection arrival essentially involves
checking the availability of resources that can be used by the new con-
nection, and if available, allocating this capacity to an incoming call.
Even if the base capacity of a certain group allows the new connection
belonging to that group to assign maximum ISP offered rate (i.e.
- C user max(i) ), because of the resource
sharing among various groups it might happen that resources from that
group has been borrowed by other group(s) not leaving the required resources
(i.e. Cshared unused ! C user max(i) ). In such a case resource
must be relinquished from the appropriate groups(s). Any such de-allocation
from existing connections leads to rearrangement of capacity
of those connections. It should be noted that capacity should be relinquished
the way it was borrowed. There are numerous ways unused capacity
can be borrowed by competing groups which we will see in sections
III-C.3 and III-D. For the sake of simplicity, the group which has
the maximum excess bandwidth, C
should release first, and then the next, and so on.
/* if the group has enough base capacity to support
a new connection with max. offered rate. */
if
hi
/* if the shared unused capacity is also enough to support
the new connection with max. offered rate. See Example 2 */
if
Cshared unused - C user max(i)
/* if the shared unused capacity has been borrowed then
capacity is relinquished from borrower(s). See Example 3 */
else n
relinquish C user max(i) from group(s) which has max excess bw
rearrange bandwidth of that group(s)
We have just mentioned that capacity can be borrowed from one
group by the others. When does one group borrows resources? Natu-
rally, when the base capacity is less than what is needed i.e
How much can one group borrow? This depends on
how much unused resources are available. If this is at least equal to
the maximum offered rate C user max(i) , then that amount is allocated,
otherwise (i.e. Cshared unused ! C user max(i) ) the whole unused resource
goes to the group in question and is then divided among all the
connections in that group
/* if the shared capacity is equal to or has exceeded the base capacity */
if
hi
/* but the unused capacity can still support the new connection
with rate. Capacity is then borrowed. See Example 4 */
if
Cshared unused - C user max(i)
/*if the unused capacity is less than the max. rate. Capacity is then
shared by existing and the new connection. See Example 5 */
else n
Cshared unused
We will now consider several numerical examples in this section to
clarify the algorithms and analysis presented above. For all the following
examples we assume that the total link bandwidth
Mbps and there are only two shared
users groups i.e. 2. For group 1 C user
C user
C user
Prior to VPN connection request in group 1:
Here, for group 1, C
and C user
C user max(1) . Also, Cshared unused
which is greater than C user max(1) . Hence, C
Prior to VPN connection request in group 1:
In this example, C
is greater than C user Mbps. This means that group 1
hasn't used all it's base bandwidth and a new connection can have the
maximum offered bandwidth 1 Mbps. However, Cshared unused at the
time of request arrival is Cshared \Gamma
Mbps. This indicates that another group has has borrowed
capacity from group 1. If that group had left at least C user
Mbps then the request could have been assigned the desired amount of
resource. Therefore, the only option left is to relinquish 1 Mbps from
the group that has borrowed it. Searching the table we find that the only
other group 2 has taken that bandwidth. Therefore, we need to deduct
1 Mbps from group 2 and recompute the individual share of a VPN
connection as C
C shared(2) \GammaC user max(1)
Mbps. Obviously, C
Mbps.
Prior to VPN connection request in group 2:
This is a case where one group has used it's full allocated base capacity
but can borrow resources from the other group which has left some
spare capacity. Here, C
the total spared capacity Cshared unused
and this value is greater than C user max(2) (i.e 2 Mbps). Therefore,
the new VPN connection request can be allocated the maximum offered
value (i.e. 2 Mbps) by even exceeding the base capacity of group
2.
Example 5 :Prior to VPN connection request in group 2:
The example here depicts a scenario where one group which has
already exceeded it's base capacity and has to accommodate a new
connection request when there is no unused resource left by other
group(s).Here, even before the new call arrival, Group 2 has borrowed
Mbps. So, the current capacity allocated to group
will have to be equally distributed among all the existing and the
new arriving VPN connection. Therefore, C
Mbps.
C.2 VPN Connection Termination
When a VPN connection terminates, resources might have to be released
from the relevant group depending on the current rate every connection
is enjoying in that group. If the rate is less than or equal to
the maximum offered rate then no capacity is released from the groups
current share and as a result all the connections in that group increases
equally. This is because the same capacity is shared by a lower number
of connections. If, however, the current rate of every connection
is already equal to the maximum offered rate, then this termination
would trigger a deduction of C user max(i) from the shared resource
C shared(i) . If all the connections were already enjoying C user max(i) ,
no rate change occurs in any of the existing connections.The algorithm
is stated as follows:
if
/*See Example 6 */
Cshared unused = Cshared unused
if
Cshared unused = Cshared unused
To clarify the VPN connection termination process will now consider
similar examples as presented in the previous section.
Example connection termination from group 1:
Here, C shared(1)
user
1. This means that
the capacity used by this group before the connection termination will
remain unchanged even after the termination. So, the new value of
C shared(1) is also 10 Mbps and each VPN connection will equally
share this capacity which is C shared(1)
capacity is deducted from this group, the total unused shared capacity
will also remain unchanged.
Example 7: Before VPN connection departure from group 1:
In this example, C shared(1)
user
states the fact that prior to this departure all active VPN connections
were using the maximum possible offered bandwidth C user
1 Mbps and in total were having
Hence, the departure should trigger a deduction of C user
Mbps from the total capacity used by this group prior to the departure
as the capacity even after the deduction will be good enough to satisfy
active connections offering highest possible
rate of 1 Mbps. Therefore, C Mbps and and
each VPN connection will receive C shared(1)
the termination process triggers deduction of C user max(1) from the
capacity used by group 1, the unused shared capacity will increase by
the same value. So, Cshared unused
C.3 VPN Capacity Expansion
Unused shared capacity left by some groups can be distributed
among others. Priority can be given to certain groups while allocating
unused capacity. In the next section we will present various policies to
allocate unused dedicated capacity and those might apply here as well.
Here we consider only one case where preference is given to the needy
groups where need is determined from the ratio C user(i)
C user max(i)
. So, we
order the groups according to this ratio where in reordered groups the
first one has the lowest C user(i)
C user max(i)
and the last one has the highest
C user(i)
C user max(i)
. Once reordering has been done the expansion algorithm
starts allocating unused bandwidth to the first group, then the next, and
so on based on the availability of resources. This can be stated as :
if
shared unused
shared
Cshared unused \Gamma [N shared(i) :C user
if
shared unused
+Cshared unused
Cshared unused
Example 8: Before VPN connection termination from group 2:
After the termination of a VPN connection from group 2,
Cshared unused Mbps. If there is need of resources by other
group(s), this capacity can be used partly or fully. We find that group
1 has need for this resource since C user(1)
user max(1)
1. Now it remains
to be seen to what extent we could use this unused capac-
ity. Here, C shared(1) +C shared unused
11 and is greater
than C user max(1) which is 1 Mbps. Therefore, capacity for group
1 can be expanded to N shared(1) :C user
Mbps allocating each existing connection C user
The remaining unused capacity will be reduced to Cshared unused \Gamma
[N shared(1) :C user
Mbps.
Example 9: Before VPN connection departure from group 2:
Unlike the previous example where group 1 only needed to use a
portion of the unused resources, all the remaining capacity can be allocated
to existing group 1 VPN connections in order to enhance the
service. C shared(1) will be increased to 10+ 2=12 Mbps and each existing
connection will receive C shared(1)
12Mbps.
D. Fair Allocation of Unused Dedicated Resources: Policy III
In the previous section we have discussed methods where one shared
service group can borrow resources from another similar group. In this
section, we will discuss the possibilities of sharing the unused dedicated
resources among various shared service groups. If the shared
service groups are allowed to borrow resources from unused dedicated
resources, we then define a new term:
shared Cded unused
The question here is how we can allocate the unused dedicated resources
fairly among the competing groups. If all VPN tunnels want
the maximum bandwidth as offered in ISP policy offer, then it is possible
that at some point:
shared
If
shared
, the quantity that is
needed to allocated the maximum possible offered rates to all connections
even after allowing the unused dedicated resources to be used by
shared service groups, is greater than 0, we need to define a fair set of
user throughput values (i.e. C user(i) ) given the set of maximum offered
loads C user max(i) and C
shared . In other words, we need to divide
this extra capacity Cded unused among all the needy groups in a fair
manner. However, fair sharing of extra resources is not a trivial issue
and was addressed by others for different network situations [20], [11],
[18], [19] . Some proposals [11] are in favour of sharing the bottleneck
capacity equally among users independent of their requirements , and
others [20], [18] advocate to penalize users causing overloads.
While we do share the resources among VPN connections in each
group, equal sharing of unused dedicated capacity will not help much
to some groups where connections are already enjoying rates close to
C user max(i) . At the same time it also doesn't alleviate the problem
of other groups having rates above C user min(i) but much less than
C user max(i) . The fairness criterion of [20] also doesn't fit here as
that would deprive the heavy user groups to gain share from unused
dedicated resources even when they are enjoying rates much below
C user max(i) . Our case is further complicated by the fact that while
penalizing heavy user groups we cannot reduce their current share, and
this is what might happen in certain cases while trying to maximize the
rates of lower user groups. In the following sections we will discuss
various fair sharing methods at the edges.
D.1 Allocation of unused resources to lower user groups first
In this case, we first need to order the user groups based on their
C user max(i) values. The objective is to satisfy the lower user groups
first by trying to allocate maximum offered values while higher user
groups have less chances to acquire resources left by dedicated service
group. The rationale behind this is that more VPN users can be satisfied
and allocating to higher user groups might bring little changes in many
cases if sufficient extra resource is not available.
If the ordering leads to service groups
it is possible that if we expand K groups the VPN tunnels
belonging to those group will enjoy the maximum offered band-
th group receives rest of unused dedicated resource,
and other tunnels remain unchanged. The total enhanced shared capacity
can then be computed as follows:
shared
N shared(i) :C user max(i)
Cded unused
[N shared(i) :C user
The above computation helps us to view how C
shared is shared
by different groups. However, this general case is true when K -
2. The other cases are:
shared
C shared(1) +Cded unused if
Cded unused
In practice, when there is unused dedicated capacity the process
starts by asking the first group if the unused capacity is enough to satisfy
all the VPN connections. If so, each connection receives a maximum
value C user max(i) and then queries the second group. Other-
wise, the whole amount of capacity is allocated to the first group and
divided among the competing connections. The process continues as
long as unused capacity is a positive figure.
Assume a situation where we have 3 groups where
VPN connections in each of them were having capacity below their
respective C user max(i) . Also, Cshared = Mbps, and for group
1: C
0:25 Mbps, for group 2: C
Mbps, C user Mbps, and for group 3: C
Mbps, C user Mbps. Prior to the
availability of Cded unused = 7 Mbps we had :
Here the groups are already ordered. Applying the algorithms we
see that the first two groups can be allocated the maximum rates.
Therefore, they are both expanded to 15 \Theta
and 12 \Theta respectively. Rest of the unused capacity
Cded unused \Gamma
Mbps goes to the third group.
D.2 Allocation of unused resources to highest needy groups first
This is much like the process as described above with the only difference
that groups are ordered based on their needs. Apportionment
mechanisms and algorithms remain the same. Here, need is determined
from the ratio of C user(i)
C user max(i)
. So, groups with lower ratios get preference
over groups with higher ratios. Therefore, the process starts feeding
the most needy group and continues as long as it has some unused
capacity.
of previous section:
C user max(3)
C user max(1)
0:67, and C user(2)
C user max(2)
0:83.
Clearly, group 3 is the most needy group. If we have Cded unused
Mbps then that can serve the the most needy group 3 and enhance it's
service. The new C
C user
0:67. In the previous examples, this group never had the chance to grab
portion of the unused bandwidth, but the new policy here allows it to
improve the service substantially.
D.3 Allocation of unused resources based on proportional needs
Although the above mechanism seems to be fair since it allocates
based on the group's need, but in many cases there will be several
needy groups with little differences in their needs, and in such
cases the apportionment might not be always fair if unused dedicated
resources are exhausted while trying to feed first few groups
and other remain deprived to get a share. In this section, we there-
fore, present a way to allocate unused resources based on proportional
need. Any group that is in need of resource, i.e, having ratio
C user(i)
C user max(i)
receives a portion of unused resource that is proportional
to the group's need. Therefore, any group i, after receiving
the extra resource based on this proportional need, is expanded to
ded unused :C shared excess(i)
shared excess
need
for group i C shared excess(i) , is actually excess quantity that is needed
to offer all connections in that group the maximum value C user max(i) .
Therefore, C shared
Example 12: Once again, let us consider example to illustrate
the use of proportional need. No ordering is needed here as allocation
of extra capacity is solely based on proportional need. Here for
group 1: C user(1)
C user max(1)
0:67, for group 2: C user(2)
C user max(2)
and for group 3: C user(3)
C user max(3)
0:5.Application of this allocation
policy will expand the capacity of group 1 to: C
7[(0:5)15\Gamma5]
connections are improved with new C
C user max(1)
0:79. Similarly, for group 2: C
Mbps, C
C user max(2)
0:89 and for group 3:
C user
0:68. This clearly shows that proportional sharing fairly enhances the
rate of most needy group 3. This wouldn't have been the case had we
applied other fairness methods.
IV. IMPLEMENTATION OF BANDWIDTH BROKER FOR DYNAMIC
CONFIGURATION
As the underlying network may provide different classes of service
to satisfy various VPN customers, by identifying the generic functionality
provided by any resource and policy options, we present the BB
with a standard WEB interface as shown in Figure 6(b). The Band-width
Broker manages the outsourced VPNs for corporate customers
that have Service Level Agreements (SLAs) with their ISPs and allows
one such user to specify demand through a WWW interface to establish
a VPN with certain QoS between two endpoints.
A. The Essential Components of Bandwidth Broker
The BB needs to keep track of existing connections and available
resources and update relevant databases to reflect the most recent net-work
state. The BB interacts with specialized configuration daemons
(CD) when a certain user request arrives to setup a tunnel and the BB
has to decide whether it can allocate enough resources to meet the demand
of that tunnel. While the BB invokes a SLA database to check
the validity of the user request, it essentially needs to maintain a connection
database that contains a list of currently active VPNs and an
edge resource database to keep track of records of quantitative resource
available (base capacity) and current resource consumption of various
router interfaces.
Fig. 6. BB WEB interface for Users
B. Examples of Dynamic Configuration
SWITCH Network
Public Internet
130.92.66.22
Univ. of Geneve
Univ. of Berne
Univ. of Berne
Fig. 7. Experimental Setup of VPN
A resource controller in the Bandwidth Broker checks resource and
connection databases whenever there is any new connection arrival or
departure that might trigger modification of rates of existing connec-
tions. For better understanding of how edge routers are dynamically
configured to meet the user demand and conform SLA we will now
demonstrate some examples of dynamic rate allocations of VPN connections
in commercial Cisco routers. By considering similar examples
as detailed in section III we will see how the simple algorithms are really
applied to the edge devices. Let us consider an experimental setup

Figure

of Difserv-VPNs where we have three VPN and QoS capable
edge routers each having private network behind them.
Configuration 1: User 'A' wants to establish a VPN connection
for source 172.17.0.100 and destination 172.20.0.100 and chooses a
menu (1-2 Mbps) from ISP provided website and submits his request.
The resource group definition and edge resource database entries are
as shown in Figure 8. Applying algorithm presented in section 3, the
policing rate C user(1) that is configured in edge router 130.92.70.101
is C Mbps. If user 'B' chooses the same
menu he also gets C since capacity in group 1 has
the ability to support that. Assume that two more users 'C' and 'D'
decide to have VPN connection with capacity varying between 0.5 and
Mbps. Group 2 can support both the connections with the maximum
available rate of 1 Mbps. Therefore, C
Mbps is also configured in the router for these connections as we see in
the following:
/*policing individual VPN connection at the inbound with C
for users 'A' and 'B' and C users 'C' and 'D'*/
rate-limit input access-group 140 2000000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 141 2000000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 142 1000000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 143 1000000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
/*Classifying the requested VPN traffic/
access-list 140 permit ip host 172.17.0.100 host 172.20.0.100
access-list 141 permit ip host 172.17.0.101 host 172.20.0.100
access-list 142 permit ip host 172.17.0.102 host 172.20.0.100
access-list 143 permit ip host 172.17.0.103 host 172.20.0.100
Here, we show only the ingress router policing and marking since
diffserv is unidirectional. We assume that bit precedence 1 is used for
EF traffic marking and traffic that exceed the specified rate are marked
as best effort (bit precedence 2). Users not familiar with Cisco routers,
should only notice the first of the traffic rate parameters (for example
2000000 in '2000000 2000000 8000000') in rate-limit
policing and marking commands. This is the rate that we refer to as
C user(i) for any group i. The other two are burst parameters.
Controller
Resource
A 172.17.0.100 140 172.20.0.100
resource definition
connection database
edge resource database
Network Elements (Edge Routers)
Request from WEB interface
Edge Router Group Base
Capacity Used
Capacity
Resource Group user-min user-max
User
ID
Source
Address ID Time
ID
Source Tun. Dest
Address Dest Tun. Resource Group Usage
Current Activation
Fig. 8. Partial entries of Connection and Resource Databases.A scenario when all connections
receive the maximum offered value
Configuration 2: Now if users 'A' and 'B' also want to establish
connections from the same sources to 172.18.0.100 and 172.18.0.101
respectively and choose a menu (0.5 - 1 Mbps) i.e. group 2, we see
that capacity is exhausted in group 2, and therefore, these two new
connections and other two existing connections share the base capacity
of 2 Mbps and each connection is configured with C
C user Mbps. This is shown in Figure 9 and the
new configuration script that is used at this point is as follows:
rate-limit input access-group 140 2000000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 141 2000000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 142 500000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 143 500000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 144 500000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
rate-limit input access-group 145 500000 2000000 8000000
conform-action set-prec-transmit 1 exceed-action set-prec-transmit 2
access-list 144 permit ip host 172.17.0.100 host 172.18.0.100
access-list 145 permit ip host 172.17.0.101 host 172.18.0.101
V.


AND CONCLUSION
In this paper, we have proposed a novel range based SLA that allows
customers to specify their requirements as a range of quantitative service
for VPN connections since they are unable or unwilling to predict
load between the VPN endpoints. To support such services we have
proposed and developed a prototype Bandwidth Broker (BB) that can
logically partition the capacity at the edges to various service classes (or
groups) of VPNs and manage them efficiently to allow resource shar-
Controller
Resource
A 172.17.0.100 140 172.20.0.100
resource definition
connection database
edge resource database
Network Elements (Edge Routers)
Request from WEB interface
Edge Router Group Base
Capacity Used
Capacity
Resource Group user-min user-max
User
ID Source
Address ID Time
ID
Source Tun. Dest
Address Dest Tun. Resource Group Usage
Current Activation
A 172.17.0.100 144 172.20.0.100 151 2 0.5 Mbps 17:20
Fig. 9. A scenario when rate of existing connections are reduced to accommodate new
connections
ing among the groups in a dynamic and fair manner. Various algorithms
with examples and analysis have been presented to provision resource
dynamically at the edges to support QoS for VPN connections.
One obvious advantage of our system is the pricing gain. The price
that customers have to pay is higher than one pays for the lower bound
capacity but lower than what is normally needed to be paid for upper
bound capacity. During low load it is possible that users might enjoy
the upper bound rate without paying anything extra. Such pricing might
be attractive to users and ISPs can take advantage of that to attract more
customers. With all these advantages we believe that our model can be
quite attractive to the ISPs willing to deploy it in a real world scenario.
VI.

ACKNOWLEDGEMENT

The work described in this paper is part of the work done in
the project Charging and Accounting Technologies for the Internet
(CATI) [4] funded by the Swiss National Science Foundation
(Project no. 5003-054559/1 and 5003-054560/1), the SNF R' Equip
project no. 2160-053299.98/1 and the foundation F-orderung der wissenschaftlichen
Forschung an der Universit?t Bern



--R

Routing Guidelines for Efficient Routing Methods.
A Framework for Differentiated Services.
An Architecture for Differentiated Services

An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions
A framework for qos-based routing in the internet
A Flexible Model for Resource Management in Virtual Private Networks.
MPLS Support of Differentiated Services.
A Framework for IP Based Virtual Private Networks.
An Expedited Forwarding phb
Bottleneck Flow Control.
Implementation of a Bandwidth Broker for Dynamic End-to-End Resource Reservation in Outsourced Virtual Private Networks
Implementation of a Service Broker for Management of QoS enabled VPNs.
Core MPLS IP VPN Architecture.


Benjamin Teitelbaum and
Fairness in Window Flow Controlled Computer Networks.
A study of fairness in packet switching networks.
Fairness in ATM networks.
--TR

--CTR
Raffaele Bolla , Roberto Bruschi , Franco Davoli, Capacity planning in IP virtual private networks under mixed traffic, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.8, p.1069-1085, 6 June 2006
Haci A. Mantar , Ibrahim T. Okumus , Junseok Hwang , Steve J. Chapin, A scalable intra-domain resource management architecture for DiffServ networks, Journal of High Speed Networks, v.15 n.2, p.185-205, January 2006
fairness;resource provisioning;Bandwidth Broker BB;connection admission;dynamic configuration;Service Level Agreement SLA;Virtual Private Network VPN;Quality-of-Service QoS;Differentiated Services DiffServ