网络测量与分析技术.ppt

网络测量与分析技术 黄泳铭华北计算技术研究所2008年秋季 Self SimilarityinWorldWideWebTraffic EvidenceandPossibleCauses I INTRODUCTIONII BACKGROUNDIII RELATEDWORKIV EXAMININGWEBTRAFFICSELF SIMILARITYV EXPLAININGWEBTRAFFICSELF SIMILARITY Self SimilarityinWorldWideWebTraffic EvidenceandPossibleCauses cont d VI CONCLUSION Abstract 最近 自相似性这一概念已经被证明适用于广域网和局域网的网络流量 本文 我们证明网络流量表现出WorldWideWeb 万维网 传输的自相似性 并且我们对自相似做出了一种假设的解释 总的方法 对NCSAMosaic实际用户做一套追踪 我们检查WWW流量的结构 两大步骤 首先我们证明WWW流量显示它与自相似模型一致性 其次我们证明自相似性可以被解释成是基于WWW文件大小的基本分配 传输中高速缓存和用户偏好的影响 用户的 思考时间 的影响和在一个局域网中许多传输的叠加 I INTRODUCTION 为了正确制定和执行的计算机网络和网络服务 如万维网 了解网络流量的性质是关键 最近的局域网流量和广域网流量调查共同挑战已经被承认的网络流量模型 例如泊松过程 发生在许多或所有时间段的流量可以用自相似性概念描述 由于在一个长的时间范围内已观查到自相似性过程的发生 它应该表现出长相关性 在任意时刻的估计值应该与将来时段的估计值相一致 然而 在网络流量中自相似背后的原因还没有被清楚地认出 在本文中 我们列出一些情况 网络流量的自相似可以从文件系统的特点和用户行为方面解释 两个必要工具 ON OFFsources 在SectionII C中会详细描述 WorldWideWeb 数据采集工作 NCSAMosaic捕获用户访问网站的访问模式我们的数据包括50多万用户文件传输要求而且包含了详细的时间和传输长度 另外 我们调查了一些Web服务器而得到文件大小的信息用来比较客户的访问模式和出现在服务器上的访问模式 文章结构 第一部分 我们考虑我们衡量的Web流量最繁忙时间自相似的可能性 第二部分 利用网络流量 用户偏好 以及文件大小数据 我们解释某一特定网络的传输时间和空闲时间是重尾的原因 II BACKGROUND A DefinitionofSelf SimilarityB StatisticalTestsforSelf SimilarityC Heavy TailedDistributions A DefinitionofSelf Similarity 给一个零平均值固定时间序列X Xt t 1 2 3 定义m聚合度序列X m X m k k 1 2 3 我们称序列X是H self similar 对于所有确定的m X m 有与被mk重新调节的序列X有相同的分布 如果X是H self similar 它有相同的自相关函数作为序列Xm中的所有m 一个长相关性进程有一个自相关函数当 这个进程的自相关函数遵循幂衰减 与传统流量模式显示的指数衰减相比较 幂衰减要慢于指数衰减 对时间序列采用自相似模型一个吸引人的特点 适当的时候 是一个序列的自相似程度可以只用一个单一的参数表示 这个参数表示序列的自相关函数的衰减速度 该参数用Hurst参数表示 II BACKGROUND A DefinitionofSelf SimilarityB StatisticalTestsforSelf SimilarityC Heavy TailedDistributions B StatisticalTestsforSelf Similarity 本文中用四种方法测试自相似 1 variance timeplot2 R Splot3 periodogrammethod4 Whittleestimator 由于我们只关心在我们的数据中的长相性 所以我们用第四种方法Whittleestimator 其两个基本结构是这是分行高斯噪声 FGN 和fractionalARIMA p d p 因为每小时收集的数据都使m增加 在使用FGN模型时Whittleestimator适用于每个m聚合度数据 随着m的增加 短相关性达到数据的平均值 如果H的值始终不变 我们可以确信它估量出了自相似的基本水平 置信区间的增长将趋于聚集程度增加 然而如果随着聚集程度的增加H的估计出现稳定 我们认为置信区间具有代表性 II BACKGROUND A DefinitionofSelf SimilarityB StatisticalTestsforSelf SimilarityC Heavy TailedDistributions C Heavy TailedDistributions 如果一个分部是重尾分布那么应该符合简单的重尾分布是Pareto分布 Pareto分布在其整个范围是双曲线 Pareto分布的概率函数是其累积分布函数是参数k是随机变量的最小可能值 为了估计我们数据中重尾的出现我们使用log logcomplementarydistribution LLCD plots有可能用LLCDplot产生参数的粗略估计 III RELATEDWORK 先前的广域网研究已经研究了FTP TELNET NNTP 和SMTPtraffic我们的数据通过在一个 stub network的WWW流量研究补充先前的研究 因为WWW流量可以解释互联网流量的很大一部分 我们集中研究网络流量的自相似性的原因 由于这个原因 我们并不分析流量资源的低 正常 繁忙的时段 相反 我们着重于在我们的记录中四个繁忙的时间 我们的文件是根据在应用层收集的数据而不是网络层 因此 我们可以检查传输时间和文件大小的关系 并能对这些分布的高速缓存和用户偏好的影响进行估计 IV EXAMININGWEBTRAFFICSELF SIMILARITY A DataCollectionB Self SimilarityofWWWTraffic A DataCollection 我们收集数据从1994年十一月21日到1995年5月8日 但是本文里用的数据只是从1995年1月17日到1995年2月28日 选择这段时间是因为各部门的WWW使用明显降低而且因为1995年3月初Mosaic在我们的网站不再是占主导地位的浏览器 这个研究跟踪数据的统计在表I 表1 IV EXAMININGWEBTRAFFICSELF SIMILARITY A DataCollectionB Self SimilarityofWWWTraffic B Self SimilarityofWWWTraffic 我们集中研究流量序列中的个别时间 以便能够提供一个尽可能接近于静止的数据 提供这四种方法的一个例子 我们在图1中分析1995年2月5日星期四4 5点这一小时的数据 图1 a variance time分析 图1 b R Splot分析 图1 c periodogrammethod 以上的三个图各表示用variance timeplot R Splot和periodogrammethod方法分析一个小时的数据证明了网络流量具有自相似性 我们使用的Whittleestimator方法要求提供基本时间序列的构成 因此我们使用分型高斯噪声模型 用这种方法分析四个最忙时间的结果见图2 图2 a 最繁忙时间 图2 b 次繁忙时间 图2 c 次空闲时间 图2 d 最空闲时间 以上四图表明我们使用的Whittleestimator方法分析网络上的数据得到的判断依然是在 stub network网络传输具有自相似性 V EXPLAININGWEBTRAFFICSELF SIMILARITY A SuperimposingHeavy TailedRenewalProcessesB ExaminingTransmissionTimesC ExaminingQuietTimes A SuperimposingHeavy TailedRenewalProcesses 考虑大量同时存在的进程 每个不是ON就是OFF 每个进程的ON和OFF周期交替 并且其中ON的时间分配是参数为的重尾 或者OFF的时间分配是参数为的重尾 这样的模型相当于一个工作站的网络 每个不是保持沉默 就是以恒定速率传输数据 对于这种模式 它显示出许多资源的收集结果是一个自相似fractionalGaussiannoise过程 其中 通过这个模型来解释Web流量的自相似性需要解释ON或OFF时间的重尾分布 在我们的研究中ON时间相当于独个网站文件的传输持续时间 OFF时间相当于传输间隔时间 如果ON和OFF时间的重尾分布这是为什么 为了回答这些问题 我们可以分析我们的客户记录的特点 V EXPLAININGWEBTRAFFICSELF SIMILARITY A SuperimposingHeavy TailedRenewalProcessesB ExaminingTransmissionTimesC ExaminingQuietTimes B ExaminingTransmissionTimes 1 TheDistributionofWebTransmissionTimes 我们首先观察的网络文件传输时间分布显示文件传输时间有明显的分布规律 图3 a 显示发生在测量期间所有的130140文件的持续时间的LLCDplot 图3 b 显示对变量k的Hillestimator的估计值 图3 a LLCDplot 图3 b Hillestimator 从图3可以看出ON时间的基本分布在一个非常高或者无穷的差异状态 值得注意的是在ON时间分布的大量的ON OFF进程的收集结果是一个自相似进程 2 WhyAreWebTransmissionTimesHighlyVariable 为了理解为什么传输时间存在较大差异 我们检查网络文件本身的大小分布 首先 我们展示在我们日志中文件传输的大小分布 所有的130140个文件传输的结果在图4中显示 图4 a LLCDplot 图4 b Hillestimator 由图4可以观察出文件大小大于10000字节时 流量分布似乎可以相当好的被重尾分布建模 一个重要问题是 为什么文件传输表现出重尾分布 filerequest不是其主要原因 其真正原因是文件传输似乎更跟据在Web中的Availablefile而定 就这两个原因的具体分析见图5 图5 a filerequest 图5 b uniquefile UniqueFiles FileTransfers和FileRequests的关系在图6中可以观察的更详细 是什么决定了uniquefiles的分布呢 为了帮助回答这个问题 我们调查了遍布北美的32个网站服务器 事实上 所有可见文件的分布出现在32个网络服务器很接近我们的客户踪迹的uniquefiles分布 Uniquefiles和AvailableFiles的文件分布见图7 图7 图7表明Uniquefiles可以被考虑成是AvailableFiles的版本 这种说法依据的假设是 缓存管理不根据引用文件的大小排除或引用 并且Uniquefiles是在一套AvailableFiles中不注重大小的抽样 因此 我们断定只要缓存是有效的 在Web中AvailableFiles可能是文件传输重尾的首要限定 用户的要求不再重要 3 WhyAreAvailableFilesHeavy Tailed 如果AvailableFiles在Web上是重尾 一个可能的解释可能是明确支持多种格式可能促进文件大小变大 因此增加分布大小的尾重 然而我们发现多种方式在一定层度上增加尾重 事实上 它不是重尾的根本原因 可见图8 图8 图8的中把所有服务器文件根据文件扩展名规成7个类别 我们使用的类别有 图片 文字 音频 视频 结果表明文本文件分布也许是重尾 事实上 文件大小分布有很长的tails之前已注意到 但他们没有明确检查尾的power law行为 值的测量被忽视了 我们把我们的记录中Web文件的分布和Unix文件系统在一次观测中发现的文件分布作比较 收集的数据见图9 图9 令人惊讶的是 图9显示了我们的Web比Unix文件系统对小文件有偏好 更重要的是 Web文件的tail分布与Unix文件tail分布不一样 V EXPLAININGWEBTRAFFICSELF SIMILARITY A SuperimposingHeavy TailedRenewalProcessesB ExaminingTransmissionTimesC ExaminingQuietTimes C ExaminingQuietTimes 在第5章A部分 我们认为网络流量的自相似性是重尾ON OFF进程的叠加 ON时间相当于个人网络文件的传输持续时间 OFF时间相当于工作站没有接收到Web数据的周期 规定OFF时间分两种情况是 积极OFF 时间和 消极OFF 的时间 积极OFF时间和消极OFF时间的差异在本节考虑的OFF时间分布中很重要 从我们的追踪中抽出OFF时间 我们进行如下解释 在每个Mosaic通信中 ai是URL的i请求的绝对达到时间 ci是URL的i请求的绝对传输时间 遵循 ci ai 是ON时间的随机变量 如图3中的描述 而 ai 1 ci 是OFF时间的随