=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 2411in 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