自适应累加型失效检测模型.doc

自适应累加型失效检测模型研究摘要:传统失效检测输出二值信息分别代表信任或怀疑,然而该机制存在灵活性不足的问题针对这种问题,累加型失效检测以怀疑级别为输出,能适应同时运行的不同进程的 qos 需求在分析和研究已有失效检测模型和累加型失效检测算法的基础上,提出一种新的累加型失效检测模型——exp-acc-fd该模型利用幂律计算出心跳间隔的加权平均值,将该均值和距上次心跳到达的时间代入指数分布函数,从而计算出被监测进程的怀疑级别实验分析表明,在相同的检测时间内,exp-acc-fd 准确性高于 nfd-e 失效检测模型和phi 失效检测模型关键词:失效检测;自适应;怀疑级别;指数分布;幂律adaptive accrual failure detection model英文作者名 shi lei1*, chen wen-yuan1, tao yong-cai1, wei lin2英文地址(1.school of information engineering, zhengzhou university, zhengzhou henan 450001, china;2.school of software technology, zhengzhou university, zhengzhou henan 450002, china)abstract: the output binary information of traditional failure detection represents trust or suspicion respectively. however, the mechanism is lack of flexibility. for this problem, cumulative-type failure detection, taking the level of suspicion as output, can adapt to the qos requirements of different processes running simultaneously. an accrual failure detection model named exp-acc-fd was proposed on the basis of analyzing and researching the existing failure detection models and accrual failure detection algorithms. it calculates the weighted mean of heartbeat inter-arrivals with power law and substitutes the weighted mean and the time between last heartbeat coming and current time into exponential distribution to get suspicion level of monitored process. the simulation analyses show that the accuracy of exp-acc-fd is higher than nfd-e and phi within the same detection time.key words: failure detection; adaptive; suspicion level; exponential distribution; power law0 引言失效检测指的是检测者利用失效检测模式及失效检测算法对被检测对象进行检测,从而判断被检测者是否失效的过程。

分布式系统中,失效检测器是失效恢复、动态重启、可靠性通信、集群管理等功能的基础[1],在无线网络、云计算等领域也有重要的应用[2- 4]出现失效现象之后,需要有效的失效检测以及数据修复技术来延缓系统的平均数据丢失时间然而,实际系统中很难在系统发生失效后立即进行数据修复,简单的做法是系统中的存储节点定期互相发送心跳信息以确定是否出现设备失效[5-6]传统的失效检测(如 chen[7])输出一个二进制信息,用 1 和 0 分别代表信任和怀疑在较为复杂的应用条件下,这种输出机制存在灵活性不足的问题[8]针对这种缺点,défago 等[9]提出一种新的失效检测模型,即累加型失效检测模型这种失效检测对每一个进程都设置一个对应的值作为输出,这个值并不简单地判定信任或怀疑,而是代表对被检测进程的怀疑级别监测进程可以根据不同的怀疑级别采取不同的措施,而不是等进程失效后再做出决定,从而提高了系统的灵活性此外,传统的失效检测器将失效检测和失效后采取的措施做成一个应用,而累加型失效检测器利用其特殊的输出机制,使失效检测可以成为一种服务,不同的进程可以对怀疑级别做出不同的解读。

hayashibara 等[8]提出的 φ 失效检测模型假设心跳到达间隔服从正态分布,根据正态分布函数计算出时间 t 之前心跳到达的概率,作为 t 时刻的怀疑级别,然后与设定的阈值比较来判定进程是否失效然而,正态分布并不是对心跳间隔分布的理想近似指数分布是一种连续概率分布,可以用来表示事件发生的时间间隔,比如旅客进机场的时间间隔等研究表明指数分布在网络运算中具有广泛的 应用[10-12]本文提出一种基于指数分布的自适应的累加型失效检测模型,称之为 exp-acc-fd,采用的与心跳间隔时间对应的指数分布函数如式(1)所示f(x)=1-exp(-xμ),x≥00,x<0(1)由于较近一段时间的心跳间隔更能真实地反映当前网络状况,因此在计算均值 μ 时较近一段时间的心跳间隔应赋予较高的权值研究表明,许多网络特征都服从幂律分布[13]因此,本文提出的exp-acc-fd 中,窗口中的心跳间隔权值的分配采用了幂律计算加权平均值1 系统模型失效检测模型可以描述为一个四元组{p,t,a,o},其中:p 表示进程的集合{p1,p2,…,pn};t 表示全局时钟,该时钟为虚拟设备[14];a:p×t→o 表示由失效检测算法决定的映射;o 表示输出的集合,令 t∈t,ot∈o,有ot={ot_p1,ot_p2,…,ot_pn},其中 ot_pi 表示时刻 t,进程 pi 的输出。

1.1 进程通信与心跳采样异步分布式系统由一系列进程{p1,p2,…,pn}构成,每个进程上 运行着一个失效检测模块,任意进程之间可以通过网络通信,并周期性地发送心跳信息每个失效检测模块设立一张系统进程表,每个表项包括一个进程号和一个滑动窗口心跳间隔信息就储存在滑动窗口中最新的心跳到达时,计算出当前时刻与之前一个心跳到达时刻的时间间隔,并将这个时间间隔存入滑动窗口如果窗口已被填满,则会同时将窗口中最旧的心跳间隔移出窗口随后,采取加权平均的方法计算出窗口中心跳间隔的均值在分配权值时,窗口填入新数据的时间与当前时间越近,所赋权值越高权值分配方法如下:设滑动窗口中储存的最后一个心跳间隔,即最新计算出的心跳间隔对应的权值为 p1,之前计算出的心跳间隔对应的权值为 p2,再之前计算出的心跳间隔对应的权值为 p3,以此类推,且有∑wi=1pi=1,其中 w 为窗口中心跳间隔的数量根据幂律,存在以下关系:pi=k·i-m已有的研究表明,参数 m 接近于 1,为方便起见,令 m=1,则pi=k/i。

由于∑wi=1k/i=k∑wi=11/i≈k(ln w+r)=1故 k≈1/(ln w+r)其中 r 为欧拉常数据此,窗口中每个心跳间隔对应的权值可被 计算出来第 3 期 石磊等:自适应累加型失效检测模型研究计算机应用 第32 卷 1.2 算法描述exp-acc-fd 的监测进程为每一个进程设立一个怀疑级别 sl 值假设心跳间隔服从指数分布,sl 可由 t 时刻心跳到达的概率表示如果在 t 时刻心跳未到达,那么此时对应的到达概率越高,怀疑级别就会越大sl 可由式(2)得出:sl(t)=1-exp(-t-t0μ)(2)其中:t 为当前时间,t0 为上次心跳到达时间, μ 为滑动窗口中心跳间隔的加权平均假定窗口中心跳间隔和之后到来的心跳间隔服从同一概率分布,即参数(均值)相同,因此 μ 在计算怀疑级别时作为参数使用sl(t)表示对进程的怀疑级别,sl(t)越大怀疑级别越高当 sl(t)=0 时,表示对应进程正常;当 sl(t)=1 时,表示对应进程已经失效。

对于两个进程 p 和 q,如果进程 q 想知道进程 p 是否失效,就向自己的检测模块发送一个信号；检测模块在收到信号后计算 p 的怀疑级别 sl,并将 sl 的值返回给进程 q；进程 q 将 sl 的值与阈值比较,判定 p 是否失效或应采取哪些措施1.3 失效检测服务失效检测服务需要具备 3 个特点:可扩展性、灵活性和自适应性[15]exp-acc-fd 能够作为一种失效检测服务来使用 可扩展性体现在新的进程加入系统时,对系统性能影响较小新加入的进程向需要通信的进程发送心跳,接收到心跳的进程与新进程将对方的信息添加到自己的进程列表中新进程对系统性能的影响主要依赖于当前的网络状况,而非系统本身针对不同的 qos 需求,不同的进程对失效检测的要求不尽相同有些进程要求失效检测模型能够快速检测出失效,对检测的准确性要求较低;而有些进程要求失效检测模型具有尽可能高的准确性,不要求其能快速检测出失效对于这些不同的服务需求,可以对不同的进程设定不同的阈值。

由式(2)可知,设置较大的阈值意味着检测时间较长且准确率较高,而设置较小的阈值意味着检测时间较短且准确率较低因此,通过为不同的进程设置合适的阈值,exp-acc-fd 能满足同时运行的不同进程的 qos 需求exp-acc-fd 是一种自适应的失效检测模型,能够适应变化的网络环境随着网络状况的变化,窗口中的心跳间隔随之改变,使得均值 μ 不断调整,达到设定的怀疑级别所需的时间也与之前不同 μ 能够对网络状况的变化及时做出反应当心跳间隔变大时, μ值也随之增加,这样达到怀疑级别所需的时间也会增加,使得失效检测模型不会在较长时间没有心跳到达的情况下判定进程失效1.4 算法失效级别证明传统的失效检测模型根据限制错误的程度可以分为 8 类一般认为,实际应用的失效检测模型应达到◇p 类的要求,即具有强完。