1 Virtual Network Embedding with Coordinated Node and Link Mapping N. M. Mosharaf Kabir Chowdhury Raouf Boutaba Muntasir Raihan Rahman Cheriton School of Computer Science Cheriton School of Computer Science Cheriton School of Computer Science University of Waterloo University of Waterloo University of Waterloo Waterloo, Canada Waterloo, Canada Waterloo, Canada Email: [email protected] Email: [email protected] Email: [email protected] 1 —Recently network virtualization has been proposed online of each of the VN Abstract embedding/mapping/assignment as a promising way to overcome the current ossification of the requests is of utmost importance in order to increase utilization Internet by allowing multiple heterogeneous virtual networks of the substrate network resources and consequently revenues (VNs) to coexist on a shared infrastructure. A major challenge of the InPs. in this respect is the VN embedding problem that deals with However, the VN embedding problem, with constraints on efficient mapping of virtual nodes and virtual links onto the substrate network resources. Since this problem is known to be virtual nodes and virtual links, can be reduced to the NP - NP -hard, previous research focused on designing heuristic-based multi-way separator problem [5], even if all the VN hard algorithms which had clear separation between the node mapping requests are known in advance. Even when all the virtual and the link mapping phases. nodes are already mapped, embedding the virtual links with This paper proposes VN embedding algorithms with better NP -hard bandwidth constraints onto substrate paths is still coordination between the two phases. We formulate the VN em- scenario. As a result, a number in the unsplittable flow bedding problem as a mixed integer program through substrate network augmentation. We then relax the integer constraints to of heuristic-based algorithms have appeared in the relevant obtain a linear program, and devise two VN embedding algo- literature [6]–[9]. Most of these proposals focused primarily rithms D-ViNE and R-ViNE using deterministic and randomized on edge mapping (using, for example, shortest path, k-shortest rounding techniques, respectively. Simulation experiments show paths, and multi-commodity flow algorithms) after employing that the proposed algorithms increase the acceptance ratio and greedy methods to the node mappings. However, preselect the revenue while decreasing the cost incurred by the substrate network in the long run. preselecting node mappings without considering its relation to the link mapping stage restricts the solution space, and may result in poor performance. NTRODUCTION I. I In this paper, we introduce better correlation between the Since its inception, the Internet has proven its worth by node mapping and the link mapping phases by proposing two supporting myriads of distributed applications and heteroge- new VN embedding algorithms D-ViNE (Deterministic VN neous networking technologies. However, due to the existence Embedding) and R-ViNE (Randomized VN Embedding). In of multiple stakeholders with conflicting goals and policies, these algorithms, we map the virtual nodes to substrate nodes alterations, even necessary ones, to the present architecture in a way that facilitates the mapping of virtual links to physical have now become almost impossible to achieve. To fend off paths in the subsequent phase. To this end, we extend the the rigidity of the existing Internet once and for all, network physical network graph by introducing meta-nodes for each virtualization has been propounded as a fundamental diversify- virtual node and connect the meta-nodes to a selected subset ing attribute of the future inter-networking paradigm that will of physical nodes (Section IV-A). We then treat each virtual allow multiple heterogeneous network architectures to coexist link with bandwidth constraints as a commodity consisting of on a shared substrate [1], [2]. In a network virtualization a pair of meta-nodes. As a result, finding an optimal flow for environment (NVE), multiple service providers (SPs) will be the commodity is equivalent to mapping the virtual link in able to create heterogeneous virtual networks (VNs) to offer an optimal way. If we introduce additional binary constraints customized end-to-end services to the end users by leasing that force only one meta-edge to be selected for each meta- shared resources from one or more infrastructure providers node, we can effectively select exactly one substrate node for (InPs) without significant investment in physical infrastructure each meta-node corresponding to a particular virtual node. We [2]–[4]. use mixed integer programming (MIP) formulation [10] to Each VN in the NVE is a collection of virtual nodes (e.g., solve the embedding problem with binary constraints on the virtual routers) that are hosted on different substrate nodes meta-edges and linear constraints on actual substrate network and interconnected by physical paths in the substrate network corresponding to virtual links. Since multiple VNs can share 1 The words ‘embedding’, ‘mapping’, and ‘assignment’ are used inter- changeably throughout this paper. the same underlying physical resources, efficient and effective

2 edges. Since solving an MIP is known to be -hard [10], NP space by assuming infinite capacity of the substrate network - finding an optimal VN embedding using MIP becomes NP resources, nor do we assume any specialized VN topologies. hard as well. As a result, we relax the integer program to Contrary to the algorithms proposed in this paper, all the obtain a linear programming formulation which can be solved existing algorithms can clearly be separated into two basic in polynomial time. We then use deterministic and randomized phases: rounding techniques on the solution of the linear program to 1) assigning virtual nodes using some greedy heuristics, approximate the values of the binary variables in the original e.g., assign virtual nodes with higher processing require- MIP. Once all the virtual nodes have been mapped, we use ments to substrate nodes with more available resources the multi-commodity flow algorithm to map the virtual links [8], [9], and onto the substrate network between the mapped virtual nodes 2) embedding virtual links onto substrate paths using short- [9], [11]. This can also be solved in polynomial-time since est path algorithms [8] in case of unsplittable flows, we assume that path splitting is supported by the substrate multi-commodity flow or using algorithms in case of network [9]. splittable flows [9], [11]. The rest of this paper is organized as follows. Section II The authors in [14] have proposed a distributed algorithm provides an overview of the related work. Following that, Sec- that simultaneously maps virtual nodes and virtual links tion III formalizes the network model and the VN embedding without any centralized controller, but the scalability and problem itself. In Section IV, we provide the optimal MIP performance of their algorithm is still not comparable with formulation for the VN embedding problem using substrate the centralized ones. network augmentation. Section V relaxes the MIP formulation The integer and mixed integer programming approaches to obtain a linear program and presents D-ViNE and R-ViNE have been applied to a number of resource allocation and using deterministic and randomized rounding techniques. Sec- optimization problems in the networking area. In [15], the tion VI presents simulation results that evaluate the proposed authors have proposed an integer programming model to solve algorithms, and we conclude in Section VII identifying future the VPN tree computation problem for bandwidth provision- research directions. ing in VPNs. Techniques of randomized rounding for linear programming relaxations to obtain approximation algorithms ELATED W ORK II. R was first introduced in [16]. The VN assignment problem is similar to the previous In this paper, we take a formal approach to solve the online works on embedding Virtual Private Networks (VPN) in a VN embedding problem using a mixed integer programming shared provider topology and the network testbed mapping formulation. To the best of our knowledge, this is the first problem [12], [13]. However, a typical VPN request con- attempt to apply mathematical programming to this problem. sists only of bandwidth requirements, specified in terms of a traffic matrix, without any constraint on its nodes. As a ODEL AND M ETWORK ESCRIPTION D ROBLEM P III. N result, most VPN design algorithms come down to finding A. Substrate Network paths for source/destination pairs. On the other hand, the We model the substrate network as a weighted undirected algorithm [13] used in the Emulab testbed considers Assign ) ( S S S S N , where N is the set = ,E G graph and denote it by bandwidth constraints alongside constraints on exclusive use S is the set of substrate links. Each E of substrate nodes and of nodes, i.e., different VNs cannot share a substrate node. S S N is associated with the CPU capacity ∈ substrate node n But in network virtualization, there are capacity and placement ) ( ) ( S S n loc and geographic location . Each weight value c n requirements on both the virtual nodes and the virtual links; in S S e substrate link ) ( ∈ between two substrate nodes i, j E i addition, substrate nodes and links can be shared by multiple and j is associated with the bandwidth capacity weight value VNs. ) ( S denoting the total amount of bandwidth. b e In order to reduce the hardness of the VN assignment S P We denote the set of all substrate paths by , and the set problem and to enable efficient heuristics, existing research to the destination s of substrate paths from the source node has been restricting the problem space in different dimensions, S . ) s, t ( node P by t which include: Fig. 1 shows a substrate network, where the numbers over 1) considering offline version of the problem (i.e., all the the links represent available bandwidths and the numbers in VN requests are known in advance) [7], [8], 2 . rectangles represent available CPU resources 2) ignoring either node requirements or link requirements [6], [7], B. VN Request 3) assuming infinite capacity of the substrate nodes and Similar to the substrate network, we model VN requests links to obviate admission control [6]–[8], and as weighted undirected graphs and denote a VN request by ) ( 4) focusing on specific VN topologies [7]. V V V . We express the requirements on virtual = N ,E G The authors in [9] consider all these issues, except for the lo- nodes and virtual links in terms of the attributes of the nodes cation constraints on the virtual nodes, by envisioning support and links of the substrate network. Each VN request has an from the substrate network through node and link migration 2 We use notations similar to [9] to denote capacities and requirements. as well as multi-path routing. We do not restrict the problem

3 10 55 80 1) Node assignment: Each virtual node from the same VN 15 3 a c different substrate node by a mapping is assigned to a request A B 12 10 V S N N : from virtual nodes to substrate nodes such → M N d 22 V V V b c 12 N ∈ ,m , n that for all 10 50 90 a ) ( 10 10 10 S V 15 20 n N ∈ M N C D E F VN Request 1 ( ) ) ( V V V V e , m = M m n iff = M n N N 60 85 20 25 17 subject to f e 17 ( )) ( ) ( 55 H G V V R ≤ M (1a) n c n b N N f d ) ( 65 70 ) ( ( )) ( V V V ≤ D ,loc n M dis loc n (1b) 20 20 N Substrate Network VN Request 2 i, j where dis ( ) measures the distance between the location of two substrate nodes i and j . Fig. 1. Mapping of VN requests onto a shared substrate network. In Fig. 1, the first VN request has the node mapping { B } a → C, b → H, c → and the second VN request has V and b . Note that two virtual nodes } H → D, f → A, e → d { f associated non-negative value D expressing how far a virtual V V from different VN requests are mapped onto the same substrate can be placed from the location specified by ∈ N node n ) ( V V . H node . D can be expressed in terms of physical distance loc n ) ( V Each virtual link is mapped to a 2) Link assignment: . or in terms of permissible delay (e.g., RTT) from n loc substrate path (unsplittable flow) or a set of substrate paths Fig. 1 shows two VN requests with node and link constraints. (splittable flow) between the corresponding substrate nodes that host the end virtual nodes of that virtual link. It is defined C. Measurement of Substrate Network Resources V S : E from virtual links to substrate →P by a mapping M E ) ( V V V V The residual or the available capacity of a substrate node, E ∈ = m , ,n paths such that for all e ) ( S R n is defined as the available CPU capacity of the N ( ) ) ( ( ) ( ) S S V V S V V substrate node n . N ∈ M M n , m ⊆P m M ,n N N E ∑ ( ) ) ( S S V R = n n c − ) n ( c subject to N V S ) ) ( ( n ↑ ∀ n V V (2) , ∈M e P ∀ ( P ≥ b e ) R E E where x ↑ y denotes that the virtual node x is hosted on the The first VN request in Fig. 1 has been assigned the { . y substrate node ) ( S G, H ( link mapping a, c ) ( , ( a, b ) → } ) , ) D, G ( , ) C, D ( →{ e Similarly, the residual capacity of a substrate link, R E } is defined as the total amount of bandwidth available on the b, c ( , } ) A, B ( , ) C, A ( { ( , ) F, E ( , ) H, F ( →{ E, B ) } ) , and S S { substrate link e ∈ E . the second VN request has the link mapping → ) d, e ( ∑ ( ) ( ) } S V S = e − e b R e ) ( b E →{ ) e, f ( ( , G, H ) } , ) C, D } D, G { . ( A, C ) ) , ( ( V S ↑ e e ∀ E. Objectives ↑ y denotes that the substrate path of the virtual link where x Our main interest in this paper is to propose online VN . x passes through the substrate link y embedding algorithms that map multiple VN requests with The available bandwidth capacity of a substrate path P ∈ S node and link constraints. We also want to increase revenue is given by P and decrease cost of the InP in the long run, in addition to ) ( S e R P ) = min ( R balancing load of the substrate network resources. E E S P e ∈ Similar to the previous work in [8], [9], we define the revenue of a VN request as: D. VN Assignment ∑ ∑ ) ) ( ( V V V When a VN request arrives, the substrate network has to G ( R (3) + b e )= c n determine whether to accept the request or not. If the request V V V V ∈ N ∈ E e n is accepted, the substrate network then determines a suitable While revenue gives an insight into how much an InP will assignment for the VN and allocates network resources on the gain by accepting a VN request, it is not very useful without substrate nodes and paths selected by that assignment. The knowing the cost the InP will incur for embedding that request. allocated resources are released once the VN expires. V The assignment of the VN request to the substrate 3 Even though multiple virtual nodes from different VN requests can be mapped to the same substrate node. network can be decomposed into two major components:

4 An example of augmented graph construction is shown in c a B A Fig. 2. B. MIP Formulation D C F E The VN embedding problem can now be formulated as V -commodity flow problem. We con- | a mixed integer | E ( ) V V i 1 ≤ E ≤| | as a commodity sider each virtual edge e i t and , respectively with source and destination nodes s i i ) ( ′ S S Meta-edge \ N N ∈ ,t . Each flow, in this setting, starts from i, s ∀ i i G H Meta-node a meta-node and ends in another meta-node. By introducing V ) can ( restrictions on the meta-edges, each meta-node n μ Cluster be forced to choose only one meta-edge to connect itself to b V . This effectively selects a ) n Ω( an actual substrate node in substrate node for each meta-node, i.e., maps the virtual node Fig. 2. Construction of an augmented substrate graph with meta-nodes and meta-edges for a VN request. corresponding to that meta-node to a substrate node. At the same time, all the virtual edges (i.e., flows) are also mapped efficiently inside the substrate network with the help of path We define the cost of embedding a VN request as the sum of splitting. We present the MIP formulation in the following total substrate resources allocated to that VN. manner. ∑ ∑ ∑ V MIP V e V VNE C G ( n f ( (4) )= ) + c S e V S V V V S e n N E ∈ e E ∈ ∈ Variables: V e where f denotes the total amount of bandwidth allocated on S i e • f : A flow variable denoting the total amount of flow uv V S for virtual link e . We use a modified e the substrate link from i ) u, v ( on the substrate edge v ’th virtual to u for the version of (4) as the objective function of our MIP formulation. edge. : A binary variable, which has the value ’1’ if x • IV. M NTEGER IXED ORMULATION FOR P ROGRAMMING I F uv ( ) ∑ i i > f 0 ; otherwise, it is set to ’0’. + f MBEDDING O PTIMAL VN E uv vu i A. Augmented Substrate Graph Construction Objective: In order to coordinate the node mapping phase with its link mapping counterpart, the base substrate network must be ∑ ∑ α uv i minimize f augmented substrate graph using the extended to create an uv u, v δ )+ ( R E S i E ∈ uv location requirement of the virtual nodes as the basis for the ∑ ∑ V V β ∈ N has an associated constraint extension. Since each n w ) ( c x (5) + m ( ) mw V on its possible placement, we can create one cluster loc n w R )+ ( δ N ∣ ∣ ′ S S S w N ∈ N m \ ∈ N V ∣ ∣ N in total) in the substrate network for each virtual node ( V V with radius D ) and call . We denote such a cluster by Ω( n Constraints: V . Ω set of the virtual node n it the - Capacity Constraints: } { ( ) )) ( ( V V S S S V ∑ ′ Ω( n ,loc n D ≤ ∈ N loc | dis n )= n i i S f + ) ( x N ≤ , ∀ u, v ∈ ) f ( (6) u, v R E u,v vu uv i V In Fig. 2, substrate nodes E , and F are within D B , ′ S S S R ∀ w N \ ∈ N N ∈ m ∀ , ) m ( c x ≥ ) w ( (7) , mw N } , hence c Ω( c )= { B, E, F distance of the virtual node . V V ∈ N we create a corresponding meta-node For each n V V μ ) , and we connect with all the substrate nodes n ( ) ( n μ - Flow Related Constraints: V with infinite bandwidth. using ) meta-edges n Ω( belonging to ∑ ∑ ′ V i i S , ) We will sometimes write the Ω( n Ω Ω( set as m ) instead of ∈ , − ,t =0 s \{ f N } u ∀ i, ∀ (8) f i i wu uw V . We combine all the meta-nodes and ) = m ( where μ n ′ ′ S S N w w ∈ N ∈ ∑ ∑ meta-edges with the substrate graph to create the augmented i i V ′ ′ ′ f = f (9) i ∀ , ) − e ( b S S S w ws s i i i ,E N ) , where =( substrate graph G ′ ′ S S w ∈ N N ∈ w ′ ∑ ∑ V S V V S N ) | } n ( μ ∪{ n ∈ N = N i V i (10) e ( b − = i f ∀ − , f ) t i wt w i i ′ S S V V S V S V ′ ′ ) ) ,n ∪{ ( μ ( ) n ,n = N E | n n Ω( ∈ ∈ } E S S N ∈ w N ∈ w

5 - Meta and Binary Constraints: to obtain integer values for the variable x and embed VN ∑ requests. ′ S S N N ∀ \ , m (11) =1 x ∈ mw RELAX LP VNE ) w m ∈ Ω( ∑ S Objective: ∀ w ∈ N , (12) 1 x ≤ mw ∑ ∑ ′ S S α uv \ N m ∈ N i f minimize uv ′ S R )+ u, v ( δ E ( ) , N R ≤ ∀ ∈ (13) u, v u, v x S i uv E uv ∈ E ′ ∑ ∑ S β w ∀ , (14) N = ∈ u, v x x uv vu x c ( + (17) ) m mw R ( w )+ δ N ′ S S S N ∈ w N \ m ∈ N - Domain Constraints: ′ Constraints: i S f ∀ ≥ u, v ∈ N 0 (15) , uv - Capacity Constraints: ′ S ∑ , 0 ∈{ (16) N ∈ u, v ∀ , } 1 x uv ′ S i i + ∈ f ( u, v ∀ , x ) u, v ( R ≤ ) N f u,v E vu uv Remarks: i ′ S S S The objective function (5) of the MIP tries to minimize • w w x c ( m ) , ∀ m ∈ N ( R \ N ≥ , ∀ ∈ N ) mw N the cost of embedding the VN request as well as balance - Flow Related Constraints: the load. By dividing the cost with the residual capacity, it ∑ ∑ ′ i i S is ensured that the resources with more residual capacities } =0 f ,t s \{ f , ∀ − i, ∀ u N ∈ i i uw wu ′ ′ are preferred over the resources with less residual capac- S S N w ∈ ∈ N w ∑ ∑ are ) w ( ≤ R ≤ R β ≤ ( 1 and ) u, v α ≤ 1 ities. w N uv E i i V ∀ b f , ) i ( e = f − w i s ws i i parameters to control the importance of load balancing ′ ′ S S ∈ w ∈ N N w while embedding a request. is a small positive δ 0 → ∑ ∑ i i V f b ( − − ) , ∀ i = e f constant to avoid dividing by zero in computing the w i wt t i i ′ ′ S S objective function. N N ∈ w ∈ w - Meta and Relaxed Binary Constraints: • Constraint set (6) and (7) contains the node and edge ∑ i i ′ S S and f in (6) en- capacity bounds. Summing up f uv vu m N =1 x \ , ∀ N ∈ mw sures that the summation of flows on both directions of ) w Ω( ∈ m ∑ u, v ) the undirected edge ( remains within its available ′ S S u, v 1 ∀ x ∈ ≤ R ∈ ( , ) , ∀ u, v ≤ N w x N mw E uv bandwidth. ′ S S N N ∈ \ m • Constraint set (8), (9), and (10) refer to the flow con- ′ S ∈ ∀ u, v x , x = N vu uv servation conditions, which denote that the net flow to a and the sink s node is zero, except for the source node i - Domain Constraints: . t node ′ i S i ∈ N 0 ≥ , ∀ u, v f uv ′ Constraint sets (11) and (12) are related to the augmented • S ∈ x ≥ 0 , (18) u, v ∀ N uv portion of the substrate graph. Constraint set (11) makes sure that only one substrate node is selected for each Remarks: meta-node, whereas constraint set (12) ensures that no variables has • The domain constraint set (18) on the x uv more than one meta-node is placed on a substrate node. been relaxed. The rest of the constraints are similar to the ones in • Constraint sets (13) and (14) together with (2) ensure that • MIP . VNE x is set whenever there is any flow in either direction uv ( of the substrate edge ) . u, v A. Deterministic Rounding Based Virtual Network Embedding Algorithm (D-ViNE) • Finally, constraint sets (15) and (16) denote the real and i and x , binary domain constraints on the variables f D-ViNE (Fig. 3) takes online VN requests as inputs and uv uv respectively. maps them onto the substrate network one at a time. It takes decisions based only on the past VN requests that it has already V. LP R LGORITHMS ASED ELAXATION AND -B A R OUNDING seen, i.e., D-ViNE uses no look-ahead. Since the integer domain constraints (16) on the x variables have already been Since solving an MIP is known to be computationally variables. x relaxed, we no longer get integer values for the intractable [10], simultaneous node and link embedding using Instead, we employ deterministic rounding technique to get MIP is practically infeasible. Hence we relax the integer VNE S , which } →{ 0 , 1 N integer values for x . We introduce φ : constraints (16) of the MIP, and obtain the following linear S S LP signifying that all the RELAX ∈ N ). Once we have the LP solution, n is initially set to zero for all program ( VNE we use deterministic and randomized rounding techniques substrate nodes are initially unused. Whenever a virtual node

6 V V V V V V ,E =( ) ) =( N N ,E 1: ) ) D-V I G NE( NE( G I R-V procedure 1: procedure ) ) ( ( ′ ′ ′ ′ ′ ′ S S S S S S Create augmented substrate graph G ,E = G Create augmented substrate graph = 2: ,E N 2: N LP RELAX 3: Solve VNE LP RELAX 3: Solve VNE S S S S 4: 4: n for all do for all n N ∈ N ∈ do S S n ) ← 0 5: ( n 5: φ ( 0 φ ) ← 6: 6: end for end for V V N n do for all N ∈ ∈ n for all 7: 7: do S S S S S S then | 8: n if φ N n ∈ )=1 n ∩{ } if ) Ω( = ( n ) ∩{ n 8: ∈ N ∅ | φ ( n Ω( )=1 then ∅ = } 9: 9: VN request cannot be satisfied VN request cannot be satisfied return 10: return 10: end if 11: end if 11: do ) for all z do 12: n Ω( ∈ z for all 12: ∈ Ω( n ) ∑ ∑ i i i i ( 13: 13: p f + ) x f + f x f ) p ( ← ← z z ( n ) z μ μ ( z ) n i i ) z zμ μ ( ( n ) μ ( n ) n ( zμ z ) n 14: end for 14: end for ∑ ( z )=0 } 15: ← Let p 15: z p { p = arg max | φ sum z max z ) n Ω( ∈ z ∈ n ) z Ω( set ( n ) ← z M 16: ∈ Ω( 16: do ) n z for all N max φ z ) ← 1 17: ( /p 17: ← p p max z sum z 18: end for 18: end for Solve MCF to map virtual edges. 19: ) ← 19: n z with probability set M p ( z N Update residual capacities of the network resources. 20: z φ ) 20: ← 1 with probability p ( z end procedure 21: 21: end for solve MCF to map virtual edges. 22: Fig. 3. D-ViNE: Deterministic rounding based Virtual Network Embedding 23: Update residual capacities of the network resources. algorithm 24: end procedure Fig. 4. R-ViNE: Randomized rounding based Virtual Network Embedding S S algorithm φ ) ( n to is mapped to a particular physical node n ,weset 1 to ensure that no substrate node is used twice for the same VN request. 1) Description and Discussion: The procedure begins by values are f the relaxed linear program, it is possible that the ) ( ′ ′ ′ S S S x very high and the corresponding values are very low or vice = N ,E creating an augmented substrate graph, G ) ( V V V and x values thwarts the possibility f versa. Multiplying the for the VN request G using the augmen- ,E N = value but very x of selecting a substrate node based on high tation method described in Section IV-A. Next it solves low value on its corresponding meta-edge and vice versa. f VNE to get a fractional solution which is at least LP RELAX The ones that have better values for both the variables and f . For each virtual MIP as good as the integer solution of VNE are more likely to be in the solution of the MIP than others. x node, D-ViNE first checks whether there are any unmapped D-ViNE maps the virtual node onto the unmapped substrate n substrate nodes within its feasible region (the substrate nodes value, breaking node )=0 ) with the highest p ( (i.e., z φ z z in the virtual nodes Ω set is Ω set). If the corresponding ties arbitrarily. empty, D-ViNE stops the embedding process immediately and Once all the virtual nodes have been mapped to different rejects the VN request. Otherwise the deterministic rounding substrate nodes, D-ViNE applies the multi-commodity flow procedure is initiated in line 12. V onto the substrate E algorithm to map the virtual edges in for n , D-ViNE calculates a value p For each virtual node z paths. One can also use shortest path algorithms when path is calculated z ∈ Ω( each substrate node n p in its cluster. ) z splitting is not supported by the substrate network. Finally, and the total flow passing as the product of the value x n ( μ z ) D-ViNE updates the residual capacities of the substrate nodes z μ n ( through the meta-edge in both directions. The reason ) and links to prepare for the next request. is as x behind using this multiplication instead of just ) n ( μ z 2) Time Complexity: An important aspect of D-ViNE is that is set to binary values x follows. In the MIP solution uv the multi-commodity flow algorithm is executed twice; first, based on the presence of flows in either direction in the RELAX LP VNE during the node mapping phase (since . When the binary constraint is relaxed, one edge ( u, v ) x would also be is a linear programming relaxation of the original mixed might expect that the fractional values of x uv proportional to the total flow in the edge ( u, v ) . But during integer multi-commodity flow problem), and second, during the LP relaxation process, the correlation between the flow the edge mapping phase. Since the multi-commodity flow and the binary variable x f variable is lost. It is because a algorithm can be solved in polynomial-time using either the linear program tries to optimize the objective function without ellipsoid algorithm or Karmarkar’s interior point algorithm for violating the constraints; it does not care about the values as linear programming [10]; hence, D-ViNE is a polynomial time long as they are within their permitted domains. As a result, in algorithm.

7 B. Randomized Rounding Based Virtual Network Embedding TABLE I Algorithm (R-ViNE) C OMPARED A LGORITHMS R-ViNE (Fig. 4) is quite similar to D-ViNE except that it Notation Algorithm Description uses randomized rounding instead of deterministic rounding. values are calculated as in D-ViNE, R-ViNE p Once the D-ViNE Deterministic Node Mapping with Splittable z Link Mapping using MCF normalizes those values within 0 to 1 range. The normalized values for each correspond to the probabilities of n ) ∈ z Ω( R-ViNE Randomized Node Mapping with Splittable Link Mapping using MCF by the optimal MIP. R-ViNE selects n z being mapped to Greedy Node Mapping with Shortest Path Based G-SP [8] ) z to map a virtual node a substrate node Ω( n n with ∈ Link Mapping . The remainder of this algorithm is similar to p probability z G-MCF [9] Greedy Node Mapping with Splittable Link its deterministic counterpart, and it is clear that this algorithm Mapping using MCF also runs in polynomial-time. D-ViNE-SP Deterministic Node Mapping with Shortest Path E ERFORMANCE VALUATION VI. P Based Link Mapping Deterministic Node Mapping with Splittable D-ViNE-LB In this section, we first describe the evaluation environment, Link Mapping using MCF, where α = = β w uv and then present our main evaluation results. Our evaluation S , ∀ u, v, w ∈ 1 N focuses primarily on quantifying the advantage of coordinating node mapping and link mapping phases in terms of acceptance ratio, revenue and cost. We also compare D-ViNE and R-ViNE with existing algorithms modified to fit into our model. 0.85 D-ViNE G-SP A. Simulation Settings D-ViNE-SP G-MCF 0.8 D-ViNE-LB We have implemented a discrete event simulator to evaluate R-ViNE the performance of our algorithms which is freely available 0.75 at [17]. The substrate network topologies in our experiments are randomly generated with 50 nodes using the GT-ITM 0.7 grids. Each pair of substrate nodes 25) × (25 tool [18] in 5 . 0 is randomly connected with probability . The cpu and 0.65 bandwidth resources of the substrate nodes and links are VN Request Acceptance Ratio real numbers uniformly distributed between 50 100 .We and 0.6 assume that VN requests arrive in a Poisson process with an VNs per 100 time units, and each one has an 4 average rate of = 1000 μ exponentially distributed lifetime with an average of 0.55 50000 40000 30000 20000 10000 0 time units. In each VN request, the number of virtual nodes Time is randomly determined by a uniform distribution between 2 Fig. 5. VN request acceptance ratio over time and 10 following similar setups to previous works [8], [9]. The average VN connectivity is fixed at 50% . The cpu requirements of the virtual nodes are real numbers uniformly distributed 0 and the bandwidth requirements of the virtual 20 to between 4 D-ViNE to 0 .Wehaveused links are uniformly distributed between 50 G-SP D-ViNE-SP the open source mixed integer programming library glpk [19] G-MCF D-ViNE-LB 3.5 . LP RELAX to solve VNE R-ViNE B. Comparison Method 3 In our evaluation, we have compared six algorithms that combine different node mapping and link mapping strategies including our contributions and algorithms from previous 2.5 Average Revenue research [8], [9] modified to fit into our model (i.e., no reconfiguration). The notations that we use to refer to different 2 algorithms are enumerated in Table I. C. Evaluation Results 1.5 30000 10000 20000 0 40000 50000 We use several performance metrics for evaluation purposes Time in our experiments. We measure the average acceptance ratio, Fig. 6. Time average of generated revenue ) for VN requests over revenue ( R ), and provisioning cost ( C time. We also measure the average node utilization and average

8 link utilization of the substrate network. In all these cases we 240 plot the performance metrics against time to show how each D-ViNE G-SP of these algorithms (Table I) actually perform in the long run. D-ViNE-SP G-MCF We summarize our key observations in the following. D-ViNE-LB 220 R-ViNE (1) Coordinated node and link mapping leads to higher acceptance ratio and larger revenue. Fig. 5 and Fig. 6 depict 200 that the proposed algorithms, D-ViNE and R-ViNE, lead to better acceptance ratio as well as higher revenue than the Average Cost 180 existing algorithms (G-SP and G-MCF) through coordinated node and link mapping. Having higher revenue along with better acceptance ratio implies that our proposed algorithms 160 actually embed VN requests that generate more revenue, instead of embedding smaller VN requests just to increase 140 the acceptance ratio. 0 10000 20000 30000 40000 50000 Time (2) Load balancing further increases the acceptance ratio and the revenue. From Fig. 5 and Fig. 6, it is evident that Fig. 7. Average cost of accepting VN requests over time D-ViNE-LB generates more revenue and accepts more VN requests than the basic D-ViNE algorithm. In D-ViNE-LB, RELAX LP the value of the objective function (17) of VNE 0.25 depends on the residual capacity of the network resources in 1 values are set to β and α addition to the provisioning cost ( here). The lower the residual capacity of a particular node or 0.2 link, the higher the value of the objective function. As a result, D-ViNE-LB tries to avoid highly utilized nodes and links as 0.15 long as it can, leaving those critical resources available for the VN requests that absolutely need them. 0.1 (3) Randomization can lead to better performance. It Node Utilization is well established in the algorithm design literature that randomization allows efficient solutions to many intractable D-ViNE 0.05 G-SP problems in polynomial time with low probability of error. D-ViNE-SP G-MCF D-ViNE-LB Our experiments show that the randomized version of our R-ViNE 0 VN embedding algorithm (R-ViNE) performs better than its 50000 0 20000 10000 30000 40000 deterministic counterpart (D-ViNE) in terms of acceptance Time ratio and revenue generation (Fig. 5 and Fig. 6). Fig. 8. Average node utilization In addition to that, for networks with large numbers of nodes randomization has been shown to be effective for load balancing [20]. This phenomena is also visible in our experiments, since R-ViNE performs similar to D-ViNE-LB in most scenarios. 0.45 (4) Load balancing slightly increases the average pro- 0.4 While load balancing increases revenue and visioning cost. 0.35 acceptance ratio by avoiding highly utilized resources, it runs 0.3 the risk of increasing the average provisioning cost as shown 0.25 in Fig 7. Since D-ViNE-LB tries to avoid highly utilized resources, sometimes it ends up suggesting a longer path to 0.2 Link Utilization map a particular virtual edge which eventually sums up to 0.15 slightly higher average provisioning cost in the long run. D-ViNE 0.1 G-SP Fig. 8 and (5) Coordination increases resource utilization. D-ViNE-SP G-MCF 0.05 Fig. 9 depict the average utilization of substrate nodes and D-ViNE-LB R-ViNE substrate links for different VN embedding algorithms. Since 0 10000 20000 30000 0 50000 40000 D-ViNE-LB has the highest acceptance ratio, it also has the Time highest node and link utilization. Fig. 9. Average link utilization However, D-ViNE-LB achieves a relatively higher gain in link utilization over its counterparts than in node utilization.

9 We believe that the reason behind this is the distributive nature EFERENCES R of D-ViNE-LB algorithm. In order to avoid links with lower [1] T. Anderson, L. Peterson, S. Shenker, and J. Turner, “Overcoming the Internet impasse through virtualization,” Computer , vol. 38, no. 4, pp. residual capacities, i.e., in order to minimize (5), D-ViNE-LB 34–41, 2005. uses longer paths containing more substrate links with higher [2] J. Turner and D. Taylor, “Diversifying the Internet,” in IEEE GLOBE- residual capacities to embed virtual links. , vol. 2, 2005. COM [3] A. Bavier, N. Feamster, M. Huang, L. Peterson, and J. Rexford, “In ONCLUSION VII. C VINI veritas: Realistic and controlled network experimentation,” in , 2006, pp. 3–14. Proceedings of SIGCOMM To make network virtualization an integral part of the future [4] N. Feamster, L. Gao, and J. Rexford, “How to lease the Internet in Internet architecture, efficient and practical algorithms for VN your spare time,” ACM SIGCOMM Computer Communication Review , vol. 37, no. 1, pp. 61–64, 2007. embedding are specially required. In this paper, we proposed [5] D. Andersen, “Theoretical approaches to node assignment,” Unpub- algorithms for VN embedding that differ from the previous ∼ lished Manuscript, http://www.cs.cmu.edu/ dga/papers/andersen-assign. algorithms by introducing coordination between node and link ps, 2002. [6] J. Fan and M. Ammar, “Dynamic topology configuration in service mapping phases. We argued that this coordination greatly Proceedings overlay networks - a study of reconfiguration policies,” in increases the solution space and the quality of the heuristic of IEEE INFOCOM , 2006. algorithms. To this end we first formulated the embedding [7] J. Lu and J. Turner, “Efficient mapping of virtual networks onto a shared substrate,” Washington University, Tech. Rep. WUCSE-2006-35, 2006. problem as a mixed integer program. We then relaxed the [8] Y. Zhu and M. Ammar, “Algorithms for assigning substrate network integer constraints and used deterministic and randomized Proceedings of IEEE resources to virtual network components,” in rounding techniques to obtain polynomial-time solvable algo- , 2006. INFOCOM [9] M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking virtual network rithms for node mapping. The node mapping phase combined embedding: Substrate support for path splitting and migration,” ACM with the multi-commodity flow based link mapping phase in , vol. 38, no. 2, pp. 17– SIGCOMM Computer Communication Review our algorithms outperformed the existing approaches in terms 29, April 2008. Theory of linear and integer programming [10] A. Schrijver, .NewYork, of acceptance ratio, revenue, and provisioning cost, as shown NY, USA: John Wiley & Sons, Inc., 1986. through simulation. [11] W. Szeto, Y. Iraqi, and R. Boutaba, “A multi-commodity flow based However, there are a number of issues that remain unre- Proceedings of the approach to virtual network resource allocation,” in , 2003, IEEE Global Telecommunications Conference (GLOBECOM’03) solved in this work and can be good starting points for further pp. 3004–3008. research in this direction. First and foremost is the analysis of [12] A. Gupta, J. M. Kleinberg, A. Kumar, R. Rastogi, and B. Yener, theoretical approximation factors of the proposed algorithms “Provisioning a virtual private network: A network design problem for Proceedings of ACM STOC , 2001, pp. 389– multicommodity flow,” in in the worst case. To this end, we are currently working on 398. developing a primal-dual based analysis framework to obtain [13] R. Ricci, C. Alfeld, and J. Lepreau, “A solver for the network testbed good lower bounds on the performance of D-ViNE and R- ACM SIGCOMM Computer Communication Review mapping problem,” , vol. 33, no. 2, pp. 65–81, April 2003. ViNE. Finding out advanced economic models, instead of [14] I. Houidi, W. Louati, and D. Zeghlache, “A distributed virtual network the simple revenue model used in the existing literature, for , 2008, pp. 5634–5640. Proceedings of IEEE ICC mapping algorithm,” in VN pricing is another important research topic that needs [15] A. Kumar, R. Rastogi, A. Silberschatz, and B. Yener, “Algorithms for IEEE/ACM provisioning virtual private networks in the hose model,” further attention. Finally, available approaches to directly solve Transactions on Networking , vol. 10, no. 4, pp. 565–578, 2002. integer and mixed integer programs (e.g., column generation) [16] P. Raghavan and C. D. Tompson, “Randomized rounding: a technique can be employed to develop efficient algorithms to obtain , Combinatorica for provably good algorithms and algorithmic proofs,” vol. 7, no. 4, pp. 365–374, 1987. optimal or near-optimal solutions for the original mixed integer [17] “ViNE-Yard,” http://www.mosharaf.com/ViNE-Yard.tar.gz. ) without any relaxation. MIP formulation ( VNE [18] E. Zegura, K. Calvert, and S. Bhattacharjee, “How to model an Inter- Proceedings of IEEE INFOCOM network,” in , 1996, pp. 594–602. A CKNOWLEDGMENT [19] “GNU Linear Programming Kit,” http://www.gnu.org/software/glpk/. [20] M. Mitzenmacher, A. W. Richa, and R. Sitaraman, “The power of two This research was partially supported by the Natural Science random choices: A survey of techniques and results,” in Handbook of and Engineering Council of Canada (NSERC) and partially by Randomized Computing . Kluwer Academic Press, 2001, pp. 255–312. WCU (World Class University) program through the Korea Science and Engineering Foundation funded by the Ministry of Education, Science and Technology (Project No. R31-2008- 000-10100-0).

If you drink no Noir, you Pinot Noir Volume 11, Issue 43 May 4, 2019 An Historical Perspective of the Winery Mailing List , I was writing about the history of Williams Selyem Winery and stated, “The P...

More info »H-1 Corridor Study Project No. CMAQ-0300 (129) ā hala Kapolei to Wai'alae/K O'ahu, Hawai'i Final Report Produced for: State of Hawai'i Department of Transportation Highways Division August 2016

More info »U.S. DEPARTMENT OF TRANSPORTATION ORDER FEDERAL AVIATION ADMINISTRATION 7400.11C JO Air Traffic Organization Policy August 13, 2018 SUBJ: Airspace Designations and Reporting Points . This O rder, publ...

More info »Spain Denominación de Origen (DO) and Denominación de Origen Calificada (DOCa) are the two highest categories of quality wine, equivalent to the EU’s Protected Designation of Origin (DOP) status. DO P...

More info »What’s Shakin’ in the Valley! March 2019 March 1, 2019 – Looking to unwind on Friday night? Enjoy dinner and music from James Vincent James Vincent Carroll plays classic rock hits from the 70's-90's o...

More info »Idaho Big Game 2019 & 2020 Seasons & Rules Edition 2019 1st Controlled Hunt Application Periods Deer, Elk, Pronghorn & Fall Black Bear: May 1 - June 5 Spring Black Bear: January 15 - February 15 Deer,...

More info »ORTH N A MERICAN I NDUSTRY LASSIFICATION C YSTEM S United States, 2017 EXECUTIVE OFFICE OF THE PRESIDENT AND BUDGET OFFICE OF MANAGEMENT

More info »Journal of Wine Economics , Volume 11, Number 3, 2016, Pages 329 – 354 doi:10.1017/jwe.2016.14 Does Organic Wine Taste Better? An Analysis of Experts ’ * Ratings b a c , Olivier Gergaud and Jinghui Li...

More info »Managing California’s Water From Conict to Reconciliation Ariel Dinar Ellen Hanak Jay Lund Richard Howitt Jerey Mount Brian Gray Peter Moyle Barton “Buzz” Thompson

More info »For the Term of His Natural Life Marcus Clarke This eBook was designed and published by Planet PDF. For more free . To hear eBooks visit our Web site at http://www.planetpdf.com/ about our latest rele...

More info »Wheaton Facility Aabybro Facility Springeld Facility P.O. Box 7900 Mølhavevej 2 1801 Business Park Drive Wheaton, Illinois DK 9440 Aabybro Springeld, Illinois 60187-7901 USA Denmark 62703 USA www.te...

More info »______________________________________________________________________ IBLIOTHECA B 153 (January–March 1996): 34-52 S ACRA J 15:1-6 ITICULTURE AND V OHN Gary W. Derickson ew Bible students today can p...

More info »injustice on our plates Immigrant Women in the U.S. Food Industry

More info »ELIZABETH A. NEVILLE Town Hall, 53095 Main Road TOWN CLERK PO Box 1179 Southold, NY 11971 VITAL STATISTICS Fax (631) 765-6145 REGISTRAR OF MARRIAGE OFFICER Telephone: (631) 765 - 1800 OFFICER RECORDS ...

More info »Current Registered Egg Handler (Rev. 04/30/2019) Name City State ZIP Cert No. In-State: 1,117 Oroville CA 12 Oaks Ranch CA-0397 95966 CA CA-0132 92883 3 Red Hart's Grove Corona 95404 CA Santa Rosa CA-...

More info »SUMMER 2015 PHOTO BY ERIC RAYMOND COMMUNITY UPDATE: OLD MISSION PENINSULA Dear Friends, We have something in common. We both love the Old Mission Peninsula and we share a deep understanding of its sig...

More info »FINAL Little Pond Embayment System Total Maximum Daily Loads For Total Nitrogen (Report # 96-TMDL-8 Control #246) COMMONWEALTH OF MASSACHUSETTS EXECUTIVE OFFICE OF ENERGY AND ENVIRONMENTAL AFFAIRS IAN...

More info »away UFWOC Larry Itliong is led Director to jail after Safeway Officials Assistant ordered his arrest in Oakland. See story~ page 5. Photo by Jon Lewis. MARCH TO THE BORDER··see p.2·3 STRIKE IN COACHE...

More info »CIRCULAR U.S. Department of Transportation FTA C 4710.1 Federal Transit Administration November 4, 2015 AMERICANS WITH DISABILITIES ACT (ADA): GUIDANCE Subject: PURPOSE. This circular provides guidanc...

More info »