《关于网络流量自相似特性的研究讲解材料》由会员分享,可在线阅读,更多相关《关于网络流量自相似特性的研究讲解材料(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倍的数据包传输时间,重传数据包流量的方差在总的流量(新数据包、重传数据包和丢失的数据包)中占据绝大多数成分。 即使改变重传机制的参数,如缓存大小、重传企图的次数和超时时限