Algorithm 3 MCRank(y) ranking indeed improves the deployment of virtual networks 1:CRank←-NormR,i←-O and further enables the substrate network to accept more VN 2:repeat requests.We also notice that the acceptance ratio of these four 3 MCRanki1←-MCRank·P algorithms is averagely less than 0.4,which is a little low.The 4: 6-MCRanki+1 MCRankill main reason behind this may be because links in the substrate 5 i←i+1 network (ANSNET has 32 nodes and 58 links,ARPANET 6:until 6<y has 20 nodes and 32 links)are sparse,while each pair of nodes in a virtual network is connected with probability 0.5. TABLE II This leads to the topology becoming the dominating factor in PARAMETERS virtual network embedding. EIC] Expectation of CPU requirement on a virtual node E[B] Expectation of bandwidth requirement on a virtual link Fig.4 also shows that the acceptance ratio of TA is E[bwl] Expectation of a basic sub-workload percentage much higher than ORS and Greedy.while ORS achieves Elpwl Expectation of a variable sub-workload occurring probability nearly the same acceptance ratio as Greedy.This implies that distinguishing between substrate nodes is helpful in virtual network mapping while opportunistic resource sharing is not VI.EXPERIMENTAL EVALUATION significantly effective when there is no topology-aware node In this section,we first describe our evaluation environment, ranking.In Figs 5 and 6,the node/link utilization ratio means then present main evaluation results. the ratio of the allocated resources to the capacity of a substrate node/link.We observe similar results where ORSTA performs A.Evaluation Environment better than TA.ORS.and Greedy. As network virtualization is still an open field,our eval- We then try to evaluate the effects of w1,E[C"],E[B"], uations follow settings similar to [7,8,10-12,20].We use E[bwl],and E[pwl],respectively.Fig.7 shows the comparison ANSNET and ARPANET as the substrate network topologies. between ORSTAs with different w settings.We see that Both the CPU capacity at substrate nodes and bandwidth ORS TA(wI =0.5)achieves the highest acceptance ratio while capacity at substrate links are generated uniformly from ORS TA(wI =0.3)gets the lowest.This is anticipated because [50,100].The arrivals of VN requests are modeled as a Poisson in MCRank,"wi=0.5"indicates the rank of a substrate process with an average rate of 5 requests per minute.For node is half determined by itself;"w=0.3"causes the each virtual network,the number of nodes is determined by rank of a substrate node to be greatly dominated by the a uniform distribution between 2 and 10;each pair of virtual amount of residual resources of other nodes.However,the nodes is connected with probability 0.5.The lifetime of each difference is not considerably significant,which means the virtual network is assumed to be exponentially distributed with stationary distribution of our Markov chain nicely represents an average of 10 minutes.The collision probability threshold the importance of substrate nodes,irrespective of whether wi is set to 0.1 throughout our evaluation.We summarize the is large or small. parameters that we vary in our evaluations in Table II. In Fig.8,we show the results of E[C"]and E[B"].We Comparing our framework with previous research on virtual note that in the case when E[C"]and E[B"]are small,the network mapping is difficult because it is the first attempt acceptance ratio is high.However,with E[C]and E[B"] that considers virtual network mapping in the context of increasing,the substrate network resources become scarce, opportunistic resource sharing at the entire network level. which causes more and more VN requests to be rejected.In Therefore,our evaluation focuses primarily on quantifying the this figure,ORS TA(E[C"]E[B]15)achieves almost the benefits of opportunistic resource sharing and topology-aware same acceptance ratio as ORS TA(E[C"]=E[B"]=20).A rea- node ranking.The notations that we use to refer to different sonable explanation is that,E[C"]=E[B"]=15 is sufficiently algorithms are enumerated in Table III.In the following large compared to the average amount of CPU/bandwidth subsection,we present the average results after running over capacities of substrate nodes/links,i.e.,75. ANSNET 100 times.(Results over ARPANET are similar and Fig.9 illustrates the effects of E[bwl]and Efpwll.Remem- omitted due to space limitation.) ber that bwl is the percentage of a basic sub-workload in the overall workload,and pwl is the probability of a variable B.Evaluation Results sub-workload happening.In this figure,ORSTA(E[bwl] We first present the comparison results between ORSTA,0.30,E[pwl]=0.15)presents the best performance,and TA,ORS,and Greedy (refer to Table III).Figs 4,5,and ORSTA(E[bwl]=0.50,E[pwl]=0.05)achieves the second 6 show the acceptance ratio over time,CDF (cumulative best.This is to say,bwl plays a more important role than pwl. distribution function)of node utilization ratios,and link uti- In summary,our proposed framework,ORS TA,increases lization ratios,respectively.In these experiments,both E[C"]the acceptance ratio through opportunistic resource sharing. and E[B"]are set to be 10;E[bwl]0.5;E[pwl]0.15, which enables the substrate network to support more VN and w=0.7.In Fig.4,the acceptance ratio of ORSTA requests and topology-aware node ranking,which treats sub- is higher than all of the other algorithms,which indicates strate nodes differently to shorten the length of substrate paths that opportunistic resource sharing and topology-aware node that virtual links are mapped to. 2414Algorithm 3 MCRank(γ) 1: MCRank ← NormR, i ← 0 2: repeat 3: MCRanki+1 ← MCRanki · P 4: δ ← ∥MCRanki+1 − MCRanki∥1 5: i ← i + 1 6: until δ < γ TABLE II Parameters E[C v ] Expectation of CPU requirement on a virtual node E[B v ] Expectation of bandwidth requirement on a virtual link E[bwl] Expectation of a basic sub-workload percentage E[pwl] Expectation of a variable sub-workload occurring probability VI. Experimental Evaluation In this section, we first describe our evaluation environment, then present main evaluation results. A. Evaluation Environment As network virtualization is still an open field, our eval￾uations follow settings similar to [7, 8, 10–12, 20]. We use ANSNET and ARPANET as the substrate network topologies. Both the CPU capacity at substrate nodes and bandwidth capacity at substrate links are generated uniformly from [50,100]. The arrivals of VN requests are modeled as a Poisson process with an average rate of 5 requests per minute. For each virtual network, the number of nodes is determined by a uniform distribution between 2 and 10; each pair of virtual nodes is connected with probability 0.5. The lifetime of each virtual network is assumed to be exponentially distributed with an average of 10 minutes. The collision probability threshold is set to 0.1 throughout our evaluation. We summarize the parameters that we vary in our evaluations in Table II. Comparing our framework with previous research on virtual network mapping is difficult because it is the first attempt that considers virtual network mapping in the context of opportunistic resource sharing at the entire network level. Therefore, our evaluation focuses primarily on quantifying the benefits of opportunistic resource sharing and topology-aware node ranking. The notations that we use to refer to different algorithms are enumerated in Table III. In the following subsection, we present the average results after running over ANSNET 100 times. (Results over ARPANET are similar and omitted due to space limitation.) B. Evaluation Results We first present the comparison results between ORS T A, T A, ORS , and Greedy (refer to Table III). Figs 4, 5, and 6 show the acceptance ratio over time, CDF (cumulative distribution function) of node utilization ratios, and link uti￾lization ratios, respectively. In these experiments, both E[C v ] and E[B v ] are set to be 10; E[bwl] = 0.5; E[pwl] = 0.15, and w1 = 0.7. In Fig. 4, the acceptance ratio of ORS T A is higher than all of the other algorithms, which indicates that opportunistic resource sharing and topology-aware node ranking indeed improves the deployment of virtual networks and further enables the substrate network to accept more VN requests. We also notice that the acceptance ratio of these four algorithms is averagely less than 0.4, which is a little low. The main reason behind this may be because links in the substrate network (ANSNET has 32 nodes and 58 links, ARPANET has 20 nodes and 32 links) are sparse, while each pair of nodes in a virtual network is connected with probability 0.5. This leads to the topology becoming the dominating factor in virtual network embedding. Fig. 4 also shows that the acceptance ratio of T A is much higher than ORS and Greedy, while ORS achieves nearly the same acceptance ratio as Greedy. This implies that distinguishing between substrate nodes is helpful in virtual network mapping while opportunistic resource sharing is not significantly effective when there is no topology-aware node ranking. In Figs 5 and 6, the node/link utilization ratio means the ratio of the allocated resources to the capacity of a substrate node/link. We observe similar results where ORS T A performs better than T A, ORS , and Greedy. We then try to evaluate the effects of w1, E[C v ], E[B v ], E[bwl], and E[pwl], respectively. Fig. 7 shows the comparison between ORS T As with different w1 settings. We see that ORS T A(w1 = 0.5) achieves the highest acceptance ratio while ORS T A(w1 = 0.3) gets the lowest. This is anticipated because in MCRank, “w1 = 0.5” indicates the rank of a substrate node is half determined by itself; “w1 = 0.3” causes the rank of a substrate node to be greatly dominated by the amount of residual resources of other nodes. However, the difference is not considerably significant, which means the stationary distribution of our Markov chain nicely represents the importance of substrate nodes, irrespective of whether w1 is large or small. In Fig. 8, we show the results of E[C v ] and E[B v ]. We note that in the case when E[C v ] and E[B v ] are small, the acceptance ratio is high. However, with E[C v ] and E[B v ] increasing, the substrate network resources become scarce, which causes more and more VN requests to be rejected. In this figure, ORS T A(E[C v ] = E[B v ] = 15) achieves almost the same acceptance ratio as ORS T A(E[C v ] = E[B v ] = 20). A rea￾sonable explanation is that, E[C v ] = E[B v ] = 15 is sufficiently large compared to the average amount of CPU/bandwidth capacities of substrate nodes/links, i.e., 75. Fig. 9 illustrates the effects of E[bwl] and E[pwl]. Remem￾ber that bwl is the percentage of a basic sub-workload in the overall workload, and pwl is the probability of a variable sub-workload happening. In this figure, ORS T A(E[bwl] = 0.30, E[pwl] = 0.15) presents the best performance, and ORS T A(E[bwl] = 0.50, E[pwl] = 0.05) achieves the second best. This is to say, bwl plays a more important role than pwl. In summary, our proposed framework, ORS T A, increases the acceptance ratio through opportunistic resource sharing, which enables the substrate network to support more VN requests and topology-aware node ranking, which treats sub￾strate nodes differently to shorten the length of substrate paths that virtual links are mapped to. 2414