CN104657220B - Scheduling model and method based on deadline and expense restriction in mixed cloud - Google Patents
Scheduling model and method based on deadline and expense restriction in mixed cloud Download PDFInfo
- Publication number
- CN104657220B CN104657220B CN201510108799.0A CN201510108799A CN104657220B CN 104657220 B CN104657220 B CN 104657220B CN 201510108799 A CN201510108799 A CN 201510108799A CN 104657220 B CN104657220 B CN 104657220B
- Authority
- CN
- China
- Prior art keywords
- msub
- mrow
- task
- deadline
- scheduling
- 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 scheduling model and method based on deadline and expense restriction in a kind of mixed cloud, not the problem of private clound utilization rate is not high in being dispatched for mixed cloud and public cloud expense is higher, two scheduling strategy-Deadline Firsts and expense preference strategy are proposed based on performance and the goal of cost, establish the task and resource model in mixed cloud, the adaptively selected suitable scheduling resource of mission requirements that can be submitted according to user, require higher task can be with priority scheduling to public cloud deadline, the task high to cost requirements can be with priority scheduling to private clound, and two kinds of strategies are satisfied by deadline and certain expense restriction.Two kinds of scheduling strategies of this paper have good performance in scheduling deadline, expense, deadline beyond rate and private clound utilization rate etc., and especially when task amount is bigger, two kinds of scheduling strategies show more preferable adaptivity and advantage.
Description
Technical field
The present invention relates to field of cloud calculation, and in particular to the scheduling based on deadline and expense restriction in a kind of mixed cloud
Model and method.
Background technology
The multiplication of extension and data volume now with enterprise's application, especially peak period, the existing cluster of enterprise can not
Meet whole demands, it is therefore desirable to roll up hardware facility input.But in addition to peak period, most equipment utilization rate is not
Height, causes the waste of a large amount of hardware devices and the increase of running cost.Therefore in order to reduce hardware input and maintenance cost, more
Carry out more enterprise's selection mixed clouds and apply deployment platform as enterprise.Except there is the local of enterprise oneself privately owned in mixed cloud
Cloud, can directly access the public cloud of computing capability higher when that cannot meet the requirements, such as some in the computing capability of private clound
The application of stronger computing capability and storage capacity is needed, or in peak period private clound resource overload, it is impossible to while processing is more
Application task.Some solutions are proposed to this many scholar, such as load are managed, or data divide excellent
Change etc., but either be directed to resource load or data application, scheduling problem is all as wherein unusual the key link：Which
Using public cloud need to be dispatched toWhich can be completed in local private cloundHow private clound utilization rate and most is maximized as far as possible
The rent of smallization public cloud is usedHow time and expense the two targets are ensured
Mainly it is described at present on the research of mixed cloud scheduling in terms of following three.
1) scheduling of single cloud：
On the research of mixed cloud scheduling problem, the scheduling positioning of some existing researchs has certain difference with this paper, it
Be the scheduling problem for studying public cloud and private clound respectively in mixed cloud, rather than how by task scheduling in mixed cloud
The problem of to public cloud or private clound.Such as document [1] Bossche V D B, Vanmechelen K, Broeckhove
J.Cost-efficient scheduling heuristics for deadline constrained workloads on
Hybrid clouds, 2011 IEEE Third International Conference on Cloud Computing
Technology and Science disclose a kind of dispatching method, when proposing a kind of cut-off for the workload in mixed cloud
Between the Cost Optimization dispatching method that constrains.Document [2] Qiu X, Yeow W L, Wu C, Lau F C.Cost-minimizing
Preemptive scheduling of mapreduce workloads on hybrid clouds, 2013IEEE/ACM
21st International Symposium on Quality of Service, a kind of mixing is proposed for minimum expense
Preemption scheduling method in cloud, it is contemplated that QoS is constrained, but it is equally to study private clound and outsourcing expense respectively.Document
[3]Van D B R,Vanmechelen K,Broeckhove J.Cost-optimal scheduling in hybrid
Iaas clouds for deadline constrained workloads, Cloud Computing (CLOUD), 2010
IEEE 3rd International Conference on. are also the workflow tune formulated respectively for public cloud and private clound
Degree method.
2) expense is stressed：
Some in existing research is to lay particular emphasis on the Cost Optimization problem discussed under being constrained in deadline.Such as document
[4]Chopra N,Singh S.Deadline and cost based workflow scheduling in hybrid
Cloud, 2013 International Conference on Advances in Computing, Communications
And Informatics (ICACCI), propose an outsourcing scheduling model, to minimize expense from the angle of cloud user
With, but it lays particular emphasis on the Cost Optimization problem discussed in public cloud, and it has certain limitations the scale solved the problems, such as.Text
Offer [5] Hoseinyfarahabady M R, Samani H R D, Leslie L M, et al.Handling
Uncertainty:Pareto-Efficient BoT Scheduling on Hybrid Clouds, 201342nd
International Conference on Parallel Processing (ICPP), application obscure portions critical path propose
A kind of workflow schedule method of expense driving.Document [6] Genez T A L, Bittencourt L F, Madeira E R
M.On the Performance-Cost Tradeoff for Workflow Scheduling in Hybrid Clouds,
Proceedings of the 2013 IEEE/ACM 6th International Conference on Utility and
Cloud Computing propose two kinds of optimizing scheduling strategies based on mixing cloud framework, but it primarily focuses on point of expense
Analysis.
3) expense and performance balance：
More researchs are that the equilibrium problem of performance and expense is discussed.Such as document [7] Abrishami S, Naghibzadeh
M,Epema D H.Cost-driven scheduling of grid workflows using partial critical
Paths is directed to the uncertain factor in mixed cloud, it is proposed that a kind of dynamic resource allocation method, using Pareto optimization method,
Expense and deadline restricted problem are considered at the same time, but its time complexity is higher, and two algorithms are both greater than equal to O (n2)
(n is task number).Document [8]
Shifrin M, Atar R, Cidon I.Optimal scheduling in the hybrid-cloud, 2013
IFIP/IEEE International Symposium on Integrated Network Management (IM 2013) are public
An adaptive heuristic workflow schedule method is opened, it considers expense and deadline restricted problem, but it is pin
Data analysis workflow in mixed cloud is scheduled.Document [9] Duan R, Prodan R, Li X.Multi-
Objective Game Theoretic Scheduling of Bag-of-Tasks Workflows on Hybrid
Clouds, IEEE TRANSACTIONS ON CLOUD COMPUTING, the scheduling that 2014.2 (1) disclose a multiple target are excellent
Change method.It will perform time and cost target as an optimization, and bandwidth and storage are used as constraints.Document [10] Rahman
M,Li X,Palit H.Hybrid heuristic for scheduling data analytics workflow
Applications in hybrid cloud environment, 2011 IEEE International Symposium on
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW) disclose one kind
Mixed cloud dispatching method, lays particular emphasis on the utilization rate for improving private clound, to obtain the balance of performance and expense.Document [11]
Javadi B,Abawajy J,Buyya R.Failure-aware resource provisioning for hybrid
Cloud infrastructure, Journal of parallel and distributed computing, 2012,72
(10) achievement in research mainly have studied in mixed cloud disclosed in, should be by task scheduling to public cloud when resource request fails
Or the scheduling problem of private clound.Document [12] Zuo X, Zhang G, Tan W.Self-Adaptive Learning PSO-
Based Deadline Constrained Task Scheduling for Hybrid IaaS Cloud, IEEE
Transactions on Automation Science and Engineering, 2014,11 (2) disclose one and are based on grain
The ADAPTIVE MIXED cloud dispatching algorithm of swarm optimization, it discusses cut-off using public cloud and privately owned cloud resource as a set
The optimization of time and the income of IaaS provider, but this method only accounts for the income of cloud provider, does not account for the flower of user
Take problem.
In conclusion existing research is primarily present problems with：
(1) it is much that the scheduling for laying particular emphasis on single cloud in mixed cloud is asked in the existing research method on mixed cloud scheduling
Topic, such as stresses the scheduling of public cloud in mixed cloud, or stress the scheduling of private clound；
(2) target of the existing scheduling research for mixed cloud much lays particular emphasis on some index in Time, Cost And Performance, such as
Stress the reduction of public cloud expense, or stress the raising of private clound utilization rate；
(3) many researchs have also contemplated that expense and performance balance problem, it is contemplated that be public cloud resource provider
Cost, rather than the expense of user.
Analyzed for more than, this patent will be directed to these problems, from the angle of user, for user to deadline
With the demand difference of expense, the scheduling problem in mixed cloud is studied, to improve the utilization rate of private clound and minimize public cloud
Spend.The dispatching method that this patent proposes is simpler, is not related to differential, integral operation, complexity is relatively low.
The content of the invention
To solve deficiency of the prior art, what the present invention was provided in a kind of mixed cloud based on deadline and expense restriction
Scheduling model and method, solve some in the scheduling for laying particular emphasis on single cloud, Time, Cost And Performance in existing mixed cloud scheduling more
Index and the problem of do not consider the cost of user side.
In order to realize above-mentioned target, the present invention adopts the following technical scheme that：.
Scheduling model based on deadline and expense restriction in a kind of mixed cloud, it is characterised in that：Including user interface,
Task requests manager and scheduling manager；User interface is used to send the task requests that user submits to request manager, appoints
Business request manager is used to task request message being transmitted to scheduling manager, and scheduling manager is according to mission requirements, with reference to guarantor
There are the public cloud and the resource information of private clound in scheduling manager, with mixed cloud dispatching method by task scheduling to publicly-owned
On cloud or private clound, user is returned result to after the processing of completion task.
Scheduling model based on deadline and expense restriction in a kind of foregoing mixed cloud, it is characterized in that：The task
Solicited message includes task size, required data volume, the deadline for requiring completion and estimated cost.
Scheduling model based on deadline and expense restriction in a kind of foregoing mixed cloud, it is characterized in that：It is described publicly-owned
The information of cloud and privately owned cloud resource includes computing capability, transmittability, calculating price and the transmission price of resource.
It is a kind of based on the scheduling model based on deadline and expense restriction in a kind of any of the above-described mixed cloud
Dispatching method, it is characterized in that：Including step：
1) resource description：
Define publicly-owned cloud resource RuFor：
Ru=＜ Cu,Lu, Pu,Su,Qu＞ (1)
Wherein, CuFor public cloud Resource Calculation ability, the calculating time of task is influenced；LuFor transmittability, task is influenced
Transmission time；PuTo calculate price, SuTo store price, QuTo transmit price；
Defining privately owned cloud resource is：
Rr=＜ Cr,Lr＞ (2)
Wherein, CrFor private clound Resource Calculation ability, the calculating time of task is influenced；LrFor transmittability, task biography is influenced
The defeated time；
2) task description：
If task TiFor a unit of task requests, each one task of resource single treatment, then task TiIt is defined as：
Ti=＜ TDi,TCi,TLi,TMi＞ (3)
Wherein, TDiFor the deadline of task；TCiFor task size；TLiFor task computation information needed amount；TMiTo appoint
The budget of business is spent；
3) schedule constraints describe：
There are two constraints in task scheduling：Deadline and expense；Task completion time is by task computation time and biography
Defeated time two parts composition；Task TiDeadline t in public cloud and private clound respectivelyiRu、tiRrIt is as follows：
Deadline constraints is tiRu≤TDiAnd tiRr≤TDi；
Task TiCost FiCalculation formula is：
Fi=TCi×Pu+TLi×Qu+TLi×Su (6)
Cost constraint is Fi≤TMi；
4) expense priority scheduling strategy：
Expense priority scheduling strategy is preferentially by task scheduling to private clound in the case where meeting deadline constraints；Adjusting
Task T is first determined whether when spendingiConstrained in the deadline of private clound, if tiRr≤TDi, then private clound is dispatched to, is otherwise dispatched to
Public cloud, when being dispatched to public cloud, will meet cost constraint Fi≤TMi；The cost problem of n task is converted into following excellent
Change problem, correlation optimization and constraint specification are as follows：
Least cost formula is：
Public cloud deadline constraints：
Private clound deadline constraints：
Cost-time constraints：
Fi=TCi×Pu+TLi×Qu+TLi×Su≤TMi (10)
5) Deadline First scheduling strategy：
Deadline First scheduling strategy is preferentially by task scheduling to completing the task in the case where meeting cost constraint
In faster resource；First determine whether deadline of the task in publicly-owned and privately owned cloud resource, task scheduling can extremely be completed as early as possible
Resource on, under equal conditions, take into account private clound preferential principle；When being dispatched to public cloud, it is necessary first to judge expense about
Beam condition, correlation optimization and constraint specification equation below：
Minimum time formula：
Public cloud deadline constraints：
Private clound deadline constraints：
Cost-time constraints：
Fi=TCi×Pu+TLi×Qu+TLi×Su≤TMi (14)。
Dispatching method based on deadline and expense restriction in a kind of foregoing mixed cloud, it is characterized in that：The formula
(3) task size is task code amount in.
Dispatching method based on deadline and expense restriction in a kind of foregoing mixed cloud, it is characterized in that：The expense
Generation in the rental of public cloud, expense include computational costs, storage charges use and transmission cost.
Dispatching method based on deadline and expense restriction in a kind of foregoing mixed cloud, it is characterized in that：The step
5) private clound preferential principle is in：If the deadline of public cloud and private clound is same or similar, task by priority scheduling extremely
Private clound, is otherwise dispatched to public cloud；The similarity of deadline is determined by threshold value λ.
The beneficial effect that the present invention is reached：The present invention proposes two scheduling strategies-cut based on performance and the goal of cost
Only time priority and expense preference strategy, establish task and resource model in mixed cloud, and what can be submitted according to user appoints
The adaptively selected suitable scheduling resource of business demand, requires deadline higher task can be with priority scheduling to publicly-owned
Cloud, the task high to cost requirements can be with priority scheduling to private clound, and two kinds of strategies are satisfied by deadline and certain
Expense restriction；Two kinds of scheduling strategies of this paper exceed rate and private clound utilization rate etc. in scheduling deadline, expense, deadline
Aspect has good performance, and especially when task amount is bigger, two kinds of scheduling strategies show preferably adaptive
Property and advantage.
Brief description of the drawings
Fig. 1 is mixed cloud scheduling model schematic diagram.
Embodiment
The invention will be further described below in conjunction with the accompanying drawings.Following embodiments are only used for clearly illustrating the present invention
Technical solution, and be not intended to limit the protection scope of the present invention and limit the scope of the invention.
As shown in Figure 1, a kind of mixed cloud scheduling model, including user interface, task requests manager and scheduling manager；
User interface is used to send the task requests that user submits to task requests manager, and task requests manager is used for please by task
Information is asked to be transmitted to scheduling manager, scheduling manager is according to mission requirements, with reference to the public cloud being stored in scheduling manager
With the resource information of private clound, with mixed cloud dispatching method by task scheduling to public cloud or private clound, complete at task
User is returned result to after reason.
Task request message includes task size, required data volume, the deadline for requiring completion and estimated cost etc.；It is public
There are the information of cloud and privately owned cloud resource, including the computing capability of two spike-type cultivars, transmittability, calculating price and transmission price etc..
The dispatching method of deadline and expense restriction in a kind of mixed cloud based on above-mentioned mixed cloud scheduling model,
1) resource description：
Resource in mixed cloud is divided into publicly-owned cloud resource and privately owned cloud resource, and resource main representative of the present invention is virtual
Machine.
Define publicly-owned cloud resource：The pattern of Amazon cloud service is simulated, defines publicly-owned cloud resource RuFor：
Ru=＜ Cu,Lu, Pu,Su,Qu＞ (1)
Wherein, CuFor public cloud Resource Calculation ability, the calculating time of task is influenced；LuFor transmittability, task is influenced
Transmission time；PuTo calculate price, SuTo store price, QuFor transmission price (exterior transmission price, Yin Yama are referred mainly to herein
Internal transmission is free of charge in inferior cloud service).
Define privately owned cloud resource：Privately owned cloud resource RrComputing capability and transmittability are only considered, without considering price factor：
Rr=＜ Cr,Lr＞ (2)
Wherein, CrFor private clound Resource Calculation ability, the calculating time of task is influenced；LrFor transmittability, task biography is influenced
The defeated time.
2) task description：
If task TiFor a unit of task requests, each one task of resource single treatment, then task TiIt is defined as：
Ti=＜ TDi,TCi,TLi,TMi＞ (3)
Wherein, TDiFor the deadline of task, task must be completed before the deadline, and return the result；If
Beyond the time, then it is assumed that the tasks carrying fails；TCiFor task size, replaced in the present invention with task code amount, should
Calculating deadline of the parameters relationship to task；TLiFor task computation information needed amount, the transmission time of task is directly affected；
TMiSpent for the budget of task, if using public cloud, required expense is no more than the parameter.
3) schedule constraints describe：
From task definition, there are two constraints in task scheduling：Deadline and expense, will meet the two constraints
Condition has to calculate the deadline of task and cost in mixed cloud scheduling model.
Task completion time is made of task computation time and transmission time two parts.By task and mix determining for cloud resource
Justice can calculating task TiDeadline t in public cloud and private clound respectivelyiRu、tiRrIt is as follows：
Therefore deadline constraints is tiRu≤TDiAnd tiRr≤TDi。
Present invention assumes that expense is produced mainly in the rental of public cloud, mainly used and transmitted by computational costs, storage charges
Expense three parts form, task TiCost F in public cloudiCalculation formula is as follows：
Fi=TCi×Pu+TLi×Qu+TLi×Su (6)
Therefore cost constraint is Fi≤TMi。
Demand difference according to different application to performance and expense, it is proposed that two kinds of scheduling strategies：One kind is excellent with expense
First scheduling strategy (referred to as Cost-First), a kind of is with the scheduling strategy of Deadline First (referred to as Time-
First)。
4) expense priority scheduling strategy：
Expense priority scheduling strategy is preferentially by task scheduling to private clound in the case where meeting deadline constraints.The plan
Slightly task T is first determined whether in schedulingiConstrained in the deadline of private clound, if tiRr≤TDi, then private clound is dispatched to, otherwise
Public cloud is dispatched to, when being dispatched to public cloud, also to meet cost constraint Fi≤TMi；The cost problem conversion of n task
It is as follows for following optimization problem, correlation optimization and constraint specification：
Least cost formula is：
Public cloud deadline constraints：
Private clound deadline constraints：
Cost-time constraints：
Fi=TCi×Pu+TLi×Qu+TLi×Su≤TMi (10)
5) Deadline First scheduling strategy：
Deadline First scheduling strategy is preferentially by task scheduling to completing the task in the case where meeting cost constraint
In faster resource.First determine whether deadline of the task in publicly-owned and privately owned cloud resource, task scheduling can extremely be completed as early as possible
Resource on, under equal conditions, take into account private clound preferential principle.That is if public cloud and private clound completion
Time is same or similar, otherwise priority scheduling to private clound is dispatched to public cloud by task.The similarity of deadline is by threshold value
λ determines that, because the threshold value is related to the cost issues of user, which can flexibly set according to user demand.Scheduling
During to public cloud, it is necessary first to judge cost constraint, correlation optimization and constraint specification equation below：
Minimum time formula：
Public cloud deadline constraints：
Private clound deadline constraints：
Cost-time constraints：
Fi=TCi×Pu+TLi×Qu+TLi×Su≤TMi (14)
Mixed cloud dispatches experimental method：
The present invention carries out the experimental method of mixed cloud scheduling using cloud simulation software Cloudsim.Use cloud simulation software
Cloudsim3.0 realizes that the software is a completely free software, it is possible to saves a large number of open for mixed cloud experiment
Branch.At present in the experiment of mixed cloud, its public cloud part is realized using actual Amazon cloud service, still
Such experimental method cost is higher.The present invention is created in tri- data of A, B, C using cloud simulation software Cloudsim3.0
The heart, using data center A as private clound, B and C as public cloud, private clound and public cloud in cloud environment are mixed for fully simulation
Difference, the parameter setting of three data centers has certain difference：A, there are 20 virtual machines in C data center, there are 200 in B
Virtual machine, and the configuration of virtual machine also has difference, and design parameter sets as shown in table 1.
1 three data center's virtual machine parameter settings of table
Using mixed cloud scheduling model, user is sent task requests to request manager, request management by user interface
Task request message is transmitted to scheduling manager by device, and scheduling manager is according to mission requirements, with reference to being stored in scheduling manager
In public cloud and private clound resource information, with the mixed cloud dispatching method of the present invention by task scheduling to public cloud or private
There is cloud completion, and return result to user.
Experiment shows that expense priority scheduling strategy and Deadline First scheduling strategy disclosed by the invention are opened with classical
Hairdo algorithm Min-Min algorithms are compared with benchmark dispatching method FIFO, exceed rate in scheduling deadline, expense, deadline
It is good with performance in terms of private clound utilization rate, under best-case the performance of four indexs have nearly 50% respectively, 15%, 72% and
75% raising, especially shows more preferable adaptivity when number of tasks increases.
Dispatching method based on deadline and expense restriction in mixed cloud proposed by the present invention is simple and practical, it is only necessary to right
Task carries out condition judgment, is not related to integral differential operation, and algorithm complex and optimization bound are analyzed as follows：
Two kinds of scheduling strategies only need to carry out condition judgment to resource tasks, so expense is preferential and Deadline First
Algorithm complex is linear, i.e. O (n), wherein n are task number.
Preferential for expense on optimizing bound problem, optimal situation is can all complete in private clound, at this time
Up to optimization, expense 0, the Cost Optimization upper limit is Fi(i.e. all costs of the task in public cloud), worst case are all
Performed in public cloud, Cost Optimization lower limit is 0；The optimization of deadline is equally divided into all to two kinds of public cloud and private clound,
Because will meet that deadline constrains, the time-optimized upper limit is TDi-tiRr, time-optimized lower limit is TDi-tiRu。
The above is only the preferred embodiment of the present invention, it is noted that for the ordinary skill people of the art
For member, without departing from the technical principles of the invention, some improvement and deformation can also be made, these are improved and deformation
Also it should be regarded as protection scope of the present invention.
Claims (6)
1. a kind of dispatching method of the scheduling model based on deadline and expense restriction in mixed cloud, it is characterized in that：Dispatch mould
Type includes user interface, task requests manager and scheduling manager；User interface is used to send the task requests that user submits
To request manager, task requests manager is used to task request message being transmitted to scheduling manager, scheduling manager according to
Mission requirements, with reference to the public cloud and the resource information of private clound being stored in scheduling manager, with mixed cloud dispatching method
By in task scheduling to public cloud or private clound, user is returned result to after the processing of completion task；
Dispatching method includes step：
1) resource description：
Define publicly-owned cloud resource RuFor：
Ru=＜ Cu,Lu, Pu,Su,Qu＞ (1)
Wherein, CuFor public cloud Resource Calculation ability, the calculating time of task is influenced；LuFor transmittability, the transmission of task is influenced
Time；PuTo calculate price, SuTo store price, QuTo transmit price；
Defining privately owned cloud resource is：
Rr=＜ Cr,Lr＞ (2)
Wherein, CrFor private clound Resource Calculation ability, the calculating time of task is influenced；LrFor transmittability, when influencing multiplexed transport
Between；
2) task description：
If task TiFor a unit of task requests, each one task of resource single treatment, then task TiIt is defined as：
Ti=＜ TDi,TCi,TLi,TMi＞ (3)
Wherein, TDiFor the deadline of task；TCiFor task size；TLiFor task computation information needed amount；TMiFor task
Budget is spent；
3) schedule constraints describe：
There are two constraints in task scheduling：Deadline and expense；When task completion time is by task computation time and transmission
Between two parts form；Task TiDeadline t in public cloud and private clound respectivelyiRu、tiRrIt is as follows：
<mrow>
<msub>
<mi>t</mi>
<mi>i</mi>
</msub>
<msub>
<mi>R</mi>
<mi>u</mi>
</msub>
<mo>=</mo>
<mfrac>
<mrow>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>C</mi>
<mi>u</mi>
</msub>
</mfrac>
<mo>+</mo>
<mfrac>
<mrow>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>L</mi>
<mi>u</mi>
</msub>
</mfrac>
<mo>-</mo>
<mo>-</mo>
<mo>-</mo>
<mrow>
<mo>(</mo>
<mn>4</mn>
<mo>)</mo>
</mrow>
</mrow>
<mrow>
<msub>
<mi>t</mi>
<mi>i</mi>
</msub>
<msub>
<mi>R</mi>
<mi>r</mi>
</msub>
<mo>=</mo>
<mfrac>
<mrow>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>C</mi>
<mi>r</mi>
</msub>
</mfrac>
<mo>+</mo>
<mfrac>
<mrow>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>L</mi>
<mi>r</mi>
</msub>
</mfrac>
<mo>-</mo>
<mo>-</mo>
<mo>-</mo>
<mrow>
<mo>(</mo>
<mn>5</mn>
<mo>)</mo>
</mrow>
</mrow>
Deadline constraints is tiRu≤TDiAnd tiRr≤TDi；
Task TiCost FiCalculation formula is：
Fi=TCi×Pu+TLi×Qu+TLi×Su (6)
Cost constraint is Fi≤TMi；
4) expense priority scheduling strategy：
Expense priority scheduling strategy is preferentially by task scheduling to private clound in the case where meeting deadline constraints；In scheduling
First determine whether task TiConstrained in the deadline of private clound, if tiRr≤TDi, then private clound is dispatched to, is otherwise dispatched to publicly-owned
Cloud, when being dispatched to public cloud, will meet cost constraint Fi≤TMi；The cost problem of n task is converted into following optimization and asks
Topic, correlation optimization and constraint specification are as follows：
Least cost formula is：
<mrow>
<mi>M</mi>
<mi>i</mi>
<mi>n</mi>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>n</mi>
</munderover>
<msub>
<mi>F</mi>
<mi>i</mi>
</msub>
<mo>=</mo>
<mi>M</mi>
<mi>i</mi>
<mi>n</mi>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>n</mi>
</munderover>
<mrow>
<mo>(</mo>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
<mo>&times;</mo>
<msub>
<mi>P</mi>
<mi>u</mi>
</msub>
<mo>+</mo>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
<mo>&times;</mo>
<msub>
<mi>Q</mi>
<mi>u</mi>
</msub>
<mo>+</mo>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
<mo>&times;</mo>
<msub>
<mi>S</mi>
<mi>u</mi>
</msub>
<mo>)</mo>
</mrow>
<mo>-</mo>
<mo>-</mo>
<mo>-</mo>
<mrow>
<mo>(</mo>
<mn>7</mn>
<mo>)</mo>
</mrow>
</mrow>
Public cloud deadline constraints：
<mrow>
<msub>
<mi>t</mi>
<mi>i</mi>
</msub>
<msub>
<mi>R</mi>
<mi>u</mi>
</msub>
<mo>=</mo>
<mfrac>
<mrow>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>C</mi>
<mi>u</mi>
</msub>
</mfrac>
<mo>+</mo>
<mfrac>
<mrow>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>L</mi>
<mi>u</mi>
</msub>
</mfrac>
<mo>&le;</mo>
<msub>
<mi>TD</mi>
<mi>i</mi>
</msub>
<mo>-</mo>
<mo>-</mo>
<mo>-</mo>
<mrow>
<mo>(</mo>
<mn>8</mn>
<mo>)</mo>
</mrow>
</mrow>
Private clound deadline constraints：
<mrow>
<msub>
<mi>t</mi>
<mi>i</mi>
</msub>
<msub>
<mi>R</mi>
<mi>r</mi>
</msub>
<mo>=</mo>
<mfrac>
<mrow>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>C</mi>
<mi>r</mi>
</msub>
</mfrac>
<mo>+</mo>
<mfrac>
<mrow>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>L</mi>
<mi>r</mi>
</msub>
</mfrac>
<mo>&le;</mo>
<msub>
<mi>TD</mi>
<mi>i</mi>
</msub>
<mo>-</mo>
<mo>-</mo>
<mo>-</mo>
<mrow>
<mo>(</mo>
<mn>9</mn>
<mo>)</mo>
</mrow>
</mrow>
Cost-time constraints：
Fi=TCi×Pu+TLi×Qu+TLi×Su≤TMi (10)
5) Deadline First scheduling strategy：
Deadline First scheduling strategy is preferentially that task scheduling is very fast to the task is completed in the case where meeting cost constraint
Resource on；First determine whether deadline of the task in publicly-owned and privately owned cloud resource, the money that task scheduling can extremely be completed as early as possible
On source, under equal conditions, private clound preferential principle is taken into account；When being dispatched to public cloud, it is necessary first to judge expense restriction bar
Part, correlation optimization and constraint specification equation below：
Minimum time formula：
<mrow>
<mi>M</mi>
<mi>i</mi>
<mi>n</mi>
<mrow>
<mo>(</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>n</mi>
</munderover>
<msub>
<mi>t</mi>
<mi>i</mi>
</msub>
<msub>
<mi>R</mi>
<mi>u</mi>
</msub>
<mo>,</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>n</mi>
</munderover>
<msub>
<mi>t</mi>
<mi>i</mi>
</msub>
<msub>
<mi>R</mi>
<mi>r</mi>
</msub>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mi>M</mi>
<mi>i</mi>
<mi>n</mi>
<mrow>
<mo>(</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>n</mi>
</munderover>
<mo>(</mo>
<mrow>
<mfrac>
<mrow>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>C</mi>
<mi>u</mi>
</msub>
</mfrac>
<mo>+</mo>
<mfrac>
<mrow>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>L</mi>
<mi>u</mi>
</msub>
</mfrac>
</mrow>
<mo>)</mo>
<mo>,</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mi>n</mi>
</munderover>
<mo>(</mo>
<mrow>
<mfrac>
<mrow>
<msub>
<mi>TC</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>C</mi>
<mi>r</mi>
</msub>
</mfrac>
<mo>+</mo>
<mfrac>
<mrow>
<msub>
<mi>TL</mi>
<mi>i</mi>
</msub>
</mrow>
<msub>
<mi>L</mi>
<mi>r</mi>
</msub>
</mfrac>
</mrow>
<mo>)</mo>
<mo>)</mo>
</mrow>
<mo>-</mo>
<mo>-</mo>
<mo>-</mo>
<mrow>
<mo>(</mo>
<mn>11</mn>
<mo>)</mo>
</mrow>
</mrow>
Public cloud deadline constraints：
Private clound deadline constraints：
Cost-time constraints：
Fi=TCi×Pu+TLi×Qu+TLi×Su≤TMi (14)。
2. the dispatching party of the scheduling model based on deadline and expense restriction in a kind of mixed cloud according to claim 1
Method, it is characterized in that：The task request message includes task size, required data volume, the deadline for requiring completion and budget
Expense.
3. the dispatching party of the scheduling model based on deadline and expense restriction in a kind of mixed cloud according to claim 1
Method, it is characterized in that：The information of the public cloud and privately owned cloud resource includes the computing capability, transmittability, calculating price of resource
With transmission price.
4. the dispatching method based on deadline and expense restriction in a kind of mixed cloud according to claim 1, its feature
It is：Task size is task code amount in the formula (3).
5. the dispatching method based on deadline and expense restriction in a kind of mixed cloud according to claim 1, its feature
It is：The generation of the expense is in the rental of public cloud, and expense includes computational costs, storage charges is used and transmission cost.
6. the dispatching method based on deadline and expense restriction in a kind of mixed cloud according to claim 1, its feature
It is：Private clound preferential principle is in the step 5)：If the deadline of public cloud and private clound is same or similar, task will
Otherwise priority scheduling is dispatched to public cloud to private clound；The similarity of deadline is determined by threshold value λ.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510108799.0A CN104657220B (en) | 2015-03-12 | 2015-03-12 | Scheduling model and method based on deadline and expense restriction in mixed cloud |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510108799.0A CN104657220B (en) | 2015-03-12 | 2015-03-12 | Scheduling model and method based on deadline and expense restriction in mixed cloud |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104657220A CN104657220A (en) | 2015-05-27 |
| CN104657220B true CN104657220B (en) | 2018-04-17 |
Family
ID=53248393
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510108799.0A Active CN104657220B (en) | 2015-03-12 | 2015-03-12 | Scheduling model and method based on deadline and expense restriction in mixed cloud |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104657220B (en) |
Families Citing this family (25)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106095581B (en) * | 2016-06-18 | 2022-07-26 | 南京采薇且歌信息科技有限公司 | Network storage virtualization scheduling method under private cloud condition |
| WO2018006872A1 (en) | 2016-07-08 | 2018-01-11 | 腾讯科技（深圳）有限公司 | Method and device for scheduling interface of hybrid cloud |
| CN106101258B (en) * | 2016-07-08 | 2021-05-25 | 腾讯科技（深圳）有限公司 | Interface calling method, device and system of hybrid cloud |
| CN107040575B (en) * | 2016-11-30 | 2020-09-22 | 苏州浪潮智能科技有限公司 | Application distribution method and device on hybrid cloud |
| CN106603438B (en) * | 2016-12-21 | 2019-07-19 | 云南电网有限责任公司信息中心 | A kind of mixed cloud utilization of resources based on cost and distribution appraisal procedure |
| CN107274053A (en) * | 2017-05-03 | 2017-10-20 | 浙江工商大学 | The wisdom logistics data method for digging dispatched based on mixed cloud |
| CN107317836A (en) * | 2017-05-16 | 2017-11-03 | 北京交通大学 | One kind mixing cloud environment lower time appreciable request scheduling method |
| CN107172168A (en) * | 2017-05-27 | 2017-09-15 | 郑州云海信息技术有限公司 | A kind of mixed cloud data storage moving method and system |
| CN107229514A (en) * | 2017-06-01 | 2017-10-03 | 南京邮电大学盐城大数据研究院有限公司 | The dispatching method of BoT tasks with budgetary restraints under a kind of mixing cloud environment |
| CN107659433B (en) * | 2017-09-08 | 2020-03-03 | 中国联合网络通信集团有限公司 | Cloud resource scheduling method and equipment |
| CN107797870A (en) * | 2017-11-10 | 2018-03-13 | 苏州铭冠软件科技有限公司 | A kind of cloud computing data resource dispatching method |
| CN107908458A (en) * | 2017-11-10 | 2018-04-13 | 苏州铭冠软件科技有限公司 | A kind of cloud computing data resource dispatching method for considering time and expense |
| US10756981B2 (en) * | 2017-11-28 | 2020-08-25 | Hewlett Packard Enterprise Development Lp | Efficiency indexes |
| CN108009023B (en) * | 2017-11-29 | 2022-06-03 | 武汉理工大学 | Task scheduling method based on BP neural network time prediction in hybrid cloud |
| CN108491164B (en) * | 2018-03-22 | 2021-04-06 | 上海精鲲计算机科技有限公司 | Hybrid cloud storage architecture system |
| CN109614038A (en) * | 2018-11-23 | 2019-04-12 | 北京信息科技大学 | A kind of multi-speed disk-scheduling method of diversification QoS constraint |
| CN110210969A (en) * | 2019-05-21 | 2019-09-06 | 深圳前海微众银行股份有限公司 | Trade link decision-making technique, device, equipment and computer readable storage medium |
| CN110300179B (en) * | 2019-07-03 | 2022-03-25 | 郑州轻工业学院 | Task scheduling method and device for security constraint in hybrid cloud environment |
| CN110730158B (en) * | 2019-09-03 | 2021-07-02 | 郑州轻工业学院 | Hybrid cloud security scheduling method and hybrid cloud security scheduling system |
| WO2021097778A1 (en) * | 2019-11-21 | 2021-05-27 | 苏州铭冠软件科技有限公司 | Cloud computing data resource scheduling method |
| WO2022041271A1 (en) * | 2020-08-31 | 2022-03-03 | 苏州铭冠软件科技有限公司 | Cloud data resource scheduling method considering time and expense in rail transit applications |
| CN113301364B (en) * | 2021-01-05 | 2024-09-06 | 阿里巴巴集团控股有限公司 | Path planning method, CDN connection establishment method, device and storage medium |
| CN113568730A (en) * | 2021-08-03 | 2021-10-29 | 北京八分量信息科技有限公司 | Constraint scheduling method and device for heterogeneous tasks and related products |
| CN113886043B (en) * | 2021-09-29 | 2024-05-03 | 北京轻舟智航科技有限公司 | Simulation task scheduling system for comprehensively deploying public cloud and private cloud |
| CN113961323B (en) * | 2021-10-20 | 2022-06-14 | 郑州轻工业大学 | Hybrid cloud-oriented security perception task scheduling method and system |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101068157A (en) * | 2007-06-07 | 2007-11-07 | 武汉理工大学 | Grid task dispatching method based on time and expense restriction |
| CN103279818A (en) * | 2013-04-25 | 2013-09-04 | 中山大学 | Method for cloud workflow scheduling based on heuristic genetic algorithm |
| CN103377407A (en) * | 2012-04-25 | 2013-10-30 | 华为技术有限公司 | Method for processing cloud service, and related device and system of cloud service |
| CN104102544A (en) * | 2014-06-30 | 2014-10-15 | 武汉理工大学 | Multi QoS (quality of service)-constrained parallel task scheduling cost optimizing method under mixed cloud environment |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8898307B2 (en) * | 2011-09-22 | 2014-11-25 | Nec Laboratories America, Inc. | Scheduling methods using soft and hard service level considerations |
| US10552774B2 (en) * | 2013-02-11 | 2020-02-04 | Amazon Technologies, Inc. | Cost-minimizing task scheduler |
-
2015
- 2015-03-12 CN CN201510108799.0A patent/CN104657220B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101068157A (en) * | 2007-06-07 | 2007-11-07 | 武汉理工大学 | Grid task dispatching method based on time and expense restriction |
| CN103377407A (en) * | 2012-04-25 | 2013-10-30 | 华为技术有限公司 | Method for processing cloud service, and related device and system of cloud service |
| CN103279818A (en) * | 2013-04-25 | 2013-09-04 | 中山大学 | Method for cloud workflow scheduling based on heuristic genetic algorithm |
| CN104102544A (en) * | 2014-06-30 | 2014-10-15 | 武汉理工大学 | Multi QoS (quality of service)-constrained parallel task scheduling cost optimizing method under mixed cloud environment |
Non-Patent Citations (1)
| Title |
|---|
| 混合云中的一个高效协调器;王宗江 等;《计算机科学》;20150115;第42卷(第1期);第93页左栏第5行-第94页右栏第29行，图2-5 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104657220A (en) | 2015-05-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN104657220B (en) | Scheduling model and method based on deadline and expense restriction in mixed cloud | |
| Zeng et al. | Joint optimization of task scheduling and image placement in fog computing supported software-defined embedded system | |
| Najafizadeh et al. | Multi-objective Task Scheduling in cloud-fog computing using goal programming approach | |
| Madni et al. | Resource scheduling for infrastructure as a service (IaaS) in cloud computing: Challenges and opportunities | |
| Masdari et al. | Efficient task and workflow scheduling in inter-cloud environments: challenges and opportunities | |
| Zuo et al. | A multi-objective optimization scheduling method based on the ant colony algorithm in cloud computing | |
| Aslanpour et al. | Resource provisioning for cloud applications: a 3-D, provident and flexible approach | |
| Zhu et al. | Scheduling stochastic multi-stage jobs to elastic hybrid cloud resources | |
| Almeida et al. | Resource management in the autonomic service-oriented architecture | |
| US8719833B2 (en) | Adaptive demand-driven load balancing | |
| Zuo et al. | A multiqueue interlacing peak scheduling method based on tasks’ classification in cloud computing | |
| CN102780759B (en) | Based on the cloud computing resource scheduling method in regulation goal space | |
| Ben-Yehuda et al. | Expert: Pareto-efficient task replication on grids and a cloud | |
| Hoenisch et al. | Cost-efficient scheduling of elastic processes in hybrid clouds | |
| Agostinho et al. | A bio-inspired approach to provisioning of virtual resources in federated clouds | |
| Bi et al. | SLA-based optimisation of virtualised resource for multi-tier web applications in cloud data centres | |
| CN106020933A (en) | Ultra-lightweight virtual machine-based cloud computing dynamic resource scheduling system and method | |
| CN102541858A (en) | Data equality processing method, device and system based on mapping and protocol | |
| Kaliaev | Multiagent approach for building distributed adaptive computing system | |
| CN107317836A (en) | One kind mixing cloud environment lower time appreciable request scheduling method | |
| WO2024164712A1 (en) | Cloud flow task scheduling method and apparatus, and electronic device and storage medium | |
| Nguyen et al. | Optimizing resource utilization in NFV dynamic systems: New exact and heuristic approaches | |
| Hamed et al. | Optimization Task Scheduling Using Cooperation Search Algorithm for Heterogeneous Cloud Computing Systems. | |
| AlOrbani et al. | Load balancing and resource allocation in smart cities using reinforcement learning | |
| Kecskemeti et al. | Facilitating self-adaptable Inter-Cloud management |
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 |