A Communication Aware DAG Workflow Cost Optimization Model And Algorithm

To pay for the services in the cloud environment has become a trend, and resource scheduling has always been a central issue in the cloud environment. As cloud building in heterogeneous environment, the communication overhead in a cloud environment cannot be ignored, but existing DAG models do not take into account communication overhead between tasks, so it is difficultly to use in a real cloud environment. To this end, the paper proposes a DAG model aware communication called CA-DAG and an algorithm for this model, called CACO based on layered algorithm, also, an improved algorithm I-CACO based on string reduction.CA-DAG model introduces communication in the original workflow model. CACO scheduling algorithm uses forward consistent rule FC to calculate the minimum completed time of workflow, solving the minimum key path method not suitable for this model. Also, by using the bottom hierarchical strategy to divide the task into separated layers, transfers the cost optimization problem from the whole to the part. Furthermore, in order to increase the space of cost optimization and improve the results, CACO adopts dynamic programming method to collect discrete "time pieces" that is produced during the selecting services.This paper also proposes an improved algorithm I-CACO based on string reduction. I-CACO puts the tasks in a group, and achieves cost optimization in the same time windows. This algorithm first determines string reduction set of the workflow before scheduling and takes hierarchical rules using in CACO, in the process of scheduling, if a task belongs to string reduction group, then uses dynamic programming method to achieve optimal cost within group.We implement CACO, I-CACO, also DBL, DTL and TCDBL in the simulation environment. The simulation results show that, comparing with DTL, DBL and TCDBL, CACO have greatly enhanced the cost optimization effect considering communication overhead as 54%、47%、29%. Otherwise, when there are so many string reduction mandates in workflow, the effects of cost optimization of I-CACO improves 18% compared to CACO.