# A Flexible Auction Model for Virtual Private Networks

Kamil Koltyś, Krzysztof Pieńkosz, Eugeniusz Toczylowski

## ► To cite this version:

Kamil Koltyś, Krzysztof Pieńkosz, Eugeniusz Toczylowski. A Flexible Auction Model for Virtual Private Networks. 10th IFIP Networking Conference (NETWORKING), May 2011, Valencia, Spain. pp.97-108, 10.1007/978-3-642-20798-3_8. hal-01597966

HAL Id: hal-01597966

https://inria.hal.science/hal-01597966

Submitted on 29 Sep 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Flexible Auction Model for Virtual Private Networks

Kamil Kołtyś, Krzysztof Pieńkosz, and Eugeniusz Toczyłowski

Institute of Control and Computation Engineering, Warsaw University of Technology,
Nowowiejska 15/19, 00-665 Warsaw, Poland,
K.J.Koltys@elka.pw.edu.pl

**Abstract.** We consider the resource allocation problem related to Virtual Private Networks (VPNs). VPN provides connections between geographically dispersed endpoints over a shared network. To realize VPN service, sufficient amount of bandwidth of network resources must be reserved for any traffic demand specified by a customer. We assume that there are many customers that want to purchase VPN services, and many network providers that offer their network resources for sale. We present a multicommodity auction model that enables the efficient management of the network resources in the market environment. On the other hand it is very convenient for the customers as it allows them to specify the bandwidth requirements concerning VPN in a very flexible way, including pipe and hose VPN representations. The proposed model has also many other valuable properties, such as individual rationality and budget balance. The auction model has a form of LP for which the computational efficiency can be improved by applying the column generation technique.

**Keywords:** auction model, virtual private network, bandwidth trading

## 1 Introduction

Virtual Private Network (VPN) is a logical network that is established over a shared network in order to provide VPN users with service compared to dedicated private lines. A sufficient amount of bandwidth of a bundle of shared network resources must be reserved for VPN service to satisfy traffic demand pattern specified by customer. The basic way of representing the set of traffic demands values of VPN is in the form of the *pipe* model [1, 2]. It requires that VPN customer specifies, for each pair of endpoints, the maximum demand volume. This approach is applicable to VPNs for which the exact traffic demands matrix can be predicted. As the number of endpoints per VPN is constantly growing, the traffic demands patterns are becoming more and more complex. Therefore, for some VPNs, it is almost impossible to predict maximum value of each traffic demand. Duffield at all proposed in [1] the *hose* VPN model in which VPN customer specifies aggregate requirements for each VPN endpoint, and not for each pair of endpoints. In comparison to the *pipe* model, the *hose* model provides a simpler and more flexible way of VPN traffic demands specification.
The customer only defines ingress and egress bandwidths of VPN endpoints, which can be more easily predicted than traffic demands matrix. In the hose model it is assumed that all patterns of traffic demands that conforms the ingress and egress bandwidths of VPN endpoints can be realized. In [6] the concept of architecture for provisioning VPNs that come sequentially in the dynamic fashion is presented. Nonetheless, it does not take into account the costs of network resources. The problem of determining the minimum cost bandwidth reservation that satisfies all VPN traffic requirements in hose model is analyzed in [3, 4]. In [5] a more general model of VPN traffic demands is considered, called polyhedral model, that allows for specifying a set of required VPN traffic demands defined by some linear inequalities.

In this paper we consider the general network resource allocation problem in the context of the multilateral trade. In this problem the network resources are owned by several market entities, such as companies laying cables, network providers and other network link owners. The customers on the market are geographically spread organizations and other institutions that are interested in purchasing VPN services. We assume that sellers offer single links and buyers want to purchase VPN services between several nodes.

Currently, the dominating form of bandwidth trading are bilateral agreements in which two participants negotiate the contract terms. The negotiations are complex, nontransparent and time consuming. The customer that wants to purchase bandwidth between several nodes connected by a set of links owned by different providers must independently negotiate with all of them. If the negotiation fails with one of them (whereas agreements with other sellers would be drawn up and signed), the customer will get useless bandwidth as it will not ensure the connection between all selected nodes. Also even if the buyer manages to purchase bandwidth that ensures connectivity between all VPN endpoints, there is a risk that VPN service could be provided by a cheaper set of links. Thus there is a need of designing more sophisticated market mechanisms that will support customers in purchasing network resources of complex structure and enable efficient management of network resources distributed among several providers. Lately analysis of bandwidth market gives promise of emerging new forms of bandwidth trading in the future [7, 8].

Most of the auction mechanisms for bandwidth trading considered in the literature concern auctioning the bundles of links [9–11]. They support purchasing VPN in a very limited way because they require that the customer explicitly specifies the set of links realizing all VPN traffic demands instead of allowing the customer for convenient VPN traffic demands specification as in the above-mentioned pipe or hose model. In [12] the multicommodity auction model for balancing communication bandwidth trading (BCBT) is presented. Although it enables submitting buy offers for end to end demands, it does not guarantee that all end to end demands associated with the particular VPN are obtained by the customer. A generalization of BCBT model that supports purchasing VPN services represented in the pipe model is proposed in [2]. In this paper we introduce a more flexible VPN auction model AM-VPN that allows the customer to
specify the requirements for VPN traffic demands defined not only in the pipe but also in the hose and mixed pipe-hose representations.

## 2 Auction Model

The proposed AM-VPN model concerns a single-round sealed-bid double auction of network resources. The set $\mathcal{V}$ represents all nodes of the network. We denote the set of sell offers by $\mathcal{E}$ and the set of buy offers by $\mathcal{B}$.

The sell offer $e \in \mathcal{E}$ regards to single link and the parameter $a_{ve}$ defined for each network node $v \in \mathcal{V}$ states which node is a source of this link ($a_{ve} = 1$), which is a destination of this link ($a_{ve} = -1$) and which nodes are not associated with this link ($a_{ve} = 0$). Sell offer $e$ includes the minimum sell unit price $S_e$ and the maximum volume of bandwidth $x_e^{\max}$ offered for sale at particular link. We assume that bandwidth of links is a fully divisible commodity and every sell offer can be partially accepted. We denote the contracted bandwidth of link offered in sell offer $e$ by variable $x_e$.

The buy offer $m \in \mathcal{B}$ regards to VPN. It contains the maximum price $E_m$ that buyer is willing to pay for VPN and specification of the VPN traffic demands. We denote the set of VPN endpoints by $\mathcal{Q}_m(\mathcal{Q}_m \subseteq \mathcal{V})$ and the set of traffic demands between VPN endpoints by $\mathcal{D}_m$. Each demand $d \in \mathcal{D}_m$ represents a required connection between source endpoint $s_d \in \mathcal{Q}_m$ and destination endpoint $t_d \in \mathcal{Q}_m$, where $s_d \neq t_d$. For demand $d \in \mathcal{D}_m$ and each network node $v \in \mathcal{V}$ the parameter $c_{vd}$ is defined, such that $c_{sdd} = 1$, $c_{tdd} = -1$ and $c_{vd} = 0$ if $v \neq s_d$ and $v \neq t_d$. Any value of the traffic demand $d \in \mathcal{D}_m$ is a variable denoted by $x_d$. The set $\mathcal{X}_m$ contains all vectors of traffic demands values $(x_d)_{d \in \mathcal{D}_m}$ that must be provided by VPN service. We assume that buy offer can be partially accepted and denote the accepted fraction of buy offer $m$ by variable $x_m$.

We propose the mixed pipe-hose model which enables to define the set $\mathcal{X}_m$ in the general way that combines pipe and hose traffic demands models. In the mixed pipe-hose model the VPN customer is able to define two types of requirements. The first type of requirements allows for specifying the egress bandwidth $b_{mv}^+$ and ingress bandwidth $b_{mv}^-$ for given endpoints $v \in \mathcal{Q}_m^H$ ($\mathcal{Q}_m^H \subseteq \mathcal{Q}_m$). The second type of requirements allows for specifying the maximum volume $h_d$ of bandwidth for some demands $d \in \mathcal{D}_m^P$ ($\mathcal{D}_m^P \subseteq \mathcal{D}_m$). Thus, in the mixed pipe-hose model the set $\mathcal{X}_m$ is defined by parameters $b_{mv}^+$, $b_{mv}^-$ and $h_d$ as follows:

$$ \mathcal{X}_m = \left\{ (x_d)_{d \in \mathcal{D}_m} : \sum_{\substack{d \in \mathcal{D}_m: \\ v=k_d}} x_d \le b_{mv}^+, \sum_{\substack{d \in \mathcal{D}_m: \\ v=t_d}} x_d \le b_{mv}^- \quad \forall v \in \mathcal{Q}_m^H; \ x_d \le h_d \quad \forall d \in \mathcal{D}_m^P \right\} $$

The above mixed pipe-hose model is a generalization of the pipe and hose models. If we put $\mathcal{Q}_m^H = \emptyset$ and $\mathcal{D}_m^P = \mathcal{D}_m$, we obtain the VPN specification in the pipe model. If we put $\mathcal{Q}_m^H = \mathcal{Q}_m$ and $\mathcal{D}_m^P = \emptyset$, we obtain the VPN specification in the hose model.

Define two following sets: $\mathcal{X} = \mathcal{X}_{m_1} \times \dots \times \mathcal{X}_{m_{|\mathcal{B}|}}$ and $\mathcal{D} = \mathcal{D}_{m_1} \cup \dots \cup \mathcal{D}_{m_{|\mathcal{D}_m|}}$ and denote by $\mathcal{T}$ a set of all scenarios of VPNs demands values $(x_d)_{d \in \mathcal{D}} \in \mathcal{X}$.
Let parameter $x_d^\tau$ be a value of demand $d \in \mathcal{D}$ in scenario $\tau \in \mathcal{T}$. We assume that routing for each demand is static and can be carried on many paths. For each demand $d$, we denote by variable $f_{ed}$ the fraction of traffic demand value $x_d^\tau$ (regardless of scenario $\tau$) that is routed through link offered in sell offer $e$.

The AM-VPN model defines the allocation and pricing rules. The allocation rule determines contracted bandwidth of sell offers and realization of buy offers that provides the maximum social welfare $\hat{Q}$. It also settles a matching of accepted sell and buy offers by assigning links bandwidth of accepted sell offers to VPN services of accepted buy offers. The pricing rule defines the revenues of sellers and payments of buyers. The allocation rule is defined as linear programming (LP) problem. Such a formulation is very advantageous because standard optimization solvers can be used to determine optimal allocation and dual prices can be used to define the pricing rule. Below we present both rules in detail.

### 3 Allocation Rule

The allocation rule can be formulated as the following optimization problem:

$$ \hat{Q} = \max \left( \sum_{m \in \mathcal{B}} E_m x_m - \sum_{e \in \mathcal{E}} S_e x_e \right) \quad (1) $$

$$ \sum_{m \in \mathcal{B}} \sum_{d \in \mathcal{D}_m} f_{ed} x_d^\tau \leq x_e \quad \forall e \in \mathcal{E}, \forall \tau \in \mathcal{T} \quad (2) $$

$$ \sum_{e \in \mathcal{E}} a_{ve} f_{ed} = c_{vd} x_m \quad \forall v \in \mathcal{V}, \forall m \in \mathcal{B}, \forall d \in \mathcal{D}_m \quad (3) $$

$$ 0 \leq x_e \leq x_e^{\max} \quad \forall e \in \mathcal{E} \quad (4) $$

$$ 0 \leq x_m \leq 1 \quad \forall m \in \mathcal{B} \quad (5) $$

$$ 0 \leq f_{ed} \quad \forall e \in \mathcal{E}, \forall m \in \mathcal{B}, \forall d \in \mathcal{D}_m \quad (6) $$

The objective function is defined by equation (1) that express the social welfare being maximized. Thus, the allocation rule provides the highest economic profit that may be obtained by the sellers and buyers as a result of the trade. The constraints (2) ensure that for each scenario the bandwidth sold at link is sufficient to realize the appropriate fraction of demands values of all buy offers. Equation (3) is a flow conservation constraint that must be met for each demand of every buy offer. If $x_m = 0$, then buy offer $m$ is rejected. If $x_m = 1$, then buy offer $m$ is fully accepted. Otherwise, buy offer $m$ is partially accepted and a set $\mathcal{X}'_m$ defined by parameters $b_{mv}^{+'} = x_m b_{mv}^{+}$, $b_{mv}^{-'} = x_m b_{mv}^{-}$ and $h'_d = x_m h_d$ is provided. Note that in such a case the connectivity between all VPN endpoints is ensured, but only the values of traffic demands that can be realized by the VPN service are smaller proportionally to $x_m$.

The above LP problem is hard to solve directly, because the constraints (2) must be defined for immense number of scenarios $\tau \in \mathcal{T}$. Below we present two different allocation models, called AR1 and AR2, that are based on compact LP formulation and column generation method, respectively.
To formulate the AR1 model of the allocation problem let us assume that the routing of all VPN demands ($f_{ed}$) is fixed. For given buy offer $m$ we denote by $x_{me}$ the bandwidth of link involved with offer $e$ that is required to realize the worst case scenario of VPN traffic demands values. Taking vector ($x_d$)$_{d \in D_m}$ as decision variables and inequalities defining set $X_m$ as constraints, we can form following optimization problem that determines the minimum value of $x_{me}$:

$$ \bar{x}_{me} = \max \left( \sum_{d \in D_m} f_{ed} x_d \right) \qquad (7) $$

$$ \sum_{d \in D_m : v=s_d} x_d \le b_{mv}^{+}, \quad \forall v \in Q_m^{H} \qquad (8) $$

$$ \sum_{d \in D_m : v=t_d} x_d \le b_{mv}^{-}, \quad \forall v \in Q_m^{H} \qquad (9) $$

$$ x_d \le h_d, \quad \forall d \in D_m^P \qquad (10) $$

$$ 0 \le x_d, \quad \forall d \in D_m \qquad (11) $$

By $\pi_{me}^{v+}$, $\pi_{me}^{v-}$ and $\pi_e^d$ we denote the dual variables corresponding to constraints (8), (9), and (10), respectively. For each buy offer $m \in B$ and demand $d \in D_m$ we define a parameter $\sigma_d$, such that $\sigma_d = 1$ if $d \in D_m^P$ and $\sigma_d = 0$ if $d \notin D_m^P$. Then, the allocation rule AR1 can be formulated as the following LP problem:

$$ \hat{Q} = \max \left( \sum_{m \in B} E_m x_m - \sum_{e \in \mathcal{E}} S_e x_e \right) \qquad (12) $$

$$ x_{me} = \sum_{v \in Q_m^H} (\pi_{me}^{v+} b_{mv}^{+} + \pi_{me}^{v-} b_{mv}^{-}) + \sum_{d \in D_m^P} \pi_e^d h_d \quad \forall m \in B, \forall e \in \mathcal{E} \qquad (13) $$

$$ 0 \le f_{ed} \le \sum_{v \in Q_m^H : v=s_d} \pi_{me}^{v+} + \sum_{v \in Q_m^H : v=t_d} \pi_{me}^{v-} + \sigma_d \pi_e^d \quad \forall e \in \mathcal{E}, \forall m \in B, \forall d \in D_m \qquad (14) $$

$$ \sum_{m \in B} x_{me} \le x_e \quad \forall e \in \mathcal{E} \qquad (15) $$

$$ \sum_{e \in \mathcal{E}} a_{ve} f_{ed} = c_{vd} x_m \quad \forall v \in V, \forall m \in B, \forall d \in D_m \qquad (16) $$

$$ 0 \le x_e \le x_e^{\max} \quad \forall e \in \mathcal{E} \qquad (17) $$

$$ 0 \le x_m \le 1 \quad \forall m \in B \qquad (18) $$

$$ 0 \le \pi_{me}^{v+}, \pi_{me}^{v-} \quad \forall e \in \mathcal{E}, \forall m \in B, \forall v \in Q_m^H \qquad (19) $$

$$ 0 \le \pi_e^d \quad \forall e \in \mathcal{E}, \forall m \in B, \forall d \in D_m^P \qquad (20) $$

where (13) and (14) represent objective function and constraints of the dual problem to (7)-(11). The optimization problem AR1 is a LP problem that can be solved directly using standard optimization solvers. A similar approach for solving a problem of provisioning VPN in the hose model was proposed in [3].

An alternative formulation AR2 of the allocation rule is also the LP problem, but it applies column generation technique to achieve optimal allocation. For
each buy offer $m \in \mathcal{B}$ we define a set $\mathcal{F}_m$ that contains scenarios of network resource allocation realizing VPN service specified in buy offer $m$. For given buy offer $m \in \mathcal{B}$, scenario $\beta \in \mathcal{F}_m$ and sell offer $e \in \mathcal{E}$ the parameter $\alpha_{me}^{\beta}$ states how much bandwidth of particular link associated with sell offer $e$ is required by scenario $\beta$. Let variable $x_m^{\beta}$ denotes the realization of buy offer $m$ in the scenario $\beta \in \mathcal{F}_m$. The master problem of the column generation algorithm used in AR2 problem determines the optimal allocation for given set of scenarios $\mathcal{F}_m$ defined for each buy offer $m \in \mathcal{B}$. It has a form of the following LP problem AR2-MP:

$$ \hat{Q} = \max \left( \sum_{m \in \mathcal{B}} E_m x_m - \sum_{e \in \mathcal{E}} S_e x_e \right) \qquad (21) $$

$$ x_{me} = \sum_{\beta \in \mathcal{F}_m} \alpha_{me}^{\beta} x_m^{\beta} \quad \forall m \in \mathcal{B}, \forall e \in \mathcal{E} \qquad (22) $$

$$ \sum_{m \in \mathcal{B}} x_{me} \leq x_e \quad \forall e \in \mathcal{E} \qquad (23) $$

$$ x_m = \sum_{\beta \in \mathcal{F}_m} x_m^{\beta} \quad \forall m \in \mathcal{B} \qquad (24) $$

$$ x_e \leq x_e^{\max} \quad \forall e \in \mathcal{E} \qquad (25) $$

$$ x_m \leq 1 \quad \forall m \in \mathcal{B} \qquad (26) $$

$$ 0 \leq x_e \quad \forall e \in \mathcal{E} \qquad (27) $$

$$ 0 \leq x_m \quad \forall m \in \mathcal{B} \qquad (28) $$

$$ 0 \leq x_m^{\beta} \quad \forall m \in \mathcal{B}, \forall \beta \in \mathcal{F}_m \qquad (29) $$

For each buy offer $m$ and prices $\xi_e$ obtained from the master problem AR2-MP we define the optimization subproblem AR2-SP$_m(\xi_e)$ that determines the allocation $\alpha_{me}$ realizing VPN service of buy offer $m$ with the lowest cost $\hat{\Psi}_m$:

$$ \hat{\Psi}_m = \min \left( \sum_{e \in \mathcal{E}} \xi_e \alpha_{me} \right) \qquad (30) $$

$$ \sum_{v \in \mathcal{Q}_m^H} (\pi_{me}^{v+} b_{mv}^{+} + \pi_{me}^{v-} b_{mv}^{-}) + \sum_{d \in \mathcal{D}_m^P} \pi_e^d h_d \leq \alpha_{me} \quad \forall e \in \mathcal{E} \qquad (31) $$

$$ 0 \le f_{ed} \le \sum_{v \in \mathcal{Q}_m^H : v=s_d} \pi_{me}^{v+} + \sum_{v \in \mathcal{Q}_m^H : v=t_d} \pi_{me}^{v-} + \sigma_d \pi_e^d \quad \forall e \in \mathcal{E}, \forall d \in \mathcal{D}_m \qquad (32) $$

$$ \sum_{e \in \mathcal{E}} a_{ve} f_{ed} = c_{vd} \quad \forall v \in \mathcal{V}, \forall d \in \mathcal{D}_m \qquad (33) $$

$$ 0 \le \alpha_{me} \quad \forall m \in \mathcal{B}, \forall e \in \mathcal{E} \qquad (34) $$

$$ 0 \le \pi_{me}^{v+}, \pi_{me}^{v-} \quad \forall e \in \mathcal{E}, \forall v \in \mathcal{Q}_m^H \qquad (35) $$

$$ 0 \le \pi_e^d \quad \forall e \in \mathcal{E}, \forall d \in \mathcal{D}_m^P \qquad (36) $$

The allocation rule of the AM-VPN model can be now formulated as the optimization problem AR2, that can be solved by the following algorithm based on the column generation technique:
1. For each $m \in \mathcal{B}$ initialize the set $\mathcal{F}_m$ (e.g. for each $m \in \mathcal{B}$ solve AR2-SP$_m(S_e)$).

2. Solve AR2-MP. For obtained optimal solution let $\hat{\lambda}_e$ and $\hat{\omega}_m$ denote the values of dual prices associated with constraints (23) and (24), respectively.

3. For each $m \in \mathcal{B}$ solve AR2-SP$_m(\hat{\lambda}_e)$ determining $\hat{\Psi}_m$ i $\hat{\alpha}_{me}$.

4. If for each $m \in \mathcal{B}$ inequality $\hat{\Psi}_m \ge \hat{\omega}_m$ is met, then allocation determined in step 2 is optimal (STOP). Otherwise for each $m \in \mathcal{B}$ that fulfills inequality $\hat{\Psi}_m < \hat{\omega}_m$, create new scenario $\beta$, such that $\alpha_{me}^{\beta} = \hat{\alpha}_{me}$, and add it to set $\mathcal{F}_m$. Go to step 2.

It can be proved that optimization problems AR1 and AR2 define equivalent allocation rules of the AM-VPN model. In general the result of the allocation rule is denoted as vector $\hat{x}=(\hat{x}_e, \hat{x}_m, \hat{x}_{me})$.

# 4 Pricing Rule

The pricing rule of the AM-VPN model is strictly connected with the formulation of AM-VPN allocation rule as it leverages the fact that allocation rule is defined by LP problems AR1 or AR2. For allocation $\hat{x}$ determined by solving problem AR1 or AR2 we define by $\hat{\lambda}_e$ the values of corresponding dual prices associated with constraint (15) in the case of AR1, or constraint (23) in the case of AR2. The pricing rule of the AM-VPN model sets the unit clearing price of link associated with offer $e$ equal to $\hat{\lambda}_e$. Then the revenue $p_e$ of the seller that submits sell offer $e$ equals:

$$p_e = \hat{\lambda}_e \hat{x}_e, \qquad (37)$$

and the payment $p_m$ of the buyer that submits buy offer $m$ equals:

$$p_m = \sum_{e \in \mathcal{E}} \hat{\lambda}_e \hat{x}_{me}. \qquad (38)$$

# 5 Model Properties

In this section we present some general properties of the proposed auction model AM-VPN. Denote the economic profit of seller whose sell offer $e$ realization is $x_e$ and revenue equals $p_e$ as follows:

$$U_e(x_e, p_e) = p_e - S_e x_e, \qquad (39)$$

Analogously, define the economic profit of the buyer whose buy offer $m$ realization is $x_m$ and payment equals $p_m$ as follows:

$$U_m(x_m, p_m) = E_m x_m - p_m. \qquad (40)$$

**Proposition 1.** The AM-VPN model has individual rationality property, i.e. for given allocation $\hat{x}$, revenues $p_e$ and payments $p_m$ determined by the AM-VPN model each seller obtains non-negative economic profit $U_e(\hat{x}_e, p_e) \ge 0$, and each buyer obtains non-negative economic profit, $U_m(\hat{x}_m, p_m) \ge 0$.
*Proof.* This proof assumes that the allocation $\hat{x}$ is given by AR2, but analogously proof can be done in the case of AR1. Let $\hat{\gamma}_{me}$, $\hat{\lambda}_e$, $\hat{\omega}_m$, $\hat{\mu}_e$, $\hat{\mu}_m$ be the values of dual variables corresponding to optimal solution of AR2 related to constraints (22)-(26), respectively. From duality theory it follows that above values satisfy the following complementary slackness conditions:

$$ \hat{x}_e(S_e + \hat{\mu}_e - \hat{\lambda}_e) = 0 \quad \forall_{e \in \mathcal{E}} \qquad (41) $$

$$ \hat{x}_m(-E_m + \hat{\mu}_m + \hat{\omega}_m) = 0 \quad \forall_{m \in \mathcal{B}} \qquad (42) $$

$$ \hat{x}_m^{\beta} \left( \sum_{e \in \mathcal{E}} \hat{\gamma}_{me} \alpha_{me}^{\beta} - \hat{\omega}_m \right) = 0 \quad \forall_{m \in \mathcal{B}}, \forall_{\beta \in \mathcal{F}_m} \qquad (43) $$

$$ \hat{x}_{me}(\hat{\lambda}_e - \hat{\gamma}_{me}) = 0 \quad \forall_{m \in \mathcal{B}}, \forall_{e \in \mathcal{E}} \qquad (44) $$

The economic profit of seller that submits sell offer $e$ is non-negative because:

$$ U_e(\hat{x}_e, p_e) = p_e - S_e \hat{x}_e = (\hat{\lambda}_e - S_e) \hat{x}_e = \hat{\mu}_e \hat{x}_e \geq 0 \qquad (45) $$

The equations in (45) results from (39), (37) and (41), respectively and the last inequality holds, because $\hat{\mu}_e \geq 0$ as it is a dual variable related to inequality constraint (25). The economic profit of the buyer that submits buy offer $m$ is non-negative because:

$$ U_m(\hat{x}_m, p_m) = E_m \hat{x}_m - p_m = E_m \hat{x}_m - \sum_{e \in \mathcal{E}} \hat{\lambda}_e \hat{x}_{me} = \qquad (46) $$

$$ = E_m \hat{x}_m - \sum_{e \in \mathcal{E}} \hat{\gamma}_{me} \hat{x}_{me} = E_m \hat{x}_m - \sum_{e \in \mathcal{E}} \hat{\gamma}_{me} \sum_{\beta \in \mathcal{F}_m} \alpha_{me}^{\beta} \hat{x}_m^{\beta} = \qquad (47) $$

$$ = E_m \hat{x}_m - \sum_{\beta \in \mathcal{F}_m} \hat{\omega}_m \hat{x}_m^{\beta} = (E_m - \hat{\omega}_m) \hat{x}_m = \hat{\mu}_m \hat{x}_m \geq 0 \qquad (48) $$

The equations in (46) results from (40) and (38), respectively. The equations in (47) follows from (44) and (22), respectively. The equations in (48) results from (43), (24) and (42), respectively, and the last inequality holds, because $\hat{\mu}_m \geq 0$ as it is a dual variable related to inequality constraint (26). □

**Proposition 2.** The AM-VPN model has budget balance property, i.e. for given allocation $\hat{x}$, revenues $p_e$ and payments $p_m$ determined by the AM-VPN model the following condition is met:

$$ \sum_{m \in \mathcal{B}} p_m = \sum_{e \in \mathcal{E}} p_e. \qquad (49) $$

*Proof.* This proof assumes that the allocation $\hat{x}$ is given by AR2, but analogously proof can be done in the case of AR1. Let $\hat{\lambda}_e$ be the value of dual variable corresponding to optimal solution of AR2 related to constraint (23). From duality theory it results that following complementary slackness condition is satisfied:

$$ \hat{\lambda}_e \left( \sum_{m \in \mathcal{B}} \hat{x}_{me} - \hat{x}_e \right) = 0 \quad \forall_{e \in \mathcal{E}} \qquad (50) $$
Then the following equations are met:

$$ \sum_{m \in \mathcal{B}} p_m = \sum_{m \in \mathcal{B}} \sum_{e \in \mathcal{E}} \hat{\lambda}_e \hat{x}_{me} = \sum_{e \in \mathcal{E}} \hat{\lambda}_e \hat{x}_e = \sum_{e \in \mathcal{E}} p_e \quad (51) $$

The equations in (51) results from (38), (50) and (37) respectively. □

We have shown that the AM-VPN is individually rational and budget balanced. These properties are very valuable. The first one guarantees that trader will not lose by participating in the auction. The second one ensures that the operator organizing the auction does not have to pay extra money in order to proceed the auction and it does not obtain any unjustified economic profits.

# 6 Flexibility of the AM-VPN Auction Model

The AM-VPN model provides a flexible way for defining the customer's preferences related to VPN service using mixed pipe-hose representation. In this section we illustrate some benefits that customer obtains by having possibility of specifying a VPN service with mixed pipe-hose representation rather than with pipe or hose representation only.

The example concerns the network presented in Fig. 1a. The network consists of 11 nodes and 10 pairs of directed links denoted by solid lines. Each directed link is involved with one sell offer. Thus, there are 20 sell offers having the same unit price 10 and maximum volume 1500. We consider one customer that want to purchase VPN service concerning nine nodes: A, B, C, D, F, G, H, J and K. The VPN topology is depicted in Fig. 1a. The numbers at nodes denote the ingress and egress bandwidth of appropriated endpoints. The dotted lines connecting the selected pairs of VPN endpoints mean the demands that are required to be satisfied by VPN. All remaining demands between VPN endpoints have not to be provided. The customer is willing to pay 60000 for this VPN service.

Above resource allocation problem can be solved by means of the AM-VPN model with customer requirements related to VPN specified in mixed pipe-hose representation. Achieved allocation is depicted in Fig. 1b. The numbers at links

<figure><img src="image_2.png" /><figcaption>Fig. 1: The network resource allocation problem solved by the AM-VPN model.</figcaption></figure>
denote the bandwidth sold to the customer. Note that the buy offer is fully
accepted. The clearing prices of links determined by the model AM-VPN are
equal to 10. Thus, the customer has to pay 10\*4000=40000 for the VPN service.

Assume now that the customer is only able to use pipe or hose model instead
of flexible mixed pipe-hose representation.

In the case of hose model the customer can only specify the ingress and egress bandwidth of each VPN endpoint. If the customer submits a buy offer that concerns such a VPN service specification the optimal allocation provided by the *AM-VPN* changes as follows: the bandwidth sold at links between nodes *E* and *G* grows to 800 and the bandwidth sold at links between nodes *G* and *H* grows to 400. The clearing prices remain the same. Thus, in comparison with mixed pipe-hose case the customer has to purchase extra 400 units of bandwidth at links between nodes *E* and *G* and extra 200 units of bandwidth at links between nodes *G* and *H* resulting in higher customer's payment, i.e. $10\*(4000+2\*400+2\*200)=52000$.

In the case of pipe model the customer must define the maximum values
of all demands. The maximum values of non-zero demands (denoted by dotted
lines) are defined according to the typical pipe mesh approach, namely as the
minimum of the egress bandwidth of source endpoint and the ingress value of
destination endpoint. Naturally, the maximum values of all remaining demands
are set to 0. If customer submits a buy offer that concerns such a VPN service
specification, the allocation provided by the *AM-VPN* changes in comparison
with the mixed pipe-hose model case at links between nodes *E* and *G* on which
the bandwidth sold to the customer grows to 1000. The clearing prices remain
the same. Thus, in comparison with mixed pipe-hose case the customer has to
purchase extra 600 units of bandwidth at links between nodes *E* and *G* resulting
in the higher customer's payment, i.e. $10\*(4000+2\*600)=52000$.

Concluding this example, if the customer specifies his requirements for VPN
traffic demands in the mixed pipe-hose model, he pays 40000 for required VPN
service but if he is able to use merely the pipe or hose model, he has to pay much
more, i.e. 52000. It results from the fact that the VPN specified in the pipe or
hose model may require more network resources than the VPN specified in the
mixed pipe-hose model which restricts the required VPN traffic demands more
accurately than the pipe or hose model. Thus, as the above example illustrates,
the flexibility of the *AM-VPN* model enables the customer to specify precisely
the VPN service requirements in the mixed pipe-hose model which may improve
his economic profit.

7 Computational Efficiency

In this section *AR1* and *AR2* allocation problems are compared in the respect
of computational efficiency. We solve several resource allocation problems con-
cerning three networks from SNDlib library [13]: *polska* (12 nodes and 18 links),
*france* (25 nodes and 45 links) and *cost266* (37 nodes and 57 links). For each
network 12 problems were prepared differing in the number of buy offers and the
<table><caption>Table 1: The time of determining the optimal allocation by *AR1* and *AR2* [s]</caption><thead><tr><th rowspan="3">Network <i>polska</i></th><th colspan="8">Buy offers</th></tr><tr><th colspan="2">5</th><th colspan="2">10</th><th colspan="2">25</th><th colspan="2">50</th></tr><tr><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th></tr></thead><tbody><tr><th>VPN endpoints</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>0,02</td><td>3,02</td><td>0,05</td><td>2,38</td><td>0,39</td><td>5,02</td><td>1,89</td><td>13,07</td></tr><tr><th>6</th><td>0,52</td><td>9,72</td><td>1,19</td><td>8,55</td><td>9,63</td><td>12,37</td><td>58,49</td><td>30,09</td></tr><tr><th>9</th><td>4,81</td><td>14,83</td><td>25,18</td><td>28,74</td><td>78,72</td><td>58,24</td><td>682,74</td><td>143,54</td></tr></tbody></table><table><thead><tr><th rowspan="3">Network <i>france</i></th><th colspan="8">Buy offers</th></tr><tr><th colspan="2">5</th><th colspan="2">10</th><th colspan="2">25</th><th colspan="2">50</th></tr><tr><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th></tr></thead><tbody><tr><th>VPN endpoints</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>0,08</td><td>12,56</td><td>0,62</td><td>22,76</td><td>2,92</td><td>22,74</td><td>4,01</td><td>51,36</td></tr><tr><th>6</th><td>1,45</td><td>86,83</td><td>7,11</td><td>83,01</td><td>50,79</td><td>124,21</td><td>142,18</td><td>169,54</td></tr><tr><th>9</th><td>5,51</td><td>233,89</td><td>52,43</td><td>232,77</td><td>294,25</td><td>333</td><td>1653,20</td><td>283,62</td></tr></tbody></table><table><thead><tr><th rowspan="3">Network <i>cost266</i></th><th colspan="8">Buy offers</th></tr><tr><th colspan="2">5</th><th colspan="2">10</th><th colspan="2">25</th><th colspan="2">50</th></tr><tr><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th><th>AR1</th><th>AR2</th></tr></thead><tbody><tr><th>VPN endpoints</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>3</th><td>0,11</td><td>33,08</td><td>0,61</td><td>19,03</td><td>3,51</td><td>22,04</td><td>27,74</td><td>31,49</td></tr><tr><th>6</th><td>3,17</td><td>78,15</td><td>10,72</td><td>63,18</td><td>117,52</td><td>123,41</td><td>692,82</td><td>188,77</td></tr><tr><th>9</th><td>12,57</td><td>266,56</td><td>57,24</td><td>222,32</td><td>17130</td><td>418,44</td><td>26101</td><td>703,2</td></tr></tbody></table>

sizes of VPNs specified in the hose model. We consider problems with 5, 10, 25 and 50 buy offers, respectively and with VPNs that consist of 3, 6 and 9 nodes. In every allocation problem there is one sell offer submitted on each link.

Table 1 presents the time of determining the optimal solution by allocation rules *AR1* and *AR2*. The computations have been performed on computer with processor Intel Core2 Duo T8100 2,1GHz, main memory 3GB and 32-bit operating system MS Vista. For solving LP problems the CPLEX 12.1 has been used. For all problems concerning small VPNs (with 3 endpoints) or having small number of buy offers (5 or 10) *AR1* is faster than *AR2*. Nevertheless, as the size of the problem grows, the solution time of *AR1* increases much more than in the case of *AR2*. The benefits from applying *AR2* rather than *AR1* are especially apparent for the largest resource allocation problem defined for the *cost266* network for which *AR1* needs more than 7 hours to determine the allocation while *AR2* calculates the optimal solution in about 11 minutes. Thus for the real resource allocation problems which usually are of large sizes it is better to use the *AR2* rather than *AR1*.

## 8 Conclusions

We propose the *AM-VPN* auction model that supports the allocation of the network resources distributed among several providers to the customers of VPN services. The model matches many sell and buy offers aiming at maximization of social surplus. The *AM-VPN* model has individual rationality and budget balance properties. The main merit of the model is flexibility in specifying the
VPN traffic demands. It enables the VPN customer to employ the pipe, hose or mixed pipe-hose representations. The presented example demonstrates benefits gained by VPN customer when using the mixed pipe-hose traffic demands model. The proposed model determines optimal allocation and prices by solving an appropriate LP optimization model. The computational efficiency for large resource allocation problems can be improved by applying column generation technique.

## Acknowledgments

The authors acknowledge the Ministry of Science and Higher Education of Poland for partially supporting the research through Project N N514 044438.

## References

1. Duffield, N.G., Goyal, P., Greenberg, A., Mishra, P., Ramakrishnan, K.K., van der Merive, J.E.: A flexible model for resource management in virtual private networks. Proc. ACM SIGCOMM 29(4) (1999) 95–108

2. Kołtyś, K., Pieńkosz, K., Toczyłowski, E., Zółtowska, I.: A bandwidth auction model for purchasing VPN. Przeglad Telekomunikacyjny 8-9 (2009) 1183–1189 (in Polish)

3. Altin, A., Amaldi, E., Belotti, P., Pinar, M.c.: Provisioning virtual private networks under traffic uncertainty. Networks 49(1) (2007) 100–115

4. Erlebach, T., Rüegg, M.: Optimal bandwidth reservation in hose-model VPNs with multi-path routing. Proc. INFOCOM (2004) 2275-2282

5. Ben-Ameur, W., Kerivin, H.: Routing of uncertain traffic demands. Optimization and Engineering 6(3) (2005) 283–313

6. Chu, J., Lea, C.: New architecture and algorithms for fast construction of hose-model vpns. IEEE/ACM Transactions on Networking 16 (2008) 670–679

7. Iselt, A., Kirstadter, A., Chahine, R.: Bandwidth trading - a business case for ASON? Proc. 11th International Telecommunications Network Strategy and Planning Symposium NETWORKS (2004) 63–68

8. Rabbat, R., Hamada, T.: Revisiting bandwidth-on-demand enablers and challengers of a bandwidth market. Proc. 10th IEEE/IFIP Network Operations and Management Symposium NOMS (2006) 1–12

9. Dramitinos, M., Stamoulis, G.D., Courcoubetis, C.: An auction mechanism for allocating the bandwidth of networks to their users. Computer Networks 51(18) (2007) 4979–4996

10. Jain, R., Varaiya, P.: Efficient market mechanisms for network resource allocation. Proc. 44th IEEE Conference on Decision and Control, and the European Control Conference (2005) 1056–1061

11. Jain, R., Walrand, J.: An efficient mechanism for network bandwidth auction. Proc. IEEE/IFIP Network Operations and Management Symposium Workshops NOMS (2008) 227–234

12. Stańczuk, W., Lubacz, J., Toczyłowski, E.: Trading links and paths on a communication bandwidth markets. Journal of Universal Computer Science 14(5) (2008) 642–652

13. Survivable network design library website: http://sndlib.zib.de/