CN102624597B - Two-way sequencing virtual network mapping method - Google Patents

Abstract

The invention provides a two-way sequencing virtual network mapping method. The method comprises the following steps of: initiatively judging a state of a current virtual networking mapping system, and calling a corresponding sequencing method; using a forward sequencing method when a revenue scale of a current virtual network is less than a scale of remaining resources of a bottom-layer physical network; using a reverse sequencing method when the revenue scale of the current virtual network is equal to or greater than the scale of the remaining resources of the bottom-layer physical network; and finally, calling a corresponding mapping algorithm to map. According to the two-way sequencing virtual network mapping method, the state of the remaining resources of the current physical network is taken fully into account, the probability of bottleneck occurred on the bottom-layer physical network under medium-sized condition is reduced, and the success rate of the virtual networking mapping and the total revenue quantity of the virtual network with successful mapping are improved. The method provided by the invention also can be used by combining with various virtual network mapping algorithms, and has the characteristic of strong expandability.

Description

A kind of mapping method of virtual network of Bidirectional sort

Technical field

Network virtualization technology is one of important method promoting oriented Internet Architecture development, its essence is by abstract, distribute, isolation mech isolation test runs multiple virtual subnet independently on a public physical network, each virtual subnet can use separate protocol architecture, and reasonable disposition can be carried out according to the demand of user's dynamic change to whole nodes and link circuit resource, thus strengthen flexibility and the diversity of network, realize the measurable and controllable property of network, the distribution of peak optimizating network resource and scheduling, improve safety and service quality, reduce operation maintenance cost, in the hope of essence solve the Internet existing ossify, with patch and be updated to main current situation.

Network virtualization technology may be used for for the research of new network architecture provides the basis of shared Physical Experiment network, bottom physical facility provider and network service operators can also be separated by it simultaneously, the network of multiple operator is allowed to share same public bottom physical network architecture (link, switching node etc.), each network has neither by the Network resource share that other web influences can adjust again flexibly wherein, heterogeneous networks operator can adopt different procotols, the end-to-end service of innovation is provided, therefore network virtualization also gets a good chance of the main flow operation mode becoming a kind of future network.

Background technology

Virtual network mapping problems is then requisite link in network virtualization technology, its major function the virtual network requests of user (Virtual Request) is reasonably mapped to the bottom physical network facility (Substrate Network) that operator provides, mapping process not only will realize the separation between virtual network and be independent of each other, thus ensure the service quality (QoS) of each virtual network user, also to try one's best simultaneously and reasonably distribute bottom physical network resource, improve resource utilization.

Due to the diversity of virtual network requests topology, and node and link two groups of restrictive conditions need to consider simultaneously, and making multiple different virtual network to be mapped to a public bottom physical network becomes NP-hard problem.For solving this problem, lot of domestic and international researcher proposes based on time window model the mapping method that some realize suboptimal solution.Time window model refers to, adds up current all empty net mapping request, and once map in each time window, to mapping successfully request, and corresponding renewal bottom physical network state; The lost request lost of mapping, puts into waiting list by request; Or directly refuse this request after meeting certain condition.This process as shown in Figure 1.

In FIG, before using mapping algorithm to map virtual network requests in current time window, all to carry out preliminary treatment to the virtual network in time window, substantially the method that all algorithms use at present is all sort from big to small according to its income (Revenue) to the request of void net, the basis of this method is: preferential mapping takes in larger void net request, these requests can be made to map successful probability increase, thus can promote overall map and successfully take in quantity.But, this method is only applicable to the situation that empty net request scale is less than bottom physical network surplus resources scale, wherein, the scale of empty net and Physical Network refers to the node processing power (CPU) of network or the size of link bandwidth (BW), and when empty net request scale equals bottom physical network surplus resources scale, make to cause being mapped to power in this way to decline rapidly, overall map is successfully taken in and is also declined rapidly, this maps the larger void net request of income due to preferential in situation such as the scale of grade, the key component of the physical network surplus resources that scale can be caused suitable is occupied, node or link bottleneck is created thus in bottom physical network, these bottlenecks will make follow-up physical network surplus resources be used smoothly, thus cause and be mapped to power drop.

In addition, the situation that empty net request scale equals bottom physical network surplus resources scale is significant in empty net mapping problems: first, when void net request scale is greater than bottom physical network surplus resources scale, on the impact of mapped system with etc. scale situation similar, the process of scale situation such as therefore can to classify as; Secondly, when void net request scale equals bottom physical network surplus resources scale, new void net request sort method is needed successfully to take in quantity to promote overall map; 3rd, when void net request scale is less than bottom physical network surplus resources scale, along with previously mapping successfully and not completing void net request constantly the taking bottom Physical Network resource of service, bottom Physical Network surplus resources can reduce gradually and reach the situation equal with void net request scale.In sum, empty net request scale equals the situation that bottom physical network surplus resources scale is a kind of key, need a kind of rational method promote now be mapped to power and overall map successfully takes in quantity.

Summary of the invention

The present invention analyzes the situation that empty net request scale equals bottom physical network surplus resources scale, find now easily to cause bottom physical network to occur bottleneck by taking in the method sorted from big to small the request of void net, namely certain has mapped successfully and has taken in some key components that larger void net request can occupy bottom Physical Network surplus resources, surplus resources may be caused to be isolated, thus can not be follow-up empty net request service, reduce and map successfully empty net request total income.In order to address this problem, a rational starting point should be: on the bottom Physical Network surplus resources of the scale of grade, increases as far as possible and maps successfully empty net request total income.

The present invention, according to this starting point, proposes to use empty net request by the method taking in sort from small to large (sorting by reversals), equals the situation of bottom physical network surplus resources scale for void net request scale.The method of this sorting by reversals, makes to take in less void net request and is paid the utmost attention to, improve the success rate of mapping, reduces the possibility that bottom physical network bottleneck occurs.Meanwhile, due to the reduction of empty net granularity, Physical Network surplus resources obtains and utilizes more fully, namely maps successfully empty net request total income and is improved.

Finally, the present invention is positive and negative two kinds of sort methods comprehensively, devise a kind of mapping method of virtual network of Bidirectional sort.In the method, before the empty net request of each mapping, all by judging that this moment void nets the scale of request and bottom physical network surplus resources, if empty net request scale is less than bottom Physical Network surplus resources scale, then call forward sort method; If empty net request scale equals bottom Physical Network surplus resources scale, then call sorting by reversals method.During for the Bidirectional sort mapping method using the present invention to propose under the virtual network map environment of routine, map incipient stage empty network planning mould and should be less than bottom Physical Network surplus resources scale, now should call forward sort method; But along with mapping successfully and not completing empty net constantly the taking bottom Physical Network resource of service, bottom Physical Network surplus resources scale starts to reduce the nearly empty net request scale of not disconnecting, now should call sorting by reversals method, to ensure the success rate of mapping and to avoid bottom physical network to occur bottleneck.

The definition that the present invention relates to:

1) (Revenue) is taken in

Revenue refers to that empty net maps the profit successfully obtained, and defines according to the successful empty net bandwidth sum CPU of mapping:

Revenue＝α _R∑BW _R+β _R∑CPU _R (1)

Wherein, BW _rthat the successful empty guipure of mapping is wide, CPU _rmap successful empty net node cpu resource, α _rand β _rbe the weight coefficient for regulating bandwidth sum CPU, also can be understood as the unit price that operator provides empty net service Time Bandwidth and cpu resource, subscript R refers to income.

The present invention, one is propose the empty net mapping method by income sorting by reversals, the method can reduce the probability occurring bottleneck in bottom physical network surplus resources effectively, thus solves empty net request scale and equal being mapped to power and mapping the problem that total income quantity falls sharply in bottom physical network surplus resources scale situation.Two is comprehensive Direct/Reverse two kinds of sort methods, and propose a kind of mapping method of virtual network of Bidirectional sort, the method can judge the scale of current Internet resources, and choice for use sorts forward or backwards, to adapt to different network condition.

(1) the empty net mapping method of sorting by reversals:

As mentioned above, existing empty net mapping algorithm generally uses empty net request to take in by it method sorted from big to small, but this method is only applicable to the situation that empty network planning mould is less than Physical Network surplus resources scale, and in practical situations both, the situation that empty network planning mould equals Physical Network surplus resources scale is just more worthy of consideration.Therefore, the present invention is directed to the situation that empty network planning mould equals Physical Network surplus resources scale, propose the method empty net request being taken in sort from small to large (sorting by reversals) according to it, then call corresponding empty net mapping algorithm.Like this, taking in less void net request will preferentially be mapped, and because income scale is less, is therefore mapped to power higher, and the probability forming bottom Physical Network bottleneck is lower, the request of follow-up void net be mapped to power also corresponding raising.The advantage of above-mentioned sorting by reversals method can represent with Fig. 2.

In fig. 2, traditional forward sort algorithm preferentially can map the maximum void net request a-b-c-d of income, thus bottleneck node A, B and D is formed in bottom Physical Network, follow-up void net request can be had influence on to the use of node C and E, thus cause the request of follow-up void net to map unsuccessfully.And sorting by reversals method maps from the minimum void net request of income, owing to avoiding the appearance of bottleneck, therefore successfully have mapped virtual network e-f, g-h, and i-j, thus improve and be mapped to power and map successful empty net total income.In addition, the method, as the pre-treatment step of empty net mapping algorithm, can combinationally use with existing empty net mapping algorithm, and plays good optimization function to the situation that empty network planning mould equals Physical Network surplus resources scale.

(2) mapping method of virtual network of Bidirectional sort:

In order to tackle more generally virtual network mapping scenarios, the present invention proposes a kind of mapping method of virtual network of Bidirectional sort, virtual network maps and is subdivided into empty net income scale and is less than the situation that the situation of bottom Physical Network surplus resources scale and empty net income scale equal bottom Physical Network surplus resources scale by the method, in addition, the situation that empty net income scale is greater than bottom Physical Network surplus resources scale is more rare in actual applications, it is on scale situations such as the impact of mapped system are similar to, the process of scale situation such as therefore also to be classified as in the present invention.

In general virtual network mapping scenarios, system mode can be less than at empty net income scale and equal constantly to change between the situation of bottom Physical Network surplus resources scale, and the mapping method of virtual network of Bidirectional sort will judge current system conditions according to following formula before each empty net carries out mapping:

${\mathrm{\γ}}_{\mathrm{scale}}(\stackrel{\‾}{\mathrm{CPU}\left(n_{\mathrm{unmapped}}^V\right)}+\stackrel{\‾}{\mathrm{BW}\left(l_{\mathrm{unmapped}}^V\right)})>\stackrel{\‾}{\mathrm{CPU}\left(n_{\mathrm{residual}}^S\right)}+\stackrel{\‾}{\mathrm{BW}\left(l_{\mathrm{residual}}^S\right)}---\left(2\right)$

Wherein, with represent the node and the link that also do not carry out all virtual networks mapped in current time window, with represent that next void net maps the node and the link surplus resources that carry out front bottom physics network.γ _scalebe the parameter for scale situation scopes such as regulating, generally get the real number between 0.8-1.2.If above formula is true, then system such as to be at the scale situation, and the empty net mapping method of Bidirectional sort will be selected to take in minimum request in the empty net request of residue, re-use corresponding empty net mapping algorithm and carry out the mapping of void net; If above formula is false, then system is in situation on a small scale, namely the income of empty net request is less than Physical Network surplus resources scale, and selection remains in empty net request by the empty net mapping method of Bidirectional sort takes in maximum request, re-uses corresponding empty net mapping algorithm and carries out the mapping of void net.

After employing the mapping method of virtual network of Bidirectional sort, the situation that empty net asks the scales such as income and bottom Physical Network node surplus resources to check and write off scale obtains classifies and micronization processes, the scale situation layer physical network of going to the bottom such as effectively to avoid and easily occur the problem of bottleneck, improve success rate and overall map successfully empty net income quantity that empty net maps.

Accompanying drawing explanation

Virtual network under Fig. 1 time window pattern maps flow process

The advantage of sorting by reversals method in the scale situations such as Fig. 2

The empty net mapping method concrete steps of Fig. 3 Bidirectional sort

Execution mode

Concrete operations flow process of the present invention is according to time window mapped mode, first adds up all void net requests to be mapped, and selects one by one according to Bidirectional sort rule, and map in a time window, idiographic flow as shown in Figure 3:

A. discharge the bottom Physical Network resource that the void net request left in previous time window takies, the void net request left comprised service request and by the request initiatively refused; Empty net request comprises the request of empty net node and empty net link request two parts;

B. add up the void net request arrived in this time window, the request that the void net request of arrival comprises newly arrived request and requeues, remember that the empty net request set of this arrival is R _ct;

C. judge the state of current mapped system according to formula (2): if formula (2) is true, then system mode such as is at the scale, the void net request therefore selecting current income minimum; If formula (2) is false, then system mode is on a small scale, the void net request therefore selecting current income maximum.Finally call mapping algorithm to map.

If D. current in step C void net request maps successfully, namely empty net node and empty network chain road map successfully simultaneously, then upgrade the state of bottom physical network; If map unsuccessfully, then waiting list is delivered in this empty net request and wait for next time window, or the request of this void net is accumulative maps after the frequency of failure is greater than the threshold values DELAY pre-set, directly this request of refusal.Upgrade R _ctstate.

E. step C to D is repeated, until R _ctin current time window void net request number reduce to 0.

This void net mapping flow process ensure that empty net request can process in real time, and the mechanism of permitting the entrance of empty net request can be undertaken controlling (as postponed, refusing empty net request) by regulating parameter.

Claims (4)

1. a mapping method of virtual network for Bidirectional sort, the step of carrying out virtual network mapping in a time window comprises:

A. discharge the bottom Physical Network resource that the void net request left in previous time window takies, the void net request left comprised service request and by the request initiatively refused; Empty net request comprises the request of empty net node and empty net link request two parts;

B. add up the void net request arrived in this time window, the request that the void net request of arrival comprises newly arrived request and requeues, the empty net request set of described arrival is R _ct;

C. judge the state of current mapped system according to formula (1): if formula (1) is true, then system mode such as is at the scale, the void net request therefore selecting current income minimum, and calls mapping algorithm and map; If formula (1) is false, then system mode be small-scale, the void net request therefore selecting current income maximum, and calls mapping algorithm and map;

If D. current in step C void net request maps successfully, namely empty net node and empty network chain road map successfully simultaneously, then upgrade the state of bottom physical network; If map unsuccessfully, then waiting list is delivered in this empty net request and wait for next time window, or the request of this void net is accumulative maps after the frequency of failure is greater than the threshold values DELAY pre-set, directly this request of refusal; Upgrade R _ctstate;

E. step C to D is repeated, until R _ctin current time window void net request number reduce to 0;

Above-mentioned formula (1) is ${\mathrm{\γ}}_{\mathrm{scale}}(\stackrel{\‾}{\mathrm{CPU}\left(n_{\mathrm{unmapped}}^V\right)}+\stackrel{\‾}{\mathrm{BW}\left(l_{\mathrm{unmapped}}^V\right)})>\stackrel{\‾}{\mathrm{CPU}\left(n_{\mathrm{residual}}^S\right)}+\stackrel{\‾}{\mathrm{BW}\left(l_{\mathrm{residual}}^S\right)}$ Wherein, with represent the node and the link that also do not carry out all virtual networks mapped in current time window, with before representing that next empty net mapping is carried out, the node of bottom physical network and link surplus resources; γ _scalebe the parameter for scale situation scopes such as regulating, get the real number between 0.8-1.2, BW is that the successful empty guipure of mapping is wide, and CPU maps successful empty net node cpu resource.

2. the method for claim 1, if above-mentioned formula (1) is true, then system such as to be at the scale situation, and the empty net mapping method of Bidirectional sort will be selected to take in minimum request in the empty net request of residue; If above-mentioned formula (1) is false, then system is in situation on a small scale, namely the income of empty net request is less than Physical Network surplus resources scale, selection remains in empty net request by the empty net mapping method of Bidirectional sort takes in maximum request, and finally use net mapping algorithm is carried out the mapping of void net by this mapping method.

3. the method for claim 1, wherein

Income refers to that empty net maps the profit successfully obtained, according to the successful empty guipure of mapping wide (BW) and CPU definition:

$\mathrm{Revenue}={\mathrm{\α}}_R\mathrm{\Σ}{\mathrm{BW}}_R+{\mathrm{\β}}_R\mathrm{\Σ}{\mathrm{CPU}}_R$

Wherein, BW _rthat the successful empty guipure of mapping is wide, CPU _rmap successful empty net node cpu resource, α _rand β _rbe the weight coefficient for regulating bandwidth sum CPU, subscript R refers to take in (Revenue).

4. method as claimed in claim 2, the empty net mapping algorithm that described mapping method uses is the mapping algorithm that can complete the mapping of single void net.