《是电饭锅 (16)》由会员分享，可在线阅读，更多相关《是电饭锅 (16)（39页珍藏版）》请在金锄头文库上搜索。
1、1,网络流量自相似特性,2,提纲,问题提出 自相似的数学描述 产生自相似的原因 自相似对网络性能的影响 国内相关工作 可能的研究方向,,3,问题提出,什么是自相似？ 为什么研究自相似？ 产生自相似的原因？泊松过程随机变量(单位时间呼叫到达的次数)是独立的、且服从相似分布，即 PXknet(t)n/n! (n0) 马尔可夫模型对过去具有有限记忆，即在已经知道“现在”的条件下，其“将来”不依赖于“过去” 时间t与过去时间t-s，若s足够大，则t与t-s时的业务量是不相关的，即仅考虑s较小时业务到达间的相关性，称之为短时相关Short Range DependenceSRD模型,4,自相似的数学描述
2、,网络流量模型 时间序列，表示每单位时间到达的字节数或数据包数量 自相似的物理描述 网络流量在很宽的时间尺度内存在突发现象，“Burst” 时间尺度几十毫秒、秒、分钟、小时,5,自相似的数学描述,数学定义 假设前提平稳随机过程，即统计特性（均值、方差、相关等）不随时间推移而变化。一阶平稳（均值为常数），二阶平稳（均值和方差为常数，任意两时间点之间的协方差只取决于时间间隔，又称之为广义平稳） 自相关函数定义为： r(k)E(Xt)(Xt+k)/E(Xt)2,6,自相似的数学描述,自相似 条件1针对一个平稳随机过程 X(Xt: t0,1,2,3) 条件2其自相关函数满足r(k) kL1(k)，当k
3、，其中01，L1是慢变函数，即对所有x0，limtL1(tx)/L1(t)1（常见的慢变函数，如L1(t)常数，L1(t)(t)） 条件3-对X进行堆叠，堆叠产生的时间序列为X(m)(Xk(m)：k1,2,3 )，其中 Xk(m) 1/m(Xkm-m+1 Xkm)，k1, 2, 3, ,7,自相似的数学描述,自相似(Exactly second order) self-similar X(m)的自相关函数r(m)满足：r(m)(k)r(k)，对所有m1, 2, (k1, 2, 3, ) 渐进自相似(Asymptotically second order) self-similar X(m)的自
4、相关函数r(m)满足： r(m)(1)211，当m r(m)(k)1/22(k2)，当m (k2, 3, ) 2表示一个算子符，其作用于函数f(k)表示2(f(k)f(k1)2f(k)f(k1),8,自相似的数学描述,自相似参数H H1/2 r(k)k(2-2H)L1(k)，当k 渐进自相似(asymptotically self-similar) r(k)1/2(k1)2H2k2H(k1)2H 严格自相似 (exactly self-similar) 参数H满足0.5H1，参数H用来表示自相似的程度,9,自相似的数学描述,自相似的特性 长相关（LRDlong range dependence
5、、large scale correlation、long term correlation ） 长相关定义若一个随机过程满足自相似的条件1和条件2，即其自相关函数随时滞的增加呈双曲线衰减（幂律衰减），则该随机过程呈现长相关性 长相关自相似，自相似是长相关的特例/简单模型 不可和性，即k r(k)。不可和性的物理意义在于高滞后的相关虽然是个别的小量，但其累计的结果则十分重要 短相关过程(short-range dependence)自相关函数呈指数衰减，即r(k)k，当k(01)，其自相关函数是可和的，即0k r(k),10,自相似的数学描述,自相似的特性 慢衰减方差 自相似过程的方差满足va
6、r(X(m)am，当m，其中01，a是与m无关的正常数，与前条件2中相同 短相关过程的方差满足var(X(m)bm1，当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(X1X2X3Xk)kX(n)，k1,2,3n，R表示重新调整尺度的极差 R/
7、S: Rescaled adjusted range analysis,12,自相似的数学描述,自相似的特性 Hurst效应 Hurst在1991年和1995年发现大多数自然产生的时间序列满足ER(n)/S(n)cnH，当n，其中Hurst参数典型为0.73，c是与n无关的正常数 若观察序列取自一个短相关模型，曼德博罗等发现，满足ER(n)/S(n)dn0.5，当n，其中d与n无关的正常数 上述两式的差异通常称之为赫斯特效应或赫斯特现象 Hurst赫斯特英国的水文专家，长期从事尼罗河水坝工程研究 Mandelbrot曼德博罗分形理论的创始人，美籍法国数学家,13,自相似的数学描述,自相似 r(
8、k) kL1(k)，k(01)，L1是慢变函数 k r(k) var(X(m)am，m(01),短相关 r(k)k，当k(01)0k r(k) var(X(m)bm1，m,14,自相似的数学描述,如何测度自相似 数学定义针对无限长度的时间序列 实际中仅仅一段时间的取样，保证取样点足够多,15,自相似的数学描述,如何测度自相似 针对有限的时间序列来估计Hurst参数 方法1分析堆叠过程X(m)的方差，自相似的慢衰减方差特性 var(X(m)am- (m) (var(X(m)(m)(a) (m),0.4 H0.8,16,自相似的数学描述,如何测度自相似 方法2基于R/S统计的时域分析 ER(n)/
9、S(n)cnH (n) (ER(n)/S(n)H(n)(c) (n)原始的时间序列分为大小为n的块，对每个块计算其R(ti,n)/S(ti,n),H0.79,17,自相似的数学描述,如何测度自相似 基于周期图(Periodogram)的频域分析 协方差函数傅立叶变换功率谱 用周期图近似估计功率谱 从谱密度中找到参数H,18,自相似的数学描述,具备自相似的数学模型 自相似理论广泛地应用在水文和经济学领域 分形(分数)高斯噪声fractional Gaussian noise FGN 分形(分数)布朗运动fractional Brownian motion FBM，是分形高斯噪声的增量和过程 分形
10、(分数)自回归滑动平均过程fractional ARIMA processes AutoRegressive Integrated Moving-Average，渐进自相似过程,19,自相似的数学描述,网络流量的建模 ON/OFF模型叠加大量的ON/OFF源，每个源有两个状态，即ON和OFF。在ON状态，以连续速率发送数据包，在OFF状态，不发送数据包。每个发生源ON或OFF的时长独立地符合重尾分布（Heavy-tailed distribution） 重尾分布若一随机变量满足重尾分布，则PXx x-，当x, 00，xk，分布函数为F(x)PXx1(k/x)，当减小，大量的概率质量集中在分布的
11、尾部 H(3)/2 佩瑞多.韦尔福雷多（Pareto Vilfredo）意大利经济学家和社会学家,20,对流量自相似研究的三个方面,分析流量的特征，建模 小波分析（Discrete Wavelet Transform）和分形理论 分形和多重分形(Multifractal)模型 “可信的”网络流量生成模型 产生流量自相似的原因 评估自相似流量对网络的影响,21,产生自相似的原因,是流量内在的特性还是网络协议的调制作用？ Web流量的自相关性 (Boston University, 1996, 1998,实际数据) Web文件大小的分布（包括用户请求的文件、实际传输的文件、文件的传输时间、服务器端
12、存储的文件等）呈重尾分布，客户端Cache的影响相对较小Web文件传输时间的重尾分布Web流量的自相似性,22,产生自相似的原因,若文件大小符合重尾分布，则对应的文件传输均导致链路层的自相似性，Web、NFS、FTP等 (Purdue University, Boston University, 1996, NS模拟) 上述情况似乎都可以从ON/OFF模型找到解释的理由,23,产生自相似的原因,对IP流量成分的进一步分析 （Hungary, Budapest Uni. Of Tech.&Econo. 实际数据,2000） 不同协议成分如IP、ICMP、TCP、UDP、HTTP、SMTP、FTP
13、data、FTPcontrol、OSPF、Telnet，是否多重分形(multifractal)和分形(monofractal，即自相似),24,产生自相似的原因,重传机制(Retransmission)产生自相似特性(CMU，1997) 模拟条件输入是泊松到达（即，新数据包（不包括重传的数据包）到达是一个简单的泊松过程），数据包长度为常数，一个队列情况，先进先服务，无拥塞控制的重传机制 结论当时间尺度超过10倍的数据包传输时间，重传数据包流量的方差在总的流量（新数据包、重传数据包和丢失的数据包）中占据绝大多数成分。 即使改变重传机制的参数，如缓存大小、重传企图的次数和超时时限，不能改变重传负
14、载的自相似特性,25,产生自相似的原因,TCP拥塞控制的浑沌特性(Ericsson，Traffic Analysis and Network Performance Lab. 2000) 浑沌系统的特征：非线性(Nonlinearity)、确定性(Determinism)、混乱中的有序(Order in disorder)、对初始状态的敏感性(蝴蝶效应)(Sensitivity to initial conditions or the “butterfly effect”)、不可预见性(Unpredictability) 模型(NS模拟)：TCP Tahoe（Slow-Start、Conges
15、tion Avoidance、Fast Retransmit） 参数设置：link rate-C、delay-D、buffer size-B以及TCP流的数量-N,26,产生自相似的原因,TCP拥塞控制的浑沌特性(Ericsson，Traffic Analysis and Network Performance Lab. 2000) 结论：B/N的比率控制着系统的相位迁移，即从周期性到浑沌，并在特定的参数下产生自相似时间序列；单个的TCP流量符合渐进自相似，H0.5；在瓶颈缓存处堆叠的TCP流量是短时相关的，H0.5，其物理解释是TCP拥塞控制使瓶颈缓存占用率最大来平滑流量，堆叠的流量得到平滑，单个TCP流仍保持长相关性。 为什么堆叠的网络流量仍具有长相关性(H0.5)？TCP拥塞控制和具有重尾特性的上层协议共同作用。 TCP本身是一个产生自相似特性的确定性过程,27,产生自相似的原因,针对传输层(TCP和UDP)更进一步的研究(Purdue University, Boston University, 1996, NS模拟) TCP(Tahoe、Reno或Vegas)可靠的传输机制和流量控制机制保留了由文件大小重尾分布所引发的长相关性 无流量控制和不可靠的UDP并不使生成的流量具有长相关性,
