计算机科学与技术（参考文献）An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks

2012 Proceedings IEEE INFOCOM An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks Sheng Zhang',Zhuzhong Qian',Jie Wu,and Sanglu Lu' State Key Lab.for Novel Software Technology,Nanjing University,China Department of Computer and Information Sciences,Temple University,USA zhangsheng @dislab.nju.edu.cn,(qzz,sanglu)@nju.edu.cn,jiewu@temple.edu Abstract-Network virtualization provides a promising way resources are utilized in an efficient and effective manner.As to overcome Internet ossification.A major challenge is virtual this problem is proven to be NP-complete [5],many heuristic network mapping,i.e,how to embed multiple virtual network algorithms [6-15]have been proposed. requests with resource constraints into a substrate network,such that physical resources are utilized in an efficient and effective However,these early algorithms did not take workload manner.Since this problem is known to be NP-complete,a variety fluctuation,e.g.,Auckland Data Trace [16],into consideration. of heuristic algorithms have been proposed.In this paper,we re- Most web-based service providers potentially target users all examine this problem and propose a virtual network mapping over the world,so it is extremely difficult to predict the framework,ORSTA,which is based on Opportunistic Resource workload before they are ready to serve end users.To cope Sharing and Topology-Aware node ranking.Opportunistic re- source sharing is taken into consideration at the entire network with a peak workload on demand,service providers often over- level for the first time and we develop an online approxima- purchase physical resources,which may lead to a considerable tion algorithm,FFA,for solving the corresponding time slot waste of resources for a normal workload.What is more assignment problem.To measure the topology importance of infrastructure providers may lose some upcoming customers a substrate node,a node ranking method,MCRank,based on due to inefficient resource utilization Markov chain is presented.We also devise a simple and practical method to estimate the residual resource of a substrate node/link. In this paper,we re-examine the virtual network mapping Extensive simulation experiments demonstrate that the proposed problem through two novel aspects,Opportunistic Resource framework enables the substrate network to achieve efficient Sharing and Topology-Aware node ranking,and we propose a physical resource utilization and to accept many more virtual novel framework,ORSTA,which provides efficient physical network requests over time. resource utilization and deployment. Index Terms-virtual network mapping;opportunistic re- source sharing;bin packing;topology-aware;markov chain Inspired by opportunistic spectrum access [17],we envision opportunistic resource sharing.Generally speaking,we model the workload in a virtual network as the combination of a I.INTRODUCTION basic sub-workload,which always exists,and a variable sub- The Internet has been extremely successful in optimizing workload,which occurs with some probability.Then,multiple the way we exchange and process information.However,due variable sub-workloads from different virtual networks are to the competing policies and interests of its stakeholders allowed to share some common resources to achieve efficient and the ever-expanding scale of Internet use,the Internet resource utilization,while for a basic sub-workload,we allo- has become resistant to fundamental changes [1,2].Network cate the corresponding,required resources as usual. virtualization has been proposed as a promising approach that Furthermore,topology-awareness is considered due to the claims to overcome the current ossification of the Internet following fact:suppose that there are two substrate nodes with [1-4].In a network virtualization environment,infrastructure the same residual CPU resources,but the residual resources providers (InPs)maintain physical/substrate networks (SNs). on their neighbors vary a lot.It is then reasonable to choose while service providers (SPs)purchase slices of physical the substrate node with more resources in its proximity,so as resources (e.g.,CPU,bandwidth,memory space,disk storage) to heuristically reduce the length of embedded virtual links. from InPs and then create customized virtual networks (VNs)Hence,to facilitate the efficient embedding of virtual networks to offer their own value-added services to end users.This we develop a Markov Chain-based substrate node ranking decoupling of traditional Internet service providers brings a algorithm to measure the "importance"of each substrate node layered service architecture,which provides flexibility and by assigning a numerical value. diversity to everyone. The contributions of this paper are the following.(i)To the One of the fundamental problems in network virtualization best of our knowledge,this is the first attempt that consid- is the virtual network embedding/mapping (VNE)problem, ers virtual network mapping in the context of opportunistic i.e.,how to embed multiple virtual network requests with re- resource sharing at the entire network level.In our previous source constraints into a substrate network,such that physical work [18],we only considered how to share bandwidth among 978-1-4673-0775-8/12/$31.00©20121EEE 2408

An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks Sheng Zhang† , Zhuzhong Qian† , Jie Wu‡ , and Sanglu Lu† † State Key Lab. for Novel Software Technology, Nanjing University, China ‡ Department of Computer and Information Sciences, Temple University, USA † zhangsheng@dislab.nju.edu.cn, {qzz,sanglu}@nju.edu.cn, ‡ jiewu@temple.edu Abstract—Network virtualization provides a promising way to overcome Internet ossification. A major challenge is virtual network mapping, i.e., how to embed multiple virtual network requests with resource constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. Since this problem is known to be NP-complete, a variety of heuristic algorithms have been proposed. In this paper, we re￾examine this problem and propose a virtual network mapping framework, ORS T A, which is based on Opportunistic Resource Sharing and Topology-Aware node ranking. Opportunistic re￾source sharing is taken into consideration at the entire network level for the first time and we develop an online approxima￾tion algorithm, FFA, for solving the corresponding time slot assignment problem. To measure the topology importance of a substrate node, a node ranking method, MCRank, based on Markov chain is presented. We also devise a simple and practical method to estimate the residual resource of a substrate node/link. Extensive simulation experiments demonstrate that the proposed framework enables the substrate network to achieve efficient physical resource utilization and to accept many more virtual network requests over time. Index Terms—virtual network mapping; opportunistic re￾source sharing; bin packing; topology-aware; markov chain I. Introduction The Internet has been extremely successful in optimizing the way we exchange and process information. However, due to the competing policies and interests of its stakeholders and the ever-expanding scale of Internet use, the Internet has become resistant to fundamental changes [1, 2]. Network virtualization has been proposed as a promising approach that claims to overcome the current ossification of the Internet [1–4]. In a network virtualization environment, infrastructure providers (InPs) maintain physical/substrate networks (SNs), while service providers (SPs) purchase slices of physical resources (e.g., CPU, bandwidth, memory space, disk storage) from InPs and then create customized virtual networks (VNs) to offer their own value-added services to end users. This decoupling of traditional Internet service providers brings a layered service architecture, which provides flexibility and diversity to everyone. One of the fundamental problems in network virtualization is the virtual network embedding/mapping (VNE) problem, i.e., how to embed multiple virtual network requests with re￾source constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. As this problem is proven to be NP-complete [5], many heuristic algorithms [6–15] have been proposed. However, these early algorithms did not take workload fluctuation, e.g., Auckland Data Trace [16], into consideration. Most web-based service providers potentially target users all over the world, so it is extremely difficult to predict the workload before they are ready to serve end users. To cope with a peak workload on demand, service providers often over￾purchase physical resources, which may lead to a considerable waste of resources for a normal workload. What is more, infrastructure providers may lose some upcoming customers due to inefficient resource utilization. In this paper, we re-examine the virtual network mapping problem through two novel aspects, Opportunistic Resource Sharing and Topology-Aware node ranking, and we propose a novel framework, ORS T A, which provides efficient physical resource utilization and deployment. Inspired by opportunistic spectrum access [17], we envision opportunistic resource sharing. Generally speaking, we model the workload in a virtual network as the combination of a basic sub-workload, which always exists, and a variable sub￾workload, which occurs with some probability. Then, multiple variable sub-workloads from different virtual networks are allowed to share some common resources to achieve efficient resource utilization, while for a basic sub-workload, we allo￾cate the corresponding, required resources as usual. Furthermore, topology-awareness is considered due to the following fact: suppose that there are two substrate nodes with the same residual CPU resources, but the residual resources on their neighbors vary a lot. It is then reasonable to choose the substrate node with more resources in its proximity, so as to heuristically reduce the length of embedded virtual links. Hence, to facilitate the efficient embedding of virtual networks, we develop a Markov Chain-based substrate node ranking algorithm to measure the “importance” of each substrate node by assigning a numerical value. The contributions of this paper are the following. (i) To the best of our knowledge, this is the first attempt that consid￾ers virtual network mapping in the context of opportunistic resource sharing at the entire network level. In our previous work [18], we only considered how to share bandwidth among 2012 Proceedings IEEE INFOCOM 978-1-4673-0775-8/12/$31.00 ©2012 IEEE 2408

multiple virtual links in a single substrate link.(ii)We propose In general,although opportunistic resource sharing brings a formal formulation of opportunistic resource sharing-based performance degradation when virtual networks encounter time slot assignment and develop an online approximation a peak workload,it enables better utilization of physical solution,FFA.(iii)We take topology into consideration and resources,increases the InPs'revenue and decreases the SPs' design a Markov chain-based node ranking method,MCRank, rent.We believe that opportunistic resource sharing can benefit to measure the "importance"of a substrate node.(iv)A simple all parties through reasonable pricing.We will not discuss how and practical method for estimating the residual resource of to set prices in this paper as it is out of the scope. a substrate node/link is devised.(v)Extensive simulations validate the effectiveness of ORS TA. III.PROBLEM FORMULATION The remainder of this paper is organized as follows.Sec- A.Assumptions tion II presents our motivation.We describe the assumptions, CPU and bandwidth are the main constraints we consider notations,and problem formulation in Section III.Then in in this paper,which is the typical case in almost all of the Sections IV and V,we give an overview of ORSTA and related literatures [6-15]on virtual network mapping so far. detailed algorithms,respectively.We evaluate ORSTA using To unify the resource notations,we assume that the substrate experiments in Section VI.Before concluding this paper in network is based on time division multiplexing,where time Section VIII,we survey related work in Section VII. is partitioned into multiple frames of equal length,and each II.MOTIVATION frame is further divided into L equal time slots,tsi,ts2.....tsL. In this way,both CPU and bandwidth can be expressed in SPs lease physical resources from InPs to create their own time slots.An SP only needs to specify the number of the virtual networks and deploy services aimed at end users.As time slots for a particular virtual node/link when he makes a we mentioned before,SPs over-purchase resources to cater request for virtual network mapping.Therefore,we will only for potentially high workload rates,otherwise,customers will focus on opportunistic bandwidth sharing in Section V-A;the suffer bad experiences when SPs purchase no more than basic results can be directly applied to opportunistic CPU sharing resources.In doing so,SPs may waste the additional purchased without any major changes. resources due to traffic fluctuation.From the perspective of an SPs deploy end-to-end value-added services aimed at the InP,the physical resources he owns are limited and constant end users,who access the services and leave at any time. in a relatively long period,so he may wish to make efficient These dynamic customers lead to workload fluctuations and use of his resources and accept more virtual networks,which further cause a waste of physical resources.As it is difficult allows for more revenue. to capture the characteristics of workload fluctuation,we use A motivational example is illustrated as follows.Suppose a simplified model:the work load wli of virtual network i that an infrastructure provider,InP-A,owns a physical link is composed of a basic sub-workload basici,which exists with a capacity of 10MB/s,and all of the other service all of the time,and a variable sub-workload variai,which providers,SP-1,SP-2 and SP-3,require a virtual link with occurs with a small probability pwli in unit time.We let a capacity of 4MB/s.We assume that InP-A charges I dollar bwl;=basici/wl;represent basic sub-workload percentage. for 1MB/s bandwidth in unit time.In the case without oppor- Workloads in different virtual networks are assumed to be tunistic resource sharing,InP-A can accept only two requests independent of each other. among three because 4MB/s *3 12MB/s 10MB/s. We believe that this model is reasonable although it is Therefore,InP-A gets 8 dollars per unit time in this case. simple.For example,in a layered video streaming service Let us take network traffic fluctuation into consideration and [19],each video frame is encoded into multiple video packets assume that each 4MB/s traffic flow is composed of a basic corresponding to multiple quality layers.These video packets sub-flow 3MB/s,which always exists,and a variable sub-flow are classified as a base or enhancement layer to meet different 1MB/s,which occurs with probability 0.1.Now,InP-A has an network conditions.The workload in this scenario is very allocation method to accept all three virtual links:by letting similar to our model.We hope that this simplified model can three variable sub-flows share the same 1MB/s and allocating provide some insights on the design of other VNE algorithms. the residual 9MB/s to three basic sub-flows.We assume that Since both the network traffic and CPU time will fluctuate flows in different virtual links are independent of each other, as the workload fluctuates,both the amounts of network flow which is reasonable,thus the probability that more than two in a virtual link and the CPU time in a virtual node are variable sub-flows occur (a collision)is: assumed to be proportional to the workload for simplicity. 1-(0.9*0.9*0.9+3*0.9*0.9*0.1)=0.109 More specifically,the flow in a virtual link is composed of a basic part,whose percentage is bwli,and a variable part, For variable sub-flows,InP-A should decrease the charge,e.g., which occurs with probability pwli.And the same statement 0.1 US dollar for 1MB/s in unit time.Therefore,in this case holds for the CPU time. with opportunistic resource sharing,InP-A can get (3+0.1)* 3=9.3 dollars,which is more than the original income;SP-1 B.Notations or SP-2 or SP-3 just needs to pay 3+0.1=3.1 dollars,which Substrate Network:a substrate network is modeled as a is less than the previous charge of 4 dollars. weighted undirected graph,Gs =(Ns,Es,Cs,B),where Ns 2409

multiple virtual links in a single substrate link. (ii) We propose a formal formulation of opportunistic resource sharing-based time slot assignment and develop an online approximation solution, FFA. (iii) We take topology into consideration and design a Markov chain-based node ranking method, MCRank, to measure the “importance” of a substrate node. (iv) A simple and practical method for estimating the residual resource of a substrate node/link is devised. (v) Extensive simulations validate the effectiveness of ORS T A. The remainder of this paper is organized as follows. Sec￾tion II presents our motivation. We describe the assumptions, notations, and problem formulation in Section III. Then in Sections IV and V, we give an overview of ORS T A and detailed algorithms, respectively. We evaluate ORS T A using experiments in Section VI. Before concluding this paper in Section VIII, we survey related work in Section VII. II. Motivation SPs lease physical resources from InPs to create their own virtual networks and deploy services aimed at end users. As we mentioned before, SPs over-purchase resources to cater for potentially high workload rates, otherwise, customers will suffer bad experiences when SPs purchase no more than basic resources. In doing so, SPs may waste the additional purchased resources due to traffic fluctuation. From the perspective of an InP, the physical resources he owns are limited and constant in a relatively long period, so he may wish to make efficient use of his resources and accept more virtual networks, which allows for more revenue. A motivational example is illustrated as follows. Suppose that an infrastructure provider, InP-A, owns a physical link with a capacity of 10MB/s, and all of the other service providers, SP-1, SP-2 and SP-3, require a virtual link with a capacity of 4MB/s. We assume that InP-A charges 1 dollar for 1MB/s bandwidth in unit time. In the case without oppor￾tunistic resource sharing, InP-A can accept only two requests among three because 4MB/s ∗ 3 = 12MB/s > 10MB/s. Therefore, InP-A gets 8 dollars per unit time in this case. Let us take network traffic fluctuation into consideration and assume that each 4MB/s traffic flow is composed of a basic sub-flow 3MB/s, which always exists, and a variable sub-flow 1MB/s, which occurs with probability 0.1. Now, InP-A has an allocation method to accept all three virtual links: by letting three variable sub-flows share the same 1MB/s and allocating the residual 9MB/s to three basic sub-flows. We assume that flows in different virtual links are independent of each other, which is reasonable, thus the probability that more than two variable sub-flows occur (a collision) is: 1 − (0.9 ∗ 0.9 ∗ 0.9 + 3 ∗ 0.9 ∗ 0.9 ∗ 0.1) = 0.109 For variable sub-flows, InP-A should decrease the charge, e.g., 0.1 US dollar for 1MB/s in unit time. Therefore, in this case with opportunistic resource sharing, InP-A can get (3 + 0.1) ∗ 3 = 9.3 dollars, which is more than the original income; SP-1 or SP-2 or SP-3 just needs to pay 3+0.1=3.1 dollars, which is less than the previous charge of 4 dollars. In general, although opportunistic resource sharing brings performance degradation when virtual networks encounter a peak workload, it enables better utilization of physical resources, increases the InPs’ revenue and decreases the SPs’ rent. We believe that opportunistic resource sharing can benefit all parties through reasonable pricing. We will not discuss how to set prices in this paper as it is out of the scope. III. Problem Formulation A. Assumptions CPU and bandwidth are the main constraints we consider in this paper, which is the typical case in almost all of the related literatures [6–15] on virtual network mapping so far. To unify the resource notations, we assume that the substrate network is based on time division multiplexing, where time is partitioned into multiple frames of equal length, and each frame is further divided into L equal time slots, ts1, ts2, ..., tsL. In this way, both CPU and bandwidth can be expressed in time slots. An SP only needs to specify the number of the time slots for a particular virtual node/link when he makes a request for virtual network mapping. Therefore, we will only focus on opportunistic bandwidth sharing in Section V-A; the results can be directly applied to opportunistic CPU sharing without any major changes. SPs deploy end-to-end value-added services aimed at the end users, who access the services and leave at any time. These dynamic customers lead to workload fluctuations and further cause a waste of physical resources. As it is difficult to capture the characteristics of workload fluctuation, we use a simplified model: the work load wli of virtual network i is composed of a basic sub-workload basici , which exists all of the time, and a variable sub-workload variai , which occurs with a small probability pwli in unit time. We let bwli = basici/wli represent basic sub-workload percentage. Workloads in different virtual networks are assumed to be independent of each other. We believe that this model is reasonable although it is simple. For example, in a layered video streaming service [19], each video frame is encoded into multiple video packets corresponding to multiple quality layers. These video packets are classified as a base or enhancement layer to meet different network conditions. The workload in this scenario is very similar to our model. We hope that this simplified model can provide some insights on the design of other VNE algorithms. Since both the network traffic and CPU time will fluctuate as the workload fluctuates, both the amounts of network flow in a virtual link and the CPU time in a virtual node are assumed to be proportional to the workload for simplicity. More specifically, the flow in a virtual link is composed of a basic part, whose percentage is bwli , and a variable part, which occurs with probability pwli . And the same statement holds for the CPU time. B. Notations Substrate Network: a substrate network is modeled as a weighted undirected graph, G s = (N s , E s ,C s , B s ), where N s 2409

VN request G'r TABLE I bm,=09,pW,=0.t 18 Substrate network sn NOTATIONS IN THIS PAPER 108 Notation Meaning 20 15 8 17 12 G Substrate network 10 W Set of nodes b Set of links 7 7 Cs Set of CPU capacity attributes 12 B Set of bandwidth capacity attributes VN request G'2 RC* Set of residual CPU resources bwW2-0.8pwW20.2 12 9 RB Set of residual bandwidth resources 12 15 P Loop-free paths set 9 7 10 G The i virtual network Set of nodes of Gy Fig.1.Notations of virtual network embedding Set of links of G Set of CPU constraints in G 吲 Set of bandwidth constraints in G? is the set of substrate nodes,and Es is the set of substrate bwl A basic sub-workload percentage in G? links.Cs is the set of CPU capacity attributes,and Bs is pwl Probability of a variable sub-workload in G the set of bandwidth capacity attributes.We use RC"(n)and RB"(e)to denote the residual CPU of substrate node ns and residual bandwidth of substrate link e,respectively.Here,we (CB,BE],(bc)(ED),(ca)(DC)).The node mapping for would mention that the amount of residual resources in the the VN request G is (dA,eF),and the link mapping presence of opportunistic resource sharing is not obvious,we is{(de)→{AG,GF. will discuss it later when necessary.We use ps to denote the C.Objective set of loop-free paths in Gs. Virtual Network:we denote a virtual network by a Virtual network mapping is done by InPs.From InPs' weighted undirected graph,G=(N,E,C,B:,bwli,pwli). standpoint,a natural objective is to increase revenue and to N is the set of virtual nodes,and E is the set of virtual decrease cost.However,an SP is only willing to pay fee links.C is the set of CPU constraints,and B"is the set proportional to his requested resources,that is,the revenue, of bandwidth constraints.bwl;represents the percentage of R(G:),of embedding a virtual network,G',can be defined as a basic sub-workload in an overall workload.pwl;means the (following the definitions in previous works [8,10]): probability of a variable sub-workload occurring in unit time. R(G)=we· (1) The notations are summarized in Table I for reference.The ∑c+ws·∑e notation system in this paper is similar to that in [8,10,20]. The principle behind these notations is that superscript indi- where @c and are the weights for CPU and bandwidth, respectively.We learn from this definition that,given a VN cates substrate/virtual networks. Fig.1 shows an example of these notations.The corre- request,the revenue is fixed.Therefore,in order to get more sponding number near each vertex/edge is the CPU/bandwidth revenue,the InP should try to accept more VN requests but capacity/constraint.For virtual link a-b in the VN request meet their resource constraints at the same time. G',the basic sub-traffic is 8*0.9 =7.2,the variable sub-traffic To this end,virtual networks should be properly and effi- is 8-7.2=0.8 and occurs with probability 0.1. ciently deployed on top of a substrate network.Due to the Virtual Network Mapping:virtual network mapping is NP-completeness of the VNE problem [5],many heuristic usually defined as a mapping M from G?to a subset of Gs, algorithms have been proposed.However,in this paper we such that some predefined constraints are satisfied.It can be re-visit this problem from two novel aspects:opportunistic decomposed into two major components:node mapping M resource sharing and topology-aware node mapping. and link mapping M. IV.FRAMEWORK OVERVIEW The node mapping Mn:NNs maps a virtual node to We present a high level overview of our framework. a substrate node,subject to:Vn",mE Ny ORS TA,as illustrated in Algorithm 1,in this section and the Mn(n')∈Ns details of ORSTA in the next section. Mn(n)=M(m")iff m"n" Initially,we compute the amount of residual resources for each substrate node/link (lines 3-4 of Alg.1),i.e.,the available RC5(Mn(n)≥Cn) CPU/bandwidth capacity.Note that,when we perform oppor- The link mapping M Eps maps a virtual link to a tunistic resource sharing,the estimation of residual resources substrate loop-free path,subject to:Ve"=(m'n")EE" becomes complicated;we will explain our method in Sec- Mi(m'n")EP (M(m"),Ma(n")) tion V-B.Afterwards,inspired by the PageRank algorithm [21] which is used by Google to assign a numerical rank to every RB'(M(m'n')≥B(e) web page,we devise a similar ranking algorithm based on In Fig.1,the node mapping for the VN request G is Markov chain [22]to compute the rank of each substrate node, (aC,bE,cDl,and the link mapping is ((ab)denoted by MCRank (line 5 of Alg.1),which is illustrated 2410

Fig. 1. Notations of virtual network embedding is the set of substrate nodes, and E s is the set of substrate links. C s is the set of CPU capacity attributes, and B s is the set of bandwidth capacity attributes. We use RCs (n s ) and RBs (e s ) to denote the residual CPU of substrate node n s and residual bandwidth of substrate link e s , respectively. Here, we would mention that the amount of residual resources in the presence of opportunistic resource sharing is not obvious, we will discuss it later when necessary. We use P s to denote the set of loop-free paths in G s . Virtual Network: we denote a virtual network by a weighted undirected graph, G v i = (N v i , E v i ,C v i , B v i , bwli , pwli) . N v i is the set of virtual nodes, and E v i is the set of virtual links. C v i is the set of CPU constraints, and B v i is the set of bandwidth constraints. bwli represents the percentage of a basic sub-workload in an overall workload . pwli means the probability of a variable sub-workload occurring in unit time. The notations are summarized in Table I for reference. The notation system in this paper is similar to that in [8, 10, 20]. The principle behind these notations is that superscript indi￾cates substrate/virtual networks. Fig. 1 shows an example of these notations. The corre￾sponding number near each vertex/edge is the CPU/bandwidth capacity/constraint. For virtual link a − b in the VN request G v 1 , the basic sub-traffic is 8∗0.9 = 7.2, the variable sub-traffic is 8 − 7.2 = 0.8 and occurs with probability 0.1. Virtual Network Mapping: virtual network mapping is usually defined as a mapping M from G v i to a subset of G s , such that some predefined constraints are satisfied. It can be decomposed into two major components: node mapping Mn and link mapping Ml . The node mapping Mn : N v i → N s maps a virtual node to a substrate node, subject to: ∀n v , m v ∈ N v i Mn(n v ) ∈ N s Mn(n v ) = Mn(m v ) iff m v = n v RCs (Mn(n v )) ≥ C v i (n v ) The link mapping Ml : E v i → P s maps a virtual link to a substrate loop-free path, subject to: ∀e v = (m vn v ) ∈ E v i Ml(m v n v ) ∈ P S (Mn(m v ),Mn(n v )) RBs (Ml(m v n v )) ≥ B v i (e v ) In Fig. 1, the node mapping for the VN request G v 1 is {a → C, b → E, c → D}, and the link mapping is {(ab) → TABLE I Notations in this paper Notation Meaning G s Substrate network N s Set of nodes E s Set of links C s Set of CPU capacity attributes B s Set of bandwidth capacity attributes RCs Set of residual CPU resources RBs Set of residual bandwidth resources P s Loop-free paths set G v i The i th virtual network N v i Set of nodes of G v i E v i Set of links of G v i C v i Set of CPU constraints in G v i B v i Set of bandwidth constraints in G v i bwli A basic sub-workload percentage in G v i pwli Probability of a variable sub-workload in G v i {CB, BE}, (bc) → {ED}, (ca) → {DC}}. The node mapping for the VN request G v 2 is {d → A, e → F}, and the link mapping is {(de) → {AG,GF}}. C. Objective Virtual network mapping is done by InPs. From InPs’ standpoint, a natural objective is to increase revenue and to decrease cost. However, an SP is only willing to pay fee proportional to his requested resources, that is, the revenue, R(G v i ), of embedding a virtual network, G v i , can be defined as (following the definitions in previous works [8, 10]): R(G v i ) = ωc · ∑ n v∈Nv C v i (n v ) + ωb · ∑ e v∈Ev B v i (e v ) (1) where ωc and ωb are the weights for CPU and bandwidth, respectively. We learn from this definition that, given a VN request, the revenue is fixed. Therefore, in order to get more revenue, the InP should try to accept more VN requests but meet their resource constraints at the same time. To this end, virtual networks should be properly and effi- ciently deployed on top of a substrate network. Due to the NP-completeness of the VNE problem [5], many heuristic algorithms have been proposed. However, in this paper we re-visit this problem from two novel aspects: opportunistic resource sharing and topology-aware node mapping. IV. Framework Overview We present a high level overview of our framework, ORS T A, as illustrated in Algorithm 1, in this section and the details of ORS T A in the next section. Initially, we compute the amount of residual resources for each substrate node/link (lines 3-4 of Alg. 1), i.e., the available CPU/bandwidth capacity. Note that, when we perform oppor￾tunistic resource sharing, the estimation of residual resources becomes complicated; we will explain our method in Sec￾tion V-B. Afterwards, inspired by the PageRank algorithm [21] which is used by Google to assign a numerical rank to every web page, we devise a similar ranking algorithm based on Markov chain [22] to compute the rank of each substrate node, denoted by MCRank (line 5 of Alg. 1), which is illustrated 2410

=01 in Section V-C.This MCRank takes both residual resources and topology into consideration in an effort to improve the 23 12 2 12 deployment of virtual networks. When a VN request arrives,we adopt the following simple greedy heuristic.In the node mapping phase(lines 7-10 of Alg. Ph=0.1 1),all virtual nodes are sorted in a decreasing order of their CPU constraints and are placed in a queue;then,we map each ts2 ts3 ts4 ts5 ts6 virtual node in the sorted queue to the unused substrate node with the highest MCRank.In the link mapping phase (lines frame 11-13 of Alg.1),we map each virtual link to the k-shortest Fig.2.Time slot assignment in a virtual link path between its end hosts (for increasing k)to minimize the length of the substrate paths that virtual links are mapped to. Then,considering workload fluctuation,we employ op- Opportunistic resource sharing for virtual network mapping portunistic resource sharing to efficiently utilize substrate is proposed in [18]for the first time.In that paper,we studied resources at the expense of collisions (line 14 of Alg.1). opportunistic bandwidth sharing in a single physical link and We formulate this opportunistic resource sharing-based local devised two heuristic algorithms from different perspectives. time slot assignment problem as an optimization problem and Here,we employ the results from our previous work and im- devise an online approximation algorithm,which is inspired prove them by developing an online approximation algorithm. by the bin packing problem [23].The details are presented in As we assumed,both the network traffic and the CPU busy section V-A. time are proportional to the workload;for a virtual link,e', When a virtual network request is successfully embed- from virtual network G',the traffic is composed of basic ded,the framework ORSTA updates RC5(n),RB(e)and sub-traffic,which equals bwli.B'(e"),and variable sub-traffic, MCRank(n),and waits for another virtual network request. which equals(1-bwli).B:(e")and happens with probability pwli.For basic sub-traffic,the InP has no choice but to allocate Algorithm 1 The Opportunistic Resource Sharing and the required number of time slots,thus we will only consider Topology-Aware Mapping Framework(ORS TA) variable sub-traffic in the subsequent discussion. 1:Initialization Phase To conserve time slots for upcoming requests,we prefer 2:while true do that each time slot can be assigned to as much variable sub- Yn'∈Ws,update RC'(n) traffic as possible.However,when more than one variable sub- Ye'∈E',update RB'(e) traffic occurs at the same time slot,a collision happens.To 5 Run MCRank(y) break the tradeoff between utilization and collision,we have Wait until a VN request,say G,arrives the following optimization problem. Os-sorted virtual nodes in Gy according to Cy Problem 1:Given a probability threshold,ph,and a set of for i=0 to Os.length do n variable sub-traffic from e',i =1.2,...,n,each requires 9 Map o[i]to the unused substrate node with the (1-bwli).B'(e")time slots with probability pwli.Find highest MCRank an assignment of time slots for the variable sub-traffic to 10: end for minimize the number of time slots used,such that:1)for 11: for all es e Es do each variable sub-traffic flow from e,the number of time 12: Map es to the k-shortest path for increasing k slots assigned to it is at least (1-bwl).B(e);2)the collision 13: end for probability at each time slot is no more than ph. 14 Yn∈Vs and Ve'∈E',run FFA(ph) 15:end while The collision probability can be obtained as follows.Let Xi indicate whether variable sub-traffic in e'occurs,i.e.,Pr[Xi= 1]pwli.For time slot k,let D&denote the set of variable V.DETAILED ALGORITHMS sub-traffic that it is assigned to.Then,the probability of a A.Opportunistic Resource Sharing-based Local Time Slot collision happening at slot k,denoted by Preollision(De),is: Assignment PTcollision(Dg)=PrL∑X≥1] 1)Preliminaries:in ORS TA.the virtual network embed- ding is completed after line 13 of Alg.I in a macroscopical sense,i.e.,node-to-node and link-to-path matching is accom- 1--pwl)-∑pw: (2) (1-pwlj)) jeD.j≠i plished.However,at a single node/link level,we also need to deal with opportunistic resource sharing-based local time Fig.2 shows a feasible assignment.ts can be assigned slots assignment.Note that both CPU and bandwidth can be to three sub-traffic flows from e',ez,and e because they represented as time slots,so we focus on assigning time slots collide with a probability 0.064 (by Eq.(2)),which is less then in a substrate link among multiple virtual links.The results ph=0.1.ts3 can not be assigned to e"and e simultaneously can be applied to a substrate node without any major changes. because the collision probability is 0.3.0.4=0.12>Ph 2411

in Section V-C. This MCRank takes both residual resources and topology into consideration in an effort to improve the deployment of virtual networks. When a VN request arrives, we adopt the following simple greedy heuristic. In the node mapping phase (lines 7-10 of Alg. 1), all virtual nodes are sorted in a decreasing order of their CPU constraints and are placed in a queue; then, we map each virtual node in the sorted queue to the unused substrate node with the highest MCRank. In the link mapping phase (lines 11-13 of Alg. 1), we map each virtual link to the k-shortest path between its end hosts (for increasing k) to minimize the length of the substrate paths that virtual links are mapped to. Then, considering workload fluctuation, we employ op￾portunistic resource sharing to efficiently utilize substrate resources at the expense of collisions (line 14 of Alg. 1). We formulate this opportunistic resource sharing-based local time slot assignment problem as an optimization problem and devise an online approximation algorithm, which is inspired by the bin packing problem [23]. The details are presented in section V-A. When a virtual network request is successfully embed￾ded, the framework ORS T A updates RCs (n s ), RBs (e s ) and MCRank(n s ), and waits for another virtual network request. Algorithm 1 The Opportunistic Resource Sharing and Topology-Aware Mapping Framework (ORS T A) 1: Initialization Phase 2: while true do 3: ∀n s ∈ N s , update RCs (n s ) 4: ∀e s ∈ E s , update RBs (e s ) 5: Run MCRank(γ) 6: Wait until a VN request, say G v i , arrives 7: Q s ← sorted virtual nodes in G v i according to C v i 8: for i = 0 to Q s .length do 9: Map Q s [i] to the unused substrate node with the highest MCRank 10: end for 11: for all e s ∈ E s do 12: Map e s to the k-shortest path for increasing k 13: end for 14: ∀n s ∈ N s and ∀e s ∈ E s , run FFA(pth) 15: end while V. Detailed Algorithms A. Opportunistic Resource Sharing-based Local Time Slot Assignment 1) Preliminaries: in ORS T A, the virtual network embed￾ding is completed after line 13 of Alg. 1 in a macroscopical sense, i.e., node-to-node and link-to-path matching is accom￾plished. However, at a single node/link level, we also need to deal with opportunistic resource sharing-based local time slots assignment. Note that both CPU and bandwidth can be represented as time slots, so we focus on assigning time slots in a substrate link among multiple virtual links. The results can be applied to a substrate node without any major changes. Fig. 2. Time slot assignment in a virtual link Opportunistic resource sharing for virtual network mapping is proposed in [18] for the first time. In that paper, we studied opportunistic bandwidth sharing in a single physical link and devised two heuristic algorithms from different perspectives. Here, we employ the results from our previous work and im￾prove them by developing an online approximation algorithm. As we assumed, both the network traffic and the CPU busy time are proportional to the workload; for a virtual link, e v i , from virtual network G v i , the traffic is composed of basic sub-traffic, which equals bwli · B v i (e v ), and variable sub-traffic, which equals (1 − bwli) · B v i (e v ) and happens with probability pwli . For basic sub-traffic, the InP has no choice but to allocate the required number of time slots, thus we will only consider variable sub-traffic in the subsequent discussion. To conserve time slots for upcoming requests, we prefer that each time slot can be assigned to as much variable sub￾traffic as possible. However, when more than one variable sub￾traffic occurs at the same time slot, a collision happens. To break the tradeoff between utilization and collision, we have the following optimization problem. Problem 1: Given a probability threshold, pth, and a set of n variable sub-traffic from e v i , i = 1, 2, . . . , n, each requires (1 − bwli) · B v i (e v i ) time slots with probability pwli . Find an assignment of time slots for the variable sub-traffic to minimize the number of time slots used, such that: 1) for each variable sub-traffic flow from e v i , the number of time slots assigned to it is at least (1−bwli)·B v i (e v i ); 2) the collision probability at each time slot is no more than pth. The collision probability can be obtained as follows. Let Xi indicate whether variable sub-traffic in e v i occurs, i.e., Pr[Xi = 1] = pwli . For time slot k, let Dk denote the set of variable sub-traffic that it is assigned to. Then, the probability of a collision happening at slot k, denoted by Prcollision(Dk), is: Prcollision(Dk) = Pr[ ∑ i∈Dk Xi ≥ 1] = 1 − ∏ i∈Dk (1 − pwli) − ∑ i∈Dk (pwli · ∏ j∈Dk , j,i (1 − pwlj)) (2) Fig. 2 shows a feasible assignment. ts1 can be assigned to three sub-traffic flows from e v 1 , e v 2 , and e v 3 because they collide with a probability 0.064 (by Eq. (2)), which is less then pth = 0.1. ts3 can not be assigned to e v 1 and e v 4 simultaneously because the collision probability is 0.3 · 0.4 = 0.12 > pth. 2411

2)A first-fit-based online approximation algorithm:the Case I:we use a particular variable sub-traffic flow,which design of our algorithm is based on the following observation: requires dmin time slots and occurs with probability Pmin, when each variable sub-traffic requires one single time slot. to replace all of the variable sub-traffic.Then.the maximal i.e.,(1 -bwli).B'(e)=1 for all i,Problem 1 is very similar allowable number of sub-traffic,vol,in a substrate slot is to bin packing.However,the occupied size in each bin is the determined by: sum of the sizes of all of the packed items in bin packing, whereas in Problem 1,the collision probability in a time slot, 1-(1-Pmin)vol-volt Pmin(1-Pmin)vol-1=Puh as shown in Eq.2,is neither linear nor multiplicative. Hence,in this case,the number of time slots required by First-fit [23]is a heuristic algorithm with an approximation all of the n sub-traffic is: factor of 2 for bin packing.In first-fit,items are considered in an arbitrary order,and for each item,first-fit attempts to place s1=”dnn the item in the first bin that can accommodate the item.If not. the item is placed into a new bin.First-fit can be executed Case II:we use another particular variable sub-traffic flow, online and has a low time complexity. which requires dmax time slots and occurs with probability Their resemblance sheds light on the design of FFA,which Pmax,to replace all of the variable sub-traffic.Then,the is based on the core idea of first-fit.The FFA Algorithm is maximal allowable number of sub-traffic,voly,in a substrate presented in Algorithm 2. slot is determined by: 1-(1-Pmax)you-voln Pmax(1-Pmaxolu-1=Pth Algorithm 2 FFA(Pih) 1:Wait until variable sub-traffic from e arrives Similarly,the number of time slots required by all of the n 2:counter←-0 sub-traffic in this case is: 3:While(counter <(1-bwli).B:(e)) ·dmar Let pos←-0 5: While(Collision(tspos,e)>Pth) 6: pos←←p05+1 Theorem I:Sffa≤(dmar·voli）/(dmin·voli）Sopr 个 Proof:it is straightforward to see that: Assign tspos to e 8: counter←counter+1 0<S1≤Som≤Sffa≤Sn then: 3)Incremental Calculation:Collision(tspos,e)is a func- SifaSμ=dmaxvoll tion that returns the probability of a collision at tspos if tspos is assigned to e'.To calculate the collision probability efficiently, :≤Si=dminvol we adopt the following incremental approach.Let De be the The theorem follows immediately. ■ set of variable sub-traffic that ts is currently assigned to.Also B.Residual Resource Estimation let: A(Dk)= 1-pwli) The amount of the residual resource in a substrate node/link iED is an important metric in VNE process.In a traditional sce- B(D)= S(pwlr (1-pwl)》 nario,where opportunistic resource sharing is not considered, iED jEDu,jti the residual CPU,RC(n),of a substrate node,n,and residual then,the collision probability Preollision(D)=1-A(D)- bandwidth,RB(e),of a substrate link,e,are defined as: B(D).When slot k is to be assigned to a new sub-traffic from RCom)=Cn-∑0n,n) e,then: Vnv A(D&Ulep)=A(Dg)(1-pwlh) RB'(e)=B'(e)- ∑fi(e',e) (3) B(D&Ulep])=B(D)(1-pwlh)+A(Dg).pwlh where fe(n",n)denotes the CPU resources of ns allocated This can be used to calculate the new collision probability. to n",and fo(e",e)denotes the bandwidth resources of es 4)Approximation Ratio:we denote by Sffa the solution allocated to e". generated by FFA,and by Sop the optimal solution.Abusing However,with opportunistic resource sharing,the residual the notation a bit,we will also use Sffa and Sopr to denote resource becomes complicated.Fig.3 shows a snapshot of the the number of time slots needed by these two solutions, time slot allocation in a substrate link.Intuitively,the residual respectively,if no confusion can be caused.Let, resource consists of the right part and the available room in Pmin minisisnpwli,dmin =minisisn((1-bwli).B(e)) the middle part which is allocated to variable sub-traffic.The pmax maxisisnpwli,dmax =maxisisn((1-bwli).B(e)) former is easy to compute while the latter is not so obvious. Suppose that the capacity of a substrate link,e",is B(e), Bin packing [23]:given n items with sizes s1.52....s.(0,1].find a and there are L time slots in a frame.There are b slots allocated packing method in unit-sized bins that minimizes the number of bins used.to basic sub-traffic and another d slots allocated to variable 2412

2) A first-fit-based online approximation algorithm: the design of our algorithm is based on the following observation: when each variable sub-traffic requires one single time slot, i.e., (1 − bwli) · B v i (e v i ) = 1 for all i, Problem 1 is very similar to bin packing1 . However, the occupied size in each bin is the sum of the sizes of all of the packed items in bin packing, whereas in Problem 1, the collision probability in a time slot, as shown in Eq. 2, is neither linear nor multiplicative. First-fit [23] is a heuristic algorithm with an approximation factor of 2 for bin packing. In first-fit, items are considered in an arbitrary order, and for each item, first-fit attempts to place the item in the first bin that can accommodate the item. If not, the item is placed into a new bin. First-fit can be executed online and has a low time complexity. Their resemblance sheds light on the design of FFA, which is based on the core idea of first-fit. The FFA Algorithm is presented in Algorithm 2. Algorithm 2 FFA(pth) 1: Wait until variable sub-traffic from e v i arrives 2: counter ← 0 3: While(counter < (1 − bwli) · B v i (e v i )) 4: Let pos ← 0 5: While(Collision(tspos, e v i ) > pth) 6: pos ← pos + 1 7: Assign tspos to e v i 8: counter ← counter + 1 3) Incremental Calculation: Collision(tspos, e v i ) is a func￾tion that returns the probability of a collision at tspos if tspos is assigned to e v i . To calculate the collision probability efficiently, we adopt the following incremental approach. Let Dk be the set of variable sub-traffic that tsk is currently assigned to. Also let: A(Dk) = ∏ i∈Dk (1 − pwli) B(Dk) = ∑ i∈Dk (pwli · ∏ j∈Dk , j,i (1 − pwlj)) then, the collision probability Prcollision(Dk) = 1 − A(Dk) − B(Dk). When slot k is to be assigned to a new sub-traffic from e v h , then: A(Dk ∪ {e v h }) = A(Dk)(1 − pwlh) B(Dk ∪ {e v h }) = B(Dk)(1 − pwlh) + A(Dk) · pwlh (3) This can be used to calculate the new collision probability. 4) Approximation Ratio: we denote by S f f a the solution generated by FFA, and by S opt, the optimal solution. Abusing the notation a bit, we will also use S f f a and S opt to denote the number of time slots needed by these two solutions, respectively, if no confusion can be caused. Let, pmin = min1≤i≤n pwli , dmin =min1≤i≤n((1 − bwli) · B v i (e v i )) pmax = max1≤i≤n pwli , dmax =max1≤i≤n((1 − bwli) · B v i (e v i )) 1Bin packing [23]: given n items with sizes s1,s2,...,sn ∈ (0, 1], find a packing method in unit-sized bins that minimizes the number of bins used. Case I: we use a particular variable sub-traffic flow, which requires dmin time slots and occurs with probability pmin, to replace all of the variable sub-traffic. Then, the maximal allowable number of sub-traffic, volI , in a substrate slot is determined by: 1 − (1 − pmin) volI − volI · pmin · (1 − pmin) volI−1 = pth Hence, in this case, the number of time slots required by all of the n sub-traffic is: S I = n volI · dmin Case II: we use another particular variable sub-traffic flow, which requires dmax time slots and occurs with probability pmax, to replace all of the variable sub-traffic. Then, the maximal allowable number of sub-traffic, volII, in a substrate slot is determined by: 1 − (1 − pmax) volII − volII · pmax · (1 − pmax) volII−1 = pth Similarly, the number of time slots required by all of the n sub-traffic in this case is: S II = n volII · dmax Theorem 1: S f f a ≤ (dmax · volI)/(dmin · volII) · S opt Proof: it is straightforward to see that: 0 < S I ≤ S opt ≤ S f f a ≤ S II then: S f f a S opt ≤ S II S I = dmax · volI dmin · volII The theorem follows immediately. B. Residual Resource Estimation The amount of the residual resource in a substrate node/link is an important metric in VNE process. In a traditional sce￾nario, where opportunistic resource sharing is not considered, the residual CPU, RCs (n s ), of a substrate node, n s , and residual bandwidth, RBs (e s ), of a substrate link, e s , are defined as: RCs (n s ) = C s (n s )− ∑ ∀n v fc(n v , n s ) RBs (e s ) = B s (e s )− ∑ ∀e v fb(e v , e s ) where fc(n v , n s ) denotes the CPU resources of n s allocated to n v , and fb(e v , e s ) denotes the bandwidth resources of e s allocated to e v . However, with opportunistic resource sharing, the residual resource becomes complicated. Fig. 3 shows a snapshot of the time slot allocation in a substrate link. Intuitively, the residual resource consists of the right part and the available room in the middle part which is allocated to variable sub-traffic. The former is easy to compute while the latter is not so obvious. Suppose that the capacity of a substrate link, e s , is B s (e s ), and there are L time slots in a frame. There are b slots allocated to basic sub-traffic and another d slots allocated to variable 2412