关于网络流量自相似特性的研究.ppt
《关于网络流量自相似特性的研究.ppt》由会员分享,可在线阅读,更多相关《关于网络流量自相似特性的研究.ppt(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
3、Traffic“, 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 Inter
5、net” “Goodbye Poisson” & “Hello Fractal” !,5,问题提出,什么是自相似? 为什么研究自相似? 产生自相似的原因? 泊松过程随机变量(单位时间呼叫到达的次数)是独立的、且服从相似分布,即 PXknet(t)n/n! (n0) 马尔可夫模型对过去具有有限记忆,即在已经知道“现在”的条件下,其“将来”不依赖于“过去” 时间t与过去时间t-s,若s足够大,则t与t-s时的业务量是不相关的,即仅考虑s较小时业务到达间的相关性,称之为短时相关Short Range DependenceSRD模型,6,自相似的数学描述,网络流量模型 时间序列,表示每单位时间到达的字
6、节数或数据包数量 自相似的物理描述 网络流量在很宽的时间尺度内存在突发现象,“Burst” 时间尺度几十毫秒、秒、分钟、小时,7,8,9,10,11,自相似的数学描述,数学定义 假设前提平稳随机过程,即统计特性(均值、方差、相关等)不随时间推移而变化。一阶平稳(均值为常数),二阶平稳(均值和方差为常数,任意两时间点之间的协方差只取决于时间间隔,又称之为广义平稳) 自相关函数定义为: r(k)E(Xt)(Xt+k)/E(Xt)2,12,自相似的数学描述,自相似 条件1针对一个平稳随机过程 X(Xt: t0,1,2,3) 条件2其自相关函数满足r(k) kL1(k),当k,其中01,L1是慢变函数
7、,即对所有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, 2, 3, ) 渐进自相似(Asymptotically second order) self-similar X(m)的自相关函数r(m)满足:
8、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.5H1,参数H用来表示自相似的程度,15,自相似的数学描述,自相似的特性 长相关(LRDlong range dependence、large sca
9、le correlation、long term correlation ) 长相关定义若一个随机过程满足自相似的条件1和条件2,即其自相关函数随时滞的增加呈双曲线衰减(幂律衰减),则该随机过程呈现长相关性 长相关自相似,自相似是长相关的特例/简单模型 不可和性,即k r(k)。不可和性的物理意义在于高滞后的相关虽然是个别的小量,但其累计的结果则十分重要 短相关过程(short-range dependence)自相关函数呈指数衰减,即r(k)k,当k(01),其自相关函数是可和的,即0k r(k),16,自相似的数学描述,自相似的特性 慢衰减方差 自相似过程的方差满足var(X(m)am,当
10、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, , Wn)min(0, W1, W2, , Wn),其中Wk(X1X2X3Xk)kX(n),k1,2,3n,R表示重新调整尺度的极差 R/S: Rescale
11、d 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赫斯特英国的水文专家,长期从事尼罗河水坝工程研究 Mandelbrot曼德博罗分形理论的创始人,美籍法国数学家,19,自相似的数学描述,自相似 r(k) kL1(k),
12、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) (var(X(m)(m)(a) (m),0.4 H0.8,22,自相似的数学描述,如何测度自相似 方法2基于R/S统计的时域分析 ER(n)/S(n)cnH (
13、n) (ER(n)/S(n)H(n)(c) (n) 原始的时间序列分为大小为n的块,对每个块计算其R(ti,n)/S(ti,n),H0.79,23,自相似的数学描述,如何测度自相似 基于周期图(Periodogram)的频域分析 协方差函数傅立叶变换功率谱 用周期图近似估计功率谱 从谱密度中找到参数H,24,自相似的数学描述,具备自相似的数学模型 自相似理论广泛地应用在水文和经济学领域 分形(分数)高斯噪声fractional Gaussian noise FGN 分形(分数)布朗运动fractional Brownian motion FBM,是分形高斯噪声的增量和过程 分形(分数)自回归滑
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于 网络流量 相似 特性 研究
链接地址:https://www.31doc.com/p-2440121.html