计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (1): 185-206.doi: 10.1007/s11390-019-1890-3

所属专题： Data Management and Data Mining； Computer Networks and Distributed Computing

• • 上一篇    下一篇

基于软管模型下的数据中心最大弹性资源调度算法

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.
  • 收稿日期:2018-07-15 修回日期:2018-08-30 出版日期:2019-01-05 发布日期:2019-01-12
  • 通讯作者: Jie Wu E-mail:jiewu@temple.edu
  • 作者简介: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.
  • 基金资助:
    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.

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 (PC)

412

补充材料

1

随着数据中心网络的日益普及，任务资源的有效管理及分配对于数据中心而言则变得越来越重要。该论文主要研究软管模型下的数据中心资源调度问题，以实现用户最大弹性调度为目标。最大弹性调度是指在用户请求虚拟集群资源分配的过程中，在满足计算和通信资源的前提下，不借助任务重新分配的方式实现用户虚拟集群增长的最大程度。本文我们首先考虑数据中心结构下的最大允许负载，使用软管模型作为通信模型。在此基础上，该论文提出一种基于消息的分布式线性解决方案传递，我们讨论该模型的几个属性和扩展。之后，根据得到的最大允许负载值，该论文提出了虚拟机的最大弹性放置方案。该方案具有可证明的最优性保证并同样适用于流量固定的多路径fat-tree数据中心结构。该论文的解决方案分别在真实实验平台以及模拟实验平台上进行了测试，大量的模拟实验与实验床实验验证了我们提出方案的有效性。

关键词: 数据中心网络, 云, 分布式算法, 弹性, hose模型, 优化

Abstract: 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] 孔雀屏, 王子彦, 黄袁, 陈湘萍, 周晓聪, 郑子彬, 黄罡. 定义和检测智能合约中低效率的Gas模式[J]. 计算机科学技术学报, 2022, 37(1): 67-82.
[2] Yu-Wei Wu, Qing-Gang Wang, Long Zheng, Xiao-Fei Liao, Hai Jin, Wen-Bin Jiang, Ran Zheng, Kan Hu. FDGLib：在数据中心中支持高效大规模图计算加速的通信库[J]. 计算机科学技术学报, 2021, 36(5): 1051-1070.
[3] Xiao-Jing Zha, Yin-Shui Xia, Shang-Luan Xie, Zhu-Fei Chu. 面向时延优化的CMOL电路容错映射[J]. 计算机科学技术学报, 2021, 36(5): 1118-1132.
[4] Yue-Wen Wu, Yuan-Jia Xu, Heng Wu, Lin-Gang Su, Wen-Bo Zhang, Hua Zhong. 大数据环境下基于数据驱动的云配置优化方法[J]. 计算机科学技术学报, 2021, 36(5): 1184-1199.
[5] Hui-Ming Tian, Zhu-Fei Chu. 基于具有互补属性器件的反相器优化策略[J]. 计算机科学技术学报, 2021, 36(5): 1145-1154.
[6] Yu-Jie Yuan, Yukun Lai, Tong Wu, Lin Gao, Li-Gang Liu. 回顾形状编辑技术：从几何角度到神经网络方法[J]. 计算机科学技术学报, 2021, 36(3): 520-554.
[7] Jun Gao, Paul Liu, Guang-Di Liu, Le Zhang. 基于深度学习与波束偏转的穿刺针定位与增强算法[J]. 计算机科学技术学报, 2021, 36(2): 334-346.
[8] Zeynep Banu Ozger, Nurgul Yuzbasioglu Uslu. 基于三元组重新排序的有效离散人工蜂群SPARQL查询路径优化[J]. 计算机科学技术学报, 2021, 36(2): 445-462.
[9] Jason Liu, Pedro Espina, Xian-He Sun. 关于储存系统建模和优化的综述[J]. 计算机科学技术学报, 2021, 36(1): 71-89.
[10] Mohammad Y. Mhawish, Manjari Gupta. 使用机器学习技术和软件度量的代码异味预测与预测分析[J]. 计算机科学技术学报, 2020, 35(6): 1428-1445.
[11] Gui-Juan Wang, Cheng-Kuan Lin, Jian-Xi Fan, Jing-Ya Zhou, Bao-Lei Cheng. 在考虑各种故障元素的情况下BCube网络的容错哈密顿性质和容错哈密顿连通性[J]. 计算机科学技术学报, 2020, 35(5): 1064-1083.
[12] Bo-Han Li, Yi Liu, An-Man Zhang, Wen-Huan Wang, Shuo Wan. 实体消解中分块技术的综述[J]. 计算机科学技术学报, 2020, 35(4): 769-793.
[13] Maryam Zarezadeh, Hamid Mala, Homa Khajeh. 利用安全多方计算保护软件定义网络策略隐私[J]. 计算机科学技术学报, 2020, 35(4): 863-874.
[14] Lan Huang, Da-Lin Li, Kang-Ping Wang, Teng Gao, Adriano Tavares. 一个关于高级综合工具性能优化的综述[J]. 计算机科学技术学报, 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：一种分布式计算框架的通用优化层[J]. 计算机科学技术学报, 2020, 35(2): 453-467.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] 张钹; 张铃;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：