1网络流量自相似特性2提纲问题提出自相似的数学描述产生自相似的原因自相似对网络性能的影响国内相关工作可能的研究方向3问题提出什么是自相似?为什么研究自相似?产生自相似的原因?泊松过程—随机变量(单位时间呼叫到达的次数)是独立的、且服从相似分布,即P[Xk=n]=e-λ△t(λ△t)n/n!(n≥0)马尔可夫模型—对过去具有有限记忆,即在已经知道“现在”的条件下,其“将来”不依赖于“过去”时间t与过去时间t-s,若s足够大,则t与t-s时的业务量是不相关的,即仅考虑s较小时业务到达间的相关性,称之为短时相关ShortRangeDependence—SRD模型4自相似的数学描述网络流量模型时间序列,表示每单位时间到达的字节数或数据包数量自相似的物理描述网络流量在很宽的时间尺度内存在突发现象,“Burst”时间尺度—几十毫秒、秒、分钟、小时5自相似的数学描述数学定义假设前提—平稳随机过程,即统计特性(均值、方差、相关等)不随时间推移而变化。一阶平稳(均值为常数),二阶平稳(均值和方差为常数,任意两时间点之间的协方差只取决于时间间隔,又称之为广义平稳)自相关函数定义为:r(k)=E[(Xt-μ)(Xt+k-μ)]/E[(Xt-μ)2]6自相似的数学描述自相似条件1—针对一个平稳随机过程X=(Xt:t=0,1,2,3…)条件2—其自相关函数满足r(k)~k-βL1(k),当k→∞,其中0<β<1,L1是慢变函数,即对所有x>0,limt→∞L1(tx)/L1(t)=1(常见的慢变函数,如L1(t)=常数,L1(t)=㏒(t))条件3-对X进行堆叠,堆叠产生的时间序列为X(m)=(Xk(m):k=1,2,3…),其中Xk(m)=1/m(Xkm-m+1+…+Xkm),k=1,2,3,…7自相似的数学描述自相似(Exactlysecondorder)self-similarX(m)的自相关函数r(m)满足:r(m)(k)=r(k),对所有m=1,2,…(k=1,2,3,…)渐进自相似(Asymptoticallysecondorder)self-similarX(m)的自相关函数r(m)满足:r(m)(1)→21-β-1,当m→∞r(m)(k)→1/2δ2(k2-β),当m→∞(k=2,3,…)δ2表示一个算子符,其作用于函数f(k)表示δ2(f(k))=f(k+1)-2f(k)+f(k-1)8自相似的数学描述自相似参数HH=1-β/2r(k)~k-(2-2H)L1(k),当k→∞渐进自相似(asymptoticallyself-similar)r(k)=1/2[(k+1)2H-2k2H+(k-1)2H]严格自相似(exactlyself-similar)参数H满足0.5<H<1,参数H用来表示自相似的程度9自相似的数学描述自相似的特性长相关(LRD—longrangedependence、largescalecorrelation、longtermcorrelation)长相关定义—若一个随机过程满足自相似的条件1和条件2,即其自相关函数随时滞的增加呈双曲线衰减(幂律衰减),则该随机过程呈现长相关性长相关≠自相似,自相似是长相关的特例/简单模型不可和性,即∑kr(k)=∞。不可和性的物理意义在于高滞后的相关虽然是个别的小量,但其累计的结果则十分重要短相关过程(short-rangedependence)自相关函数呈指数衰减,即r(k)~ρk,当k→∞(0<ρ<1),其自相关函数是可和的,即0<∑kr(k)<∞10自相似的数学描述自相似的特性慢衰减方差自相似过程的方差满足var(X(m))~am-β,当m→∞,其中0<β<1,a是与m无关的正常数,β与前条件2中β相同短相关过程的方差满足var(X(m))~bm-1,当m→∞,其中b是与m无关的正常数自相似过程的方差衰减要慢于短相关过程11自相似的数学描述自相似的特性Hurst效应H表示Hurst参数,自相关程度的度量重新调制尺度权差(R/S)—对于一个给定的观察序列X1,X2,X3…..Xn,样本均值为X(n),样本方差为S2(n),则R(n)/S(n)=1/S(n)[max(0,W1,W2,…,Wn)-min(0,W1,W2,…,Wn)],其中Wk=(X1+X2+X3…..+Xk)-kX(n),k=1,2,3…n,R表示重新调整尺度的极差R/S:Rescaledadjustedrangeanalysis12自相似的数学描述自相似的特性Hurst效应Hurst在1991年和1995年发现大多数自然产生的时间序列满足E[R(n)/S(n)]~cnH,当n→∞,其中Hurst参数典型为0.73,c是与n无关的正常数若观察序列取自一个短相关模型,曼德博罗等发现,满足E[R(n)/S(n)]~dn0.5,当n→∞,其中d与n无关的正常数上述两式的差异通常称之为赫斯特效应或赫斯特现象Hurst赫斯特—英国的水文专家,长期从事尼罗河水坝工程研究Mandelbrot曼德博罗—分形理论的创始人,美籍法国数学家13自相似的数学描述自相似r(k)~k-βL1(k),k→∞(0<β<1),L1是慢变函数∑kr(k)=∞var(X(m))~am-β,m→∞(0<β<1)短相关r(k)~ρk,当k→∞(0<ρ<1)0<∑kr(k)<∞var(X(m))~bm-1,m→∞14自相似的数学描述MeasurementperiodTotalnumberofbytesTotalnumberofpacketsEthernetutilizationAugust1989total(27.45hours)11,448,753,13427,901,9849.30%October1989total(20.86hours)14,774,694,23627,915,37615.70%January1990total(40.16hours)7,112,417,58927,954,9613.90%February1992total(47.91hours)6,585,335,73127,674,8143.10%如何测度自相似数学定义针对无限长度的时间序列实际中仅仅一段时间的取样,保证取样点足够多15自相似的数学描述如何测度自相似针对有限的时间序列来估计Hurst参数方法1—分析堆叠过程X(m)的方差,自相似的慢衰减方差特性var(X(m))~am-β(m→∞)㏒(var(X(m)))~-β㏒(m)+㏒(a)(m→∞)β≈0.4H≈0.816自相似的数学描述如何测度自相似方法2—基于R/S统计的时域分析E[R(n)/S(n)]~cnH(n→∞)㏒(E[R(n)/S(n)])~H㏒(n)+㏒(c)(n→∞)原始的时间序列分为大小为n的块,对每个块计算其R(ti,n)/S(ti,n)H≈0.7917自相似的数学描述如何测度自相似基于周期图(Periodogram)的频域分析协方差函数傅立叶变换功率谱用周期图近似估计功率谱从谱密度中找到参数H18自相似的数学描述具备自相似的数学模型自相似理论广泛地应用在水文和经济学领域分形(分数)高斯噪声—fractionalGaussiannoiseFGN分形(分数)布朗运动—fractionalBrownianmotionFBM,是分形高斯噪声的增量和过程分形(分数)自回归滑动平均过程—fractionalARIMAprocessesAutoRegressiveIntegratedMoving-Average,渐进自相似过程19自相似的数学描述网络流量的建模ON/OFF模型—叠加大量的ON/OFF源,每个源有两个状态,即ON和OFF。在ON状态,以连续速率发送数据包,在OFF状态,不发送数据包。每个发生源ON或OFF的时长独立地符合重尾分布(Heavy-taileddistribution)重尾分布—若一随机变量满足重尾分布,则P[X>x]~x-α,当x→∞,0α2。最简单的重尾分布是佩瑞多(Pareto)分布,其概率密度函数为p(x)=αkαx-α-1,α,k0,x≥k,分布函数为F(x)=P[X≤x]=1-(k/x)α,当α减小,大量的概率质量集中在分布的尾部H=(3-α)/2佩瑞多.韦尔福雷多(ParetoVilfredo)意大利经济学家和社会学家20对流量自相似研究的三个方面分析流量的特征,建模小波分析(DiscreteWaveletTransform)和分形理论分形和多重分形(Multifractal)模型“可信的”网络流量生成模型产生流量自相似的原因评估自相似流量对网络的影响21产生自相似的原因是流量内在的特性还是网络协议的调制作用?Web流量的自相关性(BostonUniversity,1996,1998,实际数据)Web文件大小的分布(包括用户请求的文件、实际传输的文件、文件的传输时间、服务器端存储的文件等)呈重尾分布,客户端Cache的影响相对较小Web文件传输时间的重尾分布Web流量的自相似性22产生自相似的原因若文件大小符合重尾分布,则对应的文件传输均导致链路层的自相似性,Web、NFS、FTP等(PurdueUniversity,BostonUniversity,1996,NS模拟)上述情况似乎都可以从ON/OFF模型找到解释的理由23产生自相似的原因对IP流量成分的进一步分析(Hungary,BudapestUni.OfTech.&Econo.实际数据,2000)不同协议成分如IP、ICMP、TCP、UDP、HTTP、SMTP、FTPdata、FTPcontrol、OSPF、Telnet,是否多重分形(multifractal)和分形(monofractal,即自相似)24产生自相似的原因重传机制(Retransmission)产生自相似特性(CMU,1997)模拟条件—输入是泊松到达(即,新数据包(不包括重传的数据包)到达是一个简单的泊松过程),数据包长度为常数,一个队列情况,先进先服务,无拥塞控制的重传机制结论—当时间尺度超过10倍的数据包传输时间,重传数据包流量的方差在总的流量(新数据包、重传数据包和丢失的数据包)中占据绝大多数成分。即使改变重传机制的参数,如缓存大小、重传企图的次数和超时时限,不能改变重传负载的自相似特性25产生自相似的原因TCP拥塞控制的浑沌特性(Ericsson,TrafficAnalysisandNetworkPerformanceLab.2000)浑沌系统的特征:非线性(Nonlinearity)、确定性(Determinism)、混乱中的有序(Orderindisorder)、对初始状态的敏感性(蝴蝶效应)(Sensitivitytoinitialconditionsorthe“butterflyeffect”)、不可预见性(Unpredictability)模型(NS模拟):TCPTahoe(Slow-Start、CongestionAvoidance、FastRetransmit)参数设置:linkrate-C、delay-D、buffersize-B以及TCP流的数量-N26产生自相似的原因TCP拥塞控制的浑沌特性(Ericsson,TrafficAnalysisandNetworkPerformanceLab.2000)结论:B/N的比率控制着系统的相位迁移,即从周期性到浑沌,并在特定的参数下产生自相似时间序列;单个的TCP流量符合渐进自相似,H>0.5;在瓶颈缓存处堆叠的TCP流量是短时相关的,H≈0.5,其物理解释是TCP拥塞控制使瓶颈缓存占用率最大来平滑流量,堆叠的流量得到平滑,单个TCP流仍保持长相关性。为什么堆叠的网络流量仍具有长相关性(H>0.5)?TCP拥塞控制和具有重尾特性的上层协议共同作用。TCP本身是一个产生自相似特性的确定性过程27产生自相似的原因针对传输层(TCP和UDP)