基于测量的自相似网络流量预测研究

基于测量的自相似网络流量预测研究

通过首次提出网络自相似过程的概念，对网络的自相似特征进行了大量研究。在文献[2、3、4、5、6、7、8、9、10、11和12]中，不同的网络环境在不同的域中传输网络时，网络具有普遍不同的自相似现象。这种相似性的长度增加，缓冲区需求能力降低，端部延迟率和传输率降低。这些测量参数的恶化程度与湖值测量的自相似度成正比。在文献中，我们研究了降低hurst参数，改进网络性能指标的方法。在web中，为了提高网络响应能力，预测了humst参数。在基于自相似特性的网络流量预测时,往往由于自相似计算过程复杂,计算量大而导致其在实际过程中无法满足实时预测应用的要求.本文在对当前自相似网络流量预测进行综述和研究的基础上,根据网络自相似流量特性提出了一种自相似网络流量预测算法.分析表明,该算法在不明显降低预测效果的情况下,可显著减少计算量.1网络搜索模型1.1随机变量的i独立同分布设m个同类的业务源,单个业务源ON状态持续时间为τ(i),OFF状态持续时间为θ(i).随机变量τ(i),θ(i)独立同分布,其分布函数为p(τ>t):t-αt→∞,1<α<2.(1)即τ(i),θ(i)均服从Pareto分布,具有有限均值E(X)<∞和无限方差.可以证明,当m→∞时,总的业务是渐近自相似的,且满足H=(3-α)/2.1.2jbm法假设分形高斯噪声{Xn}n=1,2,…为一平稳高斯噪声,均值为μ=E(Xn),方差为σ2=E[(Xn-μ)2],则r(k):H(2H-1)k2H-2,k→∞,0.5<H<1.(2)At为FBM,它满足At=mt+√amBΗt,t∈(0,∞).(3)其中,m为业务的平均到达速率,a>0为方差系数,BΗt为标准的FBM且满足0.5<H<1.1.3属性bp型随机过程{X0}n=1,2,…为FARIMA过程,如果它具有如下形式:Φ(B)=ΔdXn=Θ(B)ωn.(4)式中Φ(B)=1-Φ1(B)-…-Φp(B)p为AR项;Θ(B)=1-Θ1(B)-…-Θq(B)q为MA项;后向算子BXn=Xn-1;Δ=1-B为差分算子,Δd=(1-B)d=Γ(-d+n)/(Γ(-d)Γ(n+1))为差分分形算子,Γ(·)表示Γ函数.式中FARIMA(p,d,q)模型需要三个参数,其中p,q为整数,d为实数.对于d∈(-1/2,1/2),X为一平稳可逆过程,当k→∞时相关系数r(k):ak2d-1,a为有限正值且与k无关.X是渐近自相似的,且H=d+1/2.1.4功率谱的基本概念设随机过程x(t)的正交小波变换为x(t)=∞∑m=-∞∞∑n=-∞cmnφmn(t)‚cmn=∫∞-∞x(t)φmn(t)dt‚φmn(t)=2m/2φ(2mt-n).(5)若母小波φ(t)具有R(R>1)阶消失矩,即∫∞-∞trφ(t)dt,r=0,1,…,R-1,且小波系数{cmn}是零均值互不相关的随机变量,方差为varxmn=σ22-γm,0<γ<2R,则x(t)的功率谱为Sx(ω)=σ2∞∑-∞2-γm|Ψ(2-mω)|2,(6)且Sx(ω)是近似1/f的或称广义1/f的,即σ2L/|ω|γ≤Sx(ω)≤σ2n/|ω|γ.(7)式中σ2L,σ2n是满足0<σ2L<σ2n<∞的参数.1.5响应面模型若参数0<α≤2,σ>0,-1≤β≤1,而且μ∈R,则α稳定过程的特征函数表达式如下:Eexp(iθX)={exp{-σα|θ|α[1-iβ(signθ)tanπα2]+iμθ}‚α≠1；exp{-σ|θ|[1+iβ(signθ)ln|θ|]+iμθ}‚α=1.(8)式中:signθ={1‚θ＞0；0‚θ=0；-1,θ＜0.α为特征指数,表征突发程度;β为偏斜参数(-1<β<1),α和β联合决定概率密度函数的形状;σ为尺度参数;μ为位称参数.若X服从上述参数决定的α稳定分布,则记为X～Sα(σ,β,μ).(9)1.6尺度系数法k合成网络流量多分形小波模型合成网络数据的方法与小波域独立高斯模型方法相似.首先,生成根尺度系数U0,0和Aj,k,然后运用公式{Uj,2k=2-1/2(1+Aj-1,k)Uj-1,k‚Uj,2k+1=2-1/2(1-Aj-1,k)Uj-1,k‚(10)递归计算得到尺度系数序列{U0,k},从而合成相应的网络流量.多分形小波模型是一个乘法模型,合成信号可以用累乘公式C(n)[k]=2-nU0‚0n-1∏j=0[1+(-1)kAi,k](11)表达,上式得到的数据是非负且长相关的.1.7比较模型的自相模型各种自相似网络流量模型的优缺点见表1.2时域方法和频域方法Hurst参数估计的方法分为时域和频域两类.常用的时域方法包括方差时间法(VT)、绝对值法(Abs)、留数法(Res)和R/S法.频域方法有周期图法、Whittle法和小波法.2.1xn.12的n/m算法描述序列X的m阶聚集序列X(m)的n阶中心矩为:AΜ(m)n=1Ν/mΝ/m∑k=1|X(m)k-ˉX|n.(12)如果序列X是高斯的或方差有限的,那么对于大的N/m和m,满足:AM(m)n∝Cmn(H-1).(13)在对数坐标图得到的直线的分辨率为n(H-1).当n=1时,对应算法是绝对值法(Abs);当n=2时,对应算法为方差的时间法(VT).2.2最小均方线a+bt将原始序列X分为大小为m的子块,每子块的部分和Y(t),最小均方线a+bt,其余数的样本方差为1mm∑t=1(Y(t)-a-bt)2.(14)该方差正比于m2H.2.3rse表达对于时间序列X,部分和Y(n)及样本方差S2(n),R/S方法统计量为:RS(n)=1S(n)[max0≤i≤n(Y(t)-tnY(n))-min0≤i≤n(Y(t)-tnY(n))].(15)对于FGN有:E[RSn]∝CΗnΗ.(16)2.4谱密度的确定对于长度为N的时间序列X,其周期图定义为:Ι(v)=12πΝ|Ν∑j=1X(j)eijv|2.(17)在方差有限的情况下,考虑低频部分,谱密度为I(v)∝|v|1-2H.3.5功率谱密度的选择已知X为高斯随机序列,其周期图为I(ω),功率谱密度为f(ω,H),由最大似然原理,使g(Η)=∫π-πΙ(ω)f(ω,Η)dω‚(18)取最大值的H即为Hurst参数.2.6般估算参数的估算对一个信号x(t),利用小波分解法可分解为以下形式:x(t)=approxj+j=J∑j=1detailj(t)=∑kax(J,k)ϕJ,k(t)+j=J∑j=1∑kdx(j,k)Ψj,k(t).(19)其中ax(J,k)=<x,ϕJ,k(t)>dx(J,k)=<x,ΨJ,k(t)>.H的估计值为:Η(j1‚j2)=12[j2∑j=j1Sjjηj-j2∑j=j1Sjjj2∑j=j1Sjηjj2∑j=j1Sjj2∑j=j1Sjj2-(j2∑j=j1Sjj)2+1].(20)其中ηj=log2(1n∑k|dx(j,k)|2)‚sj=(nln22)/2j+1‚ηj为渐近方差倒数,j为分解级数,nj=2-j,n为原始数据长度,nj为j尺度小波分解下的小波函数系数的个数.2.7多种检测法联合使用的稳定性分析方差时间法、绝对值法都属于聚类方差法,计算速度较快,结果一般相同;周期图法实际使用时可使用快速傅利叶变换来提高算法的速度;R/S法是最普遍使用的方法,但速度较慢;小波法虽然速度较快,实现却相当复杂.用时间方差法、绝对值法估计H参数的时间复杂度为O(n),用留数法、R/S法和Whittle法估计H参数的时间复杂度为O(n2),其余方法的时间复杂度为O(NlogN).文献等指出在已有H参数估计方法中,Whittle估计量方法是最精确的,小波估计方法与之相近.方差时间图和R/S分析属于时域分析方法,只能统计得到Hurst系数.Whittle估计法是一种频域分析法,能得到Hurst系数的置信区间等精细结构,使自相似性更具可信性.一般来说,多种检测法应该联合使用,首先用时域法判断序列是否具有自相似性,再用频域法对Hurst系数估值,并得到Hurst系数的性能指标.3业务流的到达率分形布朗业务能较好地解释网络中的自相似现象,所以假设网络中的业务流(假设均为聚集流)是分形布朗业务:At=mt+√amΖ(t).(21)式中:m为业务流的平均到达率;a>0为方差系数(即单位时间内的方差均值比σ2/m);Z(t)为正态分形布朗业务,是严格的自相似过程.H为自相似参数.假设P(X>B)=ε,有效带宽CE的近似解为(Norros公式):CE=m+(κ(Η)-2ln(ε))1Ηa12ΗB-(1-Η)Ηm12Η.(22)式中κ(H)=HH(1-H)(1-H);ε是业务流信元丢失率.4基于测量的流量自类似于平等的带宽算法4.1通过h参数进行带宽波动的可行性自相似网络模型相关计算与H参数有着直接的联系,通过各种方法计算和求H值是进行流量自相似预测的第一步.网络流量的平均值和方差总处于不断的变化中,总流量的变化以自相似H参数进行波动.而平均流量和流量的突发性和长相关性带来了方差的波动,H参数是这种波动和长相关的直接体现,通过H参数可以动态地表征流量的波动.因此用平均流量作为等价带宽计算的均值,用H参数来计算流量波动对带宽的影响可以比较近似地求得网络实际流量.通过不断测量和计算网络流量的变化,包括均值和H参数,从而近似地预测出网络流量.由于H参数计算量大,复杂度高,因此通过减少计算量,降低计算复杂度,使网络流量预测接近实时性能,是基于测量的流量自相似带宽预测的一种可行办法.4.2采样时隙s的测量算法通过T-S窗口法测量平均流量和计算H参数,H参数在不同区间变化时重新计算.利用H参数的相对稳定性和平均流量的即时性相结合来预测网络的流量.步骤如下:1)使用T-S窗口法测量平均流量.设T为测量窗口的大小,它是成百上千个分组传输所需的时间,S为采样时隙,T=nS,n为大于5的整数;LS为采样时隙S内的平均负载,LS总是在每个采样时隙S结束时计算.采用如下策略测量和估计负载m值:在每个测量窗口Ti开始时,把m置为上一测量窗口Ti-1内包含的所有S中平均负载,即m=1n∑i=1nLsi,其中S1,S2,…,Sn为Ti-1内的n个时隙.2)使用R/S方法测量和计算网络流量,并使用Whittle法来求H参数的置信区间及H参数.3)将m作为平均值,H作为Hurst参数代入Norros公式,则可求出当前等价带宽为:CE=m+(κ(Η)-2ln(ε))1Ηa12ΗB-(1-Η)Ηm12Η.(23)4)设链路带宽为C,将C等分成n个区间.若测量值m在持续某一个区间内变化,则不重新计算H值,即H值不变,仅计算m值;若m值变化到不同区间,则启动H值计算,以此方式来实时跟踪和监测网络流量.4.3通过h计算进行流量变化时的流量预测由于自相似网络流量计算相对复杂,实时流量测量往往会占用较多的CPU时间,特别是在流量高峰期或数据量变化比较剧烈的时候,计算更加复杂和频繁.采用本文提出的算法,可将流量划分成不同区间,当流量在不同区间跳变时,才进行H参数计算.而对于流量的平均值则因为属于累加求平均算法,不会占用较多的资源.由于减少了H参数的计算量,因此对于流量的预测可以更快速和准确,而占用的计算资源却相对较少.1流量低的情况如下当流量较小时,比如占用网络带宽不到30%,可以认为网络流量的平均值可以代替网络的实际流量,此时可以不启动H参数计算.2流量大时的情况如下当流量较大时,比如占有网络带宽超过80%的情况,可以认为网络的H参数基本不变.这一点在以太网的流量自相似研究中得到了验证.3算法复杂度的变化算法在实现过程中,H参数的计算复杂度根据使用的求解方法不同而变化,设为O(x).平均值求解的复杂度是常量,当未分区时,算法实现复杂度为O(nx).分区之后,算法复杂度减小为O(xlogn).5基于自相似网络的多分形研究网络业务流中的自相似性直接影响着网络的性能,而在自相似的基础上存在着一系列的网络业务流