[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Uncertainty-Based QoS Min–Min Algorithm for Heterogeneous Multi-cloud Environment

  • Research Article - Computer Engineering and Computer Science
  • Published:
Arabian Journal for Science and Engineering Aims and scope Submit manuscript

Abstract

With the advances in virtualization technology, cloud has become the most powerful and promising platform for business, academia, public and government organizations. The cloud users do not require to maintain any IT infrastructure such as hardware, software and network resources in their premises. They can rent the services on demand from anywhere in the world just by paying for that service. In cloud computing, task allocation is a well-known problem. Many algorithms have been developed for the same. However, task allocation in a heterogeneous multi-cloud environment is much more challenging due to the dynamic nature of the cloud resources. In this paper, we present an algorithm, called uncertainty-based quality of service (QoS) Min–Min (UQMM) algorithm which considers QoS based on uncertainty parameters in heterogeneous multi-cloud environment. To the best of our knowledge, this is the first paper which deals with the task allocation problem with uncertainty-based QoS in a heterogeneous multi-cloud systems. We perform extensive simulations on the proposed algorithm using benchmark as well as synthetic datasets and measure performance in terms of various metrics. The results are compared with the popular cloud min–min scheduling, cloud min–max normalization and smoothing-based task scheduling algorithm to show the effectiveness of the proposed algorithm. Moreover, we evaluate the results using two statistical tests, namely t test and ANOVA.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Furht, B.; Escalante, A.(eds): Handbook of Cloud Computing. Springer, ISBN 978-1-4419-6523-3 (2010)

  2. Amazon Web Services. http://aws.amazon.com/. Accessed 11 April 2015

  3. IBM Cloud. http://www.ibm.com/cloud-computing/in/en/. Accessed 11 April 2015

  4. Microsoft Azure. http://azure.microsoft.com/en-us/. Accessed 15 April 2015

  5. Cloud Consulting. http://www.cloudconsulting.com/saas/. Accessed 29 April 2015

  6. Amazon Web Services (AWS). http://en.wikipedia.org/wiki/Amazon_Web_Services. Accessed 30 April 2015

  7. Montage: An Astronomical Image Mosaic Engine. http://montage.ipac.caltech.edu/index.html. Accessed 30 April 2015

  8. Southern California Earthquake Center. http://www.scec.org/. Accessed 30 April 2015

  9. Illumina. http://www.illumina.com/. Accessed 30 April 2015

  10. Brown D.A., Brady P.R., Dietz A., Cao J., Johnson B., McNabb J.: A Case Study on the Use of Workflow Technologies for Scientific Analysis: Gravitational Wave Data Analysis. Workflows for E-Science, pp. 39–59. Springer, Berlin (2007)

    Google Scholar 

  11. Livny J., Teonadi H., Livny M., Waldor M.K.: High-throughput, kingdom-wide prediction and annotation of bacterial non-coding RNAs. PLoS One 3(9), 1–12 (2008)

    Article  Google Scholar 

  12. Ullman J.D.: NP-complete scheduling problems. J. Comput. Syst. Sci. 10(3), 384–393 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  13. Braun T.D., Siegel H.J., Beck N., Boloni L.L., Maheswaran M., Reuther A.I., Robertson J.P., Theys M.D., Yao B., Hensgen D., Freund R.F.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 61(6), 810–837 (2001)

    Article  MATH  Google Scholar 

  14. Maheswaran M., Ali S., Siegel H.J., Hensgen D., Freund R.F.: Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J. Parallel Distrib. Comput. 59, 107–131 (1999)

    Article  Google Scholar 

  15. Ibarra O.H., Kim C.E.: Heuristic algorithms for scheduling independent tasks on nonidentical processors. J. Assoc. Comput. Mach. 24(2), 280–289 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  16. Armstrong, R.; Hensgen, D.; Kidd, T.: The Relative Performance of Various Mapping Algorithms is Independent of Sizable Variances in Run-time Predictions. In: 7th IEEE Heterogeneous Computing Workshop, pp. 79–87 (1998)

  17. Freund, R.F.; Gherrity, M.; Ambrosius, S.; Campbell, M.; Halderman, M.; Hensgen, D.; Keith, E.; Kidd, T.; Kussow, M.; Lima, J.D.; Mirabile, F.; Moore, L.; Rust, B.; Siegel, H.J.: Scheduling Resources in Multi-User, Heterogeneous, Computing Environments with SmartNet. In: 7th IEEE Heterogeneous Computing Workshop, pp. 184–199 (1998)

  18. Topcuoglu H., Hariri S., Wu M.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13(3), 260–274 (2002)

    Article  Google Scholar 

  19. Bajaj R., Agrawal D.P.: Improving scheduling of tasks in a heterogeneous environment. IEEE Trans. Parallel Distrib. Syst. 15(2), 107–118 (2004)

    Article  Google Scholar 

  20. Li J., Qiu M., Ming Z., Quan G., Qin X., Gu Z.: Online optimization for scheduling preemptable tasks on IaaS cloud system. J. Parallel Distrib. Comput. 72, 666–677 (2012)

    Article  Google Scholar 

  21. Wen, H.; Hai-ying, Z.; Chuang, L.; Yang, Y.: Effective Load Balancing for Cloud-based Multimedia System. In: International Conference on Electronic and Mechanical Engineering and Information Technology, pp. 165–168 (2011)

  22. Wang, S.; Yan, K.; Liao, W.; Wang, S.: Towards a Load Balancing in a Three-level Cloud Computing Network. In: 3rd IEEE International Conference on Computer Science and Information Technology, Vol. 1, pp. 108–113 (2010)

  23. Ergu D., Kou G., Peng Y., Shi Y., Shi Y.: The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment. J. Supercomput. 64, 835–848 (2013)

    Article  Google Scholar 

  24. Rai, A.; Bhagwan, R., Guha, S.: Generalized Resource Allocation for the Cloud. In: 3rd ACM Symposium on Cloud Computing (2012)

  25. Bozdag D., Ozguner F., Catalyurek U.: Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans. Parallel Distrib. Syst. 20(6), 857–871 (2009)

    Article  Google Scholar 

  26. Xu Y., Hu H., Yihe S.: Data dependence graph directed scheduling for clustered VLIW architectures. IEEE Tsinghua Sci. Technol. 15(3), 299–306 (2010)

    Article  Google Scholar 

  27. Bittencourt L.F., Madeira E.R.M., Fonseca N.L.S.D.: Scheduling in hybrid clouds. IEEE Commun. Mag. 50(9), 42–47 (2012)

    Article  Google Scholar 

  28. Xhafa F., Carretero J., Barolli L., Durresi A.: Immediate mode scheduling in grid systems. Int. J. Web Grid Serv. 3(2), 219–236 (2007)

    Article  Google Scholar 

  29. Xhafa F., Barolli L., Durresi A.: Batch mode scheduling in grid systems. Int. J. Web Grid Serv. 3(1), 19–37 (2007)

    Article  Google Scholar 

  30. Panda S.K., Jana P.K.: Efficient task scheduling algorithms for heterogeneous multi-cloud environment. J. Supercomput. 71(4), 1505–1533 (2015)

    Article  Google Scholar 

  31. Panda, S.K.; Nag, S.; Jana, P.K.: A smoothing based task scheduling algorithm for heterogeneous multi-cloud environment. In: Third IEEE International Conference on Parallel, Distributed and Grid Computing, IEEE, pp. 62–67 (2014)

  32. Panda, S.K.; Jana, P.K.: An Efficient Resource Allocation Algorithm for IaaS Cloud. In: 11th International Conference on Distributed Computing and Internet Technology. Lecture Notes in Computer Science, Springer, vol. 8956, pp. 351–355 (2015)

  33. Cisco: Quality of Service. http://www.cisco.com/c/en/us/products/ios-nx-os-software/quality-of-service-qos/index.html. Accessed 12 May 2015

  34. He X.S., Sun X.H., Von Laszewski G.: QoS guided min-min heuristic for grid task scheduling. J. Comput. Sci. Technol. 18(4), 442–451 (2003)

    Article  MATH  Google Scholar 

  35. Decai H., Yuan Y., Li-jun Z., Ke-qin Z.: Research on tasks scheduling algorithms for dynamic and uncertain computing grid based on a+bi connection number of SPA. J. Softw. 4(10), 1102–1109 (2009)

    Google Scholar 

  36. F. N. Braun. https://code.google.com/p/hcsp-chc/source/browse/trunk/AE/ProblemInstances/HCSP/Braun_et_al/u_c_hihi.0?r=93. Accessed 9th May 2015

  37. Calyam P., Rajagopalan S., Seetharam S., Selvadhurai A., Salah K., Ramnath R.: VDC-analyst: design and verification of virtual desktop cloud resource allocations. Comput. Netw. 68, 110–122 (2014)

    Article  Google Scholar 

  38. Al-Haidari, F.; Sqalli, M.; Salah, K.: Impact of CPU Utilization Thresholds and Scaling Size on Autoscaling Cloud Resources. In: 5th IEEE International Conference on Cloud Computing Technology and Science, vol. 2, pp. 256–261 (2013)

  39. Salah K., Calero J.M.A., Bernabe J.B., Perez J.M.M., Zeadally S.: Analyzing the security of windows 7 and Linux for cloud computing. Comput. Secur. 34, 113–122 (2013)

    Article  Google Scholar 

  40. Salah K., Calero J.M.A., Zeadally S., Al-Mulla S., Alzaabi M.: Using cloud computing to implement a security overlay network. IEEE Secur. Priv. 11(1), 44–53 (2013)

    Google Scholar 

  41. Al-Qawasmeh A.M., Maciejewski A.A., Wang H., Smith J., Siegel H.J., Potter J.: Statistical measures for quantifying task and machine heterogeneities. J. Supercomput. 57, 34–50 (2011)

    Article  Google Scholar 

  42. Miriam D.D.H., Easwarakumar K.S.: SPA-based task scheduling for hypercubic P2P grid systems. Int. J. Commun. Netw. Distrib. Syst. 9, 117–139 (2012)

    Article  Google Scholar 

  43. Foster, I.; Zhao, Y.; Raicu, I.; Lu, S.: Cloud Computing and Grid Computing 360-Degree Compared. In: Workshop on Grid Computing, Environment, pp 1–10 (2008)

  44. Ardagna D., Casale G., Ciavotta M., Perez J.F., Wang W.: Quality-of-service in cloud computing: modeling techniques and their applications. J. Internet Serv. Appl. 5, 1–17 (2014)

    Article  Google Scholar 

  45. Abdelmaboud A., Jawawi D.N.A., Ghani I., Elsafi A., Kitchenham B.: Quality of service approaches in cloud computing: a systematic mapping study. J. Syst. Softw. 101, 159–179 (2015)

    Article  Google Scholar 

  46. Chen J., Abedin F., Chao K., Godwin N., Li Y., Tsai C.: A hybrid model for cloud providers and consumers to agree on QoS of cloud services. Future Gener. Comput. Syst. 50, 38–48 (2015)

    Article  Google Scholar 

  47. Javadi B., Abawajy J., Buyya R.: Failure-aware resource provisioning for hybrid cloud infrastructure. J. Parallel Distrib. Comput. 72, 1318–1331 (2012)

    Article  Google Scholar 

  48. Muhuri P.K., Shukla K.K.: Real-time task scheduling with fuzzy uncertainty in processing times and deadlines. Appl. Soft Comput. 8, 1–13 (2008)

    Article  Google Scholar 

  49. Avetisyan, A.I.; Campbell, R.; Gupta, I.; Heath, M.T.; Ko, S.Y.; Ganger, G.R.; Kozuch, M.A.; O’Hallaron, D.; Kunze, M.; Kwan, T.T.; Lai, K.; Lyons, M.; Milojicic, D.S.; Lee, H.Y.; Soh, Y.C.; Ming, N.K.; Luke, J.; Namgoong, H.: Open Cirrus: A Global Cloud Computing Testbed. In: IEEE Computer Society, pp. 35–43 (2010)

  50. Greenberg A., Hamilton J., Maltz D.A., Patel P.: The cost of cloud: research problems in data center networks. ACM SIGCOMM Comput. Commun. Rev. 39(1), 68–73 (2009)

    Article  Google Scholar 

  51. Ali, S.; Siegel, H.J.; Maheswaran, M.; Hensgen, D.; Ali, S.: Task Execution Time Modeling for Heterogeneous Computing Systems. In: 9th Heterogeneous Computing Workshop, IEEE Computer Society, pp. 185-200 (2000)

  52. Ott R.L., Longnecker M.: An Introduction to Statistical Methods and Data Analysis, 6th Edition. Duxbury Press, Boston (2010)

    Google Scholar 

  53. Muller K.E., Fetterman B.A.: Regression and ANOVA: An Integrated Approach Using SAS Software. SAS Publisher, Cary (2002)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering and Information Technology, Veer Surendra Sai University of Technology, Burla, 768018, India

    Sanjaya K. Panda

  2. Department of Computer Science and Engineering, Indian School of Mines, Dhanbad, 826004, India

    Prasanta K. Jana

Authors
  1. Sanjaya K. Panda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Prasanta K. Jana
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sanjaya K. Panda.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Panda, S.K., Jana, P.K. Uncertainty-Based QoS Min–Min Algorithm for Heterogeneous Multi-cloud Environment. Arab J Sci Eng 41, 3003–3025 (2016). https://doi.org/10.1007/s13369-016-2069-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13369-016-2069-7

Keywords

Search

Navigation