ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

A scheduling algorithm towards bandwidth guarantee for virtual cluster in the cloud

  • Department of Computer Science and Technology, University of Science and Technology of China, Anhui 230026, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.06.008
  • Received Date: 25 September 2017
  • Accepted Date: 10 April 2018
  • Rev Recd Date: 10 April 2018
  • Publish Date: 30 June 2018
    Abstract

  • Abstract

    Due to the sharing of network resources in multi-tenant cloud data centers, minimum bandwidth guarantee has become one of the important methods to provide predictable performance for cloud applications. Efficient virtual network allocation helps accommodate a larger number of virtual clusters and improve the resource utilization in the cloud. Towards the demand for network bandwidth guarantee, this paper proposes a novel backtracking algorithm for scheduling virtual clusters in the cloud. For the typical tree network topology of a data center, this algorithm firstly judges whether there exists a valid solution inside each sub-tree in the network topology. After determining the sub-tree for the virtual cluster, it recursively searches for the detailed solution inside the sub-tree based on a backtracking algorithm, thus avoiding the problems of fake allocation or rejecting the request by mistake existing in related works. The experimental results show that the exact search based on backtracking can help increase the acceptance ratio of virtual cluster requests. Compared with existing algorithms, it can reduce the rejection ratio by 10% on average, which can contribute to improving the resource utilization in the cloud.

    Abstract

    Due to the sharing of network resources in multi-tenant cloud data centers, minimum bandwidth guarantee has become one of the important methods to provide predictable performance for cloud applications. Efficient virtual network allocation helps accommodate a larger number of virtual clusters and improve the resource utilization in the cloud. Towards the demand for network bandwidth guarantee, this paper proposes a novel backtracking algorithm for scheduling virtual clusters in the cloud. For the typical tree network topology of a data center, this algorithm firstly judges whether there exists a valid solution inside each sub-tree in the network topology. After determining the sub-tree for the virtual cluster, it recursively searches for the detailed solution inside the sub-tree based on a backtracking algorithm, thus avoiding the problems of fake allocation or rejecting the request by mistake existing in related works. The experimental results show that the exact search based on backtracking can help increase the acceptance ratio of virtual cluster requests. Compared with existing algorithms, it can reduce the rejection ratio by 10% on average, which can contribute to improving the resource utilization in the cloud.
    • FullText(HTML)
  • loading
    • References(14)
  • [1]
    ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: Cluster computing with working sets[C]// Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley, CA, USA: USENIX Association, 2010:10.
    [2]
    AIDA K, ABDUL-RAHMAN O, SAKANE E, et al. Evaluation on the performance fluctuation of Hadoop jobs in the cloud[C]// IEEE 16th International Conference on Computational Science and Engineering. Piscataway, NY, USA: IEEE Press, 2013: 159-166.
    [3]
    SHIEH A, KANDULA S, GREENBERG A, et al. Seawall: Performance isolation for cloud datacenter networks[C]// Proceedings of the 2nd USENIX conference on Hot topics in cloud computing. Berkeley, CA, USA: USENIX Association, 2010:1.
    [4]
    POPA L, YALAGANDULA P, BANERJEE S, et al. Elasticswitch: Practical work-conserving bandwidth guarantees for cloud computing[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 351-362.
    [5]
    GUO Chuanxiong, LU Guohan, WANG Helen, et al. SecondNet: A data center network virtualization architecture with bandwidth guarantees[C]// The 6th International Conference on emerging Networking Experiments and Technologies. New York：ACM, 2010: 15.
    [6]
    BALLANI H, COSTA P, KARAGIANNIS T, et al. Towards predictable datacenter networks[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 242-253.
    [7]
    荣 超,唐亚哲,胡成臣,等.基于带宽感知的多租户云数据中心虚拟网络分配算法[J].小型微型计算机系统,2015,36(1):7-12.
    RONG Chao, TANG Yazhe, HU Chengchen, et al. Bandwidth-aware virtual network allocation in multi-tenant cloud datacenters[J]. Journal of Chinese Computer System, 2015, 36(1): 7-12.
    [8]
    YU Hui, YANG Jiahai, XU Cong, et al. SpongeNet: Towards bandwidth guarantees of cloud datacenter with two-phase VM placement[C]// 2016 IEEE/IFIP Network Operations and Management Symposium. Piscataway, NY, USA: IEEE Press, 2016: 410-417.
    [9]
    LEE J, TURNER Y, LEE M, et al. Application-driven bandwidth guarantees in datacenters[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(4): 467-478.
    [10]
    YU Lei, CAI Zhipeng. Dynamic scaling of virtual clusters with bandwidth guarantee in cloud datacenters[C]// IEEE International Conference on Computer Communications. Piscataway, NY, USA: IEEE Press, 2016: 1-9.
    [11]
    YU Ruozhou, XUE Guoliang, ZHANG Xiang, et al. Survivable and bandwidth-guaranteed embedding of virtual clusters in cloud data centers[C]// IEEE International Conference on Computer Communications . Piscataway, NY, USA: IEEE Press, 2017.
    [12]
    李丹,陈贵海,任丰原,等.数据中心网络的研究进展与趋势[J].计算机学报,2014,37(2):259-274.
    LI Dan, CHEN Guihai, REN Fengyuan, et al[J]. Chinese Journal of Computers, 2014, 37(2): 259-274.
    [13]
    GREENBERG A, HAMILTON J R, JAIN N, et al. VL2: A scalable and flexible data center network[J]. ACM SIGCOMM Computer Communication Review, 2009, 39(4): 51-62.
    [14]
    NIU Di, XU Hong, LI Baochun, et al. Quality-assured cloud bandwidth auto-scaling for video-on-demand applications[C]// IEEE International Conference on Computer Communications. Piscataway, NY, USA: IEEE Press, 2012: 460-468.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: Cluster computing with working sets[C]// Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley, CA, USA: USENIX Association, 2010:10.
    [2]
    AIDA K, ABDUL-RAHMAN O, SAKANE E, et al. Evaluation on the performance fluctuation of Hadoop jobs in the cloud[C]// IEEE 16th International Conference on Computational Science and Engineering. Piscataway, NY, USA: IEEE Press, 2013: 159-166.
    [3]
    SHIEH A, KANDULA S, GREENBERG A, et al. Seawall: Performance isolation for cloud datacenter networks[C]// Proceedings of the 2nd USENIX conference on Hot topics in cloud computing. Berkeley, CA, USA: USENIX Association, 2010:1.
    [4]
    POPA L, YALAGANDULA P, BANERJEE S, et al. Elasticswitch: Practical work-conserving bandwidth guarantees for cloud computing[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 351-362.
    [5]
    GUO Chuanxiong, LU Guohan, WANG Helen, et al. SecondNet: A data center network virtualization architecture with bandwidth guarantees[C]// The 6th International Conference on emerging Networking Experiments and Technologies. New York：ACM, 2010: 15.
    [6]
    BALLANI H, COSTA P, KARAGIANNIS T, et al. Towards predictable datacenter networks[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 242-253.
    [7]
    荣 超,唐亚哲,胡成臣,等.基于带宽感知的多租户云数据中心虚拟网络分配算法[J].小型微型计算机系统,2015,36(1):7-12.
    RONG Chao, TANG Yazhe, HU Chengchen, et al. Bandwidth-aware virtual network allocation in multi-tenant cloud datacenters[J]. Journal of Chinese Computer System, 2015, 36(1): 7-12.
    [8]
    YU Hui, YANG Jiahai, XU Cong, et al. SpongeNet: Towards bandwidth guarantees of cloud datacenter with two-phase VM placement[C]// 2016 IEEE/IFIP Network Operations and Management Symposium. Piscataway, NY, USA: IEEE Press, 2016: 410-417.
    [9]
    LEE J, TURNER Y, LEE M, et al. Application-driven bandwidth guarantees in datacenters[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(4): 467-478.
    [10]
    YU Lei, CAI Zhipeng. Dynamic scaling of virtual clusters with bandwidth guarantee in cloud datacenters[C]// IEEE International Conference on Computer Communications. Piscataway, NY, USA: IEEE Press, 2016: 1-9.
    [11]
    YU Ruozhou, XUE Guoliang, ZHANG Xiang, et al. Survivable and bandwidth-guaranteed embedding of virtual clusters in cloud data centers[C]// IEEE International Conference on Computer Communications . Piscataway, NY, USA: IEEE Press, 2017.
    [12]
    李丹,陈贵海,任丰原,等.数据中心网络的研究进展与趋势[J].计算机学报,2014,37(2):259-274.
    LI Dan, CHEN Guihai, REN Fengyuan, et al[J]. Chinese Journal of Computers, 2014, 37(2): 259-274.
    [13]
    GREENBERG A, HAMILTON J R, JAIN N, et al. VL2: A scalable and flexible data center network[J]. ACM SIGCOMM Computer Communication Review, 2009, 39(4): 51-62.
    [14]
    NIU Di, XU Hong, LI Baochun, et al. Quality-assured cloud bandwidth auto-scaling for video-on-demand applications[C]// IEEE International Conference on Computer Communications. Piscataway, NY, USA: IEEE Press, 2012: 460-468.)
    Recommended articles
    TrendMD
    Volume 48 Issue 6 page: 495-503
    Cover

    Article Metrics

    Article views (54) PDF downloads(107)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return