关于网络流量自相似特性研究

1、关于网络流量自相似特性研究关于网络流量自相似特性研究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 N

2、etworking, February 1994.(Bellcore 510 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 Depe

3、ndence in Variable-Bit-Rate Video Traffic, IEEE Transactions on Communications, February/March/April, 1995. (193 citations) 关于网络流量自相似特性研究4问题提出意义意义开拓了全新的研究领域，经典的理论分析依据（如泊开拓了全新的研究领域，经典的理论分析依据（如泊松过程和马尔可夫模型），不在适合网络流量的分析松过程和马尔可夫模型），不在适合网络流量的分析和建模。和建模。“.the (r)evolution of the Internet is impacting the wo

4、rld of mathematics in the small as well as in the large - both on how mathematics is done, and, 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 ma

5、thematical sciences.” by Walter Willinger and Vern Paxson in “Where Mathematics meets the Internet”“Goodbye Poisson” & “Hello Fractal” !关于网络流量自相似特性研究5问题提出什么是自相似？什么是自相似？为什么研究自相似？为什么研究自相似？产生自相似的原因？产生自相似的原因？ 泊松过程泊松过程随机变量随机变量( (单位时间呼叫到达的次数单位时间呼叫到达的次数) )是独是独立的、且服从相似分布，即立的、且服从相似分布，即PXknet(t)n/n! (n0) 马尔可夫

6、模型马尔可夫模型对过去具有有限记忆，即在已经知道对过去具有有限记忆，即在已经知道“现在现在”的条件下，其的条件下，其“将来将来”不依赖于不依赖于“过去过去” 时间时间t与过去时间与过去时间t-s，若，若s足够大，则足够大，则t与与t-s时的业务量时的业务量是不相关的，即仅考虑是不相关的，即仅考虑s较小时业务到达间的相关性，较小时业务到达间的相关性，称之为短时相关称之为短时相关Short Range DependenceSRD模型模型 关于网络流量自相似特性研究6自相似的数学描述网络流量模型网络流量模型时间序列，表示每单位时间到达的字节数或数时间序列，表示每单位时间到达的字节数或数据包数量据包数

7、量自相似的物理描述自相似的物理描述网络流量在很宽的时间尺度内存在突发现象，网络流量在很宽的时间尺度内存在突发现象，“Burst”时间尺度时间尺度几十毫秒、秒、分钟、小时几十毫秒、秒、分钟、小时关于网络流量自相似特性研究7关于网络流量自相似特性研究8关于网络流量自相似特性研究9关于网络流量自相似特性研究10关于网络流量自相似特性研究11自相似的数学描述数学定义数学定义假设前提假设前提平稳随机过程，即统计特性（均值、平稳随机过程，即统计特性（均值、方差、相关等）不随时间推移而变化。一阶平稳方差、相关等）不随时间推移而变化。一阶平稳（均值为常数），二阶平稳（均值和方差为常数，（均值为常数），二阶平稳

8、（均值和方差为常数，任意两时间点之间的协方差只取决于时间间隔，任意两时间点之间的协方差只取决于时间间隔，又称之为广义平稳）又称之为广义平稳）自相关函数定义为：自相关函数定义为：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是慢变函数，即对所有是慢变函数，即对所有x0，limtL1(tx)/L1(t)1（常见的慢变函数，如（常见的慢变函数，如L1(t)常数，常数，

9、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-similarX(m)的自相关函数的自相关函数r(m)满足：满足：r(m)(k)r(k)，对所有，对所有m1, 2, (k1, 2, 3, )渐进自相似渐进自相似(Asymptotically second order) self-similarX(m)的自相关函数的自

10、相关函数r(m)满足：满足：r(m)(1)211，当当mr(m)(k)1/22(k2)，当，当m (k2, 3, )2表示一个算子符，其作用于函数表示一个算子符，其作用于函数f(k)表示表示2(f(k)f(k1)2f(k)f(k1) 关于网络流量自相似特性研究14自相似的数学描述自相似参数自相似参数HH1/2 r(k)k(2-2H)L1(k)，当当k渐进自相似渐进自相似( (asymptotically self-similar)r(k)1/2(k1)2H2k2H(k1)2H严格自相似严格自相似 (exactly self-similar)参数参数H满足满足H1，参数参数H用来表示自相似的程度

11、用来表示自相似的程度关于网络流量自相似特性研究15自相似的数学描述自相似的特性自相似的特性长相关（长相关（LRDlong range dependence、large scale correlation、long term correlation ）长相关定义长相关定义若一个随机过程满足自相似的条件若一个随机过程满足自相似的条件1 1和条和条件件2 2，即其自相关函数随时滞的增加呈双曲线衰减（幂，即其自相关函数随时滞的增加呈双曲线衰减（幂律衰减），则该随机过程呈现长相关性律衰减），则该随机过程呈现长相关性长相关长相关自相似，自相似是长相关的特例自相似，自相似是长相关的特例/ /简单模型简单模型

12、不可和性，即不可和性，即k r(k)。不可和性的物理意义在于高不可和性的物理意义在于高滞后的相关虽然是个别的小量，但其累计的结果则十滞后的相关虽然是个别的小量，但其累计的结果则十分重要分重要短相关过程短相关过程( (short-range dependence)自相关函数呈指自相关函数呈指数衰减，即数衰减，即r(k)k，当当k(01)，其自相关函其自相关函数是可和的，即数是可和的，即0k r(k) 关于网络流量自相似特性研究16自相似的数学描述自相似的特性自相似的特性慢衰减方差慢衰减方差自相似过程的方差满足自相似过程的方差满足var(X(m)am，当当m，其中其中01，a是与是与m无关的正常数

13、，无关的正常数，与前条件与前条件2 2中中相同相同短相关过程的方差满足短相关过程的方差满足var(X(m)bm1，当当m，其中其中b是与是与m无关的正常数无关的正常数 自相似过程的方差衰减要慢于短相关过程自相似过程的方差衰减要慢于短相关过程关于网络流量自相似特性研究17自相似的数学描述自相似的特性自相似的特性Hurst效应效应 H表示表示Hurst参数，自相关程度的度量参数，自相关程度的度量重新调制尺度权差重新调制尺度权差(R/S)对于一个给定的观对于一个给定的观察序列察序列X1, X2, X3 .Xn，样本均值为，样本均值为X(n)，样 本 方 差 为样 本 方 差 为 S2( n ) ，

14、则， 则 R ( n ) / S ( n ) 1/S(n)max(0, W1, W2, , 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参数典参数典型为型为，c是与是

15、与n无关的正常数无关的正常数 若观察序列取自一个短相关模型，曼德博罗等发现，若观察序列取自一个短相关模型，曼德博罗等发现，满足满足ER(n)/S(n)dn，当当n，其中其中d与与n无关的正常无关的正常数数上述两式的差异通常称之为赫斯特效应或赫斯特现象上述两式的差异通常称之为赫斯特效应或赫斯特现象 Hurst赫斯特赫斯特英国的水文专家，长期从事尼罗河水坝工程研究英国的水文专家，长期从事尼罗河水坝工程研究Mandelbrot曼德博罗曼德博罗分形理论的创始人，美籍法国数学家分形理论的创始人，美籍法国数学家关于网络流量自相似特性研究19自相似的数学描述自相似自相似r(k) kL1(k)，k(01)，L

16、1是慢变函数是慢变函数k r(k)var(X(m)am，m(01)短相关短相关r(k)k，当当k(01)0k r(k)var(X(m)bm1，m关于网络流量自相似特性研究20自相似的数学描述Measurement periodTotal number of bytesTotal number of packetsEthernet utilizationAugust 1989 total(27.45 hours)11,448,753,13427,901,9849.30%October 1989 total(20.86 hours)14,774,694,23627,915,37615.70%Jan

17、uary 1990 total(40.16 hours)7,112,417,58927,954,9613.90%如何测度自相似如何测度自相似n数学定义针对无限长度的时间序列数学定义针对无限长度的时间序列n实际中仅仅一段时间的取样，保证取样点足够多实际中仅仅一段时间的取样，保证取样点足够多 关于网络流量自相似特性研究21自相似的数学描述如何测度自相似如何测度自相似针对有限的时间序列来估计针对有限的时间序列来估计Hurst参数参数方法方法1 1分析堆叠过程分析堆叠过程X(m)的的方差，自相似的慢衰减方方差，自相似的慢衰减方差特性差特性var(X(m)am- (m)(var(X(m)(m)(a) (

18、m) )关于网络流量自相似特性研究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)关于网络流量自相似特性研究23自相似的数学描述如何测度自相似如何测度自相似基于周期图基于周期图(Periodogram)的频域分析的频域分析协方差函数协方差函数傅立叶变换傅立叶变换功率谱功率谱用周期图近似估计功率谱用周期图近似估计功率谱从谱密度中找到参数从谱密

19、度中找到参数H关于网络流量自相似特性研究24自相似的数学描述具备自相似的数学模型具备自相似的数学模型自相似理论广泛地应用在水文和经济学领域自相似理论广泛地应用在水文和经济学领域分形分形( (分数分数) )高斯噪声高斯噪声fractional Gaussian noise FGN分形分形( (分数分数) )布朗运动布朗运动fractional Brownian motion FBM，是分形高斯噪声的增量和过程，是分形高斯噪声的增量和过程分形分形( (分数分数) )自回归滑动平均过程自回归滑动平均过程fractional ARIMA processes AutoRegressive Integra

20、ted Moving-Average，渐进自相似过程，渐进自相似过程 关于网络流量自相似特性研究25自相似的数学描述网络流量的建模网络流量的建模ON/OFF模型模型叠加大量的叠加大量的ON/OFF源，每个源有两个源，每个源有两个状态，即状态，即ON和和OFF。在。在ON状态，以连续速率发送数据状态，以连续速率发送数据包，在包，在OFF状态，不发送数据包。每个发生源状态，不发送数据包。每个发生源ON或或OFF的时长独立地符合重尾分布的时长独立地符合重尾分布（Heavy-tailed distribution）重尾分布重尾分布若一随机变量满足重尾分布，则若一随机变量满足重尾分布，则PXx x-，当

21、，当x, , 00，xk，分布函数为，分布函数为F(x)PXx1(k/x)，当当减小，大量的概率质量集中在分布的尾部减小，大量的概率质量集中在分布的尾部H(3)/2佩瑞多佩瑞多. .韦尔福雷多韦尔福雷多（Pareto Vilfredo）意大利经济学家和社会学家意大利经济学家和社会学家 关于网络流量自相似特性研究26自相似的数学描述ON/OFF网络流量模型网络流量模型关于网络流量自相似特性研究27对流量自相似研究的三个方面分析流量的特征，建模分析流量的特征，建模小波分析小波分析（Discrete Wavelet Transform）和分形和分形理论理论分形和多重分形分形和多重分形(Multifr

22、actal)模型模型“可信的可信的”网络流量生成模型网络流量生成模型产生流量自相似的原因产生流量自相似的原因评估自相似流量对网络的影响评估自相似流量对网络的影响 关于网络流量自相似特性研究28产生自相似的原因 是流量内在的特性还是网络协议的调制作用？是流量内在的特性还是网络协议的调制作用？Web流量的自相关性流量的自相关性( (Boston University, 1996, 1998,实际数据实际数据)Web文件大小的分布（包括用户请求的文件、实文件大小的分布（包括用户请求的文件、实际传输的文件、文件的传输时间、服务器端存储际传输的文件、文件的传输时间、服务器端存储的文件等）呈重尾分布，客户

23、端的文件等）呈重尾分布，客户端Cache的影响相的影响相对较小对较小Web文件传输时间的重尾分布文件传输时间的重尾分布Web流流量的自相似性量的自相似性关于网络流量自相似特性研究29产生自相似的原因 若文件大小符合重若文件大小符合重尾分布，则对应的尾分布，则对应的文件传输均导致链文件传输均导致链路层的自相似性，路层的自相似性，Web、NFS、FTP等等( (Purdue University, Boston University, 1996, NS模拟模拟)上述情况似乎都可上述情况似乎都可以从以从ON/OFF模型找模型找到解释的理由到解释的理由关于网络流量自相似特性研究30产生自相似的原因 对

24、对IP流量成分的进一步流量成分的进一步分析分析（Hungary, Budapest Uni. Of Tech.&Econo. 实际数据实际数据, ,2000）不 同 协 议 成 分 如不 同 协 议 成 分 如 I P 、ICMP、TCP、UDP、HTTP、SMTP、OSPF、Telnet，是否多，是否多重分形重分形( (multifractal)和和分形分形( (monofractal，即自即自相似相似) )关于网络流量自相似特性研究31产生自相似的原因 对对IP流量成分的进一步分析流量成分的进一步分析（Hungary, Budapest Uni. Of Tech.&Econo. 实际数实际

25、数据据, ,2000）关于网络流量自相似特性研究32产生自相似的原因 重传机制重传机制( (Retransmission)产生自相似特性产生自相似特性( (CMU，1997) ) 模拟条件模拟条件输入是泊松到达（即，新数据包（不包括输入是泊松到达（即，新数据包（不包括重传的数据包）到达是一个简单的泊松过程），数据重传的数据包）到达是一个简单的泊松过程），数据包长度为常数，一个队列情况，先进先服务，无拥塞包长度为常数，一个队列情况，先进先服务，无拥塞控制的重传机制控制的重传机制结论结论当时间尺度超过当时间尺度超过1010倍的数据包传输时间，重传倍的数据包传输时间，重传数据包流量的方差在总的流量（

26、新数据包、重传数据数据包流量的方差在总的流量（新数据包、重传数据包和丢失的数据包）中占据绝大多数成分。包和丢失的数据包）中占据绝大多数成分。即使改变重传机制的参数，如缓存大小、重传企图的即使改变重传机制的参数，如缓存大小、重传企图的次数和超时时限，不能改变重传负载的自相似特性次数和超时时限，不能改变重传负载的自相似特性关于网络流量自相似特性研究33产生自相似的原因 TCP拥塞控制的浑沌特性拥塞控制的浑沌特性( (Ericsson，Traffic Analysis and Network Performance Lab. 2000)浑沌系统的特征：非线性浑沌系统的特征：非线性(Nonlinear

27、ity)、确定性、确定性(Determinism)、混乱中的有序、混乱中的有序(Order in disorder)、对初始状态的敏感性对初始状态的敏感性( (蝴蝶效应蝴蝶效应) )(Sensitivity to initial conditions or the “butterfly effect”)、不可预见性、不可预见性(Unpredictability)模型模型(NS模拟模拟)：TCP Tahoe（Slow-Start、Congestion Avoidance、Fast Retransmit）参数设置参数设置：link rate-C、delay-D、buffer size-B以及以及T

28、CP流的数量流的数量- -N 关于网络流量自相似特性研究34产生自相似的原因 TCP拥塞控制的浑沌特性拥塞控制的浑沌特性( (Ericsson，Traffic Analysis and Network Performance Lab. 2000)结论：结论：B/N的比率控制着系统的相位迁移，即从周期的比率控制着系统的相位迁移，即从周期性到浑沌，并在特定的参数下产生自相似时间序列；性到浑沌，并在特定的参数下产生自相似时间序列；单个的单个的TCP流量符合渐进自相似，流量符合渐进自相似，H；在瓶颈缓存；在瓶颈缓存处堆叠的处堆叠的TCP流量是短时相关的，其物理解释是流量是短时相关的，其物理解释是TCP

29、拥塞控制使瓶颈缓存占用率最大来平滑流量，堆拥塞控制使瓶颈缓存占用率最大来平滑流量，堆叠的流量得到平滑，单个叠的流量得到平滑，单个TCP流仍保持长相关性。流仍保持长相关性。为什么堆叠的网络流量仍具有长相关性为什么堆叠的网络流量仍具有长相关性( (H0.5)？TCP拥塞控制和具有重尾特性的上层协议共同作用。拥塞控制和具有重尾特性的上层协议共同作用。TCP本身是一个产生自相似特性的确定性过程本身是一个产生自相似特性的确定性过程 关于网络流量自相似特性研究35产生自相似的原因 针对传输层针对传输层(TCP和和UDP)更进一步的研究更进一步的研究(Purdue University, Boston Un

30、iversity, 1996, NS模拟模拟)TCP(Tahoe、Reno或或Vegas)可靠的传输机制和流可靠的传输机制和流量控制机制保留了由文件大小重尾分布所引发的量控制机制保留了由文件大小重尾分布所引发的长相关性长相关性无流量控制和不可靠的无流量控制和不可靠的UDP并不使生成的流量具并不使生成的流量具有长相关性有长相关性 关于网络流量自相似特性研究36产生自相似的原因 网络拓扑的影响网络拓扑的影响(Purdue University, Boston University, 1996, NS模拟模拟)对流量自相似的估计并不因网络拓扑结构变化而改变对流量自相似的估计并不因网络拓扑结构变化而改

31、变 关于网络流量自相似特性研究37产生自相似的原因 重尾分布的重尾分布的ON/OFF和浑沌的和浑沌的TCP导致导致Internet流量的分形特性流量的分形特性( (自相似自相似) )Application LayerTransport/NetworkLayerApplication LayerTransport/NetworkLayerHeavy-Tailed Distribution Congest Controland ReliabilitySelf-Similarity Link Traffic H关于网络流量自相似特性研究38自相似流量对网络性能的影响网络性能的度量网络性能的度量吞吐量

32、吞吐量( (throughout)、延时延时( (delay)、数据包丢失数据包丢失( (packet loss)从排队论的视角，网络是队列的集合，每个队列从排队论的视角，网络是队列的集合，每个队列有一个缓存有一个缓存( (buffer) )临时保存到达的数据包。数临时保存到达的数据包。数据包到达缓存等候转发，则会产生延时。若达到据包到达缓存等候转发，则会产生延时。若达到数据包的数量超过缓存大小，则产生丢弃数据包数据包的数量超过缓存大小，则产生丢弃数据包的现象，同时需要对丢弃的数据包进行重发，导的现象，同时需要对丢弃的数据包进行重发，导致吞吐量降低。实际上，网络的缓存通常保持很致吞吐量降低。实

33、际上，网络的缓存通常保持很大以避免数据包丢失，维护高的吞吐量大以避免数据包丢失，维护高的吞吐量关于网络流量自相似特性研究39自相似流量对网络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响缓存占用比传统排队论的分析结果要大，结果导缓存占用比传统排队论的分析结果要大，结果导致更大的延时（也即队列长度分布在自相似流量致更大的延时（也即队列长度分布在自相似流量作用下的衰减比短时相关源（泊松到达过程）作作用下的衰减比短时相关源（泊松到达过程）作用下要慢），由长相关特性决定用下要慢），由长相关特性决定 关于网络流量自相似特性研究40自相似流量对网络性能的影响自相似流量对网络性能

34、产生负面影响自相似流量对网络性能产生负面影响缓存的线性增长导致指数规律减少的数据包丢失，缓存的线性增长导致指数规律减少的数据包丢失，以及成比例增长的传输带宽利用率。该理论对自以及成比例增长的传输带宽利用率。该理论对自相关流量不适用相关流量不适用关于网络流量自相似特性研究41自相似流量对网络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响数据包丢失率与缓存大小和自相似之间的关系数据包丢失率与缓存大小和自相似之间的关系当当趋近于趋近于1 1，自相似程度增大，自相似程度增大( (H(3)/2)，数据包丢，数据包丢失率增大失率增大 关于网络流量自相似特性研究42自相似流量对网

35、络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响文件大小的重尾分布与吞吐量的关系文件大小的重尾分布与吞吐量的关系平均缓存平均缓存占用占用( (字节字节) )与与数据包数据包平均延时平均延时成比例成比例关于网络流量自相似特性研究43国内相关工作“自相似业务量的多重分形分析自相似业务量的多重分形分析”，电子学报，电子学报，20002000年，第年，第2828卷，第卷，第1 1期，；期，；“CERNET网络业务的自相似性及性能分析网络业务的自相似性及性能分析”，天津大学学报（自然科学与工程技术版），天津大学学报（自然科学与工程技术版），20002000年，第年，第3333卷，第卷，第3 3期，；期，； “突发业务的多重分形建模及其参数估计突发业务的多重分形建模及其参数估计”，电子学报，电子学报，19991999年，第年，第4 4期，第期，第2727卷；卷； “网络中业务流的自相似性与线性网络中业务流的自相似性与线性AR1模型模型”，电子学报，电子学报，19991999年，第年，第4 4期，第期，第2727卷；卷；“自相似业务模型下的队列分析自相似业务模型下的队列分析大偏差技大偏差技术术”，通信学报，通信学报，19991999年，第年，第2020卷，第卷，第4 4期；期；