824 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3,MARCH 2014 09 08 .0 是7 0 0.4 0. 0.2 02 03 02 100020003000400050006000 0.1 02 0.3 0.4 0.5 0.1 0.2 03 04 0 Time Node utilization ratio Link utilization rato (a)Acceptance ratio over time (b)CDF of node utilization ratio (c)CDF of link utilization ratio Fig.10.Comparison results among ORS,R-ViNE,and Greedy,where E[b+=10,E[b/(b+)]=0.5,Elp =0.15. implicit,if somewhat subtle:one substrate slot can virtual network is assumed to be exponentially distributed accommodate more variable subrequirements when with an average of 10 minutes.The arrivals of VN requests A becomes larger;thus,the value of index in EFF(A) are modeled as a Poisson process with an average rate of becomes smaller on average. five requests per minute.The collision probability threshold The impact of puh:Fig.9b shows the ratio of EFF(14)to is set to 0.1 throughout this evaluating scenario.The results total slots under different thresholds,while we keep are averaged over 100 times of running.(Results over n=100 and Umar =10.We note that,for fixed Umar, ARPANET are similar and are omitted due to space the ratio goes down when the threshold increases. limitations.)Our framework ORS is compared with the This is reasonable,since the threshold serves as the following two algorithms: "volume"of a substrate slot,and a larger threshold allows a substrate slot to accommodate more R-ViNE [12]:coordinated node and link mapping subrequirements.For fixed pth,the ratio goes up through mixed integer programming formulation when Umar increases.This is because a larger Umar and randomized rounding. makes the number of subrequirements that a Greedy [13]:greedy node mapping and path splitting. substrate slot can accommodate decrease,and hence, The performance metrics we use for comparison include EFF (14)needs more substrate slots. acceptance ratio,which is the ratio of the number of accepted In our simulations,we also find that,when A>14,the virtual network requests to all requests,node ufilization ratio, collision probability in the embedding results of EFF which is the ratio of the amount of the allocated CPU would be bigger than pu=0.1.In addition,this critical resources to overall CPU resources in the substrate network, value is about 10 when pth=0.2,and about eight when and link utilization ratio,which is the ratio of the amount of pth=0.3.We explain this as follows:if we replace every pi the allocated bandwidth resources to overall bandwidth with Pmar =mar(sisn)pi,then the number of subrequire- resources in the substrate network.We are also interested in ments that a single substrate slot can accommodate, denoted as y,,can be resolved by 1-(1-pmar)"- the impacts of the following parameters: pmar(1-pmaz)y=pth.Then,by double counting the .Eb+:the average total number of slots required indicators'sum,we get h =Pmary.When Pth goes up, by a virtual node or link; both y and h go up,but A goes down,indicating that h ● Eb/(b+v)]:the average percentage of the number of grows faster than y. slots in a basic subrequirement to the total number of We also conducted simulations with ph=0.2 and slots required by a virtual node or link;and p=0.3.The results are similar to the above and are, therefore,omitted due to space limitations.Briefly speak- Ep]:the average happening probability of variable subrequirements of virtual nodes and links ing,both CFF and EFF improve the resource utilization,and EFF is less time-consuming and more flexible than CFF. 6.4 Results of Entire Substrate Network 6.3 Entire Substrate Network 1. Comparison of acceptance ratios.Figs.10a,10b,and 10c In this section,we consider VNE at the level of the entire show the comparison of the acceptance ratio over network,compare our framework with two state-of-the-art time,cumulative distribution function (CDF)of node fixed-resource embedding algorithms [12],[13],and inves- utilization ratio,and CDF of link utilization ratio, tigate the impacts of various parameters. respectively.In these experiments,Eb+u is 10, Our simulation settings follow prior work [12],[13],as E[b/(b+v)]=0.5,and Elp]=0.15.In Fig.10a,as a network virtualization is still in its infancy.We use whole,the acceptance ratio of ORS is the highest, ANSNET and ARPANET as the substrate network topolo- and Greedy is the lowest,indicating that opportu- gies.Both CPU and bandwidth capacities in substrate nistic resource sharing indeed improves the deploy- networks are generated uniformly from the interval ment of virtual networks,which further enables the between 50 and 100.For virtual networks,the number of substrate network to accept more VN requests.We virtual nodes is determined by a uniform distribution notice that the acceptance ratio of three algorithms is between 2 and 10,and each pair of virtual nodes is about 0.4 on average,which is a little low.The main connected with a probability of 0.5.We also check whether reason is that links in the substrate network a virtual network is connected;if it is not,we just regenerate (ANSNET has 32 nodes and 58 links,ARPANET it until we get a connected topology.The lifetime of each has 20 nodes and 32 links)are sparse,while eachimplicit, if somewhat subtle: one substrate slot can accommodate more variable subrequirements when becomes larger; thus, the value of index in EFF() becomes smaller on average. 4. The impact of pth: Fig. 9b shows the ratio of EFF (14) to total slots under different thresholds, while we keep n ¼ 100 and vmax ¼ 10. We note that, for fixed vmax, the ratio goes down when the threshold increases. This is reasonable, since the threshold serves as the “volume” of a substrate slot, and a larger threshold allows a substrate slot to accommodate more subrequirements. For fixed pth, the ratio goes up when vmax increases. This is because a larger vmax makes the number of subrequirements that a substrate slot can accommodate decrease, and hence, EFF (14) needs more substrate slots. In our simulations, we also find that, when > 14, the collision probability in the embedding results of EFF would be bigger than pth ¼ 0:1. In addition, this critical value is about 10 when pth ¼ 0:2, and about eight when pth ¼ 0:3. We explain this as follows: if we replace every pi with pmax ¼ maxð1inÞpi, then the number of subrequire￾ments that a single substrate slot can accommodate, denoted as y, can be resolved by 1  ð1  pmaxÞ y  pmaxð1  pmaxÞ y1 y ¼ pth. Then, by double counting the indicators’ sum, we get th ¼ pmaxy. When pth goes up, both y and th go up, but goes down, indicating that th grows faster than y. We also conducted simulations with pth ¼ 0:2 and pth ¼ 0:3. The results are similar to the above and are, therefore, omitted due to space limitations. Briefly speak￾ing, both CFF and EFF improve the resource utilization, and EFF is less time-consuming and more flexible than CFF. 6.3 Entire Substrate Network In this section, we consider VNE at the level of the entire network, compare our framework with two state-of-the-art fixed-resource embedding algorithms [12], [13], and inves￾tigate the impacts of various parameters. Our simulation settings follow prior work [12], [13], as network virtualization is still in its infancy. We use ANSNET and ARPANET as the substrate network topolo￾gies. Both CPU and bandwidth capacities in substrate networks are generated uniformly from the interval between 50 and 100. For virtual networks, the number of virtual nodes is determined by a uniform distribution between 2 and 10, and each pair of virtual nodes is connected with a probability of 0.5. We also check whether a virtual network is connected; if it is not, we just regenerate it until we get a connected topology. The lifetime of each virtual network is assumed to be exponentially distributed with an average of 10 minutes. The arrivals of VN requests are modeled as a Poisson process with an average rate of five requests per minute. The collision probability threshold is set to 0.1 throughout this evaluating scenario. The results are averaged over 100 times of running. (Results over ARPANET are similar and are omitted due to space limitations.) Our framework ORS is compared with the following two algorithms: . R  V iNE [12]: coordinated node and link mapping through mixed integer programming formulation and randomized rounding. . Greedy [13]: greedy node mapping and path splitting. The performance metrics we use for comparison include acceptance ratio, which is the ratio of the number of accepted virtual network requests to all requests, node utilization ratio, which is the ratio of the amount of the allocated CPU resources to overall CPU resources in the substrate network, and link utilization ratio, which is the ratio of the amount of the allocated bandwidth resources to overall bandwidth resources in the substrate network. We are also interested in the impacts of the following parameters: . E½b þ v: the average total number of slots required by a virtual node or link; . E½b=ðb þ vÞ: the average percentage of the number of slots in a basic subrequirement to the total number of slots required by a virtual node or link; and . E½p: the average happening probability of variable subrequirements of virtual nodes and links. 6.4 Results of Entire Substrate Network 1. Comparison of acceptance ratios. Figs. 10a, 10b, and 10c show the comparison of the acceptance ratio over time, cumulative distribution function (CDF) of node utilization ratio, and CDF of link utilization ratio, respectively. In these experiments, E½b þ v is 10, E½b=ðb þ vÞ ¼ 0:5, and E½p ¼ 0:15. In Fig. 10a, as a whole, the acceptance ratio of ORS is the highest, and Greedy is the lowest, indicating that opportu￾nistic resource sharing indeed improves the deploy￾ment of virtual networks, which further enables the substrate network to accept more VN requests. We notice that the acceptance ratio of three algorithms is about 0.4 on average, which is a little low. The main reason is that links in the substrate network (ANSNET has 32 nodes and 58 links, ARPANET has 20 nodes and 32 links) are sparse, while each 824 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 Fig. 10. Comparison results among ORS, R  V iNE, and Greedy, where E½b þ v ¼ 10; E½b=ðb þ vÞ ¼ 0:5; E½p ¼ 0:15.