Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (1): 185-206.doi: 10.1007/s11390-019-1890-3

Special Issue: Data Management and Data Mining; Computer Networks and Distributed Computing

• Regular Paper • Previous Articles     Next Articles

On Maximum Elastic Scheduling in Cloud-Based Data Center Networks for Virtual Machines with the Hose Model

Shuai-Bing Lu1,2, Student Member, IEEE, Jie Wu2,*, Fellow, IEEE, Huan-Yang Zheng2, and Zhi-Yi Fang1   

  1. 1 College of Computer Science and Technology, Jilin University, Changchun 13012, China;
    2 Department of Computer and Information Sciences, Temple University, Philadelphia, PA19122, U.S.A.
  • Received:2018-07-15 Revised:2018-08-30 Online:2019-01-05 Published:2019-01-12
  • Contact: Jie Wu E-mail:jiewu@temple.edu
  • About author:Shuai-Bing Lu is currently a Ph.D. candidate in computer science and technology of Jilin University, Changchun. She is supported by the China Scholarship Council as a visiting scholar supervised by Prof. Jie Wu in the Department of Computer and Information Sciences at Temple University (2016-2018), Philadelphia. She is a student member of IEEE. Her current research focuses on distributed computing, cloud computing and fog computing.
  • Supported by:
    This research was supported in part by the National Science Foundation (NSF) of United States under Grant Nos. CNS 1757533, CNS 1629746, CNS 1564128, CNS 1449860, CNS 1461932, CNS 1460971, ⅡP 1439672, and CSC 20163100.

PDF

412

Supplement

1

With the growing popularity of cloud-based data center networks (DCNs), task resource allocation has become more and more important to the efficient use of resource in DCNs. This paper considers provisioning the maximum admissible load (MAL) of virtual machines (VMs) in physical machines (PMs) with underlying tree-structured DCNs using the hose model for communication. The limitation of static load distribution is that it assigns tasks to nodes in a once-and-for-all manner, and thus requires a priori knowledge of program behavior. To avoid load redistribution during runtime when the load grows, we introduce maximum elasticity scheduling, which has the maximum growth potential subject to the node and link capacities. This paper aims to find the schedule with the maximum elasticity across nodes and links. We first propose a distributed linear solution based on message passing, and we discuss several properties and extensions of the model. Based on the assumptions and conclusions, we extend it to the multiple paths case with a fat tree DCN, and discuss the optimal solution for computing the MAL with both computation and communication constraints. After that, we present the provision scheme with the maximum elasticity for the VMs, which comes with provable optimality guarantee for a fixed flow scheduling strategy in a fat tree DCN. We conduct the evaluations on our testbed and present various simulation results by comparing the proposed maximum elastic scheduling schemes with other methods. Extensive simulations validate the effectiveness of the proposed policies, and the results are shown from different perspectives to provide solutions based on our research.

Key words: data center network (DCN); cloud; distributed algorithm; elasticity; hose model; optimization;

[1] Bari M F, Boutaba R, Esteves R et al. Data center network virtualization:A survey. IEEE Communications Surveys and Tutorials, 2013, 15(2):909-928.
[2] Mann Z A. Allocation of virtual machines in cloud data centers-A survey of problem models and optimization algorithms. ACM Computing Surveys, 2015, 48(1):Article No. 11.
[3] Li K K, Wu J, Adam B. Elasticity-aware virtual machine placement for cloud datacenters. In Proc. the 2nd International Conference on Cloud Networking, November 2013, pp.99-107.
[4] Duffield N G, Goyal P, Greenberg A et al. A flexible model for resource management in virtual private networks. In Proc. the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, August 1999, pp.95-108.
[5] Lee Y T, Sidford A, Wong S C W. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proc. the 56th Annual Symposium on Foundations of Computer Science, October 2015, pp.1049-1065.
[6] Leiserson C E. Fat-trees:Universal networks for hardware efficient supercomputing. IEEE transactions on Computers, 1985, C-34(10):892-901.
[7] Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture. In Proc. the ACM SIGCOMM 2008 Conference on Data communication, August 2008, pp.63-74.
[8] Davie B S, Rekhter Y. MPLS:Technology and Applications (1st edition). Morgan Kaufmann, 2000.
[9] Liu Y, Muppala J K, Veeraraghavan M et al. Data Center Networks:Topologies, Architectures and Fault-Tolerance Characteristics. Springer International Publishing, 2013.
[10] Wang R X, Wickboldt J A, Esteves R P et al. Using empirical estimates of effective bandwidth in network-aware placement of virtual machines in data centers. IEEE Transactions on Network and Service Management, 2016, 13(2):267-280.
[11] Kusic D, Kephart J O, Hanson J E et al. Power and performance management of virtualized computing environments via look a head control. Cluster Computing, 2009, 12(1):1-15.
[12] Xu F, Liu F, Liu L et al. iAware:Making live migration of virtual machines interference-aware in the cloud. IEEE Transactions on Computers, 2014, 63(12):3012-3025.
[13] Yang S, Wieder P, Yahyapour R et al. Reliable virtual machine placement and routing in clouds. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(10):2965-2978.
[14] Guo C X, Lu G H, Wang H J et al. SecondNet:A data center network virtualization architecture with bandwidth guarantees. In Proc. the 6th International Conference, November 2010, Article No. 15.
[15] Deng W, Liu F, Jin H et al. Reliability-aware server consolidation for balancing energy-lifetime tradeoff in virtualized cloud datacenters. International Journal of Communication Systems, 2014, 27(4):623-642.
[16] Liu F M, Guo J, Huang X et al. eBA:Efficient bandwidth guarantee under traffic variability in datacenters. IEEE/ACM Transactions on Networking, 2017, 25(1):506-519.
[17] Li X, Wu J, Tang S et al. Let's stay together:Towards traffic aware virtual machine placement in data centers. In Proc. the 33rd IEEE International Conference on Computer Communications, April 2014, pp.1842-1850.
[18] Meng X Q, Pappas V, Zhang L. Improving the scalability of data center networks with traffic-aware virtual machine placement. In Proc. the 29th IEEE International Conference on Computer Communications, March 2010, pp.1154-1162.
[19] Xu F, Liu F M, Jin H et al. Managing performance overhead of virtual machines in cloud computing:A survey, state of the art, and future directions. Proceedings of the IEEE, 2014, 102(1):11-31.
[20] Kumar A, Rastogi R, Silberschatz A et al. Algorithms for provisioning virtual private networks in the hose model. IEEE/ACM Transactions on Networking, 2002, 10(4):565-578.
[21] Ballani H, Costa P, Karagiannis T et al. Towards predictable datacenter networks. In Proc. the 2011 ACM Conference on SIGCOMM, August 2011, pp.242-253.
[22] Lee J, Turner Y, Lee M et al. Application-driven bandwidth guarantees in datacenters. In Proc. the 2014 ACM Conference on SIGCOMM, August 2014, pp.467-478.
[23] Erlebach T, Ruegg M. Optimal bandwidth reservation in hose-model VPNs with multi-path routing. In Proc. IEEE INFOCOM 2004, March 2004, pp.2275-2282.
[24] Zhu J, Li D, Wu J P et al. Towards bandwidth guarantee in multi-tenancy cloud computing networks. In Proc. the 20th IEEE International Conference on Network Protocols, October 2012.
[25] Dutta D, Kapralov M, Post I et al. Optimal bandwidth aware VM allocation for Infrastructure-as-a-Service. arXiv:1202.3683, 2012. https://arxiv.org/abs/1202.3683, Feb. 2018.
[26] Plummer D C, Smith D M, Bittman T J et al. Five refining attributes of public and private cloud computing. Technical Report, Gartner, 2009. http://www.gartner.com/DisplayDocument, May 2018.
[27] Lu S B, Fang Z Y, Wu J et al. Elastic scaling of virtual clusters in cloud data center networks. In Proc. the 36th International Performance Computing and Communications Conference, December 2017, pp.1-8.
[28] Herbst N R, Kounev S, Reussner R. Elasticity in cloud computing:What it is, and what it is not. In Proc. the 10th International Conference on Autonomic Computing, June 2013, pp.23-27.
[29] Shawky D M, Ali A. Defining a measure of cloud computing elasticity. In Proc. the 1st International Conference on Systems and Computer Science, August 2012, pp.1-5.
[30] Li K K, Wu J, Blaisse A. Elasticity-aware virtual machine placement in k-ary cloud data centers. Parallel and Cloud Computing, 2014, 3(2):22-31.
[1] Que-Ping Kong, Zi-Yan Wang, Yuan Huang, Xiang-Ping Chen, Xiao-Cong Zhou, Zi-Bin Zheng, and Gang Huang. Characterizing and Detecting Gas-Inefficient Patterns in Smart Contracts [J]. Journal of Computer Science and Technology, 2022, 37(1): 67-82.
[2] Rui-Xiang Ma, Fei Wu, Bu-Rong Dong, Meng Zhang, Wei-Jun Li, Chang-Sheng Xie. Write-Optimized B+ Tree Index Technology for Persistent Memory [J]. Journal of Computer Science and Technology, 2021, 36(5): 1037-1050.
[3] Yu-Wei Wu, Qing-Gang Wang, Long Zheng, Xiao-Fei Liao, Hai Jin, Wen-Bin Jiang, Ran Zheng, Kan Hu. FDGLib: A Communication Library for Efficient Large-Scale Graph Processing in FPGA-Accelerated Data Centers [J]. Journal of Computer Science and Technology, 2021, 36(5): 1051-1070.
[4] Xiao-Jing Zha, Yin-Shui Xia, Shang-Luan Xie, Zhu-Fei Chu. Defect-Tolerant Mapping of CMOL Circuit Targeting Delay Optimization [J]. Journal of Computer Science and Technology, 2021, 36(5): 1118-1132.
[5] Yue-Wen Wu, Yuan-Jia Xu, Heng Wu, Lin-Gang Su, Wen-Bo Zhang, Hua Zhong. Apollo: Rapidly Picking the Optimal Cloud Configurations for Big Data Analytics Using a Data-Driven Approach [J]. Journal of Computer Science and Technology, 2021, 36(5): 1184-1199.
[6] Hui-Ming Tian, Zhu-Fei Chu. Inversion Optimization Strategy Based on Primitives with Complement Attributes [J]. Journal of Computer Science and Technology, 2021, 36(5): 1145-1154.
[7] Yu-Jie Yuan, Yukun Lai, Tong Wu, Lin Gao, Li-Gang Liu. A Revisit of Shape Editing Techniques: From the Geometric to the Neural Viewpoint [J]. Journal of Computer Science and Technology, 2021, 36(3): 520-554.
[8] Jun Gao, Paul Liu, Guang-Di Liu, Le Zhang. Robust Needle Localization and Enhancement Algorithm for Ultrasound by Deep Learning and Beam Steering Methods [J]. Journal of Computer Science and Technology, 2021, 36(2): 334-346.
[9] Zeynep Banu Ozger, Nurgul Yuzbasioglu Uslu. An Effective Discrete Artificial Bee Colony Based SPARQL Query Path Optimization by Reordering Triples [J]. Journal of Computer Science and Technology, 2021, 36(2): 445-462.
[10] Jason Liu, Pedro Espina, Xian-He Sun. A Study on Modeling and Optimization of Memory Systems [J]. Journal of Computer Science and Technology, 2021, 36(1): 71-89.
[11] Mohammad Y. Mhawish, Manjari Gupta. Predicting Code Smells and Analysis of Predictions: Using Machine Learning Techniques and Software Metrics [J]. Journal of Computer Science and Technology, 2020, 35(6): 1428-1445.
[12] Bo-Han Li, Yi Liu, An-Man Zhang, Wen-Huan Wang, Shuo Wan. A Survey on Blocking Technology of Entity Resolution [J]. Journal of Computer Science and Technology, 2020, 35(4): 769-793.
[13] Maryam Zarezadeh, Hamid Mala, Homa Khajeh. Preserving Privacy of Software-Defined Networking Policies by Secure Multi-Party Computation [J]. Journal of Computer Science and Technology, 2020, 35(4): 863-874.
[14] Lan Huang, Da-Lin Li, Kang-Ping Wang, Teng Gao, Adriano Tavares. A Survey on Performance Optimization of High-Level Synthesis Tools [J]. Journal of Computer Science and Technology, 2020, 35(3): 697-720.
[15] Yun-Cong Zhang, Xiao-Yang Wang, Cong Wang, Yao Xu, Jian-Wei Zhang, Xiao-Dong Lin, Guang-Yu Sun, Gong-Lin Zheng, Shan-Hui Yin, Xian-Jin Ye, Li Li, Zhan Song, Dong-Dong Miao. Bigflow: A General Optimization Layer for Distributed Computing Frameworks [J]. Journal of Computer Science and Technology, 2020, 35(2): 453-467.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved