虚拟网络嵌入的文章

很好的文章，Softwaredefined networking has emerged as a powerful approach to improve the customizability and flexibility of networks. In this work, we focus on virtualization in the realm of softwaredefined network ing, and study how to embed virtual networks in this environment. Virtual network embedding is an important problem because intelligent embedding can lead to better performance and a more efficient allocation of network resources compared to random mapping. In softwaredefined networking, the pres ence of a central controller is a complicating factor, and customizable routing and differences in resource sharing present new opportunities and challenges. We identify two aspects of virtual network embedding in softwaredefined networks: virtual node and link mapping, and controller placement. We tackle these problems together, developing techniques to perform embedding with two goals: balancing the load on the substrate network and minimizing controllertoswitch delays. We evaluate our techniques with sim ulation and Mininet emulation, and show that they are able to optimize for one of the above objectives while keeping the other within reasonable bounds
M. Demirci, M. Ammar/Computer Communications 45(2014)110 iv. We evaluated the impact of both techniques on the objective virtual networks, and then describe the vn embedding problem metrics(stress and controllertoswitch delays) as well as in the sdn environment other metrics such as endtoend delays and throughput We also analyzed the effects of changes in the tunable 3. 1. Identifying SDN resources parameters of our methods and definitions Virtualization in softwaredefined networks requires a mecha The remainder of the paper is organized as follows. Section 2 nism to share network resources among multiple slices. a classifi presents a brief review of related work in the literature. In Sec cation of these resources was presented in the flow visor work [2] tion 3, we describe resource sharing in SdN and formally define We summarize these as follows the vn embedding problem. Section 4 presents our approach and Switch CPU: Sharing computational power between slices at two variations of vn embedding techniques with different switches is orchestrated considering two main tasks performed priorities. Section 5 contains results from evaluation efforts con for each slice generating new flow messages to be sent to the cor ducted via simulation and Mininet [5 emulation, and Section 6 responding controller, and handling controller requests regarding summarizes the paper. the slice Cpu power demands at a switch increase with the num ber of virtual nodes and links at mapped to it/traversing it 2 Related work Bandwidth: Isolation of bandwidth is handled via perslice ueues at each port on Open flow switches. Each slice has its Vn embedding with node and link constraints is a complex own queue at each port, and these queues are serviced according problem and can be reduced to the NPhard multi way separator to the resource allocation policy. In particular, FlowVisor imple problem [11]. Much of the research in this area has focused on mentation uses minimum bandwidth queues, whereby a slice is developing heuristics by shrinking the problem space through var guaranteed a minimum of X% of the bandwidth on a link, and pos ious assumptions [12] sibly more if the link is not fully utilized. In our design, we take into Various techniques for performing vn embedding in traditional account both the number of virtual links that share a substrate link networks have been proposed by researchers [13. Hov and the number of controller toswitch connections that must go tinctions of the sDn environment(such as the centrality and the ever, dis over this link. balancing these numbers across the substrate is use importance of the controller, and differences in the virtualization ful to avoid potential hot spots and reduce the possibility of technology) necessitate a new approach We utilize some defini congestion tions and ideas from the stressbalancing vn assignment algorithm Flow entry space: The number of flow entries that can be used by each slice is also limited at each switch when a controller is over presented in [ 8] and adapt them to our problem. We define stress its limit, it is not allowed to insert any new rules at the switch. This in a modified way, and identify stressbalancing as one of two VN embedding objectives considered in this paper. is another reason to consider the number of virtual links traversing SDn is a suitable platform for network virtualization and a substrate node as part of the load on that node researchers have been working on ways to provide virtualization to enable the coexistence of multiple vNs in the SDN environment 3. 2. VN embedding problem FlowVisor [2 has been proposed as a virtualization solution in SDN. In this work, we assume the availability of a FlowVisorlike Network model: We take the underlying sdn infrastructure as lalization tool and analyze flow visor to identify the network the network substrate and model it as a graph(V, E), where V i resources to be shared in the presence of multiple VNs coexisting the set of substrate nodes and e is the set of substrate links on an sdn substrate. with flow visor each vn runs its own con We can think of vnembedding in sdn as a combination of two troller, so we include controller placement in the problem defini subproblems: 1)deciding which switches to include in a slice, and tion. In contrast, another Sdn virtualization solution FlowN 3 2) how to configure the routing within the slice. This problem be utilizes container based virtualization to run a modified version comes interesting only when there are many VNs sharing the of the noX controller [14 and it does not employ a separate con underlying infrastructure. So we are focusing on the problem of troller for each Vn but it maps NOX APi calls between the physical embedding multiple VNs on a substrate of Open Flowenabled and virtual networks We choose flow visor as the tool for virtual switches using FlowVisor ization because it is the more established and widespread solution We address controller placement and vn embedding as a joint The placement of SDn controllers has been studied [15] with problem With multiple vn requests, the location of the controlle the goal of minimizing the average and maximum delays from for each Vn can be either predetermined in the vn request (as the controller to the switches. The authors do not propose a spe some users mdy desire the ability to select precise locations for cific method for this placement, but they evaluate how much con the central controllers of their vns) and fixed at a certain location troller placement affects said delays by finding the optimal or adjustable, which means that there is no specific limitation by placement via brute force. The location of the network is specified the user regarding the controller location and the embedding algo rithm is free to select the location. To this end, we consider two op beforehand except for the placement of the controller, which can tions for each VN: VN embedding with fixedlocation controller(vnE be moved around. In this work, we incorporate the objective of de lay minimization into our embedding techniques. However, we F) and vn embedding with adjustablelocation controller(vNEA). consider a more general situation where there are many vns The only difference between these two approaches is in the whose controllers are either fixed at a predetermined location or determination of the controller location for the vn. in vnea the free to be placed anywhere. Furthermore, the topology of each controller location can be set to any node in the substrate topolo VN is given, but the mapping of that topology to the SDN substrate since we assume that the software controller can run on a host al the same location as a switch is yet to be determined Our objective for vn embedding is twofold balancing the load on switches and links while trying to minimize the average 3. Model and problem statement controllertoSwitch delay for each VN. As d measure of load,we concentrate on stress from previous work 8] in the vn embedding In this section, we first briefly discuss the nature of resource literature. We modify the definition of stress given in [8 where it sharing in softwaredefined networks in the presence of multiple was defined for a substrate node as the number of virtual nodes M. Demirci, M. Ammar/Computer Communications 45(2014)110 mapped to it, and for a substrate link as the number of virtual links component placement along with controller placement. One traversing it. We add two things to these definitions: for node method strives to balance the load and resource usage in the net stress, we take into account the additional cpu power and flow en work as much as possible while keeping controllertoswitch de try space load that comes from virtual links that traverse a node: lays within certain bounds, and the other method minimizes and for link stress, we add a component for the total load due to these delays while keeping the maximum stress under a thresh all the controllertoswitch communications going over a particu old. These embedding methods are uncoordinated 13, i.e virtual lar link. the definition of stress in this work is as follows node mapping and virtual link mapping are performed in two For a substrate node vE v, stress is a weighted combination of separate stages the number of virtual nodes assigned to it (nN(u)), and the nuimber of virtual links traversing it(n,(D)). More formally, if SN(v) denotes the stress of substrate node v, then 4. 1. Stressbalancing embedding (sbe) SN(v)=a nN(v)+B n(v), VvEv The goal of the first heuristic is to produce low and balanced Modifying the positive parameters or and B in the above defini stress on substrate nodes and links while making sure that the tion will change the importance given to each component of node worst controllertoswitch delay does not exceed a certain thresh stress. If hosting a virtual node is considered to cause more stress old Reducing stress on nodes is important for decreasing the pos for a substrate node than being part of a virtual link, x will be as ibility that resources such as CPu processing power and flow signed a bigger value relative to B, and vice versa. In a special case tables will get exhausted Keeping stress low on links helps avoid if(a, B)=(1, 0), the definition reduces to the simpler form given in congestion and may result in a lower percentage of the link's band [8]. We assume all virtual nodes place an equal load on a substrate width being consumed For delays, we use a threshold r to limit node so we only take into account the number of virtual nodes the maximum controllertoswitch delay. mapped to a substrate node in the above calculation We borrow the concept of neighborhood resource availability For a substrate linke e, total link stress is the sum of data traf (NR)for substrate nodes from [8] fic stress and contr I traffic stress. Data traffic stress is placed on e by virtual links traversing it( tr(e) is the number of such virtual NR(v)=(S maxSN(D).2ISumaxSi(e) links), and each virtual link contributes an amount equal to the ra tio of its bandwidth demand and the capacity of e Control traffic tress is a weighted contribution for each controllertoswitch path SNmax= maxvevSN(v) is the maximum node stress, and going over this link. For controller Ci, each controllertoswitch SLmax= maxeEE SL()is the maximum link stress in the substrate. L, connection contributes "i to the stress of each link on the path, in the set of substrate links adjacent to u where 0< yi<1. Let cile) denote the number of controllerto A high nr signifies that the node and the links connected to it switch connections traversing link e in the ith vn out of numV total are lightly loaded We make use of nr to inform our node selection VNs in the systen. More formally, if Si(e)denotes the stress of sub process. The main idea in this technique, similar to [8], is to map strate link e. then highdegree virtual nodes to substrate nodes with high nr, since highdegree virtual nodes are going to set up more connections tr() demand SL(e) n:C;(e),Ve∈E 2 and need more resources We perform this mapping in a controlled 台cp(e) way to ensure that the delay threshold r is not exceeded The de tails of the heuristic are shown in Algorithm 1, and an explanation In calculating the link stress, the demand of a virtual link is of the steps of the heuristic is given below. capped at the lowest substrate link capacity in the corresponding Step 1.0. Precomputation of pairwise delays: Given the substrate path since that is an implicit limit on the highest rate the virtual network topology(V, E) and the delays between neighboring link can achieve. if bandwidth demands are not known in advance nodes, find the shortest path between all VV 1 node pairs we assune they are all equal. yi can be different for each VN and populate the pairwise delay matrix for all these pairs depending on the intensity of its control traffic. A higher vi would Step 1. 1. Mapping VNs with fixedlocation controllers: Assume signify that the load caused by control traffic is more important for the heuristic is given numV VNS, numF of which having fixed con this vn than that in a VN with a lower i value troller locations For each of these numf VNs, it finds all substrate The formal problem definition for VN embedding in software nodes whose distances from the controller are at most r to form defined networks is given below. the set of potential hosts, H, for virtual nodes. Then, it performs d c Let Slice; be the ith slice sharing a network of switches The vir onetoone mapping between virtual and substrate nodes such al topology of this slice, VT, defines the nodes and links included that virtual nodes with higher degrees are mapped to substrate in this slice. VT: is described as a graph(V;,(), where V, is the set of nodes with higher NRS within the set H. After that. it maps each virtual nodes, and e; is the set of virtual links. This slice, along with virtual link to the shortest path between its source and destina s controller Ci, constitute virtual network N Our problem can tion nodes then be stated as follows Step 1.2. Mapping VNs with adjustablelocation controllers: After Given the virtual topology of all numV VNs, and information as the above step, the heuristic moves onto the VNs with adjust to whether the location of each Ci is fixed or adjustable, organize blelocation controllers It orders the VNs according to their sizes, all VNs in a way that will(1) minimize the maximum stress on a i.e. VNs with the most virtual links are mapped first. The controller switch or link while keeping all controllertoswitch delays under for the biggest VN is attached to the available substrate node with a threshold r, or(2)minimize the average controllertoswitch de he highest NR value, and then, the heuristic maps its nodes one by lay for each N; while keeping the maximum stress under a thresh one, according to the rules in Step 1. 1, and repeats this until all vNs old t are mapped Picking all nodes from H ensures that we never go over the de 4. VN embedding techniques lay threshold R for any vn. The rest is fixing all controllers to high Nr nodes and performing the mappings according to the high In this section, we describe two heuristic methods to tackle degree to high principle advocated in [8 to produce low and the NPhard vn embedding problem by addressing virtual balanced stress. M. Demirci, M. Ammar/Computer Communications 45(2014)110 4.2. Delayminimizing embedding(Dme) Algorithm 1. Stressbalancing embedding heuristic(sBe) 1: Input: Substrate network(V, E, numF VNs with fixed The second heuristic primarily aims to minimize average delays location controllers(N1,., NrumF), numVnumF VNS between Vn controllers and switches used by the vn. Keeping with adjustablelocation controllers(nnumF+1,., Nnumv these delays low is crucial for the timely response of the controller where numF< numb, and the maximum delay threshold to switch events that require intervention. The maximum stress is R not minimized but it is controlled by an upper limit t we define t 2: Compute the shortest path for all node pairs(x y)st as a pair(n, ti)to be able to impose limits on both maximum x,ycV node stress and maximum link stress These limits can be high or 3: Calculate the delay for all such node pairs low relative to each other depending on what we want to priori 4:fori1→ numf do tize. the main idea is to select nodes that are near their corre 5: Find the set h of nodes such that the delay from Ci to the sponding controllers, and then rerouting to avoid exceeding node is at most r stress thresholds. The technique is shown in algorithmic form in 6: Calculate the nr for all members of h Algorithm 2, and the operation is described in detail in the follow 7: Sort all virtual nodes in Vi in the order of decreasing node Ing steps: degree in the virtual topology. Step 2.0. Precomputation of pairwise delays: Given the 8:forj=1→l substrate network topology (V, E) and the delays between 9: Map vi to h s.t. Nr(h)=maxveHNR(v). neighboring nodes, find the shortest path between all V.V1 10: Remove h from h node pairs and populate the pairwise delay matrix for all these 11: end for paIrs. 12:forj=1→E Set the path for virtual link ei to the shortest path L Step 2. 1. Mapping VNs with fixedlocation controllers: Given numy Is, numF of which having fixedlocation controllers, the heuristic between its source and destination tarts by ranking the switches in the substrate by the delay from the controller of each of these numF VNs. For each of these numF 14: end for 15: end for VNs, it then performs a onetoone mapping between all virtual nodes and the substrate nodes that are closest to the controller 16: Order remaining VNs in terms of decreasing number of such that the stress on any of the substrate nodes will not exceed virtual links 17: for i=numF+1 nunV do TN after this stage. It determines the shortest path between the pair of nodes in each virtual link and selects that as the route for the 18: Calculate nr for all substrate nodes virtual link 19: Attach Ci to the node with the highest nr value Step 2. 2. Mapping VNs with adjustablelocation controllers: The 20: Find the set h of nodes such that the delay from ci to the heuristic orders the vNs according to their sizes, i.e., VNs with node is at most r the highest number of virtual links are mapped first. For each VN 21: Sort all virtual nodes in Vi in the order of decreasing to be mapped, it finds three nodes with the lowest average dis lode degree in the virtual topology tance to all the other substrate nodes and attaches the controller 22:forj=1→vldo of the vn to the node with the highest NR out of that three. Then 23: Map v to h E H s.t. NR(h)=maxyeH NR(v) it performs the above described fixedcontroller VN mapping 24: Remove h from h procedure 25: end for Step 23. Virtual link rerouting: After the initial mapping of all 26:forj=1→Edo VNs is completed, the next step is ensuring that the maximum 27: Set the path for virtual link e to the shortest path stress threshold t is not exceeded. to this end. the heuristic takes between its source and destination advantage of the rerouting possibilities presented by the underly 28: end for ing SDN substrate to move virtual links away from highly stressed 29: end for substrate nodes and links that are causing t to be exceeded. It cal 30: Return the final mapping and quit culates the stress on every substrate node and link, and then the maximum node stress, SNmax= maxey SN(v), and the maximum link stress, SI.max=maxeFSr(e). If either SNmax exceeds TN or S,max exceeds TL, then the heuristic performs rerouting such that each B B 12 C Substrate topology with delays owestce ay mapping DME mapping Fig. 2. Numbers next to edges represent link delays in ms Nodes marked with a v'are virtual nodes. a star next to a node signifies that the controller is placed at that location M. Demirci, M. Ammar/Computer Communications 45(2014)110 virtual link traversing a substrate node/link whose stress the node with the largest nr helps situate the vn in a relatively exceeds the threshold is remapped to the next shortest path that empty area in the substrate and routing flexibility is exploited to does not traverse said node/link, until both SNmax TN and limit maximum stress Smax≤T1 5. Evaluation Algorithm 2. Delayminimizing embedding heuristIc (dme 1: Input: Substrate network(V, E), numF VNS with fixed In this section, we evaluate our VN embedding techniques with location controllers(N1,., NnumF), numVnumF VNs with simulation and Mininet [5 emulation. We perform VN embed adjustablelocation controllers(NnumF+1,., Nnumv) where dings in an offline manner, assuming all VN requests are known numf numV and the maximum stress threshold 2: Compute the shortest path for all node pairs(x, y).t 5.1. Metrics Xy∈V 3: Calculate the delay for all such node pairs Below are the metrics that we use to evaluate our vn embed 4:fori=1→ numf do ding techniques 5: Sort all nodes in Ni according to delay from Ci 6: Available nodes←V Controllertoswitch delay: average and maximum (for each VN) Node stress: average and maximum (across the 7:forj=1→v substrate Map yi to the available node v; such that yj is the Link stress: average and maximum ( across the closest to Ci and SN(vi)+a< TN (a is from Eq (1). substrate 9: Remove vi from the list of available nodes for n Endtoend delay: average(for each VN) 10: end for Throughput: average rate of data delivery on all 11:forj=1→Edo virtual links over the period of data 12: Set the path for virtual link e to the shortest path transfer(for each VN). For a virtual between its source and destination link, this is calculated by dividing 13: end for the amount of the data transferred 14 end for over that link by the time spent to 15: Order remaining VNs in terms of decreasing number of complete the transfer. virtual links 16: for i=numF+1 nunv do As controllertoswitch delay and stress on substrate compo 17: Calculate nr for all substrate nodes nents are two things that we are optimizing for, we study how they 18: Find the 3 substrate nodes with the lowest average are affected by different types of embedding through simulation. In distance to other nodes addition, we want to gain insights as to how these goals are influ 19: Attach Ci to the one with the highest nr among this 3 encing vn performance metrics, such as endtoend delays and 20: Available nodes←V throughput. to this end, we emulate scenarios on Mininet to 21: for j 22 Map vi to the available node vj such that u is the with different embedding methods nd throughput are changing Understand how endtoend delays closest to Ci and SN(vi)+as TN 23: Remove 1: from the list of available nodes for n 5.2. Strategy 24: end for As substrate networks, we utilize 10 different topologies from 25:forj1→E 26: Set the path for virtual link e to the shortest path the Internet Topology Zoo [ 16. These topologies vary in size and between its source and destination shape, allowing us to evaluate our techniques with different net work properties. We construct 20 different virtual topologies, rang 27: end for 2 8 end for ing from 5 nodes to 20 nodes For each of these virtual topologies, ndomly select a coeffi he range[0.3, 0.7] as the prob 29 Calculate stress for each node in v and each link in e ability of connection between any two virtual node pairs. Thi 30: SNmax +maxveVSN(v), Simax maxeEESi(e gives us some variation in graph density. We randomly assign 31:tnax←v∈Vs.t.SN()= SNmax fixedlocation controllers to 5 of these VNs, the rest have adjust 32:emax←e∈Est.SL(e)S 33: if SNmax Tn or SLmax >tL lblelocation controllers (except for the part of the evaluation 34: Until SN(Umax )< TN, reroute virtual links away from vma where we vary the percentage of fixedlocation controllers, in to the next shortest path that does not traverse vr Section 5.3.5) The parameters in the node stress formula from Section 3 are 35: Until Si(emax)< TL, reroute virtual links away from emax lected as(a, B)=(1, 1). We assume all virtual link demands are to the next shortest path that does not traverse ema the same, and also equal to all substrate link capacities For y 36: else we pick a random value from the range 0,0.5] for each VN sepa 37: Return the final mapping and quit 38: end if rately. This provides a variation in the contribution of control traf fic toward link stress for different VNS. We do not let 'i go over 0.5 39: Go to 29 in this experiment because that could cause control traffic to dom inate link stress and lower the number of viable locations for con trollers, thus reducing the flexibility in controller placement(more this at the end of th on, in Section 5.3.6) The delayminimizing embedding results in low controllerto We compare SBe(Algorithm 1)and de(Algorithm 2)against switch delays because it greedily selects switches that have the two simpler variations: pure stressbalancing mapping and lowest delay to the controller. Attaching the central controller to naive delayminimizing mapping. Pure stressbalancing mapping M. Demirci, M. Ammar/Computer Communications 45(2014)110 executes sBe without regard to delays (i.e, with an extremely high significantly. However, unless stress thresholds are unreasonably delay threshold r). naive delayminimizing mapping places the low, dme may be able to get away with rerouting only a small adjustablelocation controllers randomly, and then maps virtual fraction of virtual links nodes to the closest possible substrate nodes to minimize control lertoswitch delays, similar to dme yet without any attention to 5.3. 2. Controllertoswitch delays stress. We also consider purely random mapping, which performs We look at how different embedding techniques affect the de virtual node mapping and controller localization completely ran lays between the Vn controller and the switches in the VN. We domly over the entire substrate but it performs badly enough to disrupt graph scales, so we do not show it in all graphs and we de consider both average and maximun controllertoSwWitch delays for each VN: the average is calculated over all of the switches in clare it infeasible for practical use compared to the other options We run evaluations with the following objectives cluded in a given VN, and the maximum is the delay from the con oller to the farthest switch in the vn Average and maximum controllertoswitch delays for all vNs Comparing average and maximum controllertoswitch delays for SBE, DI ME, and two simpler variations of these are shown in Figs. 3 and 4 respectively, for SBE, DMe, naive de layminimizing mapping, and pure stressbalancing mapping Each techniques, data point in these graphs represents the value for one of 20 vNs, ii. Comparing average and maximum stress for the same four averaged over mappings to 10 substrate topologies. All 20 values techniques, produced by the same technique are sorted in increasing order iii Comparing average endtoend delays and throughput using and then plotted. The Xaxis is labeled"Fraction of VNs"because Mi iV. Varying the percentage of vNs with fixedlocation control the xcoordinate corresponding to a yvalue signifies the fraction of all VNs that have a delay less than or equal to that yvalue. lers to see how this affects metrics v. Varying stress threshold t and the contribution of control VNs in this experiment (i.e, 4 out of 20)have delays of at most 10 ms, for the particular technique that the data point belongs to To produce results, we map all 20 VNs together to each of the substrate topologies using all of the different techniques to be eval uated. For each VN, we average the resulting metrics over the 10 pure stress balai substrate topologies. SBE uses a controllertoswitch delay thresh DME . old R of 50 ms, which is identified as a common target for maxi naive delay minimizing mum latency in [15 because it is the target restoration time of a SoNET ring. DME uses a variable stress threshold T=(N, tL) depending on the stress values achieved by sbe for the same sce nario. by default Tn and ti are set to be 50% more than the snmax and SLmax procuded by SBe, respectively, for a given substrate and set of vNs, howeyer we evaluate the effect of different t values in section 5.3.6 四0599000 53. Results 最=: 5.3.1. DME with a small example Before moving onto larger topologies, let us demonstrate the 00.10.20.30.40.506 0.80.9 properties of one of our heuristics: DME. We consider placing a Fraction of ns 3node vn on a 5node substrate topology with link delays ranging Fig. 3. Average controllertoswitch delays for all VNs: SBE, DME, naive delay from 5 ms to 20 ms. There are C(5, 3)10 possible virtual node minimizing mapping and pure stress balancing mapping mappings, and 5 possible controller locations, resulting in a total of 50 VN mappings. Average controllertoswitch delays for these 50 mappings range from 5 ms to almost 17 ms DMe produces the mapping with the average controllertoSwitch delay of pure stress balancing 5.33 mS, the second lowest value among the 50. Fig. 2 shows the topology of the substrate network along with the lowestdelay DME i naive delay minimizing and dme mappings The simple 3node vn topology does not allow much variation in node stress, but link stress values are more variable. We set ? (control traffic coefficient to 0.5. If the link stress threshold Ti is set to 2.5, dme does not need to perform any rerouting. How ever, if Ti is reduced to 1.5, DMe manages to get under the thresh old by rerouting a virtual link and increasing its expected endto end delay from 16 ms to 30 ms in the process. This example gives us an idea about the behavior of dme. it seems that dme should be able to achieve optimal or nearoptimal controllertoswitch delays. It may or may not need to perform rerouting depending on stress thresholds. If rerouting is required dMe can reduce 00.10.20.3040.50.60.70.80.91 the maximun stress under the threshold even in a small topology Fraction of vns with very few route options. Controllertoswitch delays are not affected by rerouting since there is no node remapping, but Fig. 4. Maximum controllertoswitch delays for all VNs: SBE, DME, naive delay endtoend delays for rerouted virtual links may increase minimizing mapping, and pure stress balancing mapping 8 M. Demirci, M. Ammar/Computer Communications 45(2014)110 We use this Xaxis in the other graphs in the remainder of this Table 2 evaluation section as well Average and maximum link stress In Fig 3, we see that dme produces very close results to(in Avg link stress Max link stress some case better than) the naive delayminimizing mapping, even Pure stress balancing 6.5 9.8 though the former is also trying to limit stress. We infer that the 10.9 stress thresholds Tn and ti do not significantly affect the mapping DME 10.3 16.1 n most cases, and when they do, the effects are minimal, possibly Naive dclay minimizing 12.7 24.3 because dme utilizes minimally invasive rerouting in Step B.3. in stead of remapping nodes in cases where stress thresholds are ex ceeded after the previous steps. SBE and the pure stressbalancing random heuristic produce higher delays, but sBe is able to perform a bit better than pure stressbalancing mostly because it forces itself DME… naive delay minimizing. to keep controllertoswitch delays under the threshold r as it is doing the mapping Maximum delays shown in Fig 4 exhibit a similar pattern: Ma imum delays for DMe and naive delayminimizing mapping are close to each other and maximum delays for the other two tech E9卫 niques are higher as expected. We see several instances where the worstcase delay for SBe is close to the threshold of 50 ms, phile the worstcase delays for pure stressbalancing exceed 50 ms in those cases. This suggests that sbe has made an active ef 10 fort to keep the maximum delay under 50 ms 533 Node and link stress 00.10.20.3040.5060.70.80.91 We now analyze the impact of the heuristics on node and link Fraction of vns stresses. For this experiment, we use the results collected from the simulation in the previous subsection( Section 5.3.2). But in Fig. 5. Average endtoend delays for all VNs: SBE, DME, random mapping, and the naive delay minimizing heuristic stead of reporting stress values per vN, we focus on the overall average across the entire substrate in all 10 topologies Average and maximum node stress values from all runs are shown in Table 1, and average and maximum link stress values are shown in Table 2 for all four techniques considered while random these values do not tell much on their own, a comparison among naive delay minimizing then yields the following: SBe performs comparably to pure stress balancing, and it may be preferable since it provides significant savings in maximum controllertoswitch delays. The naive de 16 layminimizing heuristic is about twice as bad for stress as optimal heuristics, and dme performs somewhere in between these ends 12 due to its stress balancing components 5.3.4. Endtoend delays and throughput 8 For this part of the evaluation, we use Mininet 2.0 to emulate the operation of an sdn with multiple vNs placed on it. 10 differ ent VNs are embedded on 3 substrate networks sliced using Flow 00.10.20.30.4050.60.70.80.9 Visor. Bandwidth for all substrate links is set to 100Mbps. We use Fraction of vns ping to measure endtoend delays, and execute file transfer be tween every pair of nodes via TCP with Iperf [17 Fig. 6. Average throughput for all VNs: SBE, DME, random mapping, and the naive Fig 5 demonstrates average endtoend delays from SBE, DME, delay minimizing heuristic. random mapping, and the naive delayrminimizing mapping DMe is performing considerably better than SBe and random mapping, situations due to forced rerouting increasing endtoend delays offering an average of 45% reduction compared to sbe and a 65% in DMe sbe does better than random mapping, probably because reduction compared to random mapping. DME tends to cluster it tries avoid distant lowdegree nodes the virtual nodes of a Vn as closely as possible without exceeding Fig 6 shows average throughput results collected over 20 emu stress bounds, so it is good at minimizing both controllertoswitch lations. DME achieves slightly higher throughput than random delays and endtoend delays. The naive delayminimizing map mapping since it actively avoids nodes with unacceptably high ping heuristic performs closely to DME, and even better in some stress, but they are still comparable in terms of averages. The naive delayminimizing heuristic performs the worst since it maps the VN in a confined area without any regard for node and link stress Table 1 Average and maximum node stress The stressbalancing SBe performs considerably better than the other methods. Also, there is less variation in achieved throughput Avg node stress Max node stress among different VNs(the highest average is 43% more than the Pure stress balancing 114 21.0 lowest, as opposed to 57% for DME and 67% for random mapping SBE 12.1 23.5 indicating a more balanced network. These results suggest that our DME 324 Naive delay minimizing 19.2 41.1 techniques translate into improved performance in a realistic net ork emulation environment M. Demirci, M. Ammar/ Computer Communications 45 (2014)110 Table 3 Average and maximum node stress with varying numF/numv ratios for SBe numF/numv= num F/numV=0.75 x cumInum=0.5… Avg node stress Max node stress num F/numV=0.2 rumF/num∨=0— numF/numV=0 10.8 17.1 numF/numV=0.25 119 212 numF/numV=0.5 12.8 numF/numV=0.75 13.6 numF/numB= 1 14.3 31.6 b 40 5.3.5. Varying the percentage of fixedlocation controllers In our model, we provide the option of fixing the location of the E20 .E…日…日…日… controller because a user may want to place the controller for her VN at a certain location, such as her home PC or a server at a spe =2♀日口 cific data center Assume there are numv vns to be placed numF 20.3040.50.60.70.80.91 Ith fixedlocation controllers and the remaining numb F Fraction of ns with adjustablelocation controllers e run simulations with 5 different numF/numv ratios: 0, 0. 25, 0.5, 0.75 and 1. We use the Fig 8. Maximum controllertoswitch delays for all VNs: DME with varying same 20 VNs we have been using throughout this section and 3 numF/numv ratios substrate topologies for this experiment. For each topology, we run the experiment 10 times and average the values for each VN from all mappings numF/numV. For both metrics, a higher percentage of fixedloca We evaluate SBe and dMe, both at their strong suits: minimiz tion controllers leads to higher delays due to decreased flexibilit ing average stress for SBE, and minimizing controllertoswitch de and suboptimal controller locations. However, this effect is more lays for dme. We present results regarding four metrics: average pronounced with the maximum delay values, and for smaller per and maximum node stress for SBe, and average and maximum con centages (as seen from percentagewise bigger differences toward trollertoswitch delay for DME. We do not give results for link the bottom in Fig 8). A possible explanation of this situation is that stress separately because node stress results are sufficient in dem yith the large number of VNs on the substrates, fixing more of the onstrating the relevant trends. controllers has a smaller effect on the average since some of the Table 3 displays average and maximum node stress across the fixed controller locations may actually end up being suitable by substrate achieved by sbe at 5 different values of numF/numv chance. On the other hand, fixing the location of another controller We observe approximately 30% increase in average node stress increases the probability of hitting a bad controller location (i.e and 85% increase in maximum node stress as the numF/numV ratio one that is not suitable for delay minimization), so maximum delay goes from 0 to 1. An increase in stress is expected since some of the values rise faster for low numF/numV ratios But as the ratios get fixedlocation controllers can be attached to nodes with low de larger, the probability of having already hit the worst controller grees and nr values that are suboptimal for stress minimization location also increases, so maximum delays do not rise as fast for The maximum stress is affected more because as the percentage high numF/numv ratios. of fixedlocation controllers increases, so does the probability of Therefore, the takeaway from this exercise is that an unlucky combination of fixed controller locations that puts mul tiple controllers close to each other, thus making the occurrence of The variation in the percentage of VNs with fixed controller a highstress node more likely. This impact becomes lessened for locations has a bigger effect on maximum values than aver high numF/numv ratios because the damage is already done by ages, particularly maximum controllertoswitch delays then ii. For low percentages, the negative effects that come with Figs. 7 and 8 show average and maximum controllertoswitch fixedlocation controllers are mild delays for all VNs achieved by dme at 5 different values of iii. For high percentages (75% and up), the flexibility that comes from adjustablelocation controllers has negligible positive Impact numF/numv=1 numFinumV=0.75k 5.3.6. Varying T and y 30 numF/numV=0.5 numF/numV=025…… In order to gain insight into how the stress threshold t affe numF/numV=0. the results produced by dme, we look at different levels of T. For our previous experiments, we had set the two components of T, TN and Ti, to 50% more than SNmax and SLmax produced by sBe 20 Let us define a stress allowance multiplier, denoted by o, such that Q TN=G SNmax and tL=o. SLmax. So far, we have used o=1., and a15 we now evaluate a few other values for g Table 4 summarizes our findings. We only look at average and maximum controllertoswitch delays because stress values Table 4 Delays with varying T for DME 0 Avg delay (ms) Max delay(ms) 00.10.20.30.40.50.60.70.80.9 G=1 12.37 44 Fraction of vns 24, G=1.5 Fig. 7. Average controllertoswitch delays for all VNs: DME with varying 1389 7.65 13.89 numF/numb ratios 10 M. Demirci, M. Ammar/Computer Communications 45(2014)110 Table 5 ii. The presence of the central controllers in softwaredefined Delays with varying y for DME networks as critical nodes has a significant impact on VN Avg delay(ms) Max delay (ms) embedding objectives and the locations of controllers must =0 7.49 lly in order to better optimize for perfo =0.25 8.95 16.04 mance goals γ=0. 10.76 23.12 =0.75 2547 To our knowledge, this paper presents the first effort to con 11.91 sider vn embedding and sdn controller placement together There are avenues for future work regarding this problem. First, are directly dependent on o so it is not very interesting to study one can envision a coordinated embedding solution where con stress in this case values are averaged over 20 VNs placed over 3 troller placement, virtual node mapping and virtual link mapping substrates, so the maximum delays here are averagemaximum stages are not sequential. Second, evaluation may be improved via delays When (= 1, there is a tight control over stress, which al hich al a dynamic system where VN requests are not known in advance lows less freedom in the effort to minimize delays, which rise by but arrive at different times, and or via more finelytuned vN re about 50% on average compared to the case when C=1.5. Beyond quests that include varying resource deantis explicit informa this, the gains are marginal. For o=2 and g=3, there is no signif tion about preferred controller location options etc. Third, VN icant reduction in delays, except for a few cases where maximum reconfiguration (reassignment or migration in sdn is a natura delays can be reduced thanks to the extra degree of freedom. extension and an important problem that we are planning to con Therefore, 0=1.5 appears to be a reasonable choice for DMe, centrate on next and we use that for every other experiment in this evaluation Another parameter that we experiment with is y Acknowledgements defining link stress in section 3, the definition of link stress affects both mapping techniques and potentially all metrics, but we are This work was supported in part by NsF grants CNS 1319490 presenting the effect we found the most interesting. For this simu CNS1017152 and cns1017237 lation, we assume , is equal for all VNs, and evaluate 5 different y values. Table 5 presents the controllertoswitch delay results References again averaged for 20 VNs placed over 3 substrates We see that [1 N McKeown, T. Anderson, H Balakrishnan, G. Parulkar, L Peterson, J. Rexford, the delays increase with increasing ,, but a hit more slowly after S. Shenker, J. Turner, Openflow: enabling innovation in campus nctworks, 2=0.5. This effect is probably due to the fact that when ?in SigComMcoMput.CommunreV.38(2)(2008)6974,http://dx.doi.org/ creases. control traffic and thus the locations of the controllers 10.1145/1355734.1355746 and the links around it)become more critical in determining link [2]R. Sherwood, G. Gibb. kxYap, G Appenzeller.MCasado,N.McKeown,G stress. This takes away some of the ability to move the controllers Ninth USENIX Con ference on Operating Systems Design and me dings of the freely to minimize delays because if a controller is moved to a low NR node, it will be difficult to keep link stress within bounds [3 D. Rutskoy, E. Keller, J Rexford, Scalable network virtualization in software definednetworksIeeEInternetComput17(2)(2013)2027,http:// Hence, stress becomes the dominant factor in controller place dx. doi. org/10.1109/MIC2012.144. ment, causing delays to rise. but they do not rise too much because [4geni:globalenvironmentfornetworkinnovations<http://www.geni.net>. even with less flexible controller locations, dME is still a delay [5B. Lantz, B Heller, N. McKeown, a network in a laptop: rapid prototyping for softwaredefined networks in: proceedings of the ninth ACm sIgComm minimizing heuristic and it still has flexibility in virtual node Workshop on Hot Topics in Networks, HotnetsIX. ACM. New York, NY, USA, placement to keep delays as low as possible. 2010,pp.19:119:6,http://dx.doi.org/10.1145/1868447.1868466. [6J. Turner, D. Taylor, Diversifying the internet, in: Proceedings of IFFF GLOBECOM. 2005 G Conclusions and future work [7 N Feamster, L Gao, J Rexford, How to lease the internet in your spare time, SIGCOMM Comput. Commun. Rev. 37(1)(2007)6164 8Y. Zhu, M. Ammar, Algorithms for assigning substrate nctwork resources to In this work, we have studied techniques to perform vn map virtual network components. in: Proceedings of IEEE INFOCOM, 2006 ing on an SDN substrate. The goals of our techniques were load [9]. Lu, J Turner, Efficient mapping of virtual network onto a shared substrate, balancing between switches as well as delay minimization between Tech rep, Washington University in St Louis, June 2006. [10 M. Yu,Y. Yi, J. Rexford, M. Chiang, Rethinking virtual network embedding controllers and switches. Each technique focuses on optimizing for ubstrate support for path splitting and migration, SIGCOMM Comput one of these goals while keeping the other one in check. Both Commun.Rev.38(∠J08)1729.http://dx.doi.org/10.1145/1355734.1355737 techniques couple vn controller placement with virtual node and [11 D.G. Andersen, Theoretical approaches to node assignment, Comput. Sci. Dep link assignment. Various input parameters in our definitions and 2002)86 [12N. Chowdhury, R. Boutaba, A survey of network virtualization, Comput techniques determine the extent of flexibility in embedding efforts Networks54(5)(2010)862876 and the range of improvements in evaluation metrics. [13 A. Fischer, Botero, M. Beck, H. De Meer, X. Hesselbach, Virtual network The main takeaways from this work are the following embedding: a survey, IEEE Commun. Surv. Tutorials PP(99)(2013)119, http://dx.doi.org/10.1109/surv∠01301301300155 [14Nox.<http:/www.noxrepo.org/>. i. There is a tradeoff between minimizing controllertoswitch 1 15 B Heller, R. Sherwood, N. McKeown, The controller placement problem, in delays and balancing the load on substrate nodes and links, Proceedings of the First Workshop on Hot Topics in Software Defined Networks,Hotsdn'12,Acm,NewyoRk,Ny,Usa,2012,pp.712,http:// however, these two goals are not in direct conflict each dx. doi. org10.1145/2342441.2342444 other. While it may not be possible to optimize both [ 16S. Knight, H Nguyen, N Falkner, R Bowden, M. Roughan, The internet topology goals at the Same time, it is quite possible to achieve near Zoo.IeEeJ.Sel.AreasCommun29(9)(2011)17651775.http://dx.doi.org 10.1109/SAC2011.111002 optimalresultsforonemetricwhilekeepingtheother[17IperftcpandUdpbandwidthperformancemeasurementtoolchttp:I/ metric within reasonable bounds rf.sourceforge. net/
 183KB
虚拟网络嵌入算法的研究
20210307虚拟网络嵌入算法的研究
 15.28MB
仿淘宝网多用户购物网站系统正式版
20140719如电脑数码手机销售、服装销售、化妆品销售、鲜花蛋糕、鞋帽箱包、软件产品销售、虚拟服务销售、游戏点卡充值卡销售、医药销售、酒店预订、房间预订、古董书画、建材家居家具、文具办公用品、家用电器、礼品饰品、...
 845KB
Android应用程序开发教程PDF电子书完整版、Android开发学习教程
20110330• LibWebCore LibWebCore LibWebCore LibWebCore  一个最新的 web 浏览器引擎用，支持 Android 浏览器和一个可嵌入的 web 视图。 • SGL SGL SGL SGL  底层的2D 图形引擎 • 3D3D3D3D libraries libraries ...
 1.56MB
02408仿天涯论坛模板的免费论坛系统（php在线问答系统源码）v2.0.zip
20190707也可让网站攻击者无法猜解密码，有过网站运营经验的人更懂，其中包含的更多更多深层奥秘（管理会员、虚拟活跃用户、虚拟订单、创建更宽泛话题...），成倍降低运维工作量。 这个仿天涯论坛模板的免费论坛系统在用户...
 18.68MB
单片机应用技术选编(9).(北航出版.何立民)
20160609本书是第9卷，选编了20002001年间443篇文章。其中全文编辑120篇，其余323篇摘要编辑。 注：原书无书签。为了方便阅读，本人在上传前添加了完整详细的书签。 目 录 第一章 专题论述 1.1 集成电路进入片上系统时代...
 708KB
跨多个网络域实现有效的虚拟网络嵌入
20210316跨多个网络域实现有效的虚拟网络嵌入
 487KB
基于子图的高效虚拟网络嵌入算法
20210318基于子图的高效虚拟网络嵌入算法
 14.38MB
韩式服装网店发布系统源码下载
20091227户外、军品电子商务商城购物系统、旅游、机票,网络游戏虚拟商品交易区,电玩，动漫，Cosplay，周边,居家日用，装饰，文具，园艺,邮币，古董，字画，收藏,汽车，摩托，自行车,家庭装修，五金工具网上购物系统. ...
 24KB
c#学习笔记.txt
2008121551099在线学习网发布 文章来源：网络收集 发布时间：20060525 字体： [大 中 小] 51099在线学习网 http://www.51099.com 1, 结构(struct) 与 类(class) [attributes] [modifiers] struct identifier [:...
 48B
asp.net知识库
20150618翻译MSDN文章 —— 泛型FAQ：最佳实践 Visual C# 3.0 新特性概览 C# 2.0会给我们带来什么 泛型技巧系列：如何提供类型参数之间的转换 C#2.0  Object Pool 简单实现 Attributes in C# 手痒痒,也来个c# 2.0 object ...
 179B
史上最好传智播客就业班.net培训教程60G 不下会后悔的
20130708功能点 站内搜索、栏目管理、视频播放（完全模仿优酷视频页面）、焦点图、静态页面生成（新浪、搜狐等大型网站普遍采用的技术）、文章管理、无刷新评论、评论的无刷新分页、敏感词过滤、用户管理、友情链接管理、...
 65.6MB
ASP.NET开发实战1200例(第2卷).(清华出版.房大伟.吕双).part2
201606121.2 网络信息的站内搜索 实例024 一般搜索 实例025 高级搜索 实例026 常用搜索 实例027 在自己的网站中加入Baidu和Google搜索 实例028 龙行天下搜索引擎中智能匹配检索功能 1.3 思维扩展的常用算法 实例029 ...
 896KB
基于虚拟拓扑连接特征的虚拟网络嵌入算法
20210318基于虚拟拓扑连接特征的虚拟网络嵌入算法
 127KB
基于拓扑收敛度的虚拟网络嵌入新方法
20210317基于拓扑收敛度的虚拟网络嵌入新方法
 255KB
动态资源块生成的基于共享的虚拟网络嵌入算法
20210309动态资源块生成的基于共享的虚拟网络嵌入算法
 1.49MB
基于统一增强粒子群算法的虚拟网络嵌入算法
20210310虚拟网络（VN）嵌入是网络虚拟化的主要挑战。 本文旨在通过优化VN嵌入成本来提高VN的接受率和基础设施提供商的收入。 我们首先建立两个用于VN嵌入的模型：不支持路径拆分的衬底网络的整数线性规划模型和支持路径拆分的混合整数规划模型。 然后，我们提出了一种基于统一的增强型粒子群优化算法的VN嵌入算法，称为VNEUEPSO，以解决这两种模型，而无需考虑路径拆分的支持。 在VNEUEPSO中，根据VN嵌入上下文很好地重新定义了粒子的参数和操作。 为了减少链接映射阶段的时间复杂度，在不支持路径拆分的情况下，我们使用最短路径算法进行链接映射，而在其他情况下，则建议采用贪婪k最短路径算法。 此外，提出了从大到大和从小到小的首选节点映射策略，以实现更好的收敛性和基板网络的负载平衡。 仿真结果表明，我们的算法在VN接受率和长期平均收入方面明显优于以前的方法。
 8KB
史上最好传智播客就业班.net培训教程60G 不下会后悔
20160312功能点 站内搜索、栏目管理、视频播放（完全模仿优酷视频页面）、焦点图、静态页面生成（新浪、搜狐等大型网站普遍采用的技术）、文章管理、无刷新评论、评论的无刷新分页、敏感词过滤、用户管理、友情链接管理、...
 68.0MB
ASP.NET开发实战1200例(第2卷).(清华出版.房大伟.吕双).part1
201606121.2 网络信息的站内搜索 实例024 一般搜索 实例025 高级搜索 实例026 常用搜索 实例027 在自己的网站中加入Baidu和Google搜索 实例028 龙行天下搜索引擎中智能匹配检索功能 1.3 思维扩展的常用算法 实例029 ...
 199KB
网管教程 从入门到精通软件篇.txt
20100425DUN：Microsoft拔号网络导出文件 DV：数字视频文件（MIME） DWG：AutoCAD工程图文件；AutoCAD或Generic CADD老版本的绘图格式 DXR：Macromedia Director受保护（不可编辑）电影文件 E EDA：Ensoniq ASR磁盘映像...
 6KB
.htaccess
200707190516 14:04（文章来源）http://www.dnpark.com.cn/news/mm/www/1179329504375ZKlMSgYr.html<br><br>Apache服务器的.htaccess是一个非常强大的分布式配置文件，学会使用.htaccess，对虚拟主机用户来说，可以实现众多...

下载
memoryset.zip
memoryset.zip

下载
eetop.cn_LAB2_20130402_70302250.pdf
eetop.cn_LAB2_20130402_70302250.pdf

下载
099铁路行业发展研究报告V7.0.docx
099铁路行业发展研究报告V7.0.docx

下载
浅谈网络攻击手段宁夏大学
浅谈网络攻击手段宁夏大学

下载
西农java第六次实习报告.docx
西农java第六次实习报告.docx

下载
VScode1.49.3.zip
VScode1.49.3.zip

下载
需求分布不确定条件下的多周期库存鲁棒优化模型.rar
需求分布不确定条件下的多周期库存鲁棒优化模型.rar

下载
简历 模板参考.doc
简历 模板参考.doc

下载
西农数据库实验2.docx
西农数据库实验2.docx

下载
eetop.cn_SAR ADC的设计_983203834.pdf
eetop.cn_SAR ADC的设计_983203834.pdf