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

doi:10.3969/j.issn.0253-2778.2018.06.008

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.

Key words: cloud computing, bandwidth guarantee, virtual cluster scheduling, backtracking algorithm

CLC Number:

TP393

XU Hua, LI Jing. A scheduling algorithm towards bandwidth guarantee for virtual cluster in the cloud[J]. Journal of University of Science and Technology of China, 2018, 48(6): 495-503.

References

［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.

()
()

[1]	LIU Shengjiu, LI Tianrui, LIU Jia, XIE Peng. Research on multi-fractals of weighted hypernetworks [J]. Journal of University of Science and Technology of China, 2020, 50(3): 369-381.
[2]	SHAO Xiyu, LI Jing, ZHOU Zhiqiang. Migration algorithm for Ceph block device cross clusters [J]. Journal of University of Science and Technology of China, 2018, 48(9): 748-754.
[3]	CHENG GuoLin, CHANG Hong, KE Daoming*, ZHANG Ping. Design of multiple pointer elastic buffer for high-speed interface [J]. Journal of University of Science and Technology of China, 2017, 47(10): 854-861.
[4]	LI Huakang, LIU Pan, YANG Yitao, SUN Guozi. A cloud storage access scheme with security proxy based on attribute mapping node [J]. Journal of University of Science and Technology of China, 2017, 47(4): 304-310.
[5]	CHEN Zhenguo, TIAN Liqin, LIN Chuang. Data reliable assurance model of Internet of Things based on the trust evaluation of perceived source [J]. Journal of University of Science and Technology of China, 2017, 47(4): 297-303.