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 2410Fig. 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