Level-Based Clustering Approach to Scheduling Workflows in Clouds

  • Authors

    • Tawfiq Alrawashdeh
    • Zarina Mohamad
    • Aznida Hayati Zakaria
    https://doi.org/10.14419/ijet.v7i3.28.23440
  • scheduling, workflows, cluster, divide and conquer.

  • With the rapid increment on the complexity of the workflow, and the resultant demand on the scalability of the environment, executing workflows on traditional environment such as grids and clusters has become challenging task. Generally, schedulers aims to find a trade-off between execution, user requirement, and execution cost. Combine this with the uncertainty in the execution environment results in underlining the importance of designing scalable scheduling algorithm that adopt to the changes in the execution process. Toward this end, we propose the Level-Based Clustering (LBC) algorithm. By considering each level tasks as a single object (cluster), this algorithm aims to establish a relationship between the execution requirement for each cluster, and the number of resources that must be used to execute the entire workflow. We have compared our algorithm with three well-known algorithms from the literature, and the result show that the LBC algorithm achieves 50%, 25%, 50% on average improvement in term of cost, makespan and the number of resources used, respectively.

     

     

  • References

    1. [1] K. Almi’Ani & Y. C. Lee, “Partitioning-Based Workflow Scheduling in Cloudsâ€, Proceedings of the IEEE International Conference Advanced Information Networking and Application, (2016), pp. 645–652.

      [2] K. Almi’Ani, Y. C. Lee, & B. Mans, “Resource Demand Aware Scheduling for Workflows in Cloudsâ€, Proceedings of the IEEE 16th International Symposium on Network Computing and Applications, (2017), pp. 1-5.

      [3] H. Topcuoglu, S. Hariri, & M. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computingâ€, IEEE Transactions on Parallel Distributed System, 13(30, (2002), 260–274.

      [4] S. Abrishami, M. Naghibzadeh, & D. H. Epema. “Deadline-Constrained Workflow Scheduling Algorithms for Infrastructure as a Service Cloudsâ€, Future Generation Computer Systems, 29(1), (2013), 158-169.

      [5] P. Kaur & S. Mehta, “Resource Provisioning and Work Flow Scheduling in Clouds Using Augmented Shuffled Frog Leaping Algorithmâ€, Journal of Parallel and Distributed Computing, 101, (2016), 41-50.

      [6] D. Poola, S. K. Garg, R. Buyya, Y. Yang, & K. Ramamohanarao, “Robust Scheduling of Scientific Workflows with Deadline and Budget Constraints in Cloudsâ€, Proceedings of the IEEE 28th International Conference on Advanced Information Networking and Applications, (2014), pp. 858- 865.

      [7] V. Singh, I. Gupta, & P. K. Jana, “A Novel Cost-Efficient Approach for Deadline-Constrained Workflow Scheduling by Dynamic Provisioning of Resourcesâ€, Future Generation Computer Systems, 79, (2018), 95–110.

      [8] T. Dziok, K. Figiela, & M. Malawski, “Adaptive Multi-Level Workflow Scheduling With Uncertain Task Estimatesâ€, Lecture Notes in Computer Science: Parallel Processing and Applied Mathematics, 9574, (2016), 90–100.

      [9] V. Arabnejad, K. Bubendorfer, & B. Ng, “Budget and Deadline Aware e-Science Workflow Scheduling in Cloudsâ€, IEEE Transactions on Parallel and Distributed Systems, 2018, (2018), 1-10.

      [10] G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, & K. Vahi, “Characterizing and Profiling Scientific Workflowsâ€, Future Generation Computer Systems, 29, (2013), 682–692.

      [11] S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M. H. Su, & K. Vahi, “Characterization of Scientific Workflowsâ€, Proceedings of the IEEE Third Workshop on Workflows in Support of Large-Scale Science, (2008), pp. 1-10.

      [12] J. D. Ullman, “NP-Complete Scheduling Problemsâ€, Journal of Compute and System Sciences, 10, (1975), 384-393.

      [13] S. Liu, K. Ren, K. Deng, & J. Song, “A Task Backfill Based Scientific Workflow Scheduling Strategy on Cloud Platform,†Proceedings of the IEEE Sixth International Conference on Information Science and Technology, (2016), pp. 105-110.

      [14] Y. C. Lee & A. Y. Zomaya, “Stretch Out and Compact Workflow Scheduling with Resource Abundanceâ€, Proceedings of the 13th IEEE/ACM International Symposium on Cluster Cloud and Grid Computing, (2013), pp. 219-226.

      [15] C. Q. Wu, X. Lin, D. Yu, W. Xu, & L. Li, “End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget Constraintâ€, IEEE Transactions on Cloud Computing, 3(2), (2015), 169-181.

      [16] M. A. Rodriguez & R. Buyya, “Deadline Based Resource Provisioning and Scheduling Algorithm for Scientific Workflows on Cloudsâ€, IEEE Transactions on Cloud Computing, 2(2), (2014), 222 – 235.

      [17] J. J. Durillo, H. M. Fard, & R. Prodan, “MOHEFT: A Multi-Objective List-Based Method for Workflow Schedulingâ€, Proceedings of the IEEE 4th International Conference Cloud Computing Technology and Science, (2012), pp. 185-192.

      [18] R. Prodan & M. Wieczorek, “Bi-Criteria Scheduling of Scientific Grid Workflowsâ€, IEEE Transactions on Automation Science and Engineering, 7, (2010), 7(2), 364-376.

      [19] M. Malawski, K. Figiela, M. Bubak, E. Deelman, & J. Nabrzyski, “Cost Optimization of Execution of Multi-level Deadline-Constrained Scientific Workflows on Cloudsâ€, Proceedings of the IEEE International Conference on Parallel Processing and Applied Mathematics, (2013), pp. .

      [20] M. Mao & M. Humphrey, “Auto-Scaling to Minimize Cost and Meet Application Deadlines in Cloud Workflowsâ€, Proceedings of the IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, (2011), pp. 251-260.

      [21] H. Arabnejad & J. G. Barbosa, “A Budget Constrained Scheduling Algorithm for Workflow Applicationsâ€, Journal of Grid Computing, 12(4), (2014), 665-679.

      [22] Q. Jiang, Y. C. Lee & A. Y. Zomaya, “Executing Large Scale Scientific Workflow Ensembles in Public Cloudsâ€, Proceedings of the IEEE 44th International Conference on Parallel Processing, (2015), pp. 520-529.

      [23] L. Zeng, B. Veeravalli, & X. Li, “Scalestar: Budget Conscious Scheduling Precedence-Constrained Many-Task Workflow Applications in Cloudâ€, Proceedings of the IEEE 26th International Conference on Advanced Information Networking and Applications, (2012), pp. 534-541.

      [24] J. Yu, R. Buyya, & C. K. Tham, “Cost-Based Scheduling of Scientific Workflow Applications on Utility Gridsâ€, Proceedings of the IEEE International Conference on e-Science and Grid Computing, (2005), pp. 1-9.

      [25] A. Verma & S. Kaushal, “Cost Minimized PSO Based Workflow Scheduling Plan for Cloud Computingâ€, I.J. Information Technology and Computer Science, 7, (2015), 37-43.

      [26] A. Verma & S. Kaushal, “Budget Constrained Priority Based Genetic Algorithm for Workflow Scheduling in Cloudâ€, Proceedings of the IET International Conference on Recent Trends in Information, Telecommunication and Computing, (2013), pp. 8-14.

      [27] V. Arabnejad, K. Bubendorfer, & B. Ng, “Scheduling Deadline Constrained Scientific Workflows on Dynamically Provisioned Cloud Resourcesâ€, Future Generation Computer Systems, 75, (2017), 348-364.

      [28] M. R. Garey, R. L. Graham, & J. D. Ullman, “Worst-Case Analysis of Memory Allocation Algorithmsâ€, Proceedings of the 4th Annual ACM Symposium on the Theory of Computing, (1972), pp. 143-150.

  • Downloads

  • How to Cite

    Alrawashdeh, T., Mohamad, Z., & Hayati Zakaria, A. (2018). Level-Based Clustering Approach to Scheduling Workflows in Clouds. International Journal of Engineering & Technology, 7(3.28), 284-289. https://doi.org/10.14419/ijet.v7i3.28.23440