《关于网络流量自相似特性的研究讲解材料》由会员分享，可在线阅读，更多相关《关于网络流量自相似特性的研究讲解材料（48页珍藏版）》请在金锄头文库上搜索。
1、1,关于网络流量自相似特性的研究,马皓 北大网络实验室 2002年10月31日,2,提纲,问题提出 自相似的数学描述 产生自相似的原因 自相似对网络性能的影响 国内相关工作 可能的研究方向,3,问题提出,研究起源 Will Leland, Murad Taqqu, Walter Willinger, and Daniel Wilson, On the Self-Similar Nature of Ethernet Traffic (Extended Version), IEEE/ACM Transactions on Networking, February 1994.(Bellcore 51
2、0 citations) Vern Paxson, Sally Floyd, Wide-Area Traffic: The Failure of Poisson Modeling, IEEE/ACM Transactions on Networking,3(3), June 1995. (Lawrence Berkeley Lab. 408 citations, FTP & Telnet) J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger, Long-Range Dependence in Variable-Bit-Rate Video T
3、raffic, IEEE Transactions on Communications, February/March/April, 1995. (193 citations),4,问题提出,意义 开拓了全新的研究领域，经典的理论分析依据（如泊松过程和马尔可夫模型），不在适合网络流量的分析和建模。 “.the (r)evolution of the Internet is impacting the world of mathematics in the small as well as in the large - both on how mathematics is done, and,
4、for understanding the network itself, on what sort of mathematics is done - and why this, in turn, makes Internet engineering a gold mine for new, exciting and challenging research opportunities in the mathematical sciences.” by Walter Willinger and Vern Paxson in “Where Mathematics meets the Intern
5、et” “Goodbye Poisson” & “Hello Fractal” !,6,自相似的数学描述,网络流量模型 时间序列，表示每单位时间到达的字节数或数据包数量 自相似的物理描述 网络流量在很宽的时间尺度内存在突发现象，“Burst” 时间尺度几十毫秒、秒、分钟、小时,7,8,9,10,11,自相似的数学描述,数学定义 假设前提平稳随机过程，即统计特性（均值、方差、相关等）不随时间推移而变化。一阶平稳（均值为常数），二阶平稳（均值和方差为常数，任意两时间点之间的协方差只取决于时间间隔，又称之为广义平稳） 自相关函数定义为： r(k)E(Xt)(Xt+k)/E(Xt)2,12,自相似的数
6、学描述,自相似 条件1针对一个平稳随机过程 X(Xt: t0,1,2,3) 条件2其自相关函数满足r(k) kL1(k)，当k，其中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, ,13,自相似的数学描述,自相似(Exactly second order) self-similar X(m)的自相关函数r(m)满足：r(m)(k)r(k)，对所有m1, 2, (k1
7、, 2, 3, ) 渐进自相似(Asymptotically second order) self-similar X(m)的自相关函数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),14,自相似的数学描述,自相似参数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
8、.5H1，参数H用来表示自相似的程度,15,自相似的数学描述,自相似的特性 长相关（LRDlong range dependence、large scale correlation、long term correlation ） 长相关定义若一个随机过程满足自相似的条件1和条件2，即其自相关函数随时滞的增加呈双曲线衰减（幂律衰减），则该随机过程呈现长相关性 长相关自相似，自相似是长相关的特例/简单模型 不可和性，即k r(k)。不可和性的物理意义在于高滞后的相关虽然是个别的小量，但其累计的结果则十分重要 短相关过程(short-range dependence)自相关函数呈指数衰减，即r(k)
9、k，当k(01)，其自相关函数是可和的，即0k r(k),16,自相似的数学描述,自相似的特性 慢衰减方差 自相似过程的方差满足var(X(m)am，当m，其中01，a是与m无关的正常数，与前条件2中相同 短相关过程的方差满足var(X(m)bm1，当m，其中b是与m无关的正常数 自相似过程的方差衰减要慢于短相关过程,17,自相似的数学描述,自相似的特性 Hurst效应 H表示Hurst参数，自相关程度的度量 重新调制尺度权差(R/S)对于一个给定的观察序列X1, X2, X3 .Xn，样本均值为X(n)，样本方差为S2(n)，则R(n)/S(n)1/S(n)max(0, W1, W2, ,
10、Wn)min(0, W1, W2, , Wn)，其中Wk(X1X2X3.Xk)kX(n)，k1,2,3n，R表示重新调整尺度的极差 R/S: Rescaled adjusted range analysis,18,自相似的数学描述,自相似的特性 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赫斯特英国的
11、水文专家，长期从事尼罗河水坝工程研究 Mandelbrot曼德博罗分形理论的创始人，美籍法国数学家,19,自相似的数学描述,自相似 r(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,20,自相似的数学描述,如何测度自相似 数学定义针对无限长度的时间序列 实际中仅仅一段时间的取样，保证取样点足够多,21,自相似的数学描述,如何测度自相似 针对有限的时间序列来估计Hurst参数 方法1分析堆叠过程X(m)的方差，自相似的慢衰减方差特性 var(X(m)am- (m) (v
12、ar(X(m)(m)(a) (m),0.4 H0.8,22,自相似的数学描述,如何测度自相似 方法2基于R/S统计的时域分析 ER(n)/S(n)cnH (n) (ER(n)/S(n)H(n)(c) (n) 原始的时间序列分为大小为n的块，对每个块计算其R(ti,n)/S(ti,n),H0.79,23,自相似的数学描述,如何测度自相似 基于周期图(Periodogram)的频域分析 协方差函数傅立叶变换功率谱 用周期图近似估计功率谱 从谱密度中找到参数H,24,自相似的数学描述,具备自相似的数学模型 自相似理论广泛地应用在水文和经济学领域 分形(分数)高斯噪声fractional Gaussi
13、an noise FGN 分形(分数)布朗运动fractional Brownian motion FBM，是分形高斯噪声的增量和过程 分形(分数)自回归滑动平均过程fractional ARIMA processes AutoRegressive Integrated Moving-Average，渐进自相似过程,25,自相似的数学描述,网络流量的建模 ON/OFF模型叠加大量的ON/OFF源，每个源有两个状态，即ON和OFF。在ON状态，以连续速率发送数据包，在OFF状态，不发送数据包。每个发生源ON或OFF的时长独立地符合重尾分布（Heavy-tailed distribution） 重
14、尾分布若一随机变量满足重尾分布，则PXx x-，当x, 00，xk，分布函数为F(x)PXx1(k/x)，当减小，大量的概率质量集中在分布的尾部 H(3)/2 佩瑞多.韦尔福雷多（Pareto Vilfredo）意大利经济学家和社会学家,26,自相似的数学描述,ON/OFF网络流量模型,27,对流量自相似研究的三个方面,分析流量的特征，建模 小波分析（Discrete Wavelet Transform）和分形理论 分形和多重分形(Multifractal)模型 “可信的”网络流量生成模型 产生流量自相似的原因 评估自相似流量对网络的影响,28,产生自相似的原因,是流量内在的特性还是网络协议的
15、调制作用？ Web流量的自相关性 (Boston University, 1996, 1998,实际数据) Web文件大小的分布（包括用户请求的文件、实际传输的文件、文件的传输时间、服务器端存储的文件等）呈重尾分布，客户端Cache的影响相对较小Web文件传输时间的重尾分布Web流量的自相似性,29,产生自相似的原因,若文件大小符合重尾分布，则对应的文件传输均导致链路层的自相似性，Web、NFS、FTP等 (Purdue University, Boston University, 1996, NS模拟) 上述情况似乎都可以从ON/OFF模型找到解释的理由,30,产生自相似的原因,对IP流量成
16、分的进一步分析 （Hungary, Budapest Uni. Of Tech.&Econo. 实际数据,2000） 不同协议成分如IP、ICMP、TCP、UDP、HTTP、SMTP、FTPdata、FTPcontrol、OSPF、Telnet，是否多重分形(multifractal)和分形(monofractal，即自相似),31,产生自相似的原因,对IP流量成分的进一步分析 （Hungary, Budapest Uni. Of Tech.&Econo. 实际数据,2000）,32,产生自相似的原因,重传机制(Retransmission)产生自相似特性(CMU，1997) 模拟条件输入是泊松到达（即，新数据包（不包括重传的数据包）到达是一个简单的泊松过程），数据包长度为常数，一个队列情况，先进先服务，无拥塞控制的重传机制 结论当时间尺度超过10倍的数据包传输时间，重传数据包流量的方差在总的流量（新数据包、重传数据包和丢失的数据包）中占据绝大多数成分。 即使改变重传机制的参数，如缓存大小、重传企图的次数和超时时限
