﻿ 基于虚拟机动态迁移的负载均衡策略
 计算机系统应用  2020, Vol. 29 Issue (5): 167-174 PDF

Load Balancing Strategy Based on Dynamic Migration of Virtual Machine
WANG Jing, HE Li-Li
School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China
Foundation item: Major Program of Science and Technology Bureau, Zhejiang Province (2015C03001)
Key words: data center     dynamic threshold     load balancing     virtual machine migration

1 基于虚拟机迁移的负载均衡策略 1.1 相关介绍

1.2 相关定义

 ${N_i} = \left( {C{U_i},R{U_i},B{U_i}} \right)$ (1)

 $L{d_i} = {N_i} \cdot {K_i} = {k_1} \times C{U_i} + {k_2} \times R{U_i} + {k_3} \times B{U_i}$ (2)

 $L{d_{dc}} = \frac{1}{n}\sum\limits_{i = 1}^n {L{d_i}}$ (3)

 $Thr = \left\{ {Th{r_h},Th{r_l}|Th{r_h},Th{r_l} \in \left( {0,1} \right)} \right\}$ (4)
 $Th{r_h} = \left( {Th{r_{\rm cpu}},Th{r_{\rm ram}},Th{r_{\rm band}}} \right)$ (5)

 $H = \left[ {\begin{array}{*{20}{c}} {N_{_1}^{\rm T}}&{{S_1}}&{Nu{m_1}} \\ {N_2^{\rm T}}&{{S_2}}&{Nu{m_2}} \\ \vdots & \vdots & \vdots \\ {N_{_n}^{\rm T}}&{{S_n}}&{Nu{m_n}} \end{array}} \right]$ (6)

2 基于动态阈值的迁移时机判决算法

2.1 动态阈值调整方案

(1) 考虑因素

① 全局负载度

t时段内的负载信息并根据公式(3)得到此时段内负载度集合 $\left\{ {L{d_{dc}}(1),L{d_{dc}}(2), \cdot \cdot \cdot ,L{d_{dc}}(t)} \right\}$ ; 为了减小负载瞬时值的影响, 剔除该集合中的m个孤立点, 此时负载度集合为 $\left\{ {L{d_{dc}}(1),L{d_{dc}}(2), \cdot \cdot \cdot ,L{d_{dc}}(t - m)} \right\}$ , 再采用权重法计算全局负载度, 如下:

 $L{d_{dc}} = \sum\limits_{i = 1}^{t - m} {{l_i} \cdot L{d_{dc}}\left( i \right)}$ (7)

 ${l_i} = {{{e^i}} / {\sum\limits_{j = 1}^m {{e^j}} }}$ (8)

② 高负载比率与低负载比率

 $\left\{ \begin{array}{l} \begin{array}{*{20}{c}} {L{r_h} = \displaystyle\sum\limits_{i = 1}^t {{l_i} \cdot L{r_h}(i)} } & {{N_{itype}} > Th{r_{type}}} \end{array}\\ \begin{array}{*{20}{c}} {L{r_l} = \displaystyle\sum\limits_{i = 1}^t {{l_i} \cdot L{r_l}(i)} } & {L{d_i} < Th{r_l}} \end{array} \end{array} \right.$ (9)

(2) 调整流程

$L{d_{dc}} \notin \left( {{\omega _l},{\omega _h}} \right)$ 时, 若 $\min L{r_l} < L{r_l} < \max L{r_l}$ $\min L{r_h} < L{r_h} < \max L{r_h}$ 时, 此时需进行阈值调整, 调整公式如下:

 $\left\{ \begin{array}{l} Th{r_h} = Thr_h' + \left[ {{\tau _h}\dfrac{{L{d_{dc}}}}{{Ld_{dc}'}} - \left( {1 - {\tau _h}} \right)L{r_h}} \right] \times Thr_h'\\ Th{r_l} = Thr_l' + \left[ { - {\tau _l}\dfrac{{L{d_{dc}}}}{{Ld_{dc}'}} + \left( {1 - {\tau _d}} \right)\left( {L{r_h} - L{r_l}} \right)} \right] \times Thr_l' \end{array} \right.$ (10)

$L{d_{dc}} < {\omega _l}$ $L{r_l} > \max L{r_l}$ 时, 数据中心负载度偏低, 此时需要选择需要进行迁移操作的部分轻载节点, 在轻载节点完成迁移操作后会关闭该节点. 确定待迁移(关闭)轻载节点列表方法如下:

 $\left\{ {\begin{array}{*{20}{l}} {n\left( {{\omega _l} - L{d_{dc}}} \right) < \displaystyle\sum\limits_{i = 1}^k {L{d_i}} } \\ {0 < k < n\left( {1 - \dfrac{{L{d_{dc}}}}{{{\omega _l}}}} \right) < s} \end{array}} \right.$ (11)

$L{d_{dc}} > {\omega _l}$ $L{r_h} > \max L{r_h}$ 时, 数据中心负载度偏高, 此时开启一个新的节点.

 图 1 状态阈值动态调整流程图

2.2 迁移触发算法

 $y = \prod\limits_{t \in {T_1}} {\dfrac{{x_t^{{w_t}}}}{{\mathop {\max }\limits_{t \in {T_1}} \left\{ {x_t^{{w_t}}} \right\}}}} \prod\limits_{t \in {T_2}} {\dfrac{{{{\left( {1 + \dfrac{1}{{{x_t}}}} \right)}^{{w_t}}}}}{{\mathop {\max }\limits_{t \in {T_2}} \left\{ {{{\left( {1 + \dfrac{1}{{{x_t}}}} \right)}^{{w_t}}}} \right\}}}}$ (12)

1) 收集各节点负载信息, 计算监测时间内全局负载度与高低负载节点占比, 判断是否需要更新阈值, 是则转第2)步, 否则转第3)步.

2) 分析全局负载度与高低负载占比, 调整并更新状态阈值.

3) 根据状态阈值, 分别判断各节点负载状态. 若节点负载指标高于高位负载, 开启该节点该负载指标过载评估, 转第4)步; 若节点负载度低于低位负载, 开启该节点负载度轻载评估, 转第5)步; 均未达到高低阈值要求为适载节点, 则转第7)步.

4) 对节点超过高位阈值的负载指标进行m期的查询并计算其评估值, 若评估值达到过载要求, 则判断此节点为该指标类型过载, 根据定义3, 更新高负载节点矩阵H. 转第3)步, 继续循环.

5) 对负载度低于低位阈值的节点进行m期的负载度查询并计算其评估值. 若m期内评估值均达到轻载要求, 则判断此节点轻载节点, 加入低负载节点列表.转第3)步, 继续循环.

6) 将低负载节点列表按负载度升序, 结合全局负载度, 判断是否在负载均衡范围 $\scriptstyle\left( {{\omega _l},{\omega _h}} \right)$ 中, 若 $\scriptstyle L{d_{dc}}\;< \;{\omega _{\rm{l}}}$ , 则根据式(11)计算得到待迁移操作的轻载节点集合L, 若 $\scriptstyle L{d_{dc}}\; >\; {\omega _l}$ $\scriptstyle L{r_h} \;>\; \max L{r_h}$ , 则启用一个节点.

7) 输出高负载节点矩阵H与低负载节点矩阵L.

3 基于负载类型感知的迁移选择算法

3.1 虚拟机选择算法

 ${N_{type}} - \overline {{V_{type}}} \le Th{r_{ type}}$ (13)

(1)\虚拟机与节点的资源依赖度

 ${R_{type}} = \frac{{\displaystyle\sum\limits_{i = 1}^n {{V_{type\;i}}{N_{type\;i}}} }}{{\sqrt {\left( {\displaystyle\sum\limits_{i = 1}^n {V_{type\;i}^2} } \right)\left( {\displaystyle\sum\limits_{i = 1}^n {N_{type\;i}^2} } \right)} }}$ (14)

(2) 虚拟机当前内存带宽比

 ${u_{rb}} = \sqrt {{{\left( {\frac{{{R_i}}}{{{B_i}}}} \right)}^2} - {{\left( {\frac{{{v_{{\rm ram}\;j}}}}{{{B_i}}}} \right)}^2}}$ (15)

(3)虚拟机负载贡献度

 $Lc = V \cdot K = {k_1} \times {v_{\rm cpu}} + {k_2} \times {v_{\rm ram}} + {k_3} \times {v_{\rm band}}$ (16)

 $S = \sqrt {L{c^2} + u_{rb}^2 + {{\left( {\dfrac{1}{{{R_{type}}}}} \right)}^2}}$ (17)

 $\dfrac{{{v_{\rm cpu}}}}{{CU}}:\dfrac{{{v_{\rm ram}}}}{{RU}}:\dfrac{{{v_{\rm band}}}}{{BU}}$ (18)

1) 根据节点评估得到的高负载节点列表, 获取高负载节点信息.

2) 根据此节点过载类型, 根据式(13)计算一次迁移可使得该节点解除过载情况的待筛选虚拟机集合.

3) 根据式(14)计算待筛选虚拟机集合中各虚拟机的此类资源依赖度, 并按递减排序.

4) 根据式(15)计算各虚拟机的内存带宽比; 根据式(16)计算虚拟机的负载贡献度.

5) 根据式(17)选择虚拟机作为待迁移虚拟机并计算其资源比, 加入待迁移虚拟机列表.

3.2 目的节点选择算法

 $M = \frac{{\displaystyle\sum\limits_{i = 1}^m {\sqrt {{{\left( {L{d_{_i}} - L{c_{_i}}} \right)}^2}} } }}{{\sqrt {\left( {{T_{\rm best}} - m} \right)} }}$ (19)

 $C\left( {{V_i},{N_i}} \right) = \displaystyle\sum\limits_{i \ne j} {D\left( {{N_{i\;{\rm target}}},{N_{j\;{\rm src}}}} \right)} \cdot f\left( {{V_i},{V_j}} \right)$ (20)

1) 根据节点评估得到的适载节点列表, 由负载度递增排序, 得到待选节点列表.

2) 根据式(19)计算待选节点列表计算虚拟机与节点的匹配度, 并按递减排序.

3) 按照匹配度顺序根据式(20)分别计算迁移代价.

4) 选取匹配度高且迁移代价最小的节点为目的节点.

4 实验验证与分析 4.1 实验准备

1) 虚拟机迁移次数. 实验中, 由于虚拟机个数、负载和位置的变化, 导致节点的负载动态变化, 虚拟机迁移策略影响着虚拟机的迁移次数, 故获取指定时间内的虚拟机迁移次数, 用来观测系统的虚拟机的迁移频率, 是判断虚拟机迁移策略性能的重要指标.

2) 数据中心平均负载度. 数据中心负载度是衡量数据中心负载情况与资源分配情况的有效指标, 若负载度保持较低水平则说明较多节点存在过多的空闲资源, 即资源分配不均衡, 若此指标数值过高, 则说明存在大量过载节点.

3)平均SLAV (Service Level Agreement Violation, SLAV). 平均 SLAV即平均服务等级协议违例率, 用来评价用户服务质量水平的常用指标之一, 该值越低则表示用户服务质量越高. 由于本文算法综合考虑了节点的CPU 资源、内存资源和带宽资源, 使用多维度平均SLAV计算方法, 如式(21):

 $\overline {SLAV} = \frac{1}{k}\sum\limits_{j = 1}^n {\dfrac{1}{3}\left( {\sum\limits_{i = 1}^3 {\frac{{v_{iR}^{type} - v_{iA}^{type}}}{{v_{iR}^{type}}}} } \right) \times 100\% }$ (21)

4.2 实验分析

 图 2 虚拟机迁移次数对比图

 图 3 数据中心负载度对比图

 图 4 数据中心平均SLAV对比图

5 结论与展望

 [1] Chen T, Zhu YM, Gao XF, et al. Improving resource utilization via virtual machine placement in data center networks. Mobile Networks and Applications, 2018, 23(2): 227-238. DOI:10.1007/s11036-017-0925-7 [2] Choudhary A, Govil MC, Singh G, et al. A critical survey of live virtual machine migration techniques. Journal of Cloud Computing, 2017, 6(1): 23. DOI:10.1186/s13677-017-0092-1 [3] Dave A, Patel B, Bhatt G. Load balancing in cloud computing using optimization techniques: A study. Proceedings of 2016 International Conference on Communication and Electronics Systems. Coimbatore, India. 2016. 1–6. [4] Shen HY. RIAL: Resource intensity aware load balancing in clouds. IEEE Transactions on Cloud Computing, 2017. DOI:10.1109/TCC.2017.2737628 [5] 曲晓雅, 刘真. 基于阈值滑动窗口机制的虚拟机迁移判决算法. 计算机科学, 2016, 43(4): 64-69. [6] 李腾耀, 张月玲, 张凤琴, 等. 基于动态阈值和占优资源的云资源调度方法研究. 计算机应用研究, 2017, 34(4): 1199-1203, 1216. DOI:10.3969/j.issn.1001-3695.2017.04.055 [7] Paulraj GJL, Francis SAJ, Peter JD, et al. A combined forecast-based virtual machine migration in cloud data centers. Computers & Electrical Engineering, 2018, 69: 287-300. [8] 刘鎏, 虞红芳, 郑少平. 面向业务动态变化的虚拟机迁移技术研究. 计算机应用研究, 2016, 33(2): 534-539. DOI:10.3969/j.issn.1001-3695.2016.02.050 [9] 胡荣辉, 王瑞通. 云环境下虚拟机集群迁移策略研究. 计算机技术与发展, 2017, 27(11): 33-36. DOI:10.3969/j.issn.1673-629X.2017.11.007 [10] 刘琨. 云计算负载均衡策略的研究[博士学位论文]. 长春: 吉林大学, 2016. [11] 郭三刚. 多属性对象决策的乘积指数加权法及应用. 陕西理工学院学报(自然科学版), 2012, 28(6): 34-39.