Ann. Telecommun. DOI 10.1007/s12243-016-0512-0

Exact approach for the optimal design of virtual private network trees assuming a hose workload Ali Lourimi1 · Boulbaba Thabti1 · Habib Youssef1

Received: 8 June 2015 / Accepted: 22 March 2016 © Institut Mines-T´el´ecom and Springer-Verlag France 2016

Abstract Virtual private network (VPN) design according to a tree topology has been the subject of numerous research papers. Two workload models are commonly used to allow VPN clients to specify the communication capacity they need, the hose and the pipe workload models. As opposed to the pipe model, where bandwidth needs between every pair of endpoints must be specified as a matrix, the hose model has the advantage of simple specification where only one ingress and egress bandwidths per hose endpoint are specified. However, the tree bandwidth costs obtained with the hose workload model are higher by a factor of as much as 2.5 compared to those obtained with pipe workloads Duffield et al. (SIGCOMM Comput Commun Rev 29(4):95108, 1999). In this work, we propose a two-step exact approach to design a VPN tree with minimum bandwidth cost. The first step derives a pipe workload from the user specified hose workload using an exact algorithm. The second step formulates the pipe-based VPN tree bandwidth minimization as a 0–1 integer linear program, which is solved using the exact approach proposed in Thabti et al. (1–6, 2012). The bandwidth costs of VPN trees obtained using this two-step approach are lower by a factor varying

 Ali Lourimi

ourimi [email protected] Boulbaba Thabti [email protected] Habib Youssef [email protected] 1

PRINCE Research Unit, ISITCom Hammam Sousse, University of Sousse, Sousse, Tunisia

between 1.31 and 2.23 compared to VPN trees obtained using the original hose workload. Furthermore, we show that tree solutions obtained using the derived pipe workload satisfy the original hose workload. Keywords Virtual private network · Hose model · Branch-and-cut · Maximum flow problem · Cutting plane · Separation problem

1 Introduction Virtualization has become over the last several years an important disruptive technology. It enables the rapid on-demand deployment of virtual resources over available physical resources. This is allowing better network/server consolidation and improving network/data center management. Virtual private network (VPN) technology has been in use over the last 20 years. It presents numerous advantages such as the extremely low cost as opposed to the use of leased lines, as well as the flexibility of setting them up or tearing them off. Companies found in these networks the ideal solution to communicate safely with their customers or their partners wherever they may be in the world. Virtualization is now a proven technology which is revolutionizing the information technology (IT) landscape and changing the way enterprises will be obtaining their computing needs. This agile technology is enabling the rapid and flexible setup of virtual computing environments and virtual networking infrastructures over an existing physical infrastructure. Such virtual infrastructures are setup and teared down in response to customers business needs. This has also enabled the development of another important technology: cloud computing.

Ann. Telecommun.

With virtualization and cloud computing, enterprises have now economic alternatives of requesting computing as well as infrastructure services on per-use basis. Thus, the role of the traditional internet service provider (ISP) is no longer the same as in traditional networks. In fact, there are two types of providers: infrastructure providers whose role is to manage the physical infrastructure of the network and service providers who manage virtual networks and offer cloud computing services according to various cloud models [4–7]. Network virtualization allows service providers to dynamically provision multiple heterogeneous virtual networks with the necessary bandwidth, over an existing shared physical network. The challenge is obviously the efficient sharing of resources and management of virtual networks [3, 8, 9]. VPN design has been the subject of numerous studies over the last 20 years [1, 12, 15, 16, 18]. The VPN bandwidth provisioning concerns the allocation of sufficient bandwidth on the VPN links so that all the traffic can be exchanged between the VPN endpoints. From a customer point of view, the hose model has the advantage of simplicity of specification. Indeed, only one ingress and egress bandwidth per hose endpoint needs to be specified, compared to bandwidth for each pipe between pairs of hose endpoints (see Section 2). In return, we find that the pipe model has a remarkable advantage. Indeed in [16], authors showed that bandwidth costs of trees obtained with hose workload model are higher by a factor of as much as 2.5 to 3 compared to those obtained with pipe workloads. The main contribution of this paper consists of giving a two-step exact approach to design a VPN tree with minimum bandwidth cost. Firstly, we derive a pipe workload from the user specified hose workload using an exact algorithm. Secondly, we formulate the pipe-based VPN tree bandwidth minimization as a 0–1 integer linear program, which is exactly solved using the algorithm proposed in [2]. Our experimental results show that the bandwidth costs of VPN trees obtained using this two-step approach are lower by a factor varying between 1.31 and 2.23 compared to VPN trees obtained using the original hose workload. Furthermore, we show that tree solutions obtained using the derived pipe workload satisfy the original hose workload. The remainder of this paper is organized as follows. In Section 2, we give some basic concepts. In Section 3, we briefly discuss the motivation of this work and review related literature. Section 4 gives the notations used in this paper. Section 5 describes the formulation of the VPN tree design problem in the case of the hose workload model and the exact algorithm chosen to solve this problem. We give also the formulation of the VPN tree design problem in the case of the pipe workload model and the exact

algorithm chosen to solve it. We present our exact algorithm to derive a pipe workload model from a hose workload model in Section 6. Experimental results are given in Section 7. Finally, Section 8 concludes the paper.

2 Basic concepts Network virtualization allows to securely connect distant clients over a public network. The logical connections constitute a virtual overlay network. Such a network is said virtual because it connects local networks by secured tunnels over a physical public infrastructure such as the Internet. Two approaches are commonly used to allow VPN clients to specify their workload. The first, known as the pipe workload model [10], where the expected inbound and the outbound traffic between every pair of clients is specified in the form of a matrix. For the example network given in Fig. 1 with 10 nodes and 4 VPN endpoints (A, B, C, and D), a pipe workload specification could be as follows: ⎛

− ⎜5 PipeTraff = ⎜ ⎝3 2

5 − 1 2

4 1 − 4

⎞ 1 4⎟ ⎟ 2⎠ −

where PipeTraff(i,j) (i, j = A, B, C, D, i = j ), specifies the traffic in Mbps from VPN endpoint i to VPN endpoint j. The hose workload model has been introduced by Duffield et al. [16] as a much simpler and realistic model for specifying the bandwidth requirements of a network endpoints. According to this model, each VPN specification consists of the following. –

The set of endpoints P .

Fig. 1 An example of a network with four VPN endpoints: nodes A, B, C, and D. An example of VPN Tree is indicated by thick links, where traffic between VPN terminals is forced to flow across secured end-to-end tunnels established along the tree

Ann. Telecommun.

–

The hose ingress and egress bandwidths Biin and Biout , for each endpoint i ∈ P , usually expressed in Mega bits per second (Mbps).

For the example network of Fig. 1, a possible hose workload specification could be:  B in = 10, 8, 9, 7 and  B out = 10, 10, 6, 8 Biin and Biout represent the expected traffic flows that the endpoint i receives and sends, respectively (i = A, B, C, D). In contrast to the pipe model, where the workload is specified in the form of a matrix giving the expected traffic between any two VPN endpoints, the hose model only requires the specification of two vectors, giving the expected overall incoming and outgoing traffic of each VPN endpoint. The hose model has several advantages such as the ease of specification, scalability, multiplexing gain and simple characterization [18]. In this work, we consider VPNs with a tree topology, where the VPN endpoints are connected by a Steiner tree and all VPN traffic is sent along the unique paths of this tree. An example of a VPN tree is shown with thick lines in Fig. 1. In this case of tree routing, the traffic from A to C is routed along the unique path from A to C in the tree.

3 Related work VPN provisioning that assumes a hose model has long been studied in the literature. Fingerhut et al. [13] present a network design methodology based on just the same resource provisioning concept as the hose model. The paper also gives a short literature survey on the issue. Duffield et al. in [16] were the first to address the problem of provisioning IP Virtual Private Networks. In their paper, an analysis on the bandwidth efficiency of the hose model is presented. The evaluation is based on trace driven simulations of traffic derived from a voice network and from a large corporate network. However, their networklevel analysis is limited to a single topology (a simplified 12-node approximation of AT &T  s continental backbone) and they provide numerical results for network-wide capacity demand for different hose realizations. But there is no comparison with the pipe model. Another problem is that comparison of the bandwidth efficiency of the traditional pipe and the new hose model is limited to the access links, although the bandwidth over-provisioning induced by the hose model will be present within the backbone network. The paper from Duffield et al. [16] inspired research work on developing

algorithms for designing minimum cost networks based on hose specifications. Kumar et al. in [18] argued that optimal cost solutions for hose realizations shall be based on tree topology, and they proved that the general problem with asymmetric hoses (different amount of traffic sent and received by the hose) and constrained link capacities is NP-hard. Consequently, they provided a couple of approximation algorithms with provable performance bounds. Numerical results presented in the paper concern only the hose case and there is no comparison provided with the pipe model. The latest important contribution in this field improves the tree-based hose realization by proposing restoration algorithms. Diarrassouba et al. [1] consider the integer programming formulation of the VPN tree design problem based on the hose workload model, the formulation introduced by Kumar et al. [18] contains an exponential number of constraints. Diarrassouba et al. [1] showed that the linear relaxation of this problem can be solved in polynomial time. They developed a Branch-and-Cut algorithm (that is, a linear programming-based Branch-and-Cut algorithm reinforced by the addition of violated inequalities) for the problem and showed that the algorithm they proposed is efficient and permits to solve large instances with up to 120 nodes and 10 terminals. J¨uttner et al. [10] gave an analysis and comparison of the resource requirements of VPNs based on the pipe and hose models, assuming different network sizes, network topologies, traffic demands, and different realization alternatives. Thabti et al. [2] studied the general optimization problem of provisioning a VPN with bandwidth guarantees and having a tree topology. The authors of [2] gave a detailed comparison of the bandwidth cost of VPN trees designed based on both workload models. They also showed also that a bandwidth over-provisioning factor of up to 2 is achieved by the hose model compared to solutions obtained with a pipe model.

4 Notations This section summarizes the notation used in this paper. A network is modeled as an undirected graph G = (V , E), where V and E are the node and edge sets, respectively. An edge between two nodes i and j will be denoted by ij . Let P ⊆ V be the set of terminals (VPN endpoints). A tree T is a connected subgraph of G with no cycle. A tree is a Steiner tree with respect to the terminal nodes of P if it connects all the nodes of P . Note that a Steiner tree usually connects a small subset of the graph nodes. Let Tv be a tree rooted at the node v ∈ V . Given an edge ij in ij a tree T , we denote by Ti the connected component of T containing node i when the edge ij is deleted from T , and

Ann. Telecommun. ij

ij

Pi the set of VPN endpoints in Ti . We also denote by CT (ij ) the bandwidth reserved on the link ij of the VPN tree T , and by CT the total bandwidth reserved on all the links of the VPN tree T . The distance between two nodes i and j in a graph G is the length of a shortest path (in terms of number of edges) between i and j , and is denoted by dG (ij ). dT (ij ) will denote the distance between nodes i and j in the tree T . Given a node set W ⊆ V , we will denote by W = V \ W . If W and W  are two disjoint node sets, [W, W  ] will denote the set of edges having one endnode in W and the other in W  . For W ⊆ V , δ(W ) = [W, W ], is the cut set induced by the node set W . Let H = (V , A) be a directed graph with V the node set and A the arc set. An arc from a node i to a node j will be denoted (i, j ). Given two node sets W and W  , [W, W  ] will denote the set of arcs having their origin in W and their destinations in W  . Let δ + (W ) = [W, W ] and δ − (W ) = [W , W ].

Constraints (3) are cut constraints and ensure that the nodes of Sv form a Steiner tree. After computing the optimal core node set S ∗ , the optimal VPN tree T ∗ is obtained from S ∗ by first adding in T ∗ the edges of the Steiner tree of S ∗ . Then, we contract in G the nodes of S ∗ and construct a Breadth-First-Search (BFS) tree rooted at that supernode and connecting all the VPN endpoints in P (as the leaves). Finally, the edges of that BFS tree are added to T ∗ (see the Algorithm 1 below).

5 Integer programming formulation of the VPN tree design problem 5.1 Hose model 5.1.1 Formulation The hose-based ILP formulation is due to Kumar et al. [18]. The problem of determining a Steiner tree Sv rooted at v, for all v ∈ V is modeled as an integer linear program (ILP). Let xij , yi , and ze be 0−1 variables, where yi = 1 if i ∈ Sv and yi = 0 otherwise, xij = 1 if VPN endpoint j is assigned to node i and xij = 0 otherwise, and finally ze = 1 if edge e is in the Steiner tree connecting the nodes in Sv . For all j ∈ P , we let Bj = Bjin + Bjout . Computing a Steiner tree Sv with minimum bandwidth is equivalent to solving Minimize



dG (i, j ) × Bj × xij + M ×

i∈V ,j ∈P

subjected to

xij ≥ 1, ∀j ∈ P ,

ze e∈E

(1)

i∈V

yi − xij ≥ 0, ∀i ∈ V and j ∈ P ,



 ⊂ V, ze − xij ≥ 0, ∀V ) e∈δ(V

(2) (3)

 i∈V

xij , yi and ze ∈ {0, 1}.

(4)

In this formulation, constraints (1) and (2) force that each VPN endpoint j is assigned to at least one node in Sv .

As explained before, each node set Sv , v ∈ V , is determinated by solving the ILP given earlier. Because of NP-hard nature of the optimal Steiner tree problem, we adopt integer programming techniques like Branch-and-Cut techniques to solve it. Indeed, the ILP formulation contains an exponential number of constraints (the cut constraints (3)). 5.1.2 Resolution algorithm (hoseB&C) In [1], Diarrassouba et al. gave a branch and cut algorithm to solve a linear relaxation of this problem. We call this algorithm hoseB&C. The Branch-and-Cut method is one of the most effective methods for solving hard combinatorial optimization problems. It has been widely used to solve numerous real word problems. The Branch-and-Cut method consists of solving the problem by applying the Branch-and-Bound method upon linear programming techniques. Each node of the Branch-and-Bound tree consists of a linear program obtained by considering the linear relaxation of the problem. For more details on Branch-and-Cut and cutting planes algorithms, the reader can refer to [19, 21, 24]. The main ingredient of the cutting plane method is the so-called separation problem, which consists of the following: Given a solution x of a Linear Program and a class of inequalities F , find if there exists an inequality of F which is violated by x. An algorithm used to solve a separation problem is called a separation algorithm.

Ann. Telecommun.

The integer programming formulation described earlier contains an exponential number of cut constraints (3). To solve its linear relaxation, authors in [1] used the cutting plane method. They showed that the constraint separation problem can be reduced to a maximum flow problem with lower and upper bounds, and can therefore be solved in polynomial time [1]. Let  = (x, y, z) be a solution of the problem and G(z) be the support graph of this solution, that is the graph obtained from G by removing every edge e ∈ E having z(e) = 0. According to [1], an exact separation algorithm for the cut constraints (3) can be devised by three lemmas. We first look if the graph G(z) is connected or not. If it is not connected and C1 , ..., Cr are its connected components, with v ∈ C1 , we check if for all j ∈ P and for every node i ∈ Ck , k = 2, ..., r, x ij > 0. If yes, the cut constraint induced by Ck and j is violated [1]. If G(z) is not connected and for every k = 2, ..., r, and j ∈ P , x ij = 0, then the constraint separation problem is reduced to looking for violated cut constraints in the subgraph induced by the component C1 [1]. Thus, this latter case is similar to the case when G(z) is connected. Now if G(z) is connected, then the separation problem is equivalent to finding a feasible flow between i and v, for all i ∈ V \ {v}. To do this, we build, for all j ∈ P , the graph Gj as described above. Then, for all i ∈ V \ {v}, we look for a feasible flow between i and v, using the algorithm described above (and in [11]). If there is no feasible flow between i and v, then the algorithm returns a node set W which does not satisfies the cut conditions. This node set, together with j induces a violated cut constraint [1]. If for all i ∈ V \ {v} and j ∈ P , there exists a feasible flow in Gj between i and v, then the solution (x, y, z) satisfies all the cut constraints. The computation of the node set W can be done by using the maximum flow algorithm of Ford and Fulkerson which runs in O(|V ||Aj |). The separation algorithm for cut constraints can, hence, be implemented to run in polynomial time [1]. 5.2 Pipe model 5.2.1 ILP formulation The following pipe-based ILP formulation is based on [2]. For the pipe model, a non symmetric traffic matrix D = (mod )o,d∈P describes the required bandwidth between each VPN endpoint pair (o, d). The traffic between each pair of VPN points is carried through the customer pipes (point-to-point connections) with a given pre-allocated bandwidth according to mod . Let us consider the link (i, j ) that connects the two sets

(i,j )

(i,j )

of endpoints Pi and Pj . The bandwidth c(i, j ) to be reserved on link (i, j ) of T is given by Eq. 5.

mo,d . (5) c(i, j ) = (i,j )

o∈Pi

(i,j )

,d∈Pj

Let r ∈ P a root node chosen arbitrarily for the VPN tree (can also be a user specified terminal). For each ordered pair of terminals (o, d), mod represents the non-negative amount of traffic that has to be routed from o to d. Let xij and yijod be 0 − 1 variables, where xij is 1 if {i, j } is used in the VPN tree and yijod is 1 if (i, j ) is used to root the amount of traffic mod from VPN source node o to VPN destination node d. The integer linear programming formulation ILP2 can then be defined as follows:



Minimize mod ∗ yijod (6) {i,j }∈E o,d∈P



xij ≥ 1, ∀S ⊂ V , r ∈ S, P ∩ (V \ S) = ∅, (7)

{i,j }∈δ(S)



yijod −

(i,j )∈δ + (S)





yjodi = bi , ∀i ∈ V , o, d ∈ P , (8)

(i,j )∈δ − (S)

mod ∗ (yijod + yjodi ) ≤ cij xij , ∀{i, j } ∈ E,

(9)

o,d∈W



{i,j }∈C

xij ≤

xij ≤ |C| − 1, ∀Cycle C ∈ G,

(yijod + yjodi ), ∀{i, j } ∈ E,

(10) (11)

o,d∈W

xij ∈ {0, 1}, ∀ {i, j } ∈ E, yijod

∈ {0, 1}, ∀ {i, j } ∈ E, o, d ∈ P .

(12) (13)

Where, ⎧ ⎨ 1 if i = o, bi = −1 if i = d, ⎩ 0 otherwise. The objective function seeks to minimize the total bandwidth reservation consumed by the VPN tree. The inequalities from Eqs. 7 to 11 can be interpreted as follows: Constraints (7) are the Steiner cut inequalities to ensure the connection by imposing a path between the root terminal r and the other terminals in P \ {r}. Constraints (8) ensure demand satisfaction by imposing a unit flow between each oriented pair of terminals. For each edge {i, j }, the corresponding constraints (9) guarantee on the one hand that the capacity cij reserved on {i, j } is sufficient to carry the total traffic flowing through it, and on the other hand, the constraints ensure that the traffic flowing down the links (i, j ) or (j, i) is only possible when the edge {i, j } is in the VPN tree. Constraints (10) are the classical cycle-elimination constraints to enforce the absence of cycles in the resulting graph. Constraints (11) are useful to prune leaves of the solution that do not correspond to VPN endpoints.

Ann. Telecommun.

5.2.2 Resolution algorithm (pipeB&C) The integer linear programming ILP2 consists of (|E| + 2 ∗ |E| ∗ |P | ∗ |P − 1|) variables, (2 ∗ |P − 1|) constraints (7), (|V | ∗ |P | ∗ |P − 1|) constraints (8), (|E|) constraints (9), and (|E|) constraints (11). In [2], Thabti et al. gave a branch-and-cut algorithm (pipeB&C) to solve ILP2. Their proposed exact algorithm is based on a cut-separation method to separate in an exact manner the families of inequalities with exponential number of constraints (Constraints (7) and (10)). The pipeB&C is given in Algorithm 2.

6 Exact algorithm to derive a pipe workload model from a hose workload model (H 2P ) In this section, we give our exact procedure (H 2P ) to transform a hose workload into a pipe workload. Our idea is as follows: Given a user-specified hose, instead of applying the hoseB&C algorithm [1] directly, we generate a traffic matrix that satisfies the constraints imposed by the hose in question. Afterwards, we apply the pipeB&C algorithm [2] to determine an optimally provisioned VPN tree. We give here a linear programming formulation to transform the hose into a pipe workload and we also show that the final solution satisfies the original hose workload. 6.1 Formulation Our problem can be described as follows:

Input The hose model given by: – –

The set of endpoints P . The hose ingress bandwidth Biin and the hose egress Biout , for each node i ∈ P , expressed in Mbps.

Biin and Biout represent the expected traffic flows that the endpoint i receives and sends, respectively.

The Steiner cut (7) can be separated by computing the maximum flow from the root node r to each terminal i ∈ P \ {r} as target node. This provides a minimum (r, i)-cut. Violated inequality is found if the value of the corresponding edges according to the sum of the LP-values is less than 1. The separation procedure utilizes Goldberg and Tarjan’s implementation of the preflow method given by LEMON graph library [25] for the maximum flow problem to perform the required minimum cut computations. The cycle-elimination constraints (10) can be easily separated by the shortest path computations with Dijkstra’s algorithm. Hereby, we use 1 − xijLP as the arc weights with xijLP denoting the current value of the LP-relaxation for edges {i, j } in the current node of the B&B-tree. We obtain cycles by iteratively considering each edge {i, j } ∈ E and searching for the shortest path from j to i. If the value of a shortest path plus xijLP is less than 1, we have found a cycle violating constraints (10). We add this inequality to the LP and resolve it. In each node of the B&B-tree, we perform these cutting plane separations until no further cuts can be found.

Output Traffic matrix M = (M(i, j ))i∈P ,j ∈P ,i=j that satisfies the input hose. By summing the values of the row i of the matrix M, we find the amount of traffic sent by the terminal i. To satisfy the hose, this amount should not exceed Biout , ∀i ∈ P . This is reflected in the following constraint.

M(i, j ) ≤ Biout

(14)

j  =i

Similarly, by summing the values of a column j of the matrix M, we find the amount of traffic received by the terminal j . This amount should not exceed Bjin . This is reflected in the following constraint.

M(j, i) ≤ Bjin

∀i, j ∈ P

(15)

j  =i

For the objective function, we seek to maximize the total bandwidth reserved on pipes f =

i,j ∈P ,i=j

M(i, j )

(16)

Ann. Telecommun. Table 1 Effect of the problem size on the running time in the case of hose model (CpuH) and that of our H 2P approach (CpuP) for Waxman graphs Ins

|V |

|E|

|P |

VarH

VarP

CtrH

CtrP

CpuH

CpuP

10n4 10n5 10n6 10n7 15n4 15n5 15n6 15n7 20n4 20n5 20n6 20n7 25n4 25n5 25n6 25n7 30n4 30n5 30n6 30n7 35n4 35n5 35n6 35n7 40n4 40n5 40n6 40n7 45n4 45n5 45n6 45n7 50n4 50n5 50n6 50n7 55n4 55n5 55n6 55n7 60n4 60n5 60n6 60n7 65n4 65n5 65n6 65n7

10 10 10 10 15 15 15 15 20 20 20 20 25 25 25 25 30 30 30 30 35 35 35 35 40 40 40 40 45 45 45 45 50 50 50 50 55 55 55 55 60 60 60 60 65 65 65 65

20 20 20 20 30 30 30 30 40 40 40 40 50 50 50 50 60 60 60 60 70 70 70 70 80 80 80 80 90 90 90 90 100 100 100 100 110 110 110 110 120 120 120 120 130 130 130 130

4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7

70 80 90 100 105 120 135 150 140 160 180 200 175 200 225 250 210 240 270 300 245 280 315 350 280 320 360 400 315 360 405 450 350 400 450 500 385 440 495 550 420 480 540 600 455 520 585 650

500 820 1220 1700 750 1230 1830 2550 1000 1640 2440 3400 1250 2050 3050 4250 1500 2460 3660 5100 1750 2870 4270 5950 2000 3280 4880 6800 2250 3690 5490 7650 2500 4100 6100 8500 2750 4510 6710 9350 3000 4920 7320 10,200 3250 5330 7930 11,050

44 55 66 77 64 80 96 112 84 105 126 147 104 130 156 182 124 155 186 217 144 180 216 252 164 205 246 287 184 230 276 322 204 255 306 357 224 280 336 392 244 305 366 427 264 330 396 462

166 248 350 472 246 368 520 702 326 488 690 932 406 608 860 1162 486 728 1030 1392 566 848 1200 1622 646 968 1370 1852 726 1088 1540 2082 806 1208 1710 2312 886 1328 1880 2542 966 1448 2050 2772 1046 1568 2220 3002

0.01 0.02 0.02 0.02 0.02 0.02 0.03 0.03 0.06 0.05 0.10 0.11 0.13 0.12 0.25 0.25 0.15 0.09 0.22 0.21 0.15 0.17 0.27 0.34 0.19 0.3 0.51 0.54 0.44 0.46 0.78 1.36 0.77 0.87 1.09 1.39 0.65 0.86 0.65 1.34 0.96 1.17 1.82 1.66 1.97 1.6 1.45 2.3

0.04 0.19 0.17 1.57 0.27 0.33 1.4 2.87 0.26 0.9 1.97 4.93 1.63 3.2 8.49 30.29 1.12 8.15 8.01 17.57 3.23 2.58 5.1 41.2 0.6 8.47 33.27 23.85 10.63 9.12 25.8 31.18 1.96 12.69 14.54 66.57 2.75 10.05 25.71 90.53 10.38 24.37 69.11 81.7 14.21 42.34 36.26 15.41

Ann. Telecommun. Table 1

(continued)

Ins

|V |

|E|

|P |

VarH

VarP

CtrH

CtrP

CpuH

CpuP

70n4 70n5 70n6 70n7 75n4 75n5 75n6 75n7

70 70 70 70 75 75 75 75

140 140 140 140 150 150 150 150

4 5 6 7 4 5 6 7

490 560 630 700 525 600 675 750

3500 5740 8540 11,900 3750 6150 9150 12,750

284 355 426 497 304 380 456 532

1126 1688 2390 3232 1206 1808 2560 3462

2.78 1.96 5.09 7.61 3.55 2.81 4.41 5.7

11.58 75.84 22.17 218.31 21.93 21.81 131.39 64.21

Thus, we obtain the following linear program: ⎧  maximiserf = i,j ∈P ,i=j M(i, j ) ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ out ⎪ ∀i ∈ P ; ⎨ j =i M(i, j ) ≤ Bi ,

Similarly we have

 ⎪ ⎪ ⎪ M(j, i) ≤ Bjin , ⎪ ⎪ j  =i ⎪ ⎪ ⎪ ⎪ ⎩ 0 ≤ M(i, j ),

However, according to our formulation, we know that

(i,j )

u∈Pi

∀i ∈ P ;



∀i, j ∈ P , i = j. (17)

Theorem 1 Let M be the traffic matrix solution of the ILP (17) and T the VPN tree obtained by applying pipeB&C algorithm on M. Then T satisfies the original hose model. i.e. if (i, j ) is an edge of tree T , then the cost of (i, j ) does not exceed the amount



Blout , Blin } min{ (i,j )

l∈Pj

Proof Let T be the tree obtained using the traffic matrix M. We need to show that this tree satisfies the original hose. It is sufficient to show that the cost of an edge (i, j ) of T does not exceed the amount



min{ Blout , Blin } (i,j )

(i,j )

l∈Pi

l∈Pj

For the tree T obtained from the pipe model, the reserved bandwidth on the link (i, j ) is equal to



c(i, j ) = du,v = du,v (i,j )

u∈Pi

(i,j )

,v∈Pj

(i,j )

u∈Pi

(i,j )

v∈Pj

However, according to our formulation, we know that

du,v ≤ Buout



du,v = (i,j )

(i,j )

,v∈Pj

v∈Pj



du,v

(i,j )

u∈Pi

du,v ≤ Bvin

(i,j )

u∈Pi

So, c(i, j ) ≤



Bvin

(19)

(i,j ) v∈Pj

From Eqs. 18 and 19, we obtain c(i, j ) ≤ min{

(i,j )

l∈Pi



c(i, j ) =



Bvin ,

(i,j ) v∈Pj



Buout }

(20)

(i,j ) u∈Pi

Which guarantees that the tree found supports the original hose.

7 Performance evaluation 7.1 Network topology The proposed solution algorithms have been evaluated on a large number of randomly generated graphs. We used two methods for generating random graphs. The first is the Waxman method [23] where a flat random graph is constructed. This method defines the probability of having an edge between any two nodes u and v as

(i,j )

v∈Pj

So, c(i, j ) ≤

−d

(i,j ) u∈Pi

P (u, v) = αe βL Buout

(18)

where 0 < α, β < 1, d is the Euclidian distance between nodes u and v, and L is the maximum distance

Ann. Telecommun.

between the two freely selected nodes. Large values of the parameter α result in large values of the number of edges in the graph, while a decrease in the parameter β increases the number of long edges relative to short ones. The second method used to generate graphs is the one proposed by SteinLib Testdata Library [14]. The aim of this library is to collect freely available instances of Steiner tree problems in graphs and provide some information about their origins, solvability, and characteristics.

7.2 Efficiency of H2P In this section, we compare the bandwidth costs of solutions obtained using pipe workload obtained with the H 2P procedure to costs of solutions obtained using the original user specified hose workload. This comparison is performed using a large number of randomly generated networks and hose workloads. As mentioned before, BRITE (Boston university Representative Internet Topology gEnerator) [22] was used as a tool for

Table 2 Effect of the problem size on the running time in the case of hose model (CpuH) and that of our H 2P approach (CpuP) for Waxman graphs (continuation of Table 1) Ins

|V |

|E|

|P |

VarH

VarP

CtrH

CtrP

CpuH

CpuP

80n4 80n5 80n6 80n7 85n4 85n5 85n6 85n7 90n4 90n5 90n6 90n7 95n4 95n5 95n6 95n7 100n4 100n5 100n6 100n7 I20n6 I20n7 I25n6 I30n5 I30n6 I35n6 I45n6 I45n7 I50n7 I55n7 I60n6 I60n7 I70n5 I70n6 I70n7 I80n4

80 80 80 80 85 85 85 85 90 90 90 90 95 95 95 95 100 100 100 100 20 20 25 30 30 35 45 45 50 55 60 60 70 70 70 80

160 160 160 160 170 170 170 170 180 180 180 180 190 190 190 190 200 200 200 200 40 40 50 60 60 70 90 90 100 110 120 120 140 140 140 160

4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 6 7 6 5 6 6 6 7 7 7 6 7 5 6 7 4

560 640 720 800 595 680 765 850 630 720 810 900 665 760 855 950 700 800 900 1000 180 200 225 240 270 315 405 450 500 550 540 600 560 630 497 560

4000 6560 9760 13,600 4250 6970 10,370 14,450 4500 7380 10,980 15,300 4750 7790 11,590 16,150 5000 8200 12,200 17,000 2440 3400 3050 2460 3660 4270 5490 7650 8500 9350 7320 10,200 5740 8540 700 4000

324 405 486 567 344 430 516 602 364 455 546 637 384 480 576 672 404 505 606 707 126 147 156 155 186 216 276 322 357 392 366 427 355 426 11900 324

1286 1928 2730 3692 1366 2048 2900 3922 1446 2168 3070 4152 1526 2288 3240 4382 1606 2408 3410 4612 690 932 860 728 1030 1200 1540 2082 2312 2542 2050 2772 1688 2390 3232 1286

3.55 2.87 4.47 6.96 2.14 2.66 6.82 7.93 6.23 8.74 7.35 10.53 3.98 2.82 4.78 10.39 3.76 7.15 6.84 8.49 0.12 0.13 0.18 0.10 0.23 0.30 0.76 0.74 1.75 1.32 2.22 1.46 2.52 4.68 3.86 3.48

22.7 63.26 98.77 373.37 26.71 99.99 210.46 290.36 31.23 101.34 116.25 154.82 37.53 61.99 78.32 190.3 7.54 95.33 46.52 197.41 2.61 12.95 14.8 1.04 11.95 1.96 68.6 32.53 115.71 136.21 3868 174.73 22.68 91.97 209.4 5.62

Ann. Telecommun.

generation of realistic network topologies based on Waxman graphs methods and SteinLib Testdata Library. We have generated graphs with 10 to 100 nodes by Waxman method and graphs with 33 to 93 nodes from SteinLib Testdata Library. For each type of instances, we have considered 4, 5, 6, and 7 terminal nodes in Waxman’s graph and 4 to 8 terminals nodes in SteinLib Testdata Library graphs. BRITE generator has been configured to generate graphs whose number of edges equals twice the number of nodes of the graph. For all test networks, we select as root v0 = 0.

The results are given in Tables 1, 2, 3, 4, 5, and 6. The entries of the tables are defined in Table 7. We note here that the bandwidth reduction factor (BRF) is computed as follows: BRF =

CoptH CoptP

Results for Waxman Graphs are given in Tables 1, 2, 4, and 5. We can see that the BRF varies between 1.31 for

Table 3 Effect of the problem size on the running time in the case of hose model (CpuH) and that of our H 2P approach (CpuP) for SteinLib Testdata Library Graphs Ins

|V |

|E|

|P |

VarH

VarP

CtrH

CtrP

CpuH

CpuP

es20fst11-33-36-4 es20fst11-33-36-5 es20fst11-33-36-6 es20fst11-33-36-7 es20fst11-33-36-8 es20fst14-36-44-4 es20fst14-36-44-5 es20fst14-36-44-6 es20fst14-36-44-7 es20fst14-36-44-8 es30fst01-79-115-4 es30fst01-79-115-5 es30fst01-79-115-6 es30fst01-79-115-7 es30fst01-79-115-8 es40fst01-93-127-4 es40fst01-93-127-5 es40fst01-93-127-6 es40fst01-93-127-7 es40fst01-93-127-8 es40fst03-87-107-4 es40fst03-87-107-5 es40fst03-87-107-6 es40fst03-87-107-7 es40fst03-87-107-8 es40fst04-55-55-4 es40fst04-55-55-5 es40fst04-55-55-6 es40fst04-55-55-7 es40fst04-55-55-8 es40fst13-78-95-4 es40fst13-78-95-5 es40fst13-78-95-6 es40fst13-78-95-7 es40fst13-78-95-8

33 33 33 33 33 36 36 36 36 36 79 79 79 79 79 93 93 93 93 93 87 87 87 87 87 55 55 55 55 55 78 78 78 78 78

36 36 36 36 36 44 44 44 44 44 115 115 115 115 115 127 127 127 127 127 107 107 107 107 107 55 55 55 55 55 95 95 95 95 95

4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8

201 234 267 300 333 224 260 296 332 368 510 589 668 747 826 592 685 778 871 964 542 629 716 803 890 330 385 440 495 550 485 563 641 719 797

900 1476 1476 3060 4068 1100 1804 2684 3740 4972 2875 4715 7015 9775 12995 3175 5207 7747 10,795 14,351 2900 4756 7076 9860 13,108 1375 2255 3355 4675 6215 2375 3895 5795 8075 10,735

136 170 204 238 272 148 185 222 259 296 320 400 480 560 640 376 470 564 658 752 352 440 528 616 704 224 280 336 392 448 316 395 474 553 632

474 740 740 1470 1934 526 816 1178 1612 2118 1184 1819 2610 3560 4668 1376 2122 3054 4172 5476 1284 1980 2852 3898 5118 776 1218 1770 2432 3204 1132 1758 2540 3478 4572

0.11 0.17 0.17 0.25 0.26 0.23 0.26 0.35 0.40 0.42 4.51 4.07 14.13 8.86 12.90 3.85 4.30 3.93 11.37 18.16 3.77 4.21 4.54 6.25 7.87 0.47 0.40 0.68 0.74 0.98 1.70 2.20 2.57 3.25 3.86

0.1 0.22 0.22 9.58 23.82 0.56 1.25 8.4 35.49 83.96 2.33 14.12 138.736 153.43 415.16 3.04 13.09 26.55 155.34 143.85 3.4 10.8 81.6 91.68 201.78 0.44 2.18 12.66 47.18 154.94 1.74 7.23 15.35 39.76 147.64

Ann. Telecommun. Table 4 Comparison between solution costs obtained with the hose model (CoptH) and those obtained with the H 2P approach (CoptP) using test Waxman graphs

Ins

|V |

|E|

|P |

CoptH

CoptP

BRF

10n4 10n5 10n6 10n7 15n4 15n5 15n6 15n7 20n4 20n5 20n6 20n7 25n4 25n5 25n6 25n7 30n4 30n5 30n6 30n7 35n4 35n5 35n6 35n7 40n4 40n5 40n6 40n7 45n4 45n5 45n6 45n7 50n4 50n5 50n6 50n7 55n4 55n5 55n6 55n7 60n4 60n5 60n6 60n7 65n4 65n5 65n6 65n7

10 10 10 10 15 15 15 15 20 20 20 20 25 25 25 25 30 30 30 30 35 35 35 35 40 40 40 40 45 45 45 45 50 50 50 50 55 55 55 55 60 60 60 60 65 65 65 65

20 20 20 20 30 30 30 30 40 40 40 40 50 50 50 50 60 60 60 60 70 70 70 70 80 80 80 80 90 90 90 90 100 100 100 100 110 110 110 110 120 120 120 120 130 130 130 130

4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7

1011 1935 3579 5142 1381 2115 3514 5323 1184 2289 3721 5456 1492 2380 3754 5747 1045 1679 3754 5747 1039 2323 4373 6729 1263 2579 3684 5190 868 2143 3102 5113 1256 1467 3721 6095 1048 1372 3721 5108 770 2379 3514 5456 1044 2277 3579 5781

600 1100 2200 3250 645 1090 1780 2460 638 1127 2280 3060 780 1690 2460 3489 619 1126 2146 3025 594 1115 2059 3468 631 1311 2221 3444 566 1421 1971 3409 710 981 1910 3043 618 915 1674 3007 488 1427 2167 3004 785 1326 2015 3333

1.69 1.76 1.63 1.58 2.14 1.94 1.97 2.16 1.86 2.03 1.63 1.78 1.91 1.41 1.53 1.65 1.69 1.49 1.75 1.90 1.75 2.08 2.12 1.94 2.00 1.97 1.66 1.51 1.53 1.51 1.57 1.50 1.77 1.50 1.95 2.00 1.70 1.50 2.22 1.70 1.58 1.67 1.62 1.82 1.33 1.72 1.78 1.73

Ann. Telecommun.

Table 4

(continued)

Table 5 Comparison between solution costs obtained with the hose model (CoptH) and those obtained with the H 2P approach (CoptP) using test Waxman graphs. (continuation of the Table 4)

Ins

|V |

|E|

|P |

CoptH

CoptP

BRF

70n4 70n5 70n6 70n7 75n4 75n5 75n6 75n7

70 70 70 70 75 75 75 75

140 140 140 140 150 150 150 150

4 5 6 7 4 5 6 7

1169 1519 4231 6415 1020 2308 3721 5108

767 845 2374 3548 513 1466 2288 3870

1.52 1.80 1.78 1.81 1.99 1.57 1.63 1.32

Ins

|V |

|E|

|P |

CoptH

CoptP

BRF

80n4 80n5 80n6 80n7 85n4 85n5 85n6 85n7 90n4 90n5 90n6 90n7 95n4 95n5 95n6 95n7 100n4 100n5 100n6 100n7 I20n6 I20n7 I25n6 I30n5 I30n6 I35n6 I45n6 I45n7 I50n7 I55n7 I60n6 I60n7 I70n5 I70n6 I70n7 I80n4

80 80 80 80 85 85 85 85 90 90 90 90 95 95 95 95 100 100 100 100 20 20 25 30 30 35 45 45 50 55 60 60 70 70 70 80

160 160 160 160 170 170 170 170 180 180 180 180 190 190 190 190 200 200 200 200 40 40 50 60 60 70 90 90 100 110 120 120 140 140 140 160

4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 6 7 6 5 6 6 6 7 7 7 6 7 5 6 7 4

1223 2486 3721 6095 938 1572 3102 5113 1028 1977 3684 5190 1619 2287 3721 6095 1065 2210 4373 6090 1732 4040 1437 924 1437 1749 1128 4305 4605 3740 1182 4040 1391 1485 4605 972

796 1422 2138 3550 520 941 2373 3099 545 1266 2142 3728 870 1078 1767 3343 580 1120 2090 2950 1096 2359 800 622 772 785 715 2931 3177 2792 830 2112 922 804 2668 639

1.54 1.75 1.74 1.72 1.80 1.67 1.31 1.65 1.89 1.56 1.72 1.39 1.86 2.12 2.11 1.82 1.84 1.97 2.09 2.06 1.58 1.71 1.80 1.49 1.86 2.23 1.65 1.47 1.45 1.34 1.42 1.91 1.51 1.85 1.73 1.52

Ann. Telecommun.

instance 85n6 and 2.23 for instance I 35n6. This means that the solution obtained by H 2P has a reduced cost (CoptP in the tables) by more than half that for a solution obtained directly from the hose model algorithm (CoptH in the tables).

V arH = |V |(|P | + 1) + |E| CtrH = |P |(|V | + 1)

7.3 Comparison of execution times In Tables 1 and 2, we study the effect of the problem size on the running time in the case of hose model (CpuH ) and that of our H 2P procedure (CpuP ) for Waxman Graphs. Table 6 Comparison between solution costs obtained with the hose model (CoptH) and those obtained with the H 2P approach (CoptP) using SteinLib Testdata Library graphs

For the formulation given in the case of hose model, the number of variables V arH and number of constraints CtrH are,

For the formulation given in the case of pipe model, we have: V arP = |E|(1 + 2|P |2 − 2|P |) CtrP = |V ||P |2 + (2 − |V |)|P | + 2(|E| − 1)

Ins

|V |

|E|

|P |

CoptH

CoptP

BRF

es20fst11-33-36-4 es20fst11-33-36-5 es20fst11-33-36-6 es20fst11-33-36-7 es20fst11-33-36-8 es20fst14-36-44-4 es20fst14-36-44-5 es20fst14-36-44-6 es20fst14-36-44-7 es20fst14-36-44-8 es30fst01-79-115-4 es30fst01-79-115-5 es30fst01-79-115-6 es30fst01-79-115-7 es30fst01-79-115-8 es40fst01-93-127-4 es40fst01-93-127-5 es40fst01-93-127-6 es40fst01-93-127-7 es40fst01-93-127-8 es40fst03-87-107-4 es40fst03-87-107-5 es40fst03-87-107-6 es40fst03-87-107-7 es40fst03-87-107-8 es40fst04-55-55-4 es40fst04-55-55-5 es40fst04-55-55-6 es40fst04-55-55-7 es40fst04-55-55-8 es40fst13-78-95-4 es40fst13-78-95-5 es40fst13-78-95-6 es40fst13-78-95-7 es40fst13-78-95-8

33 33 33 33 33 36 36 36 36 36 79 79 79 79 79 93 93 93 93 93 87 87 87 87 87 55 55 55 55 55 78 78 78 78 78

36 36 36 36 36 44 44 44 44 44 115 115 115 115 115 127 127 127 127 127 107 107 107 107 107 55 55 55 55 55 95 95 95 95 95

4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8

3920 10,860 10,860 22,324 32,679 5613 8764 10,994 21,531 31,112 6054 6495 16,590 23,954 32,637 7632 17,461 18,354 34,387 38,344 3696 9318 10,779 18651 29,873 10,943 10,301 37,160 41,901 61,057 7640 17,407 24,365 27,906 47,493

2311 6496 6496 13,413 19,814 3592 5727 7734 12,468 15,510 4440 4013 11,892 15,914 22,945 3362 8882 8975 19,884 25,904 2542 6156 5990 9463 16,978 6820 6065 21,822 20,900 30,856 3738 10,974 17,613 19,806 36,173

1.70 1.67 1.67 1.66 1.65 1.56 1.53 1.42 1.73 2.01 1.36 1.62 1.40 1.51 1.42 2.27 1.97 2.05 1.73 1.48 1.45 1.51 1.80 1.97 1.76 1.60 1.70 1.70 2.00 1.98 2.04 1.59 1.38 1.41 1.31

Ann. Telecommun. Table 7 Entries of the Tables 1, 2, 3, 4, 5, and 6 |V | |E| |P | CtrH VarH CoptH CpuH VarP CtrP CpuP CoptP BRF

Number of nodes of the graph Number of edges of the graph Number of terminal nodes Number of constraints in Hose formulation Number of variables in Hose formulation Tree Cost for the hose model Total CPU time for the Hose model Algorithm in seconds Number of variables in Pipe formulation Number of constraints in Pipe formulation Total CPU time for the Pipe model Algorithm in seconds Tree Cost for the pipe model Bandwidth Reduction Factor

Thus, the number of variables and number of constraints in the case of hose model grow linearly with the number of terminals, whereas they grow quadratically in the case of pipe model. In addition, if we take Waxman graphs, in this case |V | = 2|E|, and if we fix for example |P | = 4, we obtain V arH = 7|V |, V arP = 50|V |, CtrH = 4 + 4|V |, and CtrP = 6 + 16|V |, we note here the clear difference between the sizes of the two problems. Note here that the execution time of our exact algorithm to derive a pipe workload from a given hose workload is negligible. The execution time of the procedure H 2P is then very close to that of the pipeB&C algorithm (CpuP in the tables). We note that the running time of H 2P is higher than that of the algorithm hoseB&C. This is due to the size of the problem as explained above. Indeed, we note that the number of variables (V arP ) and the number of constraints (CtrP ) in the pipe model formulation are significantly higher than those of the hose model formulation namely (varH ) and (CtrH ). The results for SteinLib Testdata Library graphs are given in Tables 3 and 6. The same remarks can be stated for SteinLib Testdata Library graphs. The bandwidth reduction factor varies between 1.31 for instance es40fst13-78-95-8 and 2.27 for instance es40fst01-93-127-4. The running time of the hose model algorithm is much higher than H 2P algorithm for the same reasons explained earlier. Tables 3 and 6 compare the effect of the problem size on the running time in the case of hose model (CpuH ) and that of our H 2P procedure (CpuP ) for SteinLib Testdata Library Graphs.

7.4 Complexity of the two procedures The second factor affecting the execution time is the time complexity of the two procedures. Using the ellipsoid method, introduced by Khachian [20] for linear programming, Grtschel et al. [17] showed that if we can solve the separation problem in polynomial time for a polyhedron P , then we can solve the optimization problem on P in polynomial time. Therefore, the complexity of a cutting algorithm, on a polyhedron, does not depend on the number of constraints in the formulation, but depends on the complexity of the corresponding separation problem. In this part, we compare between the time complexity of both separation methods associated with the two algorithms. In the hoseB&C algorithm, the problem is reduced to a maximum flow problem with lower and upper bounds. This problem can then be solved in polynomial time. We note here that the solution can be obtained using the maximum flow algorithm of Ford and Fulkerson which runs in O(|V ||E|). The B&C pipe-based method is based on the proposed integer programming formulation (ILP2) that consists of two constraints families: a polynomial number of constraints (8, 9, and 11) and an exponential number of constraints (7 and 10). The worst time complexity of the first family of constraints is O(V P 2 ). The worst time complexity of the three constraints of this family (constraints 8, constraints 9, and constraints 11) are O(V P 2 ), O(E), and O(E), respectively. Nevertheless, using a separation method, the cutting plane method is able to solve the exponential LP constraints using only a polynomial number of constraints. Then, the worst √ time complexity of the second constraint family is O(V 2 E). The worst time complexity of the separation algorithms of the two families √ of constraints (constraints 7 and constraints 10) are O(V 2 E) and O(V 2 ), respectively. Therefore, since V  P , the worst √ time complexity of the B&C pipe-based method is O(V 2 E).

8 Conclusion The virtual private network design problem has been widely studied in the literature. In this work, we propose a two-step exact approach to design a VPN tree with minimum bandwidth cost, given a hose workload. This approach consists of deriving a pipe workload from the user specified hose workload. Furthermore, we show that tree solutions obtained using the derived pipe workload satisfy the original hose workload. The proposed approach resulted in a significant reduction of bandwidth costs. Indeed, our experimental results show

Ann. Telecommun.

that the bandwidth costs of VPN trees obtained using this two-step approach are lower by a factor varying between 1.31 and 2.23 compared to VPN trees obtained using the original hose workload.

10.

11.

References 1. Diarrassouba I, Lourimi A, Mahjoub AR, Youssef H (2013) Hose workload based exact algorithm for the optimal design of virtual private networks. Comput Netw 57(14):2766–2774 2. Thabti B, Lourimi A, Youssef H, Mahjoub AR, Meddeb A (2012) From constant traffic matrices to hose workload model for VPN tree design. In: Telecommunications Network Strategy and Planning Symposium (NETWORKS), 2012 XVth International, Rome-Italy, pp 1–6 3. Chowdhury NMMK, Boutaba R (2009) Network virtualization: state of the art and research challenges. IEEE Commun Mag 47(7):20–26. ISSN: 0163-6804 4. Shashank S, Hamzah A-A, Michael W, Faruk C, Gokhale A, Xenofon K (2015) A simulation as a service cloud middleware. Ann Telecommun, Springer Paris:1–16. ISSN: 0003– 4347 5. Coutinho EF, de Carvalho SFR, Rego PAL, Gomes DG, de Souza JN (2015) Elasticity in cloud computing: a survey. Ann Telecommun, Springer Paris 70(7–8):289–309. ISSN: 00034347 6. Abdelhak F, Nadjib A, Khaled B (2015) WLAN planning: separate and joint optimization of both access point placement and channel assignment. Ann Telecommun, Springer Paris 70(5– 6):263–274. ISSN: 0003-4347 7. Mohammad A, Eui-Nam H (2013) Impact of ipv4-ipv6 coexistence in cloud virtualization environment. Ann Telecommun 69(9):485–496 8. Chowdhury NMMK, Boutaba R (2010) A survey of network virtualization. Comput Netw 54(5):862–876 9. Chowdhury M, Rahman MR, Boutaba R (2012) ViNEYard: virtual network embedding algorithms with coordinated node

12. 13.

14. 15. 16.

17.

18.

19. 20. 21.

22.

23. 24. 25.

and link mapping. IEEE/ACM Trans Networking 20(1):206– 219 ´ (2003) On bandwidth efficiency of J¨uttner A, Szab´o I, Szentesi A the hose resource management model in virtual private networks. In: Proceedings of the IEEE INFOCOM 2003, San Francisco, pp 386–395 Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice Hall, New Jersey Cohen R (2003) On the establishment of an access VPN in broadband access networks. IEEE Commun Mag:156–163 Fingerhut JA, Suri S, Turner JS (1997) Designing least-cost nonblocking broadband networks. Journal of Algorithms 24(2):287– 309 STP Library, http:\\steinlib.zib.de\steinlib.php de Clerq J, Parideans O (2002) Scalability implications of virtual private networks. IEEE Commun Mag:151–157 Duffield NG, Goyal P, Greenberg A, Mishra P, Ramakrishnan KK, van der Merwe JE (1999) A flexible model for resource management in virtual private networks. SIGCOMM Comput Commun Rev 29(4):95–108 Gr¨otschel M, Lov´asz L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1:70–89 Kumar A, Rastogi R, Silberschatz A, Yener B (2002) Algorithms for provisionning virtual private networks in the hose model. IEEE/ACM Trans Networking 10(4):565–578 Korte B, Vygen J (2006) Combinatorial Optimization: Theory and Algorithms, Ed. Springer 3rd Edition Khachian LG (1979) A polynomial algorithm in linear programming. Soviet Mathematics Doklady:191–194 Mahjoub AR (2010) Polyhedral approaches. In: Paschos V (ed) Concepts of combinatorial optimization, Iste-Wiely, pp 261– 324 Medina A, Lakhina A, Matta I, Byers J (2001) BRITE: an approach to universal topology generation. IEEE/ACM Mascots:346–356 Waxman BM (1988) Routing of multipoint connections. IEEE J Sel Areas Commun 6(9):1617–1622 Woolsey L (1998) Integer programming, Ed. Wiley-Interscience Lemon Graph Library, http://lemon.cs.elte.hu