英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
万维网流量中自相似的证据和可能原因
摘要：近年来，自相似的概念已经在广域网和局域网中广泛被接受。在本文中，我们证明了在万维网中传输的网络流量子集显现出的特征与自相似性一致。使用NCSA Mosaic中用户实际使用的情况，我们验证了万维网流量的依赖结构。首先，我们证明万维网流量行为展示出自相似模型。然后，我们提出，这种流量的自相似性可以解释为基于WWW文档大小的基本分布，缓存的效果和用户偏好在文件中转移，用户“思考时间”的影响以及局域网中许多这样的转换相叠加。为了做到这一点，我们基于经验测量了客户端和WWW服务器上独立数据的分布。
关键词：文件大小，重尾，互联网，自相似性，万维网
1 导论
理解网络流量的特性是正确设计和执行电脑网络和像万维网这样的网络服务时至重要的。近期关于局域网和广域网流量的研究已经挑战了常见的用于网络流量的模型，例如泊松过程。如若流量遵循泊松或马可夫过程，他会具有突发特征并在足够长的时间尺度上区域平均平滑。相反，实际流量测量表明流量的大方差（即突发性）存在在广泛的时间尺度上。
在大部分或所有时间尺度上具有的突发性特征的流量可以在统计学上用自相似性这一概念描述。自相似性是一种与分形相关的特性――对于不同尺度，其外观特征不变。在随机对象，如时间序列，自相似性常用在分类当中：当在不同尺度上观察时，物体的相关性结构保持不变。所以，在较大范围的时间尺度内，序列会展现出超过平均范围的突发性。
由于自相似过程在一个广泛的可观察的时间尺度内爆发，它可表现出长相关性。任何时刻的值都是不可忽视且和未来时刻正相关的。令人惊讶的是（在长相关性违反直觉的方面）以太网网络流量的自相似性已经严格成立。网络流量长相关的重要性正在这些研究中[8],[13],[18]中被观察到，这表明数据包的丢失和延迟行为在模拟使用具有长依赖特性的真实数据或合成数据模拟时是完全不同的。
然而，互联网流量自相似的原因还没有确定。在本文中，我们阐述了在几种特定的情况下，网络流量可以通过文件系统特性和用户行为进行解释。在进程中，我们从流量本身追踪网络流量自相似的起源，通过文件传输，缓存系统和用户选择的动作到文件大小和用户事件的高级分布。
为弥合网络流量和高级别系统特征之间的差距，我们需利用两个基本的工具。一，为解释网络流量中单一传输长度的自相似性，我们采用[30]中描述的机制（基于[14]和[15的研究]）。如第II-C节所定义，这些文章指出自相似流量可通过大量具有ON和OFF周期长度和重尾的ON/OFF源的多路复用来构建。这样的机制可以对应一个工作站网络，每个工作站都以精致或恒定熟虑传输数据。
我们的第二个工具是利用万维网（或Web）作为对象研究弥补传输时间和高级别系统特征之间的差距。网络提供了研究流量的特殊机会因为其流量是由一个简单设置产生的文件传输，且用户行为易于监控。
为了研究网络流量模式，我们搜集了参考数据反映我们网站上Web使用情况。我们在NCSA Mosaic上捕获用户访问模式到网络。在数据采集阶段，Mosaic是为我们网络的主要浏览者，因此我们可以在本地捕获Web流量的网站图片；我们的数据集有超过五十万用户对文件传输的访问，包括访问时间数据和传输长度组成。另外，我们调查了大量Web服务器来捕获文件大小信息用以比较准入模式的用户端和服务器端。
本文共两个部分。首先，我们考虑网络流量的自相似性在忙时测量所得的可能性。为此，我们使用和[14]中非常类似的分析方法，这些分析支持了网络流量在满足最高需求时可能会显现出自相似性的观点。这一结果本省就对系统设计者尝试提高Web性能具有影响。
第二，利用我的Web流量，用户偏好和文件大小数据，我们提出对任何Web会话传输时间和安静时间都具有重尾特征的原因，这一原因也是流量自相似性的重要特征。特别的是，我们Web使用的许多特征都可以利用重尾分布来建模，包括传输时间的分布，用户请求文件的分发以及网络上可用的文件大小的底层分布。另外，通过我们测量得到的用户请求时间间隔，我们探索在呈现出闲时重尾的原因。
2 背景
- 自相似的定义
对于时间序列数据的自相似性和随附的统计检验的详细讨论可参见[2],[29]。在本小节中将以此为基础展开讨论。
给定一个零均值，平稳时间序列 ，我们定义m-聚合序列通过对原始序列X中大小为m的非交叠块求和得到。于是我们可以说，对于所有正m，与X以尺度缩放后具有相同的分布，则X序列是H-自相似的。即：
， 对于
如果X是H-自相似的，则对所有的m，有相同的自相关函数。要注意的是，这意味着此序列为分布式自相似，即聚合序列的分布除了规模变化以外和原始序列是相同的。
其结果是，自相似过程可以看作长相关过程。具有长相关的过程具有自相关函数,，其中。因此，这一过程的自相关函数服从幂律分布而传统的流量模型服从指数分布。幂律衰变比指数衰变慢，而且因为，这种序列的自相关值之和趋近于无穷。这一特点具有很多影响。第一，这样一个序列的不会像其他按基本统计预测不相关集的情况，其n个样本的均值方差与1/n呈正比得减小，而是以的比例渐少。第二，这样一个序列的功率谱是双曲线，以零频率上升至无穷大――反映出数据中长相关的“无限”影响。
在时间序列上使用自相似模型的另一个十分引人入胜的特点在于，在适当的点，序列的自相似程度可以仅仅使用一个单一参量来表达。参量表示了序列自相关函数延迟的速度。由于历史原因，使用的参数是Hurst参数。因此，对于具有长相关的自相似序列，存在。当，其自相似性和长相关性都递增。
B. 自相似度统计检验
在本文中，我们利用来检验自相似度。这些方式在[2]中有详尽的描述，且在[14]中也有相同的描述。这些方法对合成的数据集的准确性总结可参见[27]。
第一种方法，方差-时间图法，依靠自相似序列方差的慢衰减。序列的方差在对数图上成反比；与其拟合的直线斜率为-，，与自相似系数H相关，H可通过得到。第二种方法成为R/S图法，利用自相似数据集所具有的特点，其重新缩放范围和R/S统计数服从幂律增长，且其中H指数为具有n点的函数。因此，R/S图与n在对数图上呈现出的斜率可作为H的估算。第三种方法为周期图发，使用当频率接近于零时序列功率谱函数为斜率。在对数图里，周期图的拟合线为直线切斜率满足。
虽然上诉的三种图形法对于证明错误假设是有用的（如非平稳数据集），他们并不能提供置信区间，并且正如[27]中所述，他们可能会使H值大于真实值。第四种方法称为惠尔特（Whittle）估计，确实提供了置信区间，但其缺点是底层形式必须提供随机过程。最常用的两种形式为有参数的分数高斯噪声（FGN）和分数ARIMA，且（可多细节可参见[2],[4]）。这两种方法的区别在于他们对数据集短相关的假设；FGN认为不存在短相关而分数ARIMA采用固定程度的短相关。
由于我们只关心数据集的长相关，我们使用惠尔特估计如下：每小时的数据集都以增加的m阶聚合，对每个分组使用惠尔特估计中的FGN模型。这一过程利用了所有长相关过程当聚合到一个足够的阶层时接近FGN的属性，并且应该加上聚合观察的边界分布来保证它已融合到正态分布。随着m增加，短相关从数据集中取得平均值；如果H的值仍然相对不变，我们可以确定其衡量了正确的自相似度。因为聚合会是数据集变短，置信区间会随着聚合阶级增加而变长；然而，如果H的估计值随着聚合阶数增加而保持稳定，我们则考虑未分组数据集的置信区间。
C. 重尾分布
我们在本文中使用的分布具有重尾的性质。重尾分布满足：
，当
也就是说，不管随机变量的小值分布行为是怎么样的，如果分布的渐进形状是双曲线，则他是重尾的。
重尾分布模型最简单的模型为帕累托（Pareto）分布。帕累托分布在所有范围内都是双曲线；其概率质量函数为：
，
其累积分布函数由下式给出：
参数k表示随机变量的最小值。
重尾分布和其他常见的分布，例如指数，正态或泊松分布具有很多性质上的不同。当，则重尾分布具有无限方差；当，则分布具有无限均值。因此，随着减少，大部分的概率质量将分布在尾部。实际上，服从重尾分布的随机值可以在尾部产生非常大且无法忽视的值（参见[20]和[16]中的详述和例子）。
为了评估我们的数据中是否存在重尾现象，我们采用对数互补分布（LLCD）曲线。在对数轴上绘制互补分布。通过对数图，重尾分布会呈现出以下性质：
为检测实践中重尾现象，我们组成LLCD图，并寻找在尾部重要范围的大致线性现象（三个或更多数量级。）
利用LLCD图对形状参数做出粗略估计是有可能的。首先，我们检查LLCD图，选择一个合适的值，使此时的图成线性。值得合适选择是观察LLCD图的基础；在本文中，我们将定义在每一种情况下，利用结果的拟合线来估计值。
我们用来估计重尾的另一种方法是希尔（Hill）估计（详细描述见[30]）。希尔估计利用数据集中的最大值k来估计数据集的。在实践中，希尔估计图用于增加k值，只使用尾部显示幂律行为的部分；如果估计值一致，则提供的估计值。
3. 相关工作
了解WWW流量的第一步是收集跟踪数据。以前的网络研究主要注重建立代理日志[11]，[25]或服务[21]的参考模式。[5]中的作者捕获了用户痕迹，但是他们将重点放在了用户交互级的时间以此来学习浏览和页面设计。相反，我们收集数据的目标在于获取参考行为和用户接入WWW时间的完整画面。我们这一追踪（也可用于匿名FTP）的完整描述可参见[6]。
以前的广域流量研究已经研究过FTP，TELNET，NNTP和SMTP流量[19]，[20]。我们的数据通过提供在“stub”网络上WWW（HTTP）流量的视图来完善这些研究。因为WWW流量在网络流量中占据了很大一部分，理解WWW流量的性质是十分重要的。
网络流量自相似性研究的基准是[14]，我们的研究利用了许多与之前工作中相似的方法。然而，那一工作的目的在于展示网络流量的自相似性，为了达到这一目的，使用了许多多年跨度的大数据集。我们的目的并不是建立网络流量的自相似性（虽然我们暂时使用网络相关流量的有趣子集）；我们关注与检验流量自相似性背后的原因。关注点不同的结果为，我们并不分析流量数据集的闲时、正常时、忙时状态。我们关注我们的日志中最忙的四个小时。当这四小时可以很好得被描述为自相似是，日志中其他不那么忙的时间则不显示自相似特征。我们认为这只是我们日志中存在流量需要呈现的结果，比我们实际使用的会要更少[14；这一想法也在其他研究中得到了证实，结果显示随着自相似性密度会随着聚合阶数而增加。
我们的工作意图与[30]最为相似。在那篇论文中，查看分组级别的网络流量，确定各个源/目的地对之间的对流，并显示流中流量的传输和空闲时间是重尾的。相较之下，我们的论文以应用级的数据采集为基础，而非网络级。所以，我们能够财务室传输时间和文件大小之间的关系，并且能够评估缓存和用户偏在这些分布中的影响。这些观察使我们能基于[30]中得出的结论，通过传输和闲时的重尾特性确认[20]中的观察结论并不是网络协议和用户偏好的结果，而是源于信息存储和处理的更基本属性：文件大小和用户“思考时间”本身就是重尾的。
4. 测试网络流量自相似性
在这一小节中，我们证明WWW流量是呈现自相似性的。为此，我们首先描述我们是怎么测量WWW流量的；然后再在第二小节中详述得到自相似性的统计方法。
- 数据采集
为了将流量模式相关到更高等级的影响中，我们需要捕获用户行为和网络需求的各个方面。我们捕获这两只数据的方法是改变WWW浏览器来记录网站所有用户的准入。我们使用的浏览器是Mosaic，因为他的开源特性，允许用户因研究用途而更改其代码。数据采集方式和日志文件形式在[6]中给出；再次，我们只对其做一个高度的总结。
我们改变Mosaic来记录每一位用户的统一资源定位符（URL）[3]以及文件时间和从服务器转换的准入时间（如果必要的话）。为了其完整性，我们记录所有的URL无论他是服务于Mosaic的缓存还是来自文档转换；然而，我们在这一小节分析流量时间序列只有网络转换器组成。
在我们研究的所有时间内（1995年一月和二月），Mosaic是几乎所有我们所用户使用的浏览器。因此，我们的数据几乎包括我们所使用的所有WWW流量数据。由于在我们开始研究时，用户开始更喜欢不开源的商业浏览器。所以，捕获一个相当的WWW用户数据在当时变得更加困难。
捕获的数据包括在每个会话期间执行的WWW文件请求的序列，其中会话是NCSA Mosaic的一个执行。每个文件请求由其URL和会话，用户和工作站ID标识; 与请求相关联的是请求时的时间戳，文档的大小（包括协议的开销）以及对象检索时间。时间戳准确到10毫秒。 因此，为了在我们的结果中提供三个有效数字，我们将分析限制在大于或等于1秒的时间间隔。要将我们的日志转换为流量时间序列，有必要将每个请求中传输的字节均等地分配到跨传输持续时间的bin中。 虽然这个过程平滑了每次传输的流量的短期变化，但是我们时间颗粒度为1 s或更多的时间，考虑到大多数文件传输都很短的事实[6，这样的平滑几乎对我们的结果没有影响。
为了收集我们的数据，我们在波士顿大学计算机科学系的通用计算环境中安装了我们的仪器版本。该环境主要由连接在本地网络中的37个SparcStation-2工作站组成。每个工作站都有自己的本地磁盘; 日志已写入本地磁盘，随后转移到中央存储库。虽然我们从1994年9月14日至1995年5月8日期间收集资料，但文本中所用数据只能从1995年1月17日到1995年2月28
全文共14254字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144360]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
