《网络流量自相似特性》由会员分享，可在线阅读，更多相关《网络流量自相似特性（39页珍藏版）》请在金锄头文库上搜索。
1、 网络流量自相似特性网络流量自相似特性1提纲问题提出问题提出自相似的数学描述自相似的数学描述产生自相似的原因产生自相似的原因自相似对网络性能的影响自相似对网络性能的影响国内相关工作国内相关工作可能的研究方向可能的研究方向 2问题提出什么是自相似？什么是自相似？为什么研究自相似？为什么研究自相似？产生自相似的原因？产生自相似的原因？泊泊松松过过程程随随机机变变量量( (单单位位时时间间呼呼叫叫到到达达的的次次数数) )是是独独立的、且服从相似分布，即立的、且服从相似分布，即PXknet(t)n/n! (n0)马马尔尔可可夫夫模模型型对对过过去去具具有有有有限限记记忆忆，即即在在已已经经知知道道“
2、现在现在”的条件下，其的条件下，其“将来将来”不依赖于不依赖于“过去过去”时时间间t与与过过去去时时间间t-s，若若s足足够够大大，则则t与与t-s时时的的业业务务量量是是不不相相关关的的，即即仅仅考考虑虑s较较小小时时业业务务到到达达间间的的相相关关性性，称之为短时相关称之为短时相关Short Range DependenceSRD模型模型 3自相似的数学描述网络流量模型网络流量模型n时时间间序序列列，表表示示每每单单位位时时间间到到达达的的字字节节数数或或数据包数量数据包数量自相似的物理描述自相似的物理描述n网网络络流流量量在在很很宽宽的的时时间间尺尺度度内内存存在在突突发发现现象象，“B
3、urst”n时间尺度时间尺度几十毫秒、秒、分钟、小时几十毫秒、秒、分钟、小时4自相似的数学描述数学定义数学定义n假假设设前前提提平平稳稳随随机机过过程程，即即统统计计特特性性（均均值值、方方差差、相相关关等等）不不随随时时间间推推移移而而变变化化。一一阶阶平平稳稳（均均值值为为常常数数），二二阶阶平平稳稳（均均值值和和方方差差为为常常数数，任任意意两两时时间间点点之之间间的的协协方方差差只取决于时间间隔，又称之为广义平稳）只取决于时间间隔，又称之为广义平稳）n自相关函数定义为：自相关函数定义为：r(k)E(Xt)(Xt+k)/E(Xt)2 5自相似的数学描述自相似自相似n条件条件1针对一个平稳
4、随机过程针对一个平稳随机过程X(Xt: t0,1,2,3) n条条件件2其其自自相相关关函函数数满满足足r(k) kL1(k)，当当k，其其中中01，L1是是慢慢变变函函数数，即即对对所所有有x0，limtL1(tx)/L1(t)1（常常见见的的慢慢变变函函数，如数，如L1(t)常数，常数，L1(t)(t)）n条条件件3- -对对X进进行行堆堆叠叠，堆堆叠叠产产生生的的时时间间序序列列为为X(m)(Xk(m)：k1,2,3 )，其中其中Xk(m) 1/m(Xkm-m+1 Xkm)，k1, 2, 3, 6自相似的数学描述自相似自相似(Exactly second order) self-simi
5、larnX(m)的的自自相相关关函函数数r(m)满满足足：r(m)(k)r(k)，对对所所有有m1, 2, (k1, 2, 3, )渐渐进进自自相相似似(Asymptotically second order) self-similarnX(m)的自相关函数的自相关函数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) 7自相似的数学描述自相似参数自相似参数HnH1/2 nr(k)k(2-2H)L1(k)，当当k渐进自相似渐
6、进自相似( (asymptotically self-similar)nr(k)1/2(k1)2H2k2H(k1)2H严格自相似严格自相似 (exactly self-similar)n参参数数H满满足足0.5H1，参参数数H用用来来表表示示自自相相似似的程度的程度8自相似的数学描述自相似的特性自相似的特性n长长相相关关（LRDlong range dependence、large scale correlation、long term correlation ）w长长相相关关定定义义若若一一个个随随机机过过程程满满足足自自相相似似的的条条件件1 1和和条条件件2 2，即即其其自自相相关关函函
7、数数随随时时滞滞的的增增加加呈呈双双曲曲线线衰衰减减（幂律衰减（幂律衰减），），则该随机过程呈现长相关性则该随机过程呈现长相关性w长相关长相关自相似，自相似是长相关的特例自相似，自相似是长相关的特例/ /简单模型简单模型w不不可可和和性性，即即k r(k)。不不可可和和性性的的物物理理意意义义在在于于高高滞滞后后的的相相关关虽虽然然是是个个别别的的小小量量，但但其其累累计计的的结结果果则十分重要则十分重要w短短相相关关过过程程( (short-range dependence)自自相相关关函函数数呈呈指指数数衰衰减减，即即r(k)k，当当k(01)，其其自自相相关关函数是可和的，即函数是可和的
8、，即0k r(k) 9自相似的数学描述自相似的特性自相似的特性n慢衰减方差慢衰减方差w自自相相似似过过程程的的方方差差满满足足var(X(m)am，当当m，其其中中01，a是是与与m无无关关的的正正常常数数，与前条件与前条件2 2中中相同相同w短短相相关关过过程程的的方方差差满满足足var(X(m)bm1，当当m，其中其中b是与是与m无关的正常数无关的正常数 w自相似过程的方差衰减要慢于短相关过程自相似过程的方差衰减要慢于短相关过程10自相似的数学描述自相似的特性自相似的特性nHurst效应效应 wH表示表示Hurst参数，自相关程度的度量参数，自相关程度的度量w重重新新调调制制尺尺度度权权差
9、差(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(X1X2X3.Xk)kX(n)，k1,2,3n，R表表示示重重新新调调整整尺度的极差尺度的极差R/S: Rescaled adjusted range analysis11自相似的数学描述自相似的特性自相似的特性nHurst效应效应wHurst在在1991年年和和1995年年发发现现大大多多数数自自然然产产
10、生生的的时时间间序序列列满满足足ER(n)/S(n)cnH，当当n，其其中中Hurst参参数典型为数典型为0.73，c是与是与n无关的正常数无关的正常数 w若若观观察察序序列列取取自自一一个个短短相相关关模模型型，曼曼德德博博罗罗等等发发现现，满满足足ER(n)/S(n)dn0.5，当当n，其其中中d与与n无无关关的的正常数正常数w上上述述两两式式的的差差异异通通常常称称之之为为赫赫斯斯特特效效应应或或赫赫斯斯特特现现象象 Hurst赫斯特赫斯特英国的水文专家，长期从事尼罗河水坝工程研究英国的水文专家，长期从事尼罗河水坝工程研究Mandelbrot曼德博罗曼德博罗分形理论的创始人，美籍法国数学
11、家分形理论的创始人，美籍法国数学家12自相似的数学描述自相似自相似nr(k) kL1(k)，k(01)，L1是是慢变函数慢变函数nk r(k)nvar(X(m)am，m(01)短相关短相关nr(k)k，当当k(01)n0k r(k)nvar(X(m)bm1，m13自相似的数学描述Measurement periodTotal number of bytesTotal number of packetsEthernet utilizationAugust 1989 total(27.45 hours)11,448,753,13427,901,9849.30%October 1989 total(
12、20.86 hours)14,774,694,23627,915,37615.70%January 1990 total(40.16 hours)7,112,417,58927,954,9613.90%February 1992 total(47.91 hours)6,585,335,73127,674,8143.10%如何测度自相似如何测度自相似n数学定义针对无限长度的时间序列数学定义针对无限长度的时间序列n实际中仅仅一段时间的取样，保证取样点足够多实际中仅仅一段时间的取样，保证取样点足够多 14自相似的数学描述如何测度自相似如何测度自相似针针对对有有限限的的时时间间序序列列来来估估计计Hu
13、rst参数参数方方法法11分分析析堆堆叠叠过过程程X(m)的的方方差差，自自相相似似的的慢慢衰衰减减方方差特性差特性var(X(m)am- (m)(var(X(m)(m)(a) (m) )0.4 H0.815自相似的数学描述如何测度自相似如何测度自相似方方法法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.7916自相似的数学描述如何测度自相似如何测度自相似n基于周期图基于周期图(Perio
14、dogram)的频域分析的频域分析w协方差函数协方差函数傅立叶变换傅立叶变换功率谱功率谱w用周期图近似估计功率谱用周期图近似估计功率谱w从谱密度中找到参数从谱密度中找到参数H17自相似的数学描述具备自相似的数学模型具备自相似的数学模型n自相似理论广泛地应用在水文和经济学领域自相似理论广泛地应用在水文和经济学领域n分分 形形 ( (分分 数数 ) )高高 斯斯 噪噪 声声 fractional Gaussian noise FGNn分分形形( (分分数数) )布布朗朗运运动动fractional Brownian motion FBM，是分形高斯噪声的增量和过程是分形高斯噪声的增量和过程n分分形
15、形( (分分数数) )自自回回归归滑滑动动平平均均过过程程fractional ARIMA processes AutoRegressive Integrated Moving-Average，渐进自相似过程渐进自相似过程 18自相似的数学描述网络流量的建模网络流量的建模nON/OFF模模型型叠叠加加大大量量的的ON/OFF源源，每每个个源源有有两两个个状状态态，即即ON和和OFF。在在ON状状态态，以以连连续续速速率率发发送送数数据据包包，在在OFF状状态态，不不发发送送数数据据包包。每每个个发发生生源源ON或或OFF的的 时时 长长 独独 立立 地地 符符 合合 重重 尾尾 分分 布布 （
16、 Heavy-tailed distribution）n重重尾尾分分布布若若一一随随机机变变量量满满足足重重尾尾分分布布，则则PXx x-，当当x, , 00，xk，分分布布函函数数为为F(x)PXx1(k/x)，当当减小，大量的概率质量集中在分布的尾部减小，大量的概率质量集中在分布的尾部nH(3)/2佩瑞多佩瑞多. .韦尔福雷多韦尔福雷多（Pareto Vilfredo）意大利经济学家和社会学家意大利经济学家和社会学家 19对流量自相似研究的三个方面分析流量的特征，建模分析流量的特征，建模n小小波波分分析析（Discrete Wavelet Transform）和和分形理论分形理论n分形和多
17、重分形分形和多重分形(Multifractal)模型模型n“可信的可信的”网络流量生成模型网络流量生成模型产生流量自相似的原因产生流量自相似的原因评估自相似流量对网络的影响评估自相似流量对网络的影响 20产生自相似的原因 是是流流量量内内在在的的特特性性还还是是网网络络协协议议的的调调制制作作用？用？Web流量的自相关性流量的自相关性( (Boston University, 1996, 1998,实际数据实际数据)nWeb文文件件大大小小的的分分布布（包包括括用用户户请请求求的的文文件件、实实际际传传输输的的文文件件、文文件件的的传传输输时时间间、服服务务器器端端存存储储的的文文件件等等）呈
18、呈重重尾尾分分布布，客客户户端端Cache的的影影响响相相对对较较小小Web文文件件传传输输时时间间的的重重尾尾分分布布Web流量的自相似性流量的自相似性21产生自相似的原因 若若文文件件大大小小符符合合重重尾尾分分布布，则则对对应应的的文文件件传传输输均均导导致致链链路路层层的的自自相相似似性性，Web、NFS、FTP等等( (Purdue University, Boston University, 1996, NS模模拟拟)上上述述情情况况似似乎乎都都可可以以从从ON/OFF模模型型找找到解释的理由到解释的理由22产生自相似的原因 对对IP流流量量成成分分的的进进一一步步分析分析（Hun
19、gary, Budapest Uni. Of Tech.&Econo. 实实 际际 数数 据据, ,2000）n不不 同同 协协 议议 成成 分分 如如 IP、ICMP、 TCP、 UDP、HTTP、SMTP、FTPdata、 FTPcontrol、OSPF、Telnet，是是否否多多重重 分分 形形 ( (multifractal)和和 分分 形形 ( (monofractal，即自相似即自相似) )23产生自相似的原因 重重传传机机制制( (Retransmission)产产生生自自相相似似特特性性( (CMU，1997) ) n模模拟拟条条件件输输入入是是泊泊松松到到达达（即即，新新数数
20、据据包包（不不包包括括重重传传的的数数据据包包）到到达达是是一一个个简简单单的的泊泊松松过过程程），数数据据包包长长度度为为常常数数，一一个个队队列列情情况况，先先进进先先服服务务，无无拥拥塞塞控制的重传机制控制的重传机制n结结论论当当时时间间尺尺度度超超过过1010倍倍的的数数据据包包传传输输时时间间，重重传传数数据据包包流流量量的的方方差差在在总总的的流流量量（新新数数据据包包、重重传传数数据据包和丢失的数据包）中占据绝大多数成分。包和丢失的数据包）中占据绝大多数成分。n即即使使改改变变重重传传机机制制的的参参数数，如如缓缓存存大大小小、重重传传企企图图的的次数和超时时限，不能改变重传负载
21、的自相似特性次数和超时时限，不能改变重传负载的自相似特性24产生自相似的原因 TCP拥拥塞塞控控制制的的浑浑沌沌特特性性( (Ericsson，Traffic Analysis and Network Performance Lab. 2000)n浑浑沌沌系系统统的的特特征征：非非线线性性(Nonlinearity)、确确定定性性(Determinism)、混混乱乱中中的的有有序序(Order in disorder)、对对初初始始状状态态的的敏敏感感性性( (蝴蝴蝶蝶效效应应) )(Sensitivity to initial conditions or the “butterfly eff
22、ect”)、不不可可预预见见性性(Unpredictability)n模模型型(NS模模拟拟)：TCP Tahoe（Slow-Start、Congestion Avoidance、Fast Retransmit）n参参数数设设置置：link rate-C、delay-D、buffer size-B以以及及TCP流的数量流的数量- -N 25产生自相似的原因 TCP拥拥塞塞控控制制的的浑浑沌沌特特性性( (Ericsson，Traffic Analysis and Network Performance Lab. 2000)n结结论论：B/N的的比比率率控控制制着着系系统统的的相相位位迁迁移移，
23、即即从从周周期期性性到到浑浑沌沌，并并在在特特定定的的参参数数下下产产生生自自相相似似时时间间序序列列；单单个个的的TCP流流量量符符合合渐渐进进自自相相似似，H0.5；在在瓶瓶颈颈缓缓存存处处堆堆叠叠的的TCP流流量量是是短短时时相相关关的的，H0.5，其其物物理理解解释释是是TCP拥拥塞塞控控制制使使瓶瓶颈颈缓缓存存占占用用率率最最大大来来平平滑滑流流量量，堆堆叠叠的的流流量量得得到到平平滑滑，单单个个TCP流流仍仍保保持持长长相相关关性。性。n为为什什么么堆堆叠叠的的网网络络流流量量仍仍具具有有长长相相关关性性( (H0.5)？TCP拥塞控制和具有重尾特性的上层协议共同作用。拥塞控制和具
24、有重尾特性的上层协议共同作用。nTCP本身是一个产生自相似特性的确定性过程本身是一个产生自相似特性的确定性过程 26产生自相似的原因 针针对对传传输输层层(TCP和和UDP)更更进进一一步步的的研研究究(Purdue University, Boston University, 1996, NS模拟模拟)nTCP(Tahoe、Reno或或Vegas)可可靠靠的的传传输输机机制制和和流流量量控控制制机机制制保保留留了了由由文文件件大大小小重重尾尾分分布布所所引引发的长相关性发的长相关性n无无流流量量控控制制和和不不可可靠靠的的UDP并并不不使使生生成成的的流流量量具有长相关性具有长相关性 27产
25、生自相似的原因 网络拓扑的影响网络拓扑的影响(Purdue University, Boston University, 1996, NS模拟模拟)n对流量自相似的估计并不因网络拓扑结构变化而改变对流量自相似的估计并不因网络拓扑结构变化而改变 28产生自相似的原因 重重尾尾分分布布的的ON/OFF和和浑浑沌沌的的TCP导导致致Internet流量的分形特性流量的分形特性( (自相似自相似) )Application LayerTransport/NetworkLayerApplication LayerTransport/NetworkLayerHeavy-Tailed File SizeDi
26、stribution Congest Controland ReliabilitySelf-Similarity Link Traffic H29自相似流量对网络性能的影响网网络络性性能能的的度度量量吞吞吐吐量量( (throughout)、延时延时( (delay)、数据包丢失数据包丢失( (packet loss)从从排排队队论论的的视视角角，网网络络是是队队列列的的集集合合，每每个个队队列列有有一一个个缓缓存存( (buffer) )临临时时保保存存到到达达的的数数据据包包。数数据据包包到到达达缓缓存存等等候候转转发发，则则会会产产生生延延时时。若若达达到到数数据据包包的的数数量量超超过
27、过缓缓存存大大小小，则则产产生生丢丢弃弃数数据据包包的的现现象象，同同时时需需要要对对丢丢弃弃的的数数据据包包进进行行重重发发，导导致致吞吞吐吐量量降降低低。实实际际上上，网网络络的的缓缓存存通通常常保保持持很很大以避免数据包丢失，维护高的吞吐量大以避免数据包丢失，维护高的吞吐量30自相似流量对网络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响n缓缓存存占占用用比比传传统统排排队队论论的的分分析析结结果果要要大大，结结果果导导致致更更大大的的延延时时（也也即即队队列列长长度度分分布布在在自自相相似似流流量量作作用用下下的的衰衰减减比比短短时时相相关关源源（泊泊松松到
28、到达达过过程）作用下要慢），由长相关特性决定程）作用下要慢），由长相关特性决定 31自相似流量对网络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响n缓缓存存的的线线性性增增长长导导致致指指数数规规律律减减少少的的数数据据包包丢丢失失，以以及及成成比比例例增增长长的的传传输输带带宽宽利利用用率率。该该理理论对自相关流量不适用论对自相关流量不适用32自相似流量对网络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响n数数据据包包丢丢失失率率与与缓缓存存大大小小和和自自相相似似之之间间的的关关系系当当趋趋近近于于1 1，自自相相似似程程度度增增大大
29、( (H(3)/2)，数数据据包包丢丢失率增大失率增大 33自相似流量对网络性能的影响自相似流量对网络性能产生负面影响自相似流量对网络性能产生负面影响n文件大小的重尾分布与吞吐量的关系文件大小的重尾分布与吞吐量的关系平均缓存平均缓存占用占用( (字节字节) )与与数据包数据包平均延时平均延时成比例成比例34国内相关工作“自相似业务量的多重分形分析自相似业务量的多重分形分析”，电子学报，电子学报，20002000年，第年，第2828卷，第卷，第1 1期，期，P.96-98P.96-98；“CERNET网络业务的自相似性及性能分析网络业务的自相似性及性能分析”，天津大学学报（自然科学与工程技术版）
30、，天津大学学报（自然科学与工程技术版），20002000年，第年，第3333卷，第卷，第3 3期，期，P.367-370P.367-370； “突发业务的多重分形建模及其参数估计突发业务的多重分形建模及其参数估计”，电子学报，电子学报，19991999年，第年，第4 4期，第期，第2727卷；卷； “网络中业务流的自相似性与线性网络中业务流的自相似性与线性AR1模型模型”，电子学报，电子学报，19991999年，第年，第4 4期，第期，第2727卷；卷；“自相似业务模型下的队列分析自相似业务模型下的队列分析大偏差技术大偏差技术”，通信学报，通信学报，19991999年，第年，第2020卷，第卷
31、，第4 4期；期； 35国内相关工作“自相似业务合成流的建模及排队性能分析自相似业务合成流的建模及排队性能分析”，通信学，通信学报，报，19991999年，第年，第2020卷，第卷，第8 8期；期； “自相似业务：基于多分辨率采样和小波分析的自相似业务：基于多分辨率采样和小波分析的Hurst系数估计方法系数估计方法”，电子学报，电子学报，19981998年，第年，第7 7期；期； “A New Multifractal Traffic Model Based on the Wavelet Transform”、“Measurement and Analysis of IP Network Tr
32、affic”，上海复旦大学，计算机科学与工程上海复旦大学，计算机科学与工程系；系；中国科学院软件研究所，中国科学院软件研究所，“信息网前沿技术研究：通信信息网前沿技术研究：通信网络动态仿真网络动态仿真”的项目中对科技网流量进行分析，验证的项目中对科技网流量进行分析，验证广域网流量的长相关性，采用小波分析的方法分析整理广域网流量的长相关性，采用小波分析的方法分析整理采集的数据。并将广域网流量的长相关特性应用于千兆采集的数据。并将广域网流量的长相关特性应用于千兆交换路由器的缓存控制。交换路由器的缓存控制。 36可能的研究内容Internet的非线性发展（非线性的动力学系统，的非线性发展（非线性的动
33、力学系统，具备浑沌特性）具备浑沌特性）n网络协议体系的变化，从共享以太网网络协议体系的变化，从共享以太网交换以太网交换以太网ATM千兆以太网千兆以太网/ /Wireless Ethernet10G Ethernet，纯纯IPv4IPv4与与IPv6共存共存纯纯IPv6nInternet路由策略的变化路由策略的变化，“first come, first serve”公平的资源共享公平的资源共享 n网络应用的多样化，网络应用的多样化，Grid、P2P、视频会议、视频会议、Internet multicast应用、应用、Web Cache、VRML、多人多人游戏游戏 n用户人数和主机数的增多（流量源
34、的增加）用户人数和主机数的增多（流量源的增加）为研究网络流量特性提供新的契机为研究网络流量特性提供新的契机 37可能的研究内容实时探测网络流量的自相似特性实时探测网络流量的自相似特性优化网优化网络性能络性能如何实现流量整形如何实现流量整形( (Traffic shaping)?在在应用层还是在传输层应用层还是在传输层/ /网络层网络层网络流量自相似特性对实际的网络动态因网络流量自相似特性对实际的网络动态因子子- -Network Dynamics( (如为保证如为保证QOS所作所作的算法、策略、的算法、策略、TCP拥塞控制算法甚至应拥塞控制算法甚至应用层协议的设计用层协议的设计) )究竟存在多大参考价值究竟存在多大参考价值38可能的研究内容网络自相似的网络自相似的“度度”在何处？研究表明，在何处？研究表明，以太网上负载越高，自相似的程度越高。以太网上负载越高，自相似的程度越高。当网络负载在当网络负载在30 70的范围，流量的的范围，流量的波形呈现自相似特性，波形呈现自相似特性，H趋近于趋近于1 1。而当负。而当负载在载在80 99范围内，波形呈现很强的范围内，波形呈现很强的周期性，计算周期性，计算H值基本上是不可能的。值基本上是不可能的。39
