基于IFTS 的网络动态负载均衡方法*
2019-09-17任神河郑寇全关冬冬惠军华
任神河,郑寇全,关冬冬,惠军华
(1.咸阳师范学院,陕西 咸阳 712000;2.国防科技大学信息通信学院,西安 710106;3.空军西安飞行学院,西安 710306)
0 引言
随着计算机网络技术的飞速发展,异构网络服务平台高度融合,网络数据规模不断扩大,网络服务请求呈几何级数增长,网络负载不均衡问题日益突出,网络资源的合理调配已成为亟待研究解决的重点问题[1]。动态负载均衡(Dynamic Load Balancing,DLB)能够通过分析网络节点实时负载信息和系统响应情况,合理规划节点任务部署,动态消除负载分布的不平衡性,是影响网络整体承载性能的关键因素,而实时准确的负载预测是获得高效DLB的前提和基础[2-3]。由于能够通过预测掌握网络未来运行状态,并有针对性地采取负载均衡策略,加快重载节点任务迁移,使得网络在有计划、可调控的状态下稳定运行,基于预测的网络DLB 理论一经提出,就引起了广泛的关注,并迅速发展成为一个重要而又热门的课题,取得了一系列研究成果。文献[4]针对负载随机突变特性,提出了基于反传网络和动态滑动窗口机制的负载预测方法,并设计了基于神经网络的负载预测器;文献[5]提出了基于多重标准的目标节点选择与负载预测的策略,但其需要维护额外的测试数据,易导致系统负载冗余;文献[6]利用自适应算法进行节点负载预测,较好地解决了负载冗余的问题;文献[7]依据不同网络资源间的相关性,给出了异构网络负载复合预测算法,提升了复杂性网络系统的负载均衡性能;文献[8]将基于预测的负载均衡理论引入云计算领域,提出了基于预测的虚拟机节点资源调度算法,拓展了基于预测的DLB 方法的实际应用范围。然而,随着网络拓扑结构的日趋复杂,网络负载变化呈现出了时变的、非平稳的和随机的新特性,模糊不确定性非常明显,传统的负载预测方法将网络负载看作平稳时间序列,采用线性模型进行预测,对负载变化趋势的拟合度不高,且预测的实时性较差,难以有效满足负载均衡调度程序对负载预测精度的实际需求。可见,基于预测的DLB 理论的拓展研究已刻不容缓。
直觉模糊时间序列[9-11](Intuitionistic Fuzzy Time Series,IFTS)作为模糊时序预测理论的重要扩充和发展,其序列变量的数学描述更加符合客观世界的模糊本质,且具有良好的理论延展性,为求解不确定性网络负载时序预测问题提供了新的思路和方法。因此,本文在分析网络负载模糊时序变化特性的基础上,构建了网络负载IFTS 预测模型,提出了基于IFTS 的网络DLB 算法,解决了网络负载预测中随机不确定性影响大的问题,减缓了系统工作负担,并通过加入实时校正模块,克服了IFTS 预测的不平稳波动问题,提升了网络资源利用率,从根本上增强了网络动态负载均衡系统的整体性能。
1 基于IFTS 的网络负载预测方法
1.1 基础知识
定义2 假设F(t)为论域U 上的IFTS,若F(t)仅由F(t-1)确定,或者仅由F(t-2)…或者仅由F(t-m)(m>0)确定,则一阶一元IFTS 预测关系可表示为:
若F(t)由F(t-1),F(t-2),…,F(t-m)(m>0)确定,则高阶一元IFTS 预测关系为:
则称F(t)为高(k)阶多(m)元IFTS。
其中,πA(xi),πB(xi)为集合A、B 的犹豫度参数。
1.2 网络负载模糊时序特性分析
为精确预测网络负载信息,必须分析了解节点负载的时序变化规律。如下页图1 所示,美国学者[8]通过对各类型网络节点负载信息的跟踪分析,发现网络负载变化具有以下特性(图中纵横轴分别表示网络节点类型和时段内平均负载量值):
1)负载分布是一种随机过程,具有明显的时变性、非线性和高度不确定性,是符合模糊时序分布的信号序列;
图1 网络节点负载分布图
2)负载变化具有很强的时序关联性,这表明网络负载预测是可行的,且利用时序理论进行负载预测是合适的;
3)负载变化受多因素影响,呈现出多样化分布特性,且具有很强的主元、次元因果关系,符合多元时序预测规律,可利用高阶多元时间序列进行预测;
4)负载变化虽具有突变不可预测性,但在时间尺度下又具有高度的自相似性和长相关性,这表明负载预测模型需具备预测时间长度的修正和重适应机制,而高阶IFTS 预测模型的自适应阶数调节策略就可有效解决这一问题。
综上所述,网络负载变化的模糊不确定性非常明显,利用高阶多元时变性IFTS 预测理论进行的网络节点预测是完全可行的。
1.3 基于IFTS 的网络负载预测模型
IFTS 预测理论是通过直觉模糊函数描述序列数据的模糊时序变化趋势,在历史数据不完备或不精确的条件下,利用直觉模糊逻辑推理进行不确定性预测,掌握序列未来值的分布规律[10]。如图2 所示,本文针对网络负载的模糊分布特性,构建基于IFTS 的网络负载预测模型,设计模型预测实时校正机制,以期提升系统预测效率,获取高精度的负载预测结果,其算法步骤可描述为:
图2 网络负载IFTS 预测模型
算法1 网络负载IFTS 预测算法
2 基于IFTS 预测的网络动态负载均衡方法
2.1 基于IFTS 的网络动态负载均衡模型
基于预测的DLB 方法大多是通过分析负载序列的时序关联特性,利用智能算法进行节点负载状态预测,并预先采取负载均衡策略,增强系统的负载均衡效能。然而,负载预测依赖大量的历史数据,而网络负载数据往往是模糊的、不确定的和时变的,这就限制了经典预测理论在网络负载预测中的应用。因此,如图3 所示,本文利用IFTS 对复杂不确定性时序数据的处理优势,基于IFTS 实时预测进行网络节点负载分配和任务调度,并动态监测网络运行状态和节点资源利用率,优化修正预测模型参数,确保负载预测的准确性和负载均衡系统运行的可靠性。下面,重点就负载均衡模型涉及的几个关键算法分别进行描述。
图3 网络负载动态均衡模型
2.2 基于IFTS 预测的负载调度算法
网络负载调度的重点是如何将任务请求合理地分配给各服务器节点,确保网络高效稳定运行。本文提出的基于IFTS 预测的负载调度方法主要包括负载量化、分配和负载迁移两个部分。负载量化、分配是在网络任务请求初始阶段,利用自适应比例分配的方法进行节点负载初分配;负载迁移是根据节点运行状态,基于节点负载预测值和观察值间的关联关系,进行节点负载迁移,从而减少任务请求在节点间重复迁移却无法执行的现象。其算法可描述为:
算法2 基于IFTS 的负载量化、分配算法
Step1:算法初始化。设定序列抽样周期T=2ω,其中ω 为节点通信往返时间;确定节点负载平均承载值Limax,i 为网络节点序号;抽取负载序列数据样本。
算法3 基于IFTS 的负载迁移算法
Step1:设定网络节点平均承载双阈值Lmin、Lmax;
1)共享发布网络节点空闲状态,包括节点地址Ri、可承受负载迁移量Ji;
2)协同负载调度模块停止节点负载预测,并同步更新节点状态为等待迁入;
3)接收负载迁移请求,包括节点地址Sj、负载迁移量Jj以及交互通信量Cij,计算映射节点间的通信时间Tij;
5)若节点状态变更为任务工作节点,则共享发布节点承载状态;否则,依据Ek排序接收负载迁移指令。若节点状态始终空闲,则等待周期T 后返回Step2。
Step4:进行网络负载迁移调度。
1)接收共享网络范围内节点状态,若由空闲节点,跳至3),否则,等待负载迁移请求;
2)收到负载迁移任务,记录并映射生成可承载节点列表;
3)向列表节点共享负载迁移任务,包括节点地址Sj、任务量Jj以及交互通信量Cij;
4)若收到列表节点更新指令,则删除相应节点信息;否则,在可承载量满足的条件下,选取Cij值最小的节点建立映射关系,进行任务迁移并同步更新节点状态,而后跳至Step2。
Step5:默认网络节点负载适中,转至Step2。
由此可见,本文构建的网络负载调度机制是一个基于预测的节点负载状态循环判断的DLB 过程,是根据负载预测启动相应操作,任务迁移按照最优化原则选择空载节点,而不是在相邻节点间逐一传递,且节点间的信息交换是由空载节点驱动,这就降低了节点信息交互的频度和代价,提升了负载迁移效率和精度。
2.3 基于IFTS 的网络动态负载均衡方法
与其他基于预测的网络负载均衡策略相比,本文提出的DLB 算法是从负载数据变化的模糊不确定性入手,利用IFTS 描述和处理负载序列变量,基于可变阶多元自适应直觉模糊逻辑推理进行负载预测,根据节点自适应比例分配进行负载初平衡处理,利用主动型空闲节点驱动策略进行动态地基于预测的网络负载均衡操作,从而提升系统运行效率,减少节点资源浪费,增强负载均衡系统自适应特征。算法的具体步骤可描述为:
算法4 基于IFTS 的网络负载动态均衡算法
Step1:按照抽样周期,抽取t-1 时刻网络节点负载序列数据集;
Step2:利用算法1 预测t 时刻网络节点负载;Step3:利用算法2 进行基于预测的节点负载量化和初始分配,并实时判定网络负载均衡状况;
Step4:利用算法3 进行网络负载动态均衡,并实时分析网络运行状态。若系统运行平稳则转至Step5;否则,优化调整模型参数,返回Step2;
Step5:算法结束。
3 实例分析
为了验证文中算法的有效性,选取文献[7]仿真实验数据作为负载序列历史数据,设定网络节点数n=4,观测时间间隔δ=0.5 s,抽样周期T=100 s,测试时刻数N=50。
首先,选取网络节点1 的负载序列数据,利用算法1 进行负载预测,计算预测相对误差,并将其与其他常用算法进行比较,结果分别如图4、图5 所示。
由图可知,在模型预测初期,本文算法的负载预测精度有较大波动,但随着时间的推移,算法表现出了良好的预测性能,负载预测精度和效率都得到较大的提升,尤其是加入实时校正机制后,预测误差有了明显的改善,且预测系统保持了稳定良好的运行状态。当然,本文算法需经过循环测试进行参数优化调整,算法复杂度相对较高,但与系统预测性能的提升相比,其可忽略不计。
图4 网络节点负载预测图
图5 负载预测误差对比图
其次,利用文中算法进行网络动态负载均衡操作,并与文献[12]描述的负载均衡方法进行比较,结果如图6、图7 所示。
图6 文献[12]算法网络负载均衡状态图
图7 本文算法网络负载均衡状态图
由图可知,本文利用IFTS 进行网络节点负载预测,并结合节点承载量值进行负载量化和预分配处理,可充分发挥网络节点计算能力,使得初始负载分布达到了较好的均衡状态;采用主动型空闲节点驱动策略进行负载动态调度,加快了网络重载节点的任务迁移速度,克服了传统算法周期性节点探询和迁移抖动的缺陷,获取较好的系统整体资源利用率,提高了网络负载动态均衡系统的运行效率。
最后,采用负载均衡系列研究系列文献中常用的求质数算例,比较不同数据规模下网络DLB 算法的执行效率,结果如图8、图9 所示。
图8 不同节点负载下的执行时间图
图9 不同数据规模下的执行时间图
可见,网络节点空载状态下,几类算法的执行效率基本相当,但当网络节点额外负载数目和数据规模不断扩大时,本文算法表现出了较大的优越性,获得了更为满意的网络负载均衡效果。因此,面对日益复杂的集群异构网络结构,本文算法具有更为广阔的应用前景。
4 结论
负载均衡是影响网络整体性能的关键因素,本文在分析网络负载模糊变化特性的基础上,构建了网络负载IFTS 预测模型,解决了随机非平稳负载序列数据难以预测的问题;利用基于预测的局部自优化比例分配方法进行节点负载预分配处理,充分发挥了网络节点整体计算优势;采用主动型空闲节点驱动策略进行网络负载动态调度,有效地降低了采样频率,提高了系统运行效率。通过实验分析,本文算法更有利于网络节点资源的优化配置。如何在提升节点负载预测时效性的前提下,降低负载均衡算法复杂度将是下一步研究的重点。