High Availability for VM Placement and a Stochastic Model for Multiple Knapsack
High Availability for VM Placement and a Stochastic Model for Multiple Knapsack
复制标题
虚拟机放置的高可用性和多背包的随机模型
DOI：
10.1109/icccn.2017.8038384
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Shukla, Himanshu
中科院分区：
文献类型：
--
作者：
Shen, Bochao;Sundaram, Ravi;Russell, Alexander;Aiyar, Srinivas;Gupta, Karan;Nagpal, Abhinay;Ramesh, Aditya;Shukla, Himanshu
k-HA（高可用性）是云和集群中VM放置的重要容错属性-它是通过从故障主机重新定位VM而不中断其他VM来容忍多达k个主机故障的能力。长期以来，人们一直认为[1]确定k-HA布局的存在是CNOPP 3 -hard的。在一个令人惊讶而又简单的结果中，我们表明，k-HA减少到多个背包，因此在NP= NP 1。我们提出了一个多背包的随机模型，不仅捕捉现实世界的工作负载，但也提供了一个统一的基础，比较不同的多项式时间算法的效率。我们证明，使用中心极限定理和线性规划，存在一个最好的多项式时间的启发式，虽然不切实际的实施的角度来看。我们转向工业实践，并讨论了常用的优化方法的缺点-First- fit，Best-fit，Worst-fit，MTHM和CSP。负载平衡是工业中的基本客户需求。基于集群工作负载的大型真实数据集（来自行业领导者Nutanix），我们证明了自然负载平衡启发式-水填充-具有几个优秀的属性。我们比较和对比注水MTHM使用我们的随机模型，发现注水是一个启发式的选择。
k-HA (high-Availability) is an important faulttolerance property of VM placement in clouds and clusters - it is the ability to tolerate up to k host failures by relocating VMs from failed hosts without disrupting other VMs. It has long been assumed [1] that deciding the existence of a k-HA placement is ΣP 3 -hard. In a surprising yet simple result we show that k-HA reduces to multiple knapsack and hence is in NP= ΣP 1 . We propose a stochastic model for multiple knapsack that not only captures real-world workloads but also provides a uniform basis for comparing the efficiencies of different polynomial-time heuristics. We prove, using the central limit theorem and linear programming, that, there exists a best polynomial-time heuristic, albeit impractical from the standpoint of implementation. We turn to industry practice and discuss the drawbacks of commonly used heuristics-First- fit,Best-fit,Worst-fit,MTHM and CSP. Load-balancing is a fundamental customer requirement in industry. Based on a large real-world dataset of cluster workloads (from industry leader Nutanix) we show that the natural load-balancing heuristic - Water- filling - has several excellent properties. We compare and contrast Water-filling with MTHM using our stochastic model and find that Water-filling is a heuristic of choice.
登录
查看更多内容
离散分布和连续分布下的平均案例分析之间的根本差异：装箱案例研究
影响因子：
3.7
作者：
E. Coffman;C. Courcoubetis;M. Garey;David S. Johnson;L. McGeoch;P. Shor;R. Weber;M. Yannakakis
通讯作者：
M. Yannakakis
CHASE：云计算环境中的组件高可用性感知调度程序
DOI：
10.1109/cloud.2015.70
发表时间：
2015
期刊：
2015 IEEE 8th International Conference on Cloud Computing
影响因子：
--
作者：
Manar Jammal;A. Kanso;A. Shami
通讯作者：
A. Shami
分布式云中可靠的虚拟机放置
DOI：
10.1109/rndm.2016.7608297
发表时间：
2016
期刊：
2016 8th International Workshop on Resilient Networks Design and Modeling (RNDM)
影响因子：
--
作者：
Song Yang;P. Wieder;R. Yahyapour
通讯作者：
R. Yahyapour
LLL 算法的历史
DOI：
10.1007/978-3-642-02295-1_1
发表时间：
2010
期刊：
2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing
影响因子：
--
作者：
I. Smeets;A. Lenstra;H. Lenstra;L. Lovász;P. E. Boas
通讯作者：
P. E. Boas