计算机系统性能评价+7

1第7讲自相似传输模型（第六章）（先看一些自相似简介，自然中的自相似现象，了解自相似学科的背景）本单元的学习我们需要掌握以下内容：1.为什么要研究自相似传输模型？2.了解自相似现象（自然中的自相似现象、几何中分型学、信息学中的自相似）3.数据自相似现象的数学描述及性质4.自相似现象在对性能评价的影响为什么要研究自相似传输模型？（1）在一些真实系统中，排队分析结果不同与实际观测结果；（2）真实的网络业务具有统计上的自相似性；（3）自相似作为一门新的数学工具，正在用于许多领域中。自相似网站：数据的自相似现象例子：1Mbs传输链路，4000bits的帧，每一个帧的传输时间为4ms。在接收者接收帧到达的时间(每一个帧的第1位到达)：082432728096104216224240248288296312320648656672680720728744752864872888896936944960968很难给出到达的统计规律和特性呈现出突发性一些到达时间紧密组合在一起，一些到达时间松散，最大间隔328ms（从320到648），很多比较小的间隔40ms左右。我们压缩这个传输，分成集群，在每个集群中到达帧之间的间隔不超过5个帧的传输时间（20ms），并且记录每个集群的开始时间，我们有：0722162886487208649362在集群之间的间隔是不均衡的，仍然难于考察其特性。试图进行更大的压缩，在每个集群中到达帧之间的间隔不超过10个帧的传输时间（40ms），并且记录每个集群的开始时间，我们有：0216648864在这种情况下，4个集群中每个集群之间的间隔是216，432，216。一个小间隔216，跟随一个大间隔432，再跟随一个相同的小间隔216。现在回来看第一次压缩的情况，有8个集群，072216288648720864936同后面的压缩有相同的规律。前4个集群：到达的间隔是72，144，72。后4个集群：到达的间隔也是72，144，72。两个集群组之间有一个大的间隔。再回来观测原来32个数据帧的达到，将它们分成8个组，有同样的规律呈现。082432728096104216224240248288296312320648656672680720728744752864872888896936944960968在每个组中，数据帧到达的间隔是8，16，8。结论：该时间序列在各个分辨率上都呈现出相同的模式，与压缩的程度无关。这就是信息学上的自相似的特性。自相似是一个物理现象，在一个域(dimension)以不同程度的“透镜”或不同尺度进行观测时，表现出同一性。域可以是空间（以长度，宽度度量）或时间。本节仅考虑时间序列和对于时间而呈现自相似性的随机过程。(a)一个时间序列(b)压缩的时间序列图6.1.1自相似时间序列图6.1.1显示了在时间序列上的自相似现象。图6.1.1(a)可以看做数据帧到达时间序列，而图6.1.1(b)可以看做数据帧压缩集群到达时间序列。这个例3子可从坎特(Cantor，也有翻译为康托集)集中推导出来。坎特集的组织结构，遵循如下规律：1.从[0,1]闭区间开始，由一个长线表示。2.去掉这个长线中间的1/3部分。3.对每下一步，去掉上一步产生长线中间的1/3部分。这是一个递归过程，可由下列步骤精确定义。让Si表示第i层递归后的坎特集，那么：1,9897,3231,9291,021,3231,011,00SSS我们可想象坎特线是一个时间线，每下一步按乘1/3修改时间线。在每一步，集合的左（右）部分的处理同整个集合的处理相同。坎特集合揭示所有自相似现象的两个特性：1.可以在任何小级别(scale)上进行组织。组织过程可无穷尽，可得到各种间隔的样式。另一方面，在不断重复修改下，我们可以看到一个平滑、连续的曲线，同时它就越来越没有特点。2.结构的重复性。一个自相似结构包含在所有级别上本身更小的重复。例如，在每一步，坎特集合的左（右）部分是上一步整个集合的完全重复。在真实物理现象中，这些特性不一定完全保持。在某个级别的某个点，结构和自相似性可能破坏，但纵观所有级别的整个范围，物理现象呈现出自相似性。6.2自相似数据传输由于数据传输是一个随机过程，因此，要考虑统计自相似。6．2．1自相似定义1．连续时间定义一个自相似随机过程的常见定义是基于连续时间变量的直接分级，见下面描述。一个随机过程x(t)具有参数H(0.5H1)在统计上是自相似，如果对于任何a0，过程a-Hx(at)同x(t)有相同的统计特性。相互关系可由下面3个条件表达：41.HaatxEtxE均值2.HaatxVartxVar2方差3.HXXaasatRstR2,,自相关H是突发(Hurst)参数或叫做自相似参数，它是自相似的关键度量。更确切地说，H是统计现象持续性(persistence)的测量，是随机过程的长范围相关(long-rangedependence)的一个测量。H＝0.5表示缺少自相似。H值越接近1，持续性或长范围相关的程度就越大。例：考虑分数布朗运动(fractionalBrownianmotion,FBM)过程BH(t)定义如下：15.0;0)(HttXtBHH其中，X是一个正态分布的随机变量，它的均值为0，方差为1；H是这个过程的一个参数。证明它具有自相性。已知:对正态分布的的随机变量X,E[X]=0,Var[X]=1,FBM过程的概率密度分布表达为：HHtxHBettxf222221,可以证明这个随机过程具有平稳增量，在随机过程中已经证明：Var[BH(t)–BH(s)]=E[(BH(t)–BH(s))2]=|t–s|2H证明：（1）均值：因为E[X]=0，所以E[BH(t)]=0。（2）方差：对于任何随机变量X和常数a，Var(aX)=a2Var(X)，因此Var[BH(t)]=Var[tHX]=t2H。对于一个给定的t值，BH(t)等于一个常数乘以正态随机变量X，因此BH(t)是具有零均值的正态分布随机变量。注意当H＝0.5时，FBM过程就简化为一个一般布朗运动过程。（3）自相关BH(t)的自相关是一个重要数量关系，表达为stRHB,=E[BH(t)BH(s)]。这个值可用下面方法推导。首先，可以获得：)()(2)()()()(222sBtBsBtBEsBtBEHHHHHH重新排列，获得：5HHHHHHHHHHHHHststsBtBVarsBVartBVarsBtBEsBEtBEsBtBE22222221)()()()(21)()()()(21)()(利用上面的式子：stRaststaasatasatasatRHHBHHHHHHHHB,221,22222222综合以上三点：分布朗运动过程具有自相似性。2．离散时间定义在很多情况，我们关心一个随机过程，它是定义在离散时间点上，离散时间随机过程X(t)定义为{xt,t=0,1,2,}。对于一个静止时间序列x，我们定义m-压缩时间序列,2,1,0,)()(kxxmkm，以致于：kmmkmiimkxmx)1()(1例如，)3(x定义为：331323)3(kkkkxxxx这个压缩时间序列一种观察的方法可认为是压缩时间级别的一种技术。我们可以考虑)1(x是这个时间序列的最高级或最高解。过程)3(x是相同过程在级别上缩减3的一个因子。如果过程的统计(均值、方差、相关等)随着压缩而保留，那么我们能够处理和解决自相似过程。我们也能把序列)(mx的每一个点看做过程x的一个时间的平均。对于一个遍历(ergodic)过程，一个时间平均应等于全体平均，而且时间平均的方差当m变大时应相当快地变成零。对于一个自相似过程，情况并不是这样，方差是要变成零，但要比静态遍历过程慢得多。一个具有参数β(0β1)的过程x是确切自相似的，如果对于所有m=1,2,6，我们有mxVarxVarm)()()(方差)()()(kRkRxxm自动相关参数β是同上面定义突发参数H是相关的，H=1-(β/2)。对于静态、遍历的过程β=1，而且时间均值的方差以1/m的速率减成零。对于一个自相似过程，时间均值的方差减成零的速率相当慢。一个弱的自相似过程条件描述如下：一个过程x说做是渐近自相似的，如果对于所有k足够大mxVarxVarm)()()(方差maskRkRxxm)()()(自动相关这个定义说明压缩过程的自动相关同前面的定义有相同的形式，变化的程度或突发性在不同时间级别是相同的。6．2．2自相似过程的性质1．长范围相关自相似过程最重要特性之一是长范围相关。这个特性以τ增加时自协方差C(τ)的行为来定义。对许多过程来说，自协方差随着τ快速减弱。例如，泊松增加过程具有增量L和均值λ，对于τL，自协方差是：0)()(222RC一般，一个短范围相关(short-rangdependent)过程满足条件：它的自协方差减弱速率至少同指数一样快，有10,)(akasakCk其中≈表示两边的表达式是彼此渐进成比例。在典型的数据传输模型中，一般使用的是短范围相关过程。使用下列关系式：1110xxxkk7我们能获得kkC)(是有限的。同上述短范围相关相反，一个长范围相关有双曲线减弱的自协方差：10,)(kaskkC其中β如以前定义一样，是相关的突发参数，H=1-(β/2)。在种情况中，kkC)(。长范围相关直观地影响自相似过程的持续性，亦即，在所有时间级别上集群和突发特性的存在。2．频谱密度(SpectralDensity)平稳随机过程的功率谱（或谱密度）是它自相关函数的傅立叶变换。关于长范围相关的另一种说法，可由频谱表达。功率频谱密度接近幂定律：10,01)(waswwS一个离散时间随机过程的频谱密度可以定义如下：kkkwjkRSekRwS)()0()()(2能够表达γ=1–β=2H–1。同长范围相关相反，短范围相关过程的特性由频谱密度表达时，当w→0，它依旧是有限的。当γ=0或者说H＝0.5，表明是短范围相关过程。在自动相关函数中，如果对于大的k，R(k)的值不能充分快速地衰弱而形成一个有限和，造成S(0)的值是无限的。3．重尾分布(Heavy-tailedDistributions)重尾分布可由概率密度表达，概率密度函数用于描述传输过程，例如，分组到达的间隔时间和突发长度。一个随机过程X的分布说是重尾的，如果：80,1Pr)(1xasxxXobxF在一般情况下，一个具有重尾分布的随机变量，表现出一个高的或甚至无限的方差。最简单的重尾分布是具有参数k和α(k,α0)的帕里多(Pareto)分布，它的密度和分布函数是：)(0)()(kxxFxf)0;(1)()(1kxxkxFxkkxf并且它的均值是：)1(1][kXE参数k规定随机变量可取的最小值。参数决定随机变量的均值和方差：如果2，分布有无限的方差；如果1，它有无限的均值和方差。图6.2.2比较了Pareto和指数密度函数在长线性级别上的情况。注意到，在这个级别上，指数密度函数是一条直线，反映分布的指数性衰减。Pareto分布的尾部衰减比指数慢得多，这就是“重尾”的含义。6．2．2自相似数据传输的例子自从1993年以来，一些研究成果已经表明数据传输的样式可由自相似过程9模拟，它适合真实网络的多种情况。下面表现一些典型例子。例子1.Ethernet传输Leland和Willinger等人收集了在Bellcore在1989年和1992年之间各种各样Et