数据分组网络中业务模型的研究进展

数据分组网络中业务模型的研究进展

1泊松或马尔可夫模型主要作用于网络业务的特性到目前为止，电信网络已经发展成为一个传统意义上的电话网络，包括我们熟悉而未知的网络、移动互联网、广播电视网络等。本文关注的是基于数据分组交换的网络,数据分组网包括的范围很广,在数据分组网中,使用了新的技术和新的网络思想,提供给用户新的业务和新的应用,那么传统的业务模型对网络业务的描述是否仍然适用呢?分组交换网是基于分组交换的,这与传统电信网的电路交换有根本差别,在分组网中传送的主要是数据业务,包括正在兴起的多媒体业务,而在传统的电信网中传送的主要业务是话音业务。在传统的网络设计和系统分析中采用泊松过程或马尔可夫过程可以得到很好的结果,但是在对分组网络的业务进行监测后发现,如果仍然采用泊松或马尔可夫模型,那么得到的排队分析结果就和实际情况有很大的差别,比如第一代ATM交换机根据传统的排队模型做出的缓存大小的预测大大小于实际需要的缓存容量,这样的差别是由于实际网络业务在多数甚至全部的时间尺度内表现出很大的变化(长相关性),而泊松或马尔可夫模型是无记忆、短相关的,只在很短的时间范围内表现出突发性,所以用泊松或马尔可夫模型分析得到的结果是过于优化的结果。近年来,在网络业务模型的描述中,采用了自相似性(self-similar)或称为长相关性(long-range-dependent,LRD)这一概念来描述实测到的网络业务过程中表现出的突发性,这些业务包括局域网(LAN)业务、广域网(WAN)业务、VBR视频业务、WWW业务等。研究人员采用分形(fractal)来描述这些业务并进行建模。普通的分形过程被称为自相似随机过程,或单分形(monofractal)。但是由于网络业务的时间尺度可以在很大的范围内变化,实测网络业务不仅表现出长相关,还表现出了短相关性,那么用普通的自相似过程能不能完全地描述网络业务在很小的时间尺度下的特性呢?对小的时间尺度的网络业务的特性有没有必要描述呢?对此也有不同的观点,MuradS.Taqqu等认为对LAN和WAN没有必要将模型的难度上升到多分形(multifractal),但更多的观点认为多分形模型在网络业务模型上的研究是有必要的。本文首先描述了自相似随机过程的定义及性质,包括普通的自相似随机过程(单分形)和多分形;然后介绍已有的效果较好的模拟多分形的业务模型,并对这些模型进行分析;最后说明这些模型对网络业务带来的影响。2随机过程的数学描述2.1一般的随机过程文献中对自相似随机过程的定义有很多种,分为连续时间随机过程和离散时间随机过程。2.1.1意义上的相似参数一个时间连续的随机过程被称为自相似随机过程,如果其中,λ>0,0<H<1,=d表示分布意义上的相等。H被称作自相似参数,或Hurst参数,H的值是相关的持续性的量度:H越大,相关性越强。由式(1)有:分形布朗运动(fractionalBrownianmotion,FBm)过程是一种典型的自相似随机过程,已经有比较成功的使用FBm的网络业务模型。2.1.2随机过程相关函数网络流量的分析已经被严格地限制为离散时间的二阶或近似二阶自相似过程。Leland等及Beran等对自相似随机过程的定义是:令X={Xt:t=0,1,2,…}为一个协方差平稳的随机过程,其均值为u,方差为62,自相关函数为r(k),k≥0。假设r(k)形为0<β<1。注意到,这被称为随机过程的长相关性(LRD)。对m=1,2,3,…,令X(m)={Xt(m):t=1,2,3,…}表示由X得到的叠加过程这是一个协方差平稳的随机过程。X称为有Hurst参数H=1–β/2的(严格的)二阶自相似过程,如果对所有m=1,2,3,…,Var(X(m))=σ2m–β且这里r(m)(k)是X(m)的自相关函数,如果对所有足够大的k,有则X被称作(近似)二阶自相似,其中r(k)由式(2)定义。X具有自相似性的意思是X(m)和X具有(严格的或近似的)相同的二阶统计特性。2.2算法的基本思想多分形的概念最早是用于对湍流(turbulence)现象的间断性的描述,将间断性用于描述网络业务时,其表达的是网络业务的突发性的合成以及在不同时间尺度下突发性的不同。可以想象,一个简单的多分形模型就能够描述基本的(可能是时变的)LRD业务的突发性。典型的多分形的定义是基于乘法过程或层叠模型(multiplicativeprocessesorcascademodels)得到的。假设有一单位长度的线段,并且这个线段有一单位质量,将此单位线段分解成一系列小的线段,每一段长度为ε,同时将单位质量划分成权重列{wi},其中wi是第i段线段的质量,则其矩为这里q是实数。当wj为0时,wjq项也为零,不用考虑。q为正数时得到的是较大的权重,而负的q值得到的是较小的权重,如果我们有一个关于q的实函数τ(q),使得对每一个q,有且权重{wi}是不均匀的,那么权重列wi(ε)组成一个多分形(multifractal)测度,注意到归一化条件说明τ(1)=0。{wi}的不均匀性由所谓的广义维数(generalizeddimensions)Dq可以比较好地说明Dq是关于q的单减函数,当{wi}不均匀时,Dq与q密切相关。目前对乘法多分形的研究是基于二进划分的,具体方法是,将单位线段分成等长度的两段,同时将单位质量划分成r和1-r两部分,并将它们分配给分成的两段线段,参数r是一个普通的随机变量,有概率密度函数函数(pdf)P(r),0≤r≤1,r称为乘子(multiplier),根据同样的规律划分刚才得到的线段,此过程的图解见图1,乘子r在图中写成rij,其中i表示第i次分解,第i次分解后每段线段的长度是2-i,假设P(r)关于r=1/2对称,并且有连续的矩u,u2,这样rij和1-rij的边缘分布均为P(r),第N次分解后权{wn,n=1,2,…,2N},可以写为wn=u1u2…uN,这里,ul(l=1,2,…,N)为rij或1-rij,这样,{ui,i≥1}均为独立同分布的具有pdfP(r)的随机变量,选择不同的pdfP(r),就可以得到不同的二进乘法多分形过程。图2为选择不同pdf得到的{wi}举例,其分解次数为12。将不同的{wi}用于网络业务模型的排队分析中,wi的值的物理意义可以为到达间隔时间,也可以为单位时间内业务量(分组数、比特数等),这样多分形过程就可以用于网络业务的建模。3多分形特性的提出在网络业务模型的研究中,MuradS.Taqqu的结论是能够使用自相似业务模型时,没有必要采用多分形模型。而Feldmannn和Gilbert等分析了WAN业务的多分形特性,得出的结论是对WAN业务而言,在考虑其短的时间尺度变化时需要多分形模型,后来他们提出了一种复合模型:短时间尺度的多分形+长时间尺度的LRD模型;美国莱斯大学的RudolfH.Riedi等提出了一种基于小波变换的多分形模型(multifractalwaveletmodel,MWM);加州大学洛杉矶分校的GaoJian-Bo[12～14]提出一种乘法多分形模型。这些模型在对一些著名的实测网络业务流量数据的分析中都表现出比原来单纯使用单分形模型更好的特性。下面主要就后两种模型进行讨论。3.1基于多自相似模型的小波模型离散小波变换(discretewavelettransform)用位移和膨胀后的小波函数ψ(t)以及位移后的比例函数φ(t)来替代原来的信号X(t),选择适当的小波和比例函数,使成为正交基,则信号X(t)可以表示为其中对以时刻0、频率f0为中心的小波ψ(t),小波因子Wj,k是时刻2–jk,频率2jf0时的信号内容的量度,比例因子Uj,k是时刻2-jk时的局部均值的量度。小波变换中,j是分析的尺度:J0表示的是最大的尺度或是最低的分析精度;j越大分析精度越高。Haar小波是最简单的正交小波基,其小波和比例函数见图3。小波变换可以很好地近似分形布朗运动(FBm)和分形高斯噪声(fGn)的Karhunen-Loeve变换。这样小波变换就可以用于网络业务的传统自相似模型中,模拟其LRD特性等。但是真实的网络业务本质上是正值的,而且其突发性更强,另外除了长相关性外,真实的网络业务还有短相关性,这与单纯的自相似性不一致。为了使模型中信号总为正值(与实际情况相同),有对所有j,k来说,|Wj,k|≤Uj,k,假设Wj,k=Aj,kUj,k,其中乘子Aj,k是[-1,1]上的独立随机变量。这就建立了一个多分形的小波模型(MWM)。如果适当地选择Aj,k,与fGn模型一样,MWM能很好地表示出一组正数的LRD特性,而且由于MWM的乘法构造,MWM还能使其高阶统计特性与实际情况相符,这是fGn做不到的。图4为实际的网络业务数据与分别由WMW和fGn得到的数据的比较,可以看到,MWM更好地模拟了实际情况。乘法过程用随机乘子将一个节点流过的网络流量划分成小的部分,这在时间尺度小的时候非常适用于对网络业务的模拟。另外由于MWM还能很好的模拟网络业务的长相关性,在已有对LAN和WAN业务的模拟中,可以看到MWM性能的优越性。但是WMW需要log2n个参数,其中n是业务流数据的长度,这样其计算的复杂性相应就比较大,这也是MWM的一个缺点。3.2基于数据的乘子设置GaoJian-Bo[12～14]提出了乘法多分形模型来模拟分组数据网络的业务。此模型包含两种类型:点过程模型和计数过程模型。这两种模型都只有1到2个参数,也就是说非常简单。GaoJian-Bo在对著名的Bellcore(现为Telcordia)给出的网络业务实测数据分析以后,发现LAN和WAN中业务流数据在一定的时间尺度范围内,其到达间隔时间序列与分组长度序列等点过程是多分形的;而计数过程虽然只是近似多分形的,但其在视频变比特率业务(VBRtraffic)的业务建模中完全适用。另外计数过程在研究网络业务合成时比点过程方便。乘法多分形过程的构造简介如下:{Ti}和{Bi}用来定义实际网络业务过程,{Ti}是到达间隔时间序列,其中Ti表示第i与第i+1个分组之间的到达间隔时间,{Bi}表示分组长度序列,其中Bi表示第i个分组的长度。这样得到的网络业务称为B流量。在固定分组长度的网络中,设分组长度均为,{Ti}同前,这样得到的网络业务称为P流量。在网络节点测得的合成业务流被视为随机计数过程,表示固定时间(∆t)内到达节点的比特数目或分组数目,分别写为表示第i个间隔中到达的比特数,表示第i个时隙里到达的分组数,每个分组的大小是b个比特,这些过程可以直接由B流量和P流量得到,分别称为流量。由∆t的选取可以得到网络业务的多分形性要在一定的尺度范围内才能体现。对到达间隔时间序列与分组长度序列而言,可以考虑排队系统MFe/MFg/1,MFe和MFg表示多分形到达间隔时间列和分组大小列的分布分别为双指数分布(式(15))和截尾高斯分布(式(16)),选择适当的αe和αg,就对网络业务建立了模型。图5是单服务员FIFO排队系统实测网络业务数据(虚线)与相应的MFe/MFg/1排队模型(实线)得到的等待队长的分布比较,MFe/MFg/1模型的参数为(αe,αg)=(20,190),图中三条线的业务量强度由上到下分别为ρ=0.7、0.5和0.3。可以证明,MFe/MFg/1模型得到的系统尾分布特性与由实际情况得到的尾分布特性一致对计数过程而言,选择乘子的pdf为选择参数对(p,d),使得到的乘法多分形过程在系统轻、中、重负载的情况下都能很好的与实测网络业务相符合。另外注意到对不算太小的业务量强度而言,系统缓存大小超过一定值时,系统的尾概率几乎垂直下降,称这一点为膝点(kneepoint),膝点在工程应用中很重要,因为它比较精确地描述了网络业务的突发性。图6比较了随业务量强度变化的不同业务(实测与由模型得到的)的膝点,图中,虚线是实测业务,实线是乘法多分形业务模型所得业务。3.3主要影响因素多分形模型应用与网络业务的建模时,不但能表现网络业务的在大的时间尺度下的突发性,还能表现单分形模型不能表现的小的时间尺度下的突发性,这与多分形过程本身的多比例特性紧密联系在一起。由于小波变换本身固有的比例特性,用小波这个数学工具来表现多分形是很好的选择,但是由于小波变换的复杂性,导致使用小波变换的困难。乘法多分形模型在表现多分形特性时,模型简单,参数比较少,但是在对实测的LAN和WAN中业务的计数过程的表示中,不能精确表现网络业务的多分形特性。另外由于网络性质的变化很快,在不同网络中有不同的表现,相应参数就会改变,那么在网络设计时,得对网络特性有一个比较正确的认识,使用的模型才能很好地预测网络的性质。对于网络业务模型的研究,还会着眼于其精确性和易实现性,数学工具的选择非常重要。例如英国的QueenMaryandWestfieldCollege的RaulJ.MondragonC用混沌映射(chaoticmaps)的方法提出一种业务模型来模拟网络业务,这种研究还在进行中。这也是应用数学的研究方向之一。另外由于我们现在一般网络业务看作多个独立源业务的合成,那么多分形业务流的合成是否仍然保持其多分形特性,如果是那么相应参数是否应该改变,怎样改变呢?这也是多分形业务研究的一个方向。在现代移动通信(比如第三代移动通信)中,引入了越来越多的除话音以外的业务,使移动通信网中的业务也趋向于表现