关于网络流量自相似特性的研究 马皓 北大网络实验室 2002年10月31日.

Presentation on theme: "关于网络流量自相似特性的研究 马皓 北大网络实验室 2002年10月31日."— Presentation transcript:

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 510 citations) Vern Paxson, Sally Floyd, Wide-Area Traffic: The Failure of Poisson Modeling, IEEE/ACM Transactions on Networking,3(3), June (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 Traffic", IEEE Transactions on Communications, February/March/April, (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, 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 Internet” “Goodbye Poisson” & “Hello Fractal” !

5 问题提出 什么是自相似？ 为什么研究自相似？ 产生自相似的原因？ 泊松过程—随机变量(单位时间呼叫到达的次数)是独立的、且服从相似分布，即
P[Xk＝n]＝e－λ△t(λ△t)n/n! (n≥0) 马尔可夫模型—对过去具有有限记忆，即在已经知道“现在”的条件下，其“将来”不依赖于“过去” 时间t与过去时间t-s，若s足够大，则t与t-s时的业务量是不相关的，即仅考虑s较小时业务到达间的相关性，称之为短时相关Short Range Dependence—SRD模型

6 自相似的数学描述 网络流量模型 自相似的物理描述 时间序列，表示每单位时间到达的字节数或数据包数量
网络流量在很宽的时间尺度内存在突发现象，“Burst” 时间尺度—几十毫秒、秒、分钟、小时

7

8

9

10

11 自相似的数学描述 数学定义 假设前提—平稳随机过程，即统计特性（均值、方差、相关等）不随时间推移而变化。一阶平稳（均值为常数），二阶平稳（均值和方差为常数，任意两时间点之间的协方差只取决于时间间隔，又称之为广义平稳） 自相关函数定义为： r(k)＝E[(Xt－μ)(Xt+k－μ)]/E[(Xt－μ)2]

12 自相似的数学描述 自相似 条件1—针对一个平稳随机过程 X＝(Xt: t＝0,1,2,3…)
条件2—其自相关函数满足r(k) ～ k－βL1(k)，当k→∞，其中0＜β＜1，L1是慢变函数，即对所有x＞0，limt→∞L1(tx)/L1(t)＝1（常见的慢变函数，如L1(t)＝常数，L1(t)＝㏒(t)） 条件3-对X进行堆叠，堆叠产生的时间序列为X(m)＝(Xk(m)：k＝1,2,3 …)，其中 Xk(m) ＝1/m(Xkm-m+1＋ …＋Xkm)，k＝1, 2, 3, …

13 自相似的数学描述 自相似(Exactly second order) self-similar
X(m)的自相关函数r(m)满足：r(m)(k)＝r(k)，对所有m＝1, 2, … (k＝1, 2, 3, …) 渐进自相似(Asymptotically second order) self-similar X(m)的自相关函数r(m)满足： r(m)(1)→21－β－1，当m→∞ r(m)(k)→1/2δ2(k2－β)，当m→∞ (k＝2, 3, …) δ2表示一个算子符，其作用于函数f(k)表示δ2(f(k))＝f(k＋1)－2f(k)＋f(k－1)

14 自相似的数学描述 自相似参数H H＝1－β/2 r(k)～k－(2-2H)L1(k)，当k→∞
渐进自相似(asymptotically self-similar) r(k)＝1/2[(k＋1)2H－2k2H＋(k－1)2H] 严格自相似 (exactly self-similar) 参数H满足0.5＜H＜1，参数H用来表示自相似的程度

15 自相似的数学描述 自相似的特性 长相关（LRD—long range dependence、large scale correlation、long term correlation ） 长相关定义—若一个随机过程满足自相似的条件1和条件2，即其自相关函数随时滞的增加呈双曲线衰减（幂律衰减），则该随机过程呈现长相关性 长相关≠自相似，自相似是长相关的特例/简单模型 不可和性，即∑k r(k)＝∞。不可和性的物理意义在于高滞后的相关虽然是个别的小量，但其累计的结果则十分重要 短相关过程(short-range dependence)自相关函数呈指数衰减，即r(k)～ρk，当k→∞(0＜ρ＜1)，其自相关函数是可和的，即0＜∑k r(k)＜∞

16 自相似的数学描述 自相似的特性 慢衰减方差 自相似过程的方差满足var(X(m))～am－β，当m→∞，其中0＜β＜1，a是与m无关的正常数，β与前条件2中β相同 短相关过程的方差满足var(X(m))～bm－1，当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＝(X1＋X2＋X3…..＋Xk)－kX(n)，k＝1,2,3…n，R表示重新调整尺度的极差 R/S: Rescaled adjusted range analysis

18 自相似的数学描述 自相似的特性 Hurst效应
Hurst在1991年和1995年发现大多数自然产生的时间序列满足E[R(n)/S(n)]～cnH，当n→∞，其中Hurst参数典型为0.73，c是与n无关的正常数 若观察序列取自一个短相关模型，曼德博罗等发现，满足E[R(n)/S(n)]～dn0.5，当n→∞，其中d与n无关的正常数 上述两式的差异通常称之为赫斯特效应或赫斯特现象 Hurst赫斯特—英国的水文专家，长期从事尼罗河水坝工程研究 Mandelbrot曼德博罗—分形理论的创始人，美籍法国数学家

19 自相似的数学描述 自相似 r(k) ～ k－βL1(k)，k→∞(0＜β＜1)，L1是慢变函数 ∑k r(k)＝∞
var(X(m))～am－β，m→∞(0＜β＜1) 短相关 r(k)～ρk，当k→∞(0＜ρ＜1) 0＜∑k r(k)＜∞ var(X(m))～bm－1，m→∞

20 自相似的数学描述 如何测度自相似 数学定义针对无限长度的时间序列 实际中仅仅一段时间的取样，保证取样点足够多
Measurement period Total number of bytes Total number of packets Ethernet utilization August 1989 total(27.45 hours) 11,448,753,134 27,901,984 9.30% October 1989 total(20.86 hours) 14,774,694,236 27,915,376 15.70% January 1990 total(40.16 hours) 7,112,417,589 27,954,961 3.90% February 1992 total(47.91 hours) 6,585,335,731 27,674,814 3.10%

21 自相似的数学描述 如何测度自相似 针对有限的时间序列来估计Hurst参数 方法1—分析堆叠过程X(m)的方差，自相似的慢衰减方差特性
var(X(m))～am-β (m→∞) ㏒(var(X(m)))～－β㏒(m)＋㏒(a) (m→∞) β≈0.4 H≈0.8

22 自相似的数学描述 如何测度自相似 方法2—基于R/S统计的时域分析 E[R(n)/S(n)]～cnH (n→∞)
㏒(E[R(n)/S(n)])～H㏒(n)＋㏒(c) (n→∞) 原始的时间序列分为大小为n的块，对每个块计算其R(ti,n)/S(ti,n) H≈0.79

23 自相似的数学描述 如何测度自相似 基于周期图(Periodogram)的频域分析 协方差函数傅立叶变换功率谱 用周期图近似估计功率谱
从谱密度中找到参数H

24 自相似的数学描述 具备自相似的数学模型 自相似理论广泛地应用在水文和经济学领域
分形(分数)高斯噪声—fractional Gaussian 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） 重尾分布—若一随机变量满足重尾分布，则P[X＞x] ～ x-α，当x→∞, 0<α<2。最简单的重尾分布是佩瑞多（Pareto）分布，其概率密度函数为p(x)＝αkα x-α-1，α,k>0，x≥k，分布函数为F(x)＝P[X≤x]＝1－(k/x)α，当α减小，大量的概率质量集中在分布的尾部 H＝(3－α)/2 佩瑞多.韦尔福雷多（Pareto Vilfredo）意大利经济学家和社会学家

26 自相似的数学描述 ON/OFF网络流量模型

27 对流量自相似研究的三个方面 分析流量的特征，建模 产生流量自相似的原因 评估自相似流量对网络的影响
小波分析（Discrete Wavelet Transform）和分形理论 分形和多重分形(Multifractal)模型 “可信的”网络流量生成模型 产生流量自相似的原因 评估自相似流量对网络的影响

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

29 产生自相似的原因 若文件大小符合重尾分布，则对应的文件传输均导致链路层的自相似性，Web、NFS、FTP等
(Purdue University, Boston University, 1996, NS模拟) 上述情况似乎都可以从ON/OFF模型找到解释的理由

30 产生自相似的原因 对IP流量成分的进一步分析
（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倍的数据包传输时间，重传数据包流量的方差在总的流量（新数据包、重传数据包和丢失的数据包）中占据绝大多数成分。 即使改变重传机制的参数，如缓存大小、重传企图的次数和超时时限，不能改变重传负载的自相似特性

33 产生自相似的原因 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、Congestion Avoidance、Fast Retransmit） 参数设置：link rate-C、delay-D、buffer size-B以及TCP流的数量-N

34 产生自相似的原因 TCP拥塞控制的浑沌特性(Ericsson，Traffic Analysis and Network Performance Lab. 2000) 结论：B/N的比率控制着系统的相位迁移，即从周期性到浑沌，并在特定的参数下产生自相似时间序列；单个的TCP流量符合渐进自相似，H＞0.5；在瓶颈缓存处堆叠的TCP流量是短时相关的，H≈0.5，其物理解释是TCP拥塞控制使瓶颈缓存占用率最大来平滑流量，堆叠的流量得到平滑，单个TCP流仍保持长相关性。 为什么堆叠的网络流量仍具有长相关性(H＞0.5)？TCP拥塞控制和具有重尾特性的上层协议共同作用。 TCP本身是一个产生自相似特性的确定性过程

35 产生自相似的原因 针对传输层(TCP和UDP)更进一步的研究(Purdue University, Boston University, 1996, NS模拟) TCP(Tahoe、Reno或Vegas)可靠的传输机制和流量控制机制保留了由文件大小重尾分布所引发的长相关性 无流量控制和不可靠的UDP并不使生成的流量具有长相关性

36 产生自相似的原因 网络拓扑的影响 对流量自相似的估计并不因网络拓扑结构变化而改变
(Purdue University, Boston University, 1996, NS模拟) 对流量自相似的估计并不因网络拓扑结构变化而改变

37 Heavy-Tailed File Size Self-Similarity Link Traffic H
产生自相似的原因 重尾分布的ON/OFF和浑沌的TCP导致Internet流量的分形特性(自相似) Heavy-Tailed File Size Distribution  Application Layer Application Layer Transport/Network Layer Transport/Network Layer Congest Control and Reliability Self-Similarity Link Traffic H

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

39 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响
缓存占用比传统排队论的分析结果要大，结果导致更大的延时（也即队列长度分布在自相似流量作用下的衰减比短时相关源（泊松到达过程）作用下要慢），由长相关特性决定

40 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响
缓存的线性增长导致指数规律减少的数据包丢失，以及成比例增长的传输带宽利用率。该理论对自相关流量不适用

41 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响
数据包丢失率与缓存大小和自相似之间的关系—当α趋近于1，自相似程度增大(H＝(3－α)/2)，数据包丢失率增大

42 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响 文件大小的重尾分布与吞吐量的关系 平均缓存 占用(字节) 与 数据包 平均延时
成比例

43 国内相关工作 “自相似业务量的多重分形分析”，电子学报，2000年，第28卷，第1期，P.96-98；
“CERNET网络业务的自相似性及性能分析”，天津大学学报（自然科学与工程技术版），2000年，第33卷，第3期，P ； “突发业务的多重分形建模及其参数估计”，电子学报，1999年，第4期，第27卷； “网络中业务流的自相似性与线性AR1模型”，电子学报，1999年，第4期，第27卷； “自相似业务模型下的队列分析—大偏差技术”，通信学报，1999年，第20卷，第4期；

44 国内相关工作 “自相似业务合成流的建模及排队性能分析”，通信学报，1999年，第20卷，第8期；
“自相似业务：基于多分辨率采样和小波分析的Hurst系数估计方法”，电子学报，1998年，第7期； “A New Multifractal Traffic Model Based on the Wavelet Transform”、“Measurement and Analysis of IP Network Traffic”，上海复旦大学，计算机科学与工程系； 中国科学院软件研究所，“信息网前沿技术研究：通信网络动态仿真”的项目中对科技网流量进行分析，验证广域网流量的长相关性，采用小波分析的方法分析整理采集的数据。并将广域网流量的长相关特性应用于千兆交换路由器的缓存控制。

45 可能的研究内容 Internet的非线性发展（非线性的动力学系统，具备浑沌特性） 为研究网络流量特性提供新的契机
网络协议体系的变化，从共享以太网交换以太网ATM千兆以太网/Wireless Ethernet10G Ethernet，纯IPv4IPv4与IPv6共存纯IPv6 Internet路由策略的变化，“first come, first serve”公平的资源共享 网络应用的多样化，Grid、P2P、视频会议、Internet multicast应用、Web Cache、VRML、多人游戏 用户人数和主机数的增多（流量源的增加） 为研究网络流量特性提供新的契机

46 可能的研究内容 实时探测网络流量的自相似特性优化网络性能 如何实现流量整形(Traffic shaping)?在应用层还是在传输层/网络层
网络流量自相似特性对实际的网络动态因子-Network Dynamics(如为保证QOS所作的算法、策略、TCP拥塞控制算法甚至应用层协议的设计)究竟存在多大参考价值

47 可能的研究内容 网络自相似的“度”在何处？研究表明，以太网上负载越高，自相似的程度越高。当网络负载在30％～ 70％的范围，流量的波形呈现自相似特性，H趋近于1。而当负载在80％～ 99％范围内，波形呈现很强的周期性，计算H值基本上是不可能的。

48 The End!