基于FBM模型的自相似流量建模仿真
2011-07-13裴承艳陈子辰康凤举
卢 颖 , 裴承艳 , 陈子辰, 康凤举
(1.西安工业大学 计算机科学与工程学院,陕西 西安 710032;2.西北工业大学 航海工程学院,陕西 西安 710072)
网络流量的研究对于改进网络结构,提高网络性能,进行入侵检测,提高网络安全性方面等都有着重要的作用。传统的业务模型大多假设基于泊松过程,即一种短程相关模型,其数学意义为:对于随机过程x(t)的当值与它的所有历值都无关,这种模型简单易实现。上世纪90年代,Leland等人在文献[1]中第一次明确提出了网络流量具有自相似性,并证明了网络流量的自相似性表现为网络业务数据流在很长时间范围内都具一种长程相关性,即对于随机过程的当值与它的所有历值都有关。之后,各国的研究人员对现有的一些网络进行观测和分析,发现无论网络的拓扑结构、用户数量、服务类型如何变化,这种自相似性始终存在。本文基于FBM模型分别采用RMD和Fourier变换法进行了流量序列的仿真生成实验,并利用R/S和方差时间曲线图法对所产生的自相似序列进行了验证及结果分析。
1 网络流量的自相似过程的定义
考察一个协方差平稳的统计过程 X={Xt:t=0,1,2,3,…},该过程的数学期望 μ=E[Xt]为常数,方差 σ2=E[(Xt-μ)2]为有限值,自相关函数 r(k)=E[(Xt-μ)(Xt+k-μ)]/σ2,k=1,2,3,…,仅与k有关.其中Xt可理解为第t个单位时间里到达的网络业务实体数。假定X的自相关函数有如下形式[2]:
对于每一个 m=1,2,3,…,令 X(m)={Xmt:t=0,1,2,3,…}表示一个新的序列,其中 Xmk=1/m(Xkm-m+1+…+Xkm),k=1,2,3,…代表长度为m的聚集过程.如是X(m)也定义了一个广义平稳随机过程,r(m)(k)表示 X(m)的自相关函数。 如果对所有的 m,均有:
当k→∞,称X为精确二阶自相似过程,并称H=1-β/2为其自相似参数。
2 自相似网络流量的刻画——FBM流量模型及仿真建模
在对网络业务流量建模中,要求用尽量少的参数来对实际网络的通信流量建模,另外就是要求产生的合成数据序列要显示与测量数据的相似的特征。常用的自相似数学模型中,分形布朗运动FBM是一种较为方便的流量模型。该模型是基于分形高斯噪声FGN(Fractal Gaussian Noise)过程的,是FGN的一个增量过程[3]。
仿真实验中分别采用随机中点置位法和离散Fourier变换法对FBM模型进行建模研究,从而产生分形高斯噪声的业务量。并对不同的自相似系数,不同的算法生成的网络流量序列进行对比,从而分析各自的性能。
2.1 随机中点置位法(RMD)
随机中点置位法(RMD法)利用逐渐子分区间方法产生模拟序列。该方法最大的优点在于快速。算法原理:先细分时间间隔[0,T],然后通过求左右两点的算术平均值,迭代地获得中点的数值,并加上一个偏移量。基于MATLAB仿真平台编写RMD算法步骤如下[4-5]:
原始业务流数据经过伪随机序列的加权迭代操作,生成前台序列,对前台序列进行性能分析,不断地调整模型参数,使得前台序列的性能与原始序列相匹配,并形成最终的RMD模型。
1)采用MATLAB中M语言中的random()生成一个均值为 0,方差为 1 的伪随机序列 G=G(n)(n=1,2,3…2m)作为原始序列;
4)迭代运算后的前台序列在数学上分析起来比较困难,所以对其进行余弦修正,SY=cos(X),最后得到生成的序列SY(n)(n=1,2,3,…2m)。
2.2 Fourier变换法
Fourier变换法是通过对分形高斯噪声的频谱进行Fourier变换获得业务数据,有很高的准确性,其基本思路是:产生一个频谱,然后对这个频谱进行快速Fourier逆变换。
基于matlab仿真平台编写快速Fourier逆变换法算法步骤如下[6]:
3 自相似序列生成实验及分析
3.1 自相似序列的生成
分别采用RMD算法和Fourier变换法,基于MATLAB软件进行仿真,设定自相似参数为0.7,0.8,0.9时生成序列长度为 8 192的自相似序列,图1(a)为 H=0.9时的 RMD算法生成结果,(b)为H=0.9时的Fourier变换法生成结果。
图1 RMD算法和Fourier变换法的自相似序列生成结果Fig.1 Self-similar sequence generated by RMD algorithm and Fourier algorithm
3.2 自相似过程中常用的参数估计法
常用自相似参数估计方法有:方差时间曲线图法、绝对值法、R/S方法、周期图法等[7],本文采用R/S法和方差时间曲线图法对生成序列的自相似性进行检验。
1)R/S 方法
2)方差时间曲线图法
自相似过程m的重聚集时间序列X<m>,其方差服从:Var(x<m>)=m-β·Var(x)。 其中,Hurst参数满足:H=1-(β/2),且 0<β<1。 给上述等式两边求对数可得:log[Var(X<m>)]=log[Var(X)]-β log(m)。 只需将 log[Var(X<m>)]与 m 的关系在对数坐标系中画出来,并通过线性拟合所得一斜率为-β的直线,若斜率在-1与0之间,则满足自相似性[8-9],即可间接计算Hurst参数。
3.3 生成序列的自相似性检测
对RMD算法生成的随机序列利用R/S方法和方差时间曲线图法进行Hurst参数估计。分别检测的是RMD算法指定H值为0.7,0.8和0.9时生成序列的自相似参数H值。
1)基于R/S方法的流量自相似性估计
根据R/S方法,如图2,在检测结果生成的散点图中两条虚线分别表示斜率为1以及斜率为0.5的直线。图中有很多散点通过线性拟合可得一条直线,该直线的斜率即Hurst参数,其值在0.5到1之间,具体数据如表1。H为算法指定理论值,H′为检测H值。为了更好地检验估测值与理论值的匹配程度,可以用相对误差的大小来表示,即ΔH=(H′-H)/H。
图2 R/S方法检测3个序列样本所得到的散点图Fig.2 Scatters of three sample sequence generated by R/S detected algorithm
图3 方差时间曲线图法检测3个序列样本所得到的散点图Fig.3 Scatters of three sample sequence generated by R/S test algorithm
表1 自相似序列的R/S检测结果(RMD算法)Tab.1 Test results of self-similar sequence generated by R/S algorithm(RMD algorithm)
表2 自相似序列的R/S检测结果(Fourier变换法)Tab.2 Test results of self-similar sequence generated by R/S algorithm(Fourier algorithm)
2)基于方差时间曲线图法的流量自相似性估计
在测量结果生成的散点图3中,有一条斜率为-1的直线。 另外一条是 log[Var(X<m>)]与 m 的 log-log 曲线关系经过线性拟合后所得的直线,其斜率满足-1到0之间,记拟合后的直线斜率为β,且β与H满足:H=1+0.5β。由方差时间曲线图法原理可知仿真结果满足自相似性。
从表1和表2中可以看出,得到的H′值与原自相似流的理论H值基本上匹配,其相对误差ΔH较小,从而证明了仿真算法的正确性。通过对RMD和Fourier变换法所生成的自相似序列进行比较,可以得出:RMD算法没有复杂的函数参与计算,计算流程清晰,速度快,而且简便易行,能快速地生成自相似序列,但Fourier变换法的生成序列准确性相对较高。RMD算法和Fourier变换法可以直接选择能够影响生成序列的自相似特性的变量值;但由于RMD算法是通过不断的分割间隔产生样本数据序列,生成的序列是在两个端点范围内的,所以选择哪个端点作为起始分割的端点,对最终产生的数据序列的自相似特性是有影响的,可能会给后来的自相似性参数估测带来不稳定性。
4 结束语
网络流量的自相似性决定了网络的行为特征,只有基于自相似的建模才能准确描述网络的实际情况。文中基于FBM模型分别采用RMD和Fourier变换法进行了流量序列的产生,并利用R/S和方差时间曲线图法对所产生的自相似序列进行了验证,表明了所仿真算法的正确性。此外还对两种方法在自相似序列生成的精度,产生速度和计算复杂性方面进行了比较。
[1]Leland W E,aqqu M S,Willinger W,et a1.On the selfsimilar nature of Ethernet traffic(extended version)[J].IEEE/ACM Transactions on Networking,1994,2(1):115.
[2]Lee Y H,Kassam S A.Generalized median filtering and related nonlinear filtering techniques[J].IEEE Transactions on A-coustica,Speech,Signal Processing,1985,33(3):672-683.
[3]Mandelbort B B,Van N J.Fractional brownian motions,factional noises and applications[J].SIAM Review;1968,10(4):422-437.
[4]朱效稳,谭献海,陈柏秀.基于多FBM的网络流量建模研究[J].铁路计算机应用,2009, 18(6):10-13.
ZHU Xiao-wen, TAN Xian-hai, CHEN Bai-xiu.Research on modeling of network traffic based on(MK)-FBM[J].Railway Computer Application, 2009, 18(6):10-13.
[5]李林峰,裘正定.自相似网络流量的Hurst指数的迭代估计算法[J].电子与信息学报,2006,Vol.28(12):136-158.
LI Lin-feng,QIU Zheng-ding.An iterative method to estimate hurst index of self-similar network traffic[J].Journal of Electronics&Information Technology,2006,28(12):136-158.
[6]徐明伟,仝爱军.基于自相似模型的网络性能测试[J].计算机工程与应用,2002, 38(5):56-59.
XU Ming-wei,TONG Ai-jun.Network performance testing based on self-similar modeling[J].Computer Engineering and Applications, 2002, 38(5):56-59.
[7]傅雷扬,王汝传,王海艳,等.R/S方法求解网络流量自相似参数的实现与应用[J].南京航空航天大学学报,2007,39(3):358-362.
FU Lei-yang, WANG Ru-chuan, WANG Hai-yan, et al.Implementation and application of computing self-similar parameter by R/S approach to analyze network traffic[J].Transactions of Nanjing University of Aeronautics amp;Astronautics,2007,39(3):358-362.
[8]王新.自相似网络流量的建模与预测[D].北京:清华大学,2003.
[9]王西锋,高岭,张晓孪.自相似网络流量预测的分析和研究[J].计算机技术与发展,2007,17(11):42-45.
WANG Xi-feng, GAO Ling,ZHANG Xiao-luan.Analysis and research on self-similarnetwork traffic forecast[J].Computer Technology and Development,2007,17(11):42-45.