网络流量自相似特性.ppt

1 提纲 问题提出自相似的数学描述产生自相似的原因自相似对网络性能的影响国内相关工作可能的研究方向 2 问题提出 什么是自相似 为什么研究自相似 产生自相似的原因 泊松过程 随机变量 单位时间呼叫到达的次数 是独立的 且服从相似分布 即P Xk n e t t n n n 0 马尔可夫模型 对过去具有有限记忆 即在已经知道 现在 的条件下 其 将来 不依赖于 过去 时间t与过去时间t s 若s足够大 则t与t s时的业务量是不相关的 即仅考虑s较小时业务到达间的相关性 称之为短时相关ShortRangeDependence SRD模型 3 自相似的数学描述 网络流量模型时间序列 表示每单位时间到达的字节数或数据包数量自相似的物理描述网络流量在很宽的时间尺度内存在突发现象 Burst 时间尺度 几十毫秒 秒 分钟 小时 4 自相似的数学描述 数学定义假设前提 平稳随机过程 即统计特性 均值 方差 相关等 不随时间推移而变化 一阶平稳 均值为常数 二阶平稳 均值和方差为常数 任意两时间点之间的协方差只取决于时间间隔 又称之为广义平稳 自相关函数定义为 r k E Xt Xt k E Xt 2 5 自相似的数学描述 自相似条件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 6 自相似的数学描述 自相似 Exactlysecondorder self similarX m 的自相关函数r m 满足 r m k r k 对所有m 1 2 k 1 2 3 渐进自相似 Asymptoticallysecondorder self similarX 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 7 自相似的数学描述 自相似参数HH 1 2r k k 2 2H L1 k 当k 渐进自相似 asymptoticallyself similar r k 1 2 k 1 2H 2k2H k 1 2H 严格自相似 exactlyself similar 参数H满足0 5 H 1 参数H用来表示自相似的程度 8 自相似的数学描述 自相似的特性长相关 LRD longrangedependence largescalecorrelation longtermcorrelation 长相关定义 若一个随机过程满足自相似的条件1和条件2 即其自相关函数随时滞的增加呈双曲线衰减 幂律衰减 则该随机过程呈现长相关性长相关 自相似 自相似是长相关的特例 简单模型不可和性 即 kr k 不可和性的物理意义在于高滞后的相关虽然是个别的小量 但其累计的结果则十分重要短相关过程 short rangedependence 自相关函数呈指数衰减 即r k k 当k 0 1 其自相关函数是可和的 即0 kr k 9 自相似的数学描述 自相似的特性慢衰减方差自相似过程的方差满足var X m am 当m 其中0 1 a是与m无关的正常数 与前条件2中 相同短相关过程的方差满足var X m bm 1 当m 其中b是与m无关的正常数自相似过程的方差衰减要慢于短相关过程 10 自相似的数学描述 自相似的特性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 Rescaledadjustedrangeanalysis 11 自相似的数学描述 自相似的特性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曼德博罗 分形理论的创始人 美籍法国数学家 12 自相似的数学描述 自相似r k k L1 k k 0 1 L1是慢变函数 kr k var X m am m 0 1 短相关r k k 当k 0 1 0 kr k var X m bm 1 m 13 自相似的数学描述 如何测度自相似数学定义针对无限长度的时间序列实际中仅仅一段时间的取样 保证取样点足够多 14 自相似的数学描述 如何测度自相似针对有限的时间序列来估计Hurst参数方法1 分析堆叠过程X m 的方差 自相似的慢衰减方差特性var X m am m var X m m a m 0 4H 0 8 15 自相似的数学描述 如何测度自相似方法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 16 自相似的数学描述 如何测度自相似基于周期图 Periodogram 的频域分析协方差函数 傅立叶变换 功率谱用周期图近似估计功率谱从谱密度中找到参数H 17 自相似的数学描述 具备自相似的数学模型自相似理论广泛地应用在水文和经济学领域分形 分数 高斯噪声 fractionalGaussiannoiseFGN分形 分数 布朗运动 fractionalBrownianmotionFBM 是分形高斯噪声的增量和过程分形 分数 自回归滑动平均过程 fractionalARIMAprocessesAutoRegressiveIntegratedMoving Average 渐进自相似过程 18 自相似的数学描述 网络流量的建模ON OFF模型 叠加大量的ON OFF源 每个源有两个状态 即ON和OFF 在ON状态 以连续速率发送数据包 在OFF状态 不发送数据包 每个发生源ON或OFF的时长独立地符合重尾分布 Heavy taileddistribution 重尾分布 若一随机变量满足重尾分布 则P X x x 当x 00 x k 分布函数为F x P X x 1 k x 当 减小 大量的概率质量集中在分布的尾部H 3 2佩瑞多 韦尔福雷多 ParetoVilfredo 意大利经济学家和社会学家 19 对流量自相似研究的三个方面 分析流量的特征 建模小波分析 DiscreteWaveletTransform 和分形理论分形和多重分形 Multifractal 模型 可信的 网络流量生成模型产生流量自相似的原因评估自相似流量对网络的影响 20 产生自相似的原因 是流量内在的特性还是网络协议的调制作用 Web流量的自相关性 BostonUniversity 1996 1998 实际数据 Web文件大小的分布 包括用户请求的文件 实际传输的文件 文件的传输时间 服务器端存储的文件等 呈重尾分布 客户端Cache的影响相对较小 Web文件传输时间的重尾分布 Web流量的自相似性 21 产生自相似的原因 若文件大小符合重尾分布 则对应的文件传输均导致链路层的自相似性 Web NFS FTP等 PurdueUniversity BostonUniversity 1996 NS模拟 上述情况似乎都可以从ON OFF模型找到解释的理由 22 产生自相似的原因 对IP流量成分的进一步分析 Hungary BudapestUni OfTech Econo 实际数据 2000 不同协议成分如IP ICMP TCP UDP HTTP SMTP FTPdata FTPcontrol OSPF Telnet 是否多重分形 multifractal 和分形 monofractal 即自相似 23 产生自相似的原因 重传机制 Retransmission 产生自相似特性 CMU 1997 模拟条件 输入是泊松到达 即 新数据包 不包括重传的数据包 到达是一个简单的泊松过程 数据包长度为常数 一个队列情况 先进先服务 无拥塞控制的重传机制结论 当时间尺度超过10倍的数据包传输时间 重传数据包流量的方差在总的流量 新数据包 重传数据包和丢失的数据包 中占据绝大多数成分 即使改变重传机制的参数 如缓存大小 重传企图的次数和超时时限 不能改变重传负载的自相似特性 24 产生自相似的原因 TCP拥塞控制的浑沌特性 Ericsson TrafficAnalysisandNetworkPerformanceLab 2000 浑沌系统的特征 非线性 Nonlinearity 确定性 Determinism 混乱中的有序 Orderindisorder 对初始状态的敏感性 蝴蝶效应 Sensitivitytoinitialconditionsorthe butterflyeffect 不可预见性 Unpredictability 模型 NS模拟 TCPTahoe Slow Start CongestionAvoidance FastRetransmit 参数设置 linkrate C delay D buffersize B以及TCP流的数量 N 25 产生自相似的原因 TCP拥塞控制的浑沌特性 Ericsson TrafficAnalysisandNetworkPerformanceLab 2000 结论 B N的比率控制着系统的相位迁移 即从周期性到浑沌 并在特定的参数下产生自相似时间序列 单个的TCP流量符合渐进自相似 H 0 5 在瓶颈缓存处堆叠的TCP流量是短时相关的 H 0 5 其物理解释是TCP拥塞控制使瓶颈缓存占用率最大来平滑流量 堆叠的流量得到平滑 单个TCP流仍保持长相关性 为什么堆叠的网络流量仍具有长相关性 H 0 5 TCP拥塞控制和具有重尾特性的上层协议共同作用 TCP本身是一个产生自相似特性的确定性过程 26 产生自相似的原因 针对传输层 TCP和UDP 更进一步的研究 PurdueUniversity BostonUniversity 1996 NS模拟 TCP Tahoe Reno或Vegas 可靠的传输机制和流量控制机制保留了由文件大小重尾分布所引发的长相关性无流量控制和不可靠的UDP并不使生成的流量具有长相关性 27 产生自相似的原因 网络拓扑的影响 PurdueUniversity BostonUniversity 1996 NS模拟 对流量自相似的估计并不因网络拓扑结构变化而改变 28 产生自相似的原因 重尾分布的ON OFF和浑沌的TCP导致Internet流量的分形特性 自相似 ApplicationLayer Transport NetworkLayer ApplicationLayer Transport NetworkLayer Heavy TailedFileSizeDistribution CongestControlandReliability Self SimilarityLinkTrafficH 29 自相似流量对网络性能的影响 网络性能的度量 吞吐量 throughout 延时 delay 数据包丢失 packetloss 从排队论的视角 网络是队列的集合 每个队列有一个缓存 buffer 临时保存到达的数据包 数据包到达缓存等候转发 则会产生延时 若达到数据包的数量超过缓存大小 则产生丢弃数据包的现象 同时需要对丢弃的数据包进行重发 导致吞吐量降低 实际上 网络的缓存通常保持很大以避免数据包丢失 维护高的吞吐量 30 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响缓存占用比传统排队论的分析结果要大 结果导致更大的延时 也即队列长度分布在自相似流量作用下的衰减比短时相关源 泊松到达过程 作用下要慢 由长相关特性决定 31 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响缓存的线性增长导致指数规律减少的数据包丢失 以及成比例增长的传输带宽利用率 该理论对自相关流量不适用 32 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响数据包丢失率与缓存大小和自相似之间的关系 当 趋近于1 自相似程度增大 H 3 2 数据包丢失率增大 33 自相似流量对网络性能的影响 自相似流量对网络性能产生负面影响文件大小的重尾分布与吞吐量的关系 平均缓存占用 字节 与数据包平均延时成比例 34 国内相关工作 自相似业务量的多重分形分析 电子学报 2000年 第28卷 第1期 P 96 98 CERNET网络业务的自相似性及性能分析 天津大学学报 自然科学与工程技术版 2000年 第33卷 第3期 P 367 370 突发业务的多重分形建模及其参数估计 电子学报 1999年 第4期 第27卷 网络中业务流的自相似性与线性AR1模型 电子学报 1999年 第4期 第27卷 自相似业务模型下的队列分析 大偏差技术 通信学报 1999年 第20卷 第4期 35 国内相关工作 自相似业务合成流的建模及排队性能分析 通信学报 1999年 第20卷 第8期 自相似业务 基于多分辨率采样和小波分析的Hurst系数估计方法 电子学报 1998年 第7期 ANewMultifractalTrafficModelBasedontheWaveletTransform MeasurementandAnalysisofIPNetworkTraffic 上海复旦大学 计算机科学与工