CN103997515B - Center system of selection and its application are calculated in a kind of distributed cloud - Google Patents
Center system of selection and its application are calculated in a kind of distributed cloud Download PDFInfo
- Publication number
- CN103997515B CN103997515B CN201410172326.2A CN201410172326A CN103997515B CN 103997515 B CN103997515 B CN 103997515B CN 201410172326 A CN201410172326 A CN 201410172326A CN 103997515 B CN103997515 B CN 103997515B
- Authority
- CN
- China
- Prior art keywords
- center
- virtual machine
- calculating
- user
- subgraph
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention discloses center system of selection is calculated in a kind of distributed cloud, belong to cloud platform technical field of data processing, it is high to solve the problems, such as that prior art selection calculates center to center communications cost.The standard at the calculatings center in this method selection subgraph is the length of longest path existing for subgraph, all summits processes and only passes through a longest path in subgraph.The present invention effectively overcomes the technological deficiency of randomized policy and Greedy strategy when selecting calculating center, the virtual machine number of user's request can be not only provided, also improve the Performance And Reliability needed for mass data processing in cloud, the communication cost between calculating center is reduced, reduces overall unnecessary resource consumption.
Description
Technical field
The invention belongs to cloud platform technical field of data processing, be related in a kind of distributed cloud calculate center system of selection and
It is applied, and in particular to a kind of to be used to realize calculating center selecting party in the distributed cloud for reducing the communication cost between calculating center
Method and its application.
Background technology
Distributed cloud computing system is made up of the sub- calculating center for being dispersed in various regions, and each sub- computing system is by local calculating
Resource and storage resource and Internet resources composition, provide the user the services such as calculating storage.Wherein, different geographical positions are distributed in
The calculating put connects centrally through wide area network.
Distributed cloud computing system has the advantages of many relative to centralized cloud computing system.Distributed cloud computing mode
It is low to the dependence of network bandwidth, because the processing and storage of data are carried out in the cloud computing subsystem of local, a side
The customer data that each subsystem in face needs to service greatly reduces, and each subsystem only needs to handle the client near apart from oneself
The service request sent, so effectively reduces network load, improves the response time of processing task.Distributed cloud computing mould
Formula has high flexibility, and each subsystem can be the specific demand for user of independent process, can also cooperate at offer
The ability of the task of reason demand complicated calculations amount.It also has the characteristics of robustness is high and scalability is strong, distributed cloud computing
In system, subsystems independently dispose the running for not interfering with other subsystems.The huge task process of computational processing
In, computationally intensive module can preferentially be distributed to the idle calculating center processing of load, realize that the load of whole system is equal
Weighing apparatus.In distributed cloud computing system, even if a certain subsystem breaks down, by the task dynamic migration of this subsystem to normal
The son of running calculates center processing, whole cloud computing system will not be caused to paralyse, will not also interrupt service makes user's resentment sound
Carry road.During building distributed system, subsystems can utilize existing calculating storage resource to reduce and build expense.
Application program will obtain optimum performance in cloud platform, reduce overall unnecessary resource consumption, be application program
The placement for providing the virtual machine of service is key factor.When user asks to reach, a calculating center may be without enough
Resource supports the virtual machine that user needs, and especially prevalent especially for the task of processing big data mass data, cloud platform needs
Want multiple calculating centers and provide service jointly for user's request, the overall communication cost reduced between calculating center will be helpful to use
Family program obtains better performance, therefore how to reduce the overall communication between calculating center and turn into a key issue.
When user asks the virtual machine of certain amount, cloud platform generally has two kinds of strategies to be handled.One kind is random
Strategy, one is randomly choosed in distributed cloud system and calculates center processing user request, the virtual machine needed is distributed for user.
Another kind is Greedy strategy, selects the maximum calculating center of capacity to be handled for user's request in distributed cloud system, when
When there is this calculating center off-capacity, capacity is maximum in the remaining calculating center of reselection one provides for user's request
Service.However, to meet the virtual machine number of user's request, either randomized policy or Greedy strategy, can cause excessive
Network service cost, its underlying cause be selected when selecting calculating center Optimal calculation center probability it is very low.Cause
This, is there is an urgent need to find a kind of calculating center system of selection for reducing network service cost as far as possible in distributed cloud computing, with
The defects of making up above two selection strategy.
The content of the invention
To overcome existing randomized policy and Greedy strategy to easily cause excessive network service cost when selecting calculating center
Technical problem, the present invention for user submit needed for virtual machine quantity this case, there is provided a kind of distributed cloud is fallen into a trap
The system of selection of calculation center and its application, on the premise of ensureing that user can obtain cloud service, there is provided network service cost is reduced,
Reduce unnecessary network resources waste.
The present invention adopts the technical scheme that：
Center system of selection is calculated in a kind of distributed cloud, is comprised the following steps：
1) the non-directed graph G=(V, E) that center is calculated in distributed cloud is set, wherein V is the set on summit in non-directed graph G,
The calculating center in distributed cloud is represented, E is the set on side in non-directed graph G, represents the connection between different calculating centers；
2) the set V' on a summit is randomly selected in non-directed graph G, the calculating at the calculating center representated by set V' is held
Amount is preset by user；Using the source point v0 in set V' as starting point, by summit nearest apart from source point v0 around source point v0
It is added in set V', if the calculating capacity that the calculating center in set V' possesses reaches calculating capacity set in advance, eventually
The only addition on summit；If the calculating capacity that the calculating center in set V' possesses is not up to calculating capacity set in advance, after
It is continuous that summit nearest apart from source point v0 around source point v0 is added in set V'；
3) to the set V' for meeting to terminate summit addition, the length sum on the side of connected graph is as two summits in set V'
Between inside nose section, using the inside nose section as first line segment；
4) two summits of first line segment in set V' are formed into vertex set V1, removes two tops of first line segment
The every other summit of point forms another vertex set V2；Calculate the summit to vertex set V1 summit in vertex set V2
Outside nose section and outside longest path length, two summits composition set U of outside nose section；By in set U
Two summits are added in vertex set V1, and by two summits of outside nose section from set V2Middle removal；Then, will count
The length of the outside nose section calculated sums up with outside longest path length, and the length value that this is added and obtained as
The outside longest path length of next iteration process；
5) step 4) is iterative process, and the end condition of iterative process is until vertex set V2 is empty set；If top
Point set V2 meets the end condition of iterative process, then obtains outside longest path length and selective Optimal calculation is distributed with
The optimal subgraph G' at center.
The technical scheme that the present invention takes further comprises：
The application of calculating center system of selection in a kind of distributed cloud, the mission requirements according to user to cloud platform trustship,
Using center system of selection is calculated in described distributed cloud, optimal subgraph G' is screened in cloud platform, in optimal subgraph G'
Optimal calculation center provides the virtual machine for meeting user's request；
Assuming that the resource requirement for meeting application program or required by task that cloud platform provides is (θ1,θ2,…,θn), cloud platform
In the different types of virtual machine of m kinds be present, it is (c that virtual machine that type is k, which takes resource,1k,c2k,…,cnk), payment expense is
pk；
User is allowed on the premise of enough resources are obtained, Optimal calculation center is selected in the optimal subgraph G', it is optimal
The calculation formula that the virtual machine that calculating center provides takes the minimum payment expense of resource is as follows：
Wherein, i represents the virtual machine that type existing for cloud platform is i, i span [1, m]；xiExpression type is i
Virtual machine demand number；piRepresent that the virtual machine that type is i pays expense；
The calculation formula of the expenditure minimum cost meets following constraints：
Wherein, (x1,x2,…,xm) represent each type of virtual machine demand number.
Further, it is assumed that n calculating center in the optimal subgraph G' be present, the capacity at each calculating center is respectively
d1,d2,…,dn；The distributed task scheduling of user's request is made up of m sub- tasks, the virtual machine number difference needed for each subtask
It is g1,g2,…,gm；The distributed task scheduling of user's request needs N number of virtual machine, and meets g1+g2+…+gm=N；
Some variable for calculating center placement certain amount virtual machine is pj(yj), j ∈ { 1,2 ..., n }, variable pj(yj)
Represent that calculating center j is currently placing yjAvailable bandwidth size under conditions of individual virtual machine, variable pj(yj) virtual with placing
The increase of machine number and reduce；
Variable xijk, i ∈ 1,2 ..., N }, j ∈ 1,2 ..., n }, k ∈ 1,2 ..., and m } represent that virtual machine i is subtask k
Service is provided, while is placed in the j of calculating center；
Make the maximized target formula of the available bandwidth sum between calculating center as follows：
The maximized target formula of available bandwidth sum made between calculating center meets following constraints：
Constraints one：
Constraints two：
Constraints three：
Wherein, the variable x in constraints oneijk∈ { 0,1 }, it is an integer variable, some specific virtual machine is only one
Individual sub- task service can only be placed in a calculating center simultaneously；Constraints two represents the void at some calculating center of distribution
Plan machine number is less than the capacity equal to this calculating center；Constraints three represents that all calculating centers carry for some subtask
The virtual machine number sum of confession is equal to the virtual machine number needed for this subtask.
Beneficial effects of the present invention：
Optimal should be able to provide what is serviced, it is necessary to rationalize and be placed as application program to make application program be obtained in cloud platform
Virtual machine, to reduce overall unnecessary resource consumption.This feelings of the present invention for virtual machine quantity needed for user's submission
Condition, there is provided center system of selection is calculated in a kind of distributed cloud.This method, which establishes, to be judged to select suitable son in cloud platform
The standard at center is calculated in figure, can not only provide the user the virtual machine number for meeting user's request, also achieves reduction meter
Communication cost between calculation center, effectively overcome the technology of existing randomized policy and Greedy strategy when selecting calculating center not
Foot.The present invention improves the Performance And Reliability met needed for mass data processing, it is possible to achieve to magnanimity in distributed cloud
Data are accurately and rapidly handled.
The present invention is elaborated further below with reference to embodiment.
Figure of description
Suitable subgraph and longest path flow chart is found in Fig. 1 non-directed graphs.
Longest path schematic diagram in Fig. 2 subgraphs.
The longest path length of the single request of Fig. 3 processing 1000 virtual machines of application.
The big request of 50 to 100 virtual machines of Fig. 4 process demands.
The small request of 10 to 20 virtual machines of Fig. 5 process demands.
Fig. 6 asks the performance comparision of algorithms of different for the user of 100 virtual machines of demand.
Embodiment
Embodiment 1：
A crucial research point is reasonable distribution and the dynamic dispatching of resource in cloud computing platform service research.Work as exploitation
When user's hosts applications service, cloud platform needs to provide specific virtual machine to support the operation of application program, and this is current allusion quotation
Type and most ripe cloud computing service mode-infrastructure services (IaaS).User has the mode of two kinds of application services
Available, a kind of is the virtual machine quantity for submitting user's request, waits cloud platform response；Another kind is that user submits deployment support
Application program of the pipe in cloud platform, the virtual machine needed for distribution runs user program to cloud platform automatically.
For such case of virtual machine quantity needed for user's submission, cloud computing platform needs to select a satisfaction for user
Resource needed for user is in communication with each other the most short calculating centralization of distance simultaneously.It is logical between reduction calculating center as far as possible in order to realize
The target of cost is believed, it is necessary to select optimal subgraph to provide the user service, the good and bad standard right and wrong of subgraph selected by measurement
Chang Guanjian's.Judge that the good and bad standard of subgraph is the length of longest path existing for subgraph herein, all summits are passed through in subgraph
And only pass through a longest path.Data or the request of identical scale are handled, the time that task serial performs is greater than task
The time that distribution performs.In the worst case, the longest path that serial task passes through in subgraph, its time handled are sons
The time upper limit of all tasks of figure processing same size.The length of this longest path is the upper limit of communication distance in subgraph.
Based on above-mentioned thought, calculating center system of selection in a kind of distributed cloud is present embodiments provided, as shown in figure 1,
Comprise the following steps：
1) the non-directed graph G=(V, E) that center is calculated in distributed cloud is set, wherein V is the set on summit in non-directed graph G,
The calculating center in distributed cloud is represented, E is the set on side in non-directed graph G, represents the connection between different calculating centers；
2) the set V' on a summit is randomly selected in non-directed graph G, the calculating at the calculating center representated by set V' is held
Amount is preset by user；Using the source point v0 in set V' as starting point, by summit nearest apart from source point v0 around source point v0
It is added in set V', if the calculating capacity that the calculating center in set V' possesses reaches calculating capacity set in advance, eventually
The only addition on summit；If the calculating capacity that the calculating center in set V' possesses is not up to calculating capacity set in advance, after
It is continuous that summit nearest apart from source point v0 around source point v0 is added in set V'；
3) to the set V' for meeting to terminate summit addition, the length sum on the side of connected graph is as two summits in set V'
Between inside nose section, using the inside nose section as first line segment, and calculate in set V' first line segment
Internal nose segment length；
4) two summits of first line segment in set V' are formed into vertex set V1, removes two tops of first line segment
The every other summit of point forms another vertex set V2；Calculate the summit to vertex set V1 summit in vertex set V2
Outside nose section and outside longest path length, two summits composition set U of outside nose section；By in set U
Two summits are added in vertex set V1, and by two summits of outside nose section from vertex set V2Middle removal；Then,
The length of the outside nose section calculated is summed up with outside longest path length, and the length value that this is added and obtained
Outside longest path length as next iteration process；
5) step 4) is iterative process, and the end condition of iterative process is until vertex set V2 is empty set；If top
Point set V2 meets the end condition of iterative process, then obtains outside longest path length and selective Optimal calculation is distributed with
The optimal subgraph G' at center.
The subgraph that capacity meets virtual machine quantitative requirement is have found as stated above, and all summits in this subgraph to the greatest extent may be used
The close source point v0 of energy, the topological diagram formed centered on source point v0.Obtain simultaneously into the most long way on all summits in subgraph
The length in footpath, this is the upper limit of communication distance in this subgraph.Set V1 includes two tops for forming farthest (length) line segment length
Point, set V2 include other all summits in addition to summit in V1 in required subgraph.
The subgraph being gathered in around source point centered on a point has been found, and obtains connecting all tops in subgraph
The longest path of point, each summit was only entered once.All summits in artwork are traveled through, are found in obtained each subgraph most long
The subgraph of shortest path, this subgraph are optimal subgraphs.One task was entered longest path in this subgraph and serially performed
Performance be performance limits that calculating center in this subgraph performs every other task.Calculating center in other subgraphs
Performance is lower than optimal subgraph.
Embodiment 2：
Enterprise-class tools or development of user can directly be submitted to cloud platform and need the application program of trustship and answer in cloud platform
Miscellaneous task.Cloud platform is firstly the need of the resource requirement for meeting application program or task, while the maximized use for reducing user
Expense cost.
Mission requirements according to from user to cloud platform trustship, selected using center is calculated in the distributed cloud described in embodiment 1
Selection method, screens optimal subgraph G' in cloud platform, and the Optimal calculation center in optimal subgraph G', which provides, meets user's request
Virtual machine；
Assuming that the resource requirement for meeting application program or required by task that cloud platform provides is (θ1,θ2,…,θn), cloud platform
In the different types of virtual machine of m kinds be present, it is (c that virtual machine that type is k, which takes resource,1k,c2k,…,cnk), payment expense is
pk；
User is allowed on the premise of enough resources are obtained, Optimal calculation center is selected in the optimal subgraph G', it is optimal
The calculation formula that the virtual machine that calculating center provides takes the minimum payment expense of resource is as follows：
Wherein, i represents the virtual machine that type existing for cloud platform is i, i span [1, m]；xiExpression type is i
Virtual machine demand number；piRepresent that the virtual machine that type is i pays expense；
The calculation formula of the expenditure minimum cost meets following constraints：
Wherein, (x1,x2,…,xm) represent each type of virtual machine demand number.The constraints of the present embodiment is to needing
The all restricted relation of each resource asked, the resource needed according to client, there is provided different types of virtual machine, each type
Virtual machine number is in a scope.Calculated relationship can use lingo programs to calculate each type of virtual machine demand (x1,
x2,…,xm)。
Embodiment 3：
Method described in embodiment 1 is also applied for the execution of distributed task scheduling.Assuming that two each summits of subgraph possess together
The capacity of sample size, as shown in Fig. 2 the distance of each grid is 1/3 length in figure, in A figures and B figures point-to-point transmission it is most long away from
From being respectivelyWithThe longest path length of A figures is respectively
And the longest path length for entering all summits of B figures isThe two of first subgraph
Longest distance is that the longest distance of first 2 points of subgraph is less than the longest distance of second subgraph point-to-point transmission between point, when second
The longest path of individual subgraph is shorter, illustrates the situation of the intensive aggregation in calculating center occur, and interaction, frequently virtual machine is placed
In the calculating center cluster of aggregation, it is possible to reduce the overall bandwidth that task run needs, selected by standard of longest path length
Execution of second subgraph gone out to distributed task scheduling is also more helpful.
Embodiment 4：
Because cloud computing needs data volume to be processed very huge big, the calculating storage resource of single machine can not meet sea
Measure the requirement of the performance and reliability etc. needed for data processing.Therefore in distributed data system, how to magnanimity
Data are accurately and quickly handled, and are one of the key problems that solution is badly in need of in current cloud computing.
The distributed programmed models of MapReduce meet the data processing under cloud computing environment and receive extensive concern.
MapReduce programming models also in constantly improve, company that many team and supporting increase income respectively for the model refinement its
Strategy execution efficiency and optimization inner strategy and integrated existing outstanding open source system etc..Application based on MapReduce is got over
Come more, be increasingly becoming the main contents of cloud platform trustship.Distributed task scheduling has become the main task of cloud computing processing.
The purpose of method described in embodiment 1 is to select to provide the optimal son serviced for user task or application program
Figure.Assuming that this is the distributed task scheduling of main flow in a cloud computing, it is made up of m sub- tasks, is different subtask service virtual machines
Communication between cluster is considerably less, is communicated between the virtual machine of same subtask service frequent.Reach and reduce meter as far as possible
Communication cost and overall communication cost between calculation center is, it is necessary to be that different subtask classifying rationallies calculates in subgraph G '
Center cluster so that most short at same calculating center or mutual distance as far as possible for the virtual machine with a sub- task service
Calculate centralization.
Assuming that using in the distributed cloud described in embodiment 1 calculate center system of selection screening optimal subgraph G' in exist
N calculating center, the capacity at each calculating center is d respectively1,d2,…,dn；The distributed task scheduling of user's request is appointed by m son
Business composition, the virtual machine number needed for each subtask is g respectively1,g2,…,gm；The distributed task scheduling of user's request needs N number of
Virtual machine, and meet g1+g2+…+gm=N；
Some variable for calculating center placement certain amount virtual machine is pj(yj), j ∈ { 1,2 ..., n }, variable pj(yj)
Represent that calculating center j is currently placing yjAvailable bandwidth size under conditions of individual virtual machine, variable pj(yj) virtual with placing
The increase of machine number and reduce；
Variable xijk, i ∈ 1,2 ..., N }, j ∈ 1,2 ..., n }, k ∈ 1,2 ..., and m } represent that virtual machine i is subtask k
Service is provided, while is placed in the j of calculating center；
Make the maximized target formula of the available bandwidth sum between calculating center as follows：
The maximized target formula of available bandwidth sum made between calculating center meets following constraints：
Constraints one：
Constraints two：
Constraints three：
Wherein, the variable x in constraints oneijk∈ { 0,1 }, it is an integer variable, some specific virtual machine is only one
Individual sub- task service can only be placed in a calculating center simultaneously；Constraints two represents the void at some calculating center of distribution
Plan machine number is less than the capacity equal to this calculating center；Constraints three represents that all calculating centers carry for some subtask
The virtual machine number sum of confession is equal to the virtual machine number needed for this subtask.
Embodiment 5：
The present embodiment is realized on CloudSim platforms calculates center cluster under method and distributed task scheduling described in embodiment 1
Divide to verify the reasonability of proposed virtual machine Placement Strategy.In simulation process, all masters in CloudSim emulation platforms
Machine configuration is the bandwidth of 5G internal memory, 2TB external memory and 1Gbps, and host-processor is single core processor, and processor speed is
1000,2000 or 3000MIPS.In the case that cpu busy percentage is 0, node consumption watt/hour of electric energy 170, and CPU full loads
When, node consumption watt/hour of electric energy 260.The internal memory 1G of virtual machine, external memory 100GB, with a width of in CloudSim emulation platforms
250Mbps, the CPU processing speeds that each virtual machine needs are distributed in as 250,500,750 or 1000MIPS.
For the performance of the methods described of testing example 1, the present embodiment creates 1000 × 1000 grid and random
User asks, the obtained output result after the processing of the methods described of embodiment 1, and subgraph selected by measurement is most in output result
Long path length.The position at calculating center is randomly distributed on this 1000 × 1000 network, and the distance for calculating center is grid
On Euclidean distance between points.5 distributed cloud scenes are devised, respectively comprising 100,75,50,25,10 meters
Calculate Center Number.The number that each distributed cloud possesses server is the same.Therefore, calculating center possesses the number of server
The number for possessing calculating center with a cloud is inversely proportional.There is each calculating center in the cloud at 100 calculating centers to possess service
The number of device is between 50 to 100.For have 50 calculating centers clouds each calculate center possess server number it is random
It is distributed between 100 to 200.
In the present embodiment, the methods described of embodiment 1 is referred to as Approx strategies.Tactful Approx and randomized policy
Random and Greedy strategy Greedy are contrasted.Random strategies are that random selection one calculates center processing user request,
If a calculating center can not provide service alone, then randomly choose next calculating center and be jointly processed by user's request.
Greedy strategies are then that the calculating center for selecting capacity maximum provides service for user's request, if a calculating center without
Method fulfils the task all by oneself, and the maximum calculating center of the next capacity of reselection handles user's request, so circulation, Zhi Daoji together
The capacity for calculating centralization meets that user asks.
In first experiment, the single request of 1000 virtual machines of test request.As shown in figure 3, illustrate each plan
Result slightly.Approx strategies are all substantially better than two other strategy in 5 scenes, are higher by nearly 75%.Random strategies
There is similar performance with Greedy strategies, as can be seen from Figure 4 the longest path length of subgraph is with calculating center number
Reduce and diminish.Because physical host becomes more with the reduction for calculating center number.
Next it is the contrast experiment of distinct methods.In first client's request set, continuous 100 applications 50 of user
Virtual machine number between to 100, obtains 100 subgraphs, and this request is referred to as big request by the present embodiment.Calculate all sons
The average value of the longest path length of figure.In second client's request set, user continuously sends 500 requests, every time request
Virtual machine between 10 to 20, referred to as small request.The average value of all subgraph longest paths is equally calculated.Fig. 4
The average value of the longest path length of big request and small request is sets forth with Fig. 5.As can be known from Fig. 5 and Fig. 6,
Greedy strategies are better than Random strategies, are higher by 33% or so and 66% or so respectively.Approx strategies are then better than Greedy
Strategy, 83% or so and 86% or so are higher by respectively.For same strategy, the longest path length asked greatly is greater than small ask
Ask.Because the virtual machine asked greatly is likely to be positioned in multiple calculating centers, the length of longest path is added.
In the experiment of overall communication amount between statistics calculating center, to asking for one virtual machine distribution of emulation platform submission
Ask, the virtual machine number of request is 100.Respectively in the case where possessing the distributed cloud scene at 2,3,4,5,6,7 and 8 calculating centers,
Measurement is total using the communication between calculating center in Approx strategies, Greedy strategies and the optimal subgraph of Random strategy gained respectively
With.It is a random number between 100 to 200 that the virtual machine sum that center possesses is calculated under each scene.Each distributed cloud
The request dry run that distributes for a virtual machine of scene 100 times, obtains average communication summation.It is from fig. 6 it can be seen that right
Communication cost between All Policies, calculating center becomes big with the increase for calculating center number, because with calculating
The increase of center number, the available virtual machine number for calculating center diminish, and the virtual machine for distributing to user is placed in multiple calculating
In the heart, communication cost increases therewith.The performance of Greedy strategy performances is better than Random strategies, and Approx strategies are then better than
Greedy strategies, and increasing with the center of calculating, gap is increasing.
Further narration has been done to the present invention above in conjunction with embodiment, but the present invention is not limited to above-mentioned embodiment,
In one skilled in the relevant art's possessed knowledge, it can also be made on the premise of present inventive concept is not departed from
Various change.
Claims (3)
1. center system of selection is calculated in a kind of distributed cloud, it is characterised in that comprise the following steps：
1) the non-directed graph G=(V, E) that center is calculated in distributed cloud is set, wherein V is the set on summit in non-directed graph G, is represented
Calculating center in distributed cloud, E are the set on side in non-directed graph G, represent the connection between different calculating centers；
2) randomly select the set V' on a summit in non-directed graph G, the calculating capacity at the calculating center representated by set V' by
User presets；Using the source point v0 in set V' as starting point, summit nearest apart from source point v0 around source point v0 is added
Into set V', if the calculating capacity that the calculating center in set V' possesses reaches calculating capacity set in advance, top is terminated
The addition of point；If the calculating capacity that the calculating center in set V' possesses is not up to calculating capacity set in advance, continue by
The summit nearest apart from source point v0 is added in set V' around source point v0；
3) to the set V' for meeting to terminate summit addition, the length sum on the side of connected graph is as between two summits in set V'
Internal nose section, using the inside nose section as first line segment；
4) two summits of first line segment in set V' are formed into vertex set V1, removes two summits of first line segment
Every other summit forms another vertex set V2；Calculate summit in vertex set V2 to vertex set V1 summit outside
Portion's nose section and outside longest path length, two summits composition set U of outside nose section；By two in set U
Summit is added in vertex set V1, and two summits of outside nose section are removed from vertex set V2；Then, will
The length of the outside nose section calculated sums up with outside longest path length, and the length value that this is added and obtained is made
For the outside longest path length of next iteration process；
5) step 4) is iterative process, and the end condition of iterative process is until vertex set V2 is empty set；If vertex set
The end condition that V2 meets iterative process is closed, then obtains outside longest path length and selective Optimal calculation center is distributed with
Optimal subgraph G'.
2. a kind of method that cloud platform processing user submits application program or task, it is characterised in that：According to user to cloud platform
The mission requirements of trustship, using center system of selection is calculated in a kind of distributed cloud described in claim 1, screened in cloud platform
Optimal subgraph G', the Optimal calculation center in optimal subgraph G' provide the virtual machine for meeting user's request；
The resource requirement for meeting application program or required by task that cloud platform provides is (θ1,θ2,…,θn), m be present in cloud platform
The different types of virtual machine of kind, it is (c that the virtual machine that type is k, which takes resource,1k,c2k,…,cnk), payment expense is pk；Wherein,
N is the quantity of resource requirement, and is positive integer；
User is allowed on the premise of enough resources are obtained, Optimal calculation center, Optimal calculation are selected in the optimal subgraph G'
The calculation formula that the virtual machine that center provides takes the minimum payment expense of resource is as follows：
Wherein, i represents the virtual machine that type existing for cloud platform is i, i span [1, m]；xiIt is the virtual of i to represent type
Machine demand number；piRepresent that the virtual machine that type is i pays expense；
The calculation formula of the expenditure minimum cost meets following constraints：
Wherein, (x1,x2,…,xm) represent each type of virtual machine demand number.
3. the method that cloud platform processing user according to claim 2 submits application program or task, it is characterised in that：Institute
State and n calculating center in optimal subgraph G' be present, the capacity at each calculating center is d respectively1,d2,…,dn；Point of user's request
Cloth task is made up of m sub- tasks, and the virtual machine number needed for each subtask is g respectively1,g2,…,gm；User's request
Distributed task scheduling needs N number of virtual machine, and meets g1+g2+…+gm=N；
Some variable for calculating center placement certain amount virtual machine is pj(yj), j ∈ { 1,2 ..., n }, variable pj(yj) represent meter
Calculation center j is currently placing yjAvailable bandwidth size under conditions of individual virtual machine, variable pj(yj) with placement virtual machine number
Increase and reduce；
Variable xijk, i ∈ 1,2 ..., N }, j ∈ 1,2 ..., n }, k ∈ 1,2 ..., and m } represent that virtual machine i provides for subtask k
Service, while be placed in the j of calculating center；
Make the maximized target formula of the available bandwidth sum between calculating center as follows：
The maximized target formula of available bandwidth sum made between calculating center meets following constraints：
Constraints one：
Constraints two：
Constraints three：
Wherein, the variable x in constraints oneijk∈ { 0,1 }, it is an integer variable, some specific virtual machine is only a son
Task service can only be placed in a calculating center simultaneously；Constraints two represents the virtual machine at some calculating center of distribution
Number is less than the capacity equal to this calculating center；Constraints three represents what all calculating centers provided for some subtask
Virtual machine number sum is equal to the virtual machine number needed for this subtask.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201410172326.2A CN103997515B (en) | 2014-04-25 | 2014-04-25 | Center system of selection and its application are calculated in a kind of distributed cloud |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201410172326.2A CN103997515B (en) | 2014-04-25 | 2014-04-25 | Center system of selection and its application are calculated in a kind of distributed cloud |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103997515A CN103997515A (en) | 2014-08-20 |
| CN103997515B true CN103997515B (en) | 2018-02-02 |
Family
ID=51311518
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201410172326.2A Active CN103997515B (en) | 2014-04-25 | 2014-04-25 | Center system of selection and its application are calculated in a kind of distributed cloud |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103997515B (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104298604B (en) * | 2014-11-06 | 2017-06-20 | 哈尔滨工业大学 | Cloud service robustness testing system and method for testing |
| CN106126315A (en) * | 2016-06-17 | 2016-11-16 | 广东工业大学 | A kind of virtual machine distribution method in the data center of minimization communication delay |
| CN106991195B (en) * | 2017-04-28 | 2020-08-11 | 南京大学 | Distributed subgraph enumeration method |
| CN107528742B (en) * | 2017-09-28 | 2020-06-12 | 南京航空航天大学 | Virtual machine deployment method oriented to cloud data center network optimization |
| WO2020181455A1 (en) * | 2019-03-11 | 2020-09-17 | 深圳大学 | Geographically distributed graph processing method and system |
| CN111222159B (en) * | 2019-12-30 | 2022-07-05 | 中国电子科技集团公司第三十研究所 | Cloud platform data leakage path identification method based on graph computing technology |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP2552065A1 (en) * | 2011-07-29 | 2013-01-30 | Telefonaktiebolaget L M Ericsson (publ) | Controller placement for fast failover in the split architecture |
| CN103019822A (en) * | 2012-12-07 | 2013-04-03 | 北京邮电大学 | Large-scale processing task scheduling method for income driving under cloud environment |
| CN103067524A (en) * | 2013-01-18 | 2013-04-24 | 浪潮电子信息产业股份有限公司 | Ant colony optimization computing resource distribution method based on cloud computing environment |
| CN103414752A (en) * | 2013-07-16 | 2013-11-27 | 上海交通大学 | Network-awareness cloud data center virtual machine allocation method |
-
2014
- 2014-04-25 CN CN201410172326.2A patent/CN103997515B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP2552065A1 (en) * | 2011-07-29 | 2013-01-30 | Telefonaktiebolaget L M Ericsson (publ) | Controller placement for fast failover in the split architecture |
| CN103019822A (en) * | 2012-12-07 | 2013-04-03 | 北京邮电大学 | Large-scale processing task scheduling method for income driving under cloud environment |
| CN103067524A (en) * | 2013-01-18 | 2013-04-24 | 浪潮电子信息产业股份有限公司 | Ant colony optimization computing resource distribution method based on cloud computing environment |
| CN103414752A (en) * | 2013-07-16 | 2013-11-27 | 上海交通大学 | Network-awareness cloud data center virtual machine allocation method |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103997515A (en) | 2014-08-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103997515B (en) | Center system of selection and its application are calculated in a kind of distributed cloud | |
| CN104038540B (en) | Method and system for automatically selecting application proxy server | |
| CN105103506B (en) | For the method and system for the non-homogeneous bandwidth request allocation bandwidth in system for cloud computing | |
| CN106534318B (en) | A kind of OpenStack cloud platform resource dynamic scheduling system and method based on flow compatibility | |
| CN108021435B (en) | Cloud computing task flow scheduling method with fault tolerance capability based on deadline | |
| CN108170530B (en) | Hadoop load balancing task scheduling method based on mixed element heuristic algorithm | |
| CN107291536B (en) | Application task flow scheduling method in cloud computing environment | |
| CN105471985A (en) | Load balance method, cloud platform computing method and cloud platform | |
| CN108667657B (en) | SDN-oriented virtual network mapping method based on local feature information | |
| CN108270805B (en) | Resource allocation method and device for data processing | |
| CN103401939A (en) | Load balancing method adopting mixing scheduling strategy | |
| WO2012173641A1 (en) | Decentralized management of virtualized hosts | |
| WO2022213529A1 (en) | Instance deployment method and apparatus, cloud system, computing device, and storage medium | |
| CN115134371A (en) | Scheduling method, system, equipment and medium containing edge network computing resources | |
| CN115421930B (en) | Task processing method, system, device, equipment and computer readable storage medium | |
| CN110798517A (en) | Decentralized cluster load balancing method and system, mobile terminal and storage medium | |
| CN102662764A (en) | Dynamic cloud computing resource optimization allocation method based on semi-Markov decision process (SMDP) | |
| CN107729514A (en) | A kind of Replica placement node based on hadoop determines method and device | |
| CN105488134A (en) | Big data processing method and big data processing device | |
| Li et al. | QoS-aware and multi-objective virtual machine dynamic scheduling for big data centers in clouds | |
| CN109976879B (en) | Cloud computing virtual machine placement method based on resource usage curve complementation | |
| CN110167031A (en) | A kind of resource allocation methods towards centralized base station, equipment and storage medium | |
| CN108536518A (en) | Method and system, reference platform, service terminal and the memory of task scheduling | |
| CN110958192B (en) | Virtual data center resource allocation system and method based on virtual switch | |
| CN109062683A (en) | The method, apparatus and computer readable storage medium of host resource distribution |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |