RESOURCE RENTING FOR PERIODICAL CLOUD WORK FLOW APPLICATIONS
ABSTRACT
Cloud computing is a new resource provisioning mechanism, which represents a convenient way for users to accessdifferent computing resources. Periodical workflow applications commonly exist in scientific and business analysis, a many otherfields. One of the most challenging problems is to determine the right amount of resources for multiple periodical workflow applications.In this paper, the periodical workflow applications scheduling problem with total renting cost minimization is considered. The novelty ofthis work relies precisely on this objective function, which is more realistic in practice than the more commonly considered makespanminimization. An integer programming model is constructed for the problem under study. A Precedence Tree based Heuristic (PTH) isdeveloped which considers three types of initial schedule construction methods. Based on the initial schedule, two improvementprocedures are presented. The proposed methods are compared with existing algorithms for the related makespan based multipleworkflow scheduling problem. Experimental and statistical results demonstrate the effectiveness and efficiency of the proposedalgorithm.
EXISTING SYSTEM:
Workflow scheduling is a relevant problem both for users as wellas for CSPs and therefore it has been studied thoroughly. Tasksare usually mapped to suitable resources so as to optimize someperformance criterion. In the traditional distributed field (utilityGrids), resources were usually geographically dispersed clusters.Resources were encapsulated as services and services were notshareable between tasks of the workflow. Only mapping wasrequired and timetabling was not necessary during the schedulingprocess. There are two main objectives: cost optimization underdeadline constraints and execution time optimization under budgetconstraints. Common methods for time optimization includedynamic programming, branch and bound, decompositionbasedmethods, list scheduling algorithm, critical pathbased allocation, greedy randomized adaptive search and ant colony optimization approach. Methods for costoptimization include the deadline-MDP algorithm , DET(Deadline Early Tree) algorithm, PCP (Partial Critical Paths)algorithm and the CPI (Critical Path-based Iterative) heuristic. Other related works on allocating resources to workflowapplications include improving QoS in computational grids market-oriented hierarchical scheduling strategy, workflowapplications with security constraints double auction-basedscheduling of scientific applications and workflow schedulingwith multiple objectives. However, only a few papershave focused on the scheduling of workflow applications in cloudcomputing, in which resources (virtual machines) were usuallygeographically concentrated and shared by tasks and workflows.In cloud computing,
PROPOSED SYSTEM:
We consider scheduling periodical workflowapplications on cloud resources with the objective of minimizingthe total renting cost. This objective is closer to actual applicationscenarios, specially when compared to other more studiedobjectives that deal with the minimization of the completion timeof the workflow application (makespan). This related makespanobjective multiple workflow scheduling problem was studied in [4]and . However, in the Cloud, while makespan can be reducedalmost arbitrarily by renting more and more resources from theCSPs, users are usually concerned about total renting costs ratherthan in finishing their workflow applications as soon as possible.To the best of our knowledge, the problem under study is NPhardand has not been considered yet in the literature. The mainchallenges are: (i) Determining the actual start times for multipleperiodical workflow applications with different QoS constraints.(ii) Determining the appropriate amounts of reserved resourcesfor tasks of different workflow applications. (iii) Mapping taskswith different modes to rented resources in order to minimize thetotal renting cost. The problem is mathematically modeled usingInteger Programming. A Precedence Tree based Heuristic (PTH)is developed for the considered problem which consists of threecomponents: workflow combination, initial schedule constructionand schedule improvement. Three types of sink nodes are establishedfor the workflow construction. Based on the enumerationtree scheme, a dynamic one-step rule considering both extracost and freedom is developed for the schedule construction.Two main schedule improvement procedures considering bothexecution mode and resource type are presented. The multi-factoranalysis of variance technique is used to find the best constructionrules and improvement procedures. Comparisons with algorithmsfor the similar workflow scheduling problem show that PTH savesa lot of total renting cost for periodical workflow applications.
CONCLUSION AND FUTURE WORK
In this paper the multiple periodical workflow scheduling problemwith cost minimization is considered regarding the long-termresource rental relationship between the users and the CSP. Theprecedence tree based heuristic (PTH) is developed for the consideredproblem which contains a Synchronization based WorkflowsCombination procedure (SWC), three types of precedence treebased initial schedule Construction Methods (CM) and a modeand resource based Schedule Improvement Procedure (SIP). Theproposed PTH is compared on randomly generated instances withalgorithms for the similar makespan based multiple workflowscheduling problem. Experimental results demonstrate that theone-step heuristic with dynamic _ is the best initial scheduleconstruction method no matter the number of workflows, tasks,modes or types of resource. The SIP has a greater influence on theperformance of the PTH. The performance of MMPE increaseswith the rising in the number of execution modes while RAPincreases with the rising in the types of resource. The combinationof MMPE and RAP gives the best result when comparing toother adapted algorithms. The proposed PTH is also comparedwith the adapted algorithms on a simulated real public cloud.PTH saves a lot of cost for both Montage and LIGO applicationswhile comparing with resource provisioning with only on-demandinstances.Few works have been carried out on the multiple workflowsscheduling problem. The proposed schedule construction andimprovement procedures can be easily adapted to other workflowbased scheduling problems. Future work might include moreaccurate models to predict the arrival of workflows. Problems withresources that are not sharable between workflows are also worthconsidering.
REFERENCES
[1] E. Deelman, D. Gannon, M. Shields, and I. Taylor, “Workflows ande-science: An overview of workflow system features and capabilities,”Future Generation Computer Systems, vol. 25, no. 5, pp. 528–540, 2009.
[2] D. A. Brown, P. R. Brady, A. Dietz, J. Cao, B. Johnson, and J. McNabb,“A case study on the use of workflow technologies for scientific analysis:Gravitational wave data analysis,” in Workflows for e-Science. Springer,2007, pp. 39–59.
[3] AmazonEC2, “Amazon elastic compute cloud (Amazon EC2),”http://aws.amazon.com/ec2/pricing, 2014.
[4] M. Xu, L. Cui, H. Wang, and Y. Bi, “A multiple QoS constrainedscheduling strategy of multiple workflows for cloud computing,” in IEEEInternational Symposium on Parallel and Distributed Processing withApplications (ISPA 2009). IEEE, 2009, pp. 629–634.
[5] L. F. Bittencourt and E. R. Madeira, “Towards the scheduling of multipleworkflows on computational grids,” Journal of grid computing, vol. 8,no. 3, pp. 419–441, 2010.[6] J. Yu and R. Buyya, “Scheduling scientific workflow applications withdeadline and budget constraints using genetic algorithms,” ScientificProgramming, vol. 14, no. 3, pp. 217–230, 2006.
[7] E. Demeulemeester, W. S. Herroelen, and S. E. Elmaghraby, “Optimalprocedures for the discrete time/cost trade-off problem in project networks,”European Journal of Operational Research, vol. 88, no. 1, pp.50–68, 1996.
[8] E. Demeulemeester, B. De Reyck, B. Foubert, W. S. Herroelen, andM. Vanhoucke, “New computational results on the discrete time/costtrade-off problem in project networks,” Journal of the OperationalResearch Society, vol. 49, no. 11, pp. 1153–1163, 1998.
[9]¨O. Hazir, M. Haouari, and E. Erel, “Discrete time/cost trade-off prob-lem: A decomposition-based solution algorithm for the budget version,”Computers & Operations Research, vol. 37, no. 4, pp. 649–655, 2010.
[10] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective andlow-complexity task scheduling for heterogeneous computing,” IEEETransactions on Parallel and Distributed Systems, vol. 13, no. 3, pp.260–274, 2002.