（计算机系统结构专业论文）基于自相似流量预测的拥塞预警方法.pdf

上海交通大学硕士学位论文 基于自相似流量预测的拥塞预警方法 摘要 t 随着局域网的迅速发展，针对局域网的性能评测技术也变得越 来越重要。但根据最近的测量表明，局域网流量分布并非符合泊松 分布，而是具有自相似性钡而导致传统的排队论分析方法不再适 用于局域网的性能评测。i 为了在进行局域网性能评测时避免发生拥 塞，本文提出了一种基于自相似流量预测的拥塞预警方法。主要研 究内容包括： 1 通过将单个以太网信源描述为p a r e t o 分布的o n o f f ( 通 断) 信源，将若干个这样的信源进行叠加所产生的流量可以使用 分数高斯噪声f g n 来描述，并且该结果反映了真实的以太网通 信量。 2 推导了一个关于分数高斯噪声f g n 的最小方差预测公式， 根据此公式可以预测出自相似流量的概率分布。 3 根据预测出的自相似流量的概率分布是否超过拥塞概率 门限，来选择是否发出拥塞预警。 4 最后本论文设计了一个实验，以验证这一基于自相似流量 预测的拥塞预警方法的正确性。 本文摆脱了传统的排队论分析方法，针对高负载情况下的局域 上海交通大学硕士学位论文 网性能评测，提出了一条基于自相似流量预测的拥塞预警方法，从 而对网络流量自相似性的分析和应用，作了有益的探索。 关键词：自相顿，拥塞预警，分数高斯噪声 o y 上海交通大学硕士学位论文 am e t h o do fc o n g e s t i o na l a r mb a s e do nt h ep r e d i c t l o n f o rs e l f - s i m l l a rt r a f f i c a b s t r a c t w i t ht h ed e v e l o p m e n to fl a n ，t h ep e r f o r m a n c em e a s u r e m e n t so f l a nb e c o m em o r ea n dm o r ei m p o r t a n t b u tr e c e n tm e a s u r e m e n t so f n e t w o r kt r a f f i ch a v es h o w nt h a tt h i st r a f f i co fl a ni s s t a t i s t i c a l l y s e l f - s i m i l a ra n di t sd i s t r i b u t i o ni s n tp o i s s o n s ot h eq u e u i n gm o d e lc a n t b e u s e di nt h e p e r f o r m a n c e m e a s u r e m e n t so fl a n t oa v o i dt h e c o n g e s t i o n i nt h e p e r f o r m a n c em e a s u r e m e n t so fl a n ，am e t h o do f c o n g e s t i o na l a r m b a s e do nt h e p r e d i c t i o n f o rs e l f - s i m i l a rt r a f f i ci s p r o p o s e d i t i sc o m p o s e do ff o u rc o n t e n t sb e l o w ： 1 s o m e e x p e r i m e n t s o n a g g r e g a t i n g2 0 ，5 0 ，a n d1 0 0p a r e t oo n o f f s o u r c e sw e r ep e r f o r m e d t h er e s u l ti st h ea g g r e g a t i o no fm o r e t h a n1 0 0s o u f c e sc a nb e a c c u r a t e l ya p p r o x i m a t e db y af g n 2 t h i sp a p e r g i v e sa f o r m u l aa b o u tt h eo p t i m al i n e a r p r e d i c t i o nf o r f g n 3 a c c o r d i n gt o t h ep r e d i c t i o nf o rf g n ，i ft h ep r o b a b i l i t yo ft h e a g g r e g a t et r a f f i ce x c e e d st h ep r o b a b i l i t yt h r e s h o l d ，ac o n g e s t i o n a l a r mw i l lb es e to f f 4 a t l a s t ，s o m ee x p e r i m e n t sw e r ep e r f o r m e d t o j u s t i f y t h i sm e t h o d 上海交通大学硕士学位论文 b a s e do nt h ep r e d i c t i o nf o rs e l f - s i m i l a rt r a f f i c i ns u m m a r y , t h i sp a p e rp r o p o s e dan e wm e t h o do f c o n g e s t i o n a l a r mb a s e do nt h ep r e d i c t i o nf o rs e l f - s i m i l a rt r a f f i c t h ea u t h o r h o p e a l lt h ew o r kd o n ec a nb eh e l p f u lt ot h ef u r t h e rr e s e a r c ho nt h e s e l f - s i m i l a rt r a f f i c k e yw o r d s ：s e i f - s i n l il a r ，c o n g e s t i o na i a r m ，f g n 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 嗽移芗彩、 日期：。- 3 年文 7 q 州 阳 ， 月 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上方框内打“4 ”) 学位论文作者签名：指导教师签名： 弓蝙融| 唧；， ，577 馥氅玉 日期：参；年文月7 日日期：硼；年月，于日 上海交通大学硕士学位论文 1 1 性能评价技术 第1 章绪论 当前网络性能飞速增长，按照“新摩尔定律”一光纤定律，互联网带宽每 9 个月增加一倍，但成本降低一半；同时硬件设备包括个人终端p c 和网络设备 ( 如路由器、交换机等) 性能也在不断提高。生产厂商和服务提供商热衷于建设 越来越高速的网络，一些与之相关的技术也不断得到发展；然而用户们往往抱 怨实际获得的网络服务性能的增长与硬件设备性能的增长并不成正比，这就说 明了一个问题：在当前的软、硬件技术水平下，构建网络相对简单、方便，而 管理网络则是一项长期的工作，限制网络性能的瓶颈往往是由于管理的缺陷使 网络的实际性能无法得到充分利用。这一点使得以下两个方面的技术需求变得 尤为迫切：一是如何有效管理高速网络，从而充分利用其性能。二是如何准确 的衡量实际提供或获得的网络服务质量。这种需求主要来自两个方面：首先是 来自i n t e m e t 服务提供商( i s p ) ，i s p 对于不同的网络性能可以提供不同种类的 服务和相对灵活的价格：从用户的角度来说，也需要衡量所购买的网络服务是 否物有所值。 计算机网络性能评测的目的主要有三个：选择、改进和设计。具体而言， 是指在众多的设计方案选择一个最合适的方案，即在一定的价格范围内选择性 能最好的方案，达到较好的性能价格比：对已有系统的性能缺陷和瓶颈进行改 进，以提高其运行效率：对未来设计的系统进行性能预测，在性能成本方面实 现最佳设计或配置。 一般认为，l a n 的性能由应用方面的需要、所连设备的性能及运行环境等诸 因素相互作用，相互影响所决定，既涉及硬件技术，又涉及软件技术，因此，很难 以一两个简单参数对l a n 的性能作出全面评价从系统设计、管理、维护等角 度来考察，有三个参数需要考虑：信道吞吐量( s ) 、信道利用率( u ) 和延迟时间 ( d ) 。此外，考察网络性能还要考虑网络工作的稳定性、公平性和健壮性 上海交通大学硕士学位论文 1 信道吞吐量( s ) ：描述在单位时间内被成功传送的信息量，可以是每秒 多少个报文或多少个报文分组。 2 信道利用率( u ) ：描述的是信道传输信息的时间( 有效时间) 与信道总 可利用时间之比。在这里它通常不包括报头开销、传输冲突等各种形式的开销。 3 延迟时间( d ) ：也称传输延迟或时延，描述的是分组从源站开始产生直 至最后被成功地传送到目的站所需要的时间，它由四个部分组成：排队延迟、访 问延迟、发送时间和传播延迟。 计算机网络的性能一般包括以下两个大的方面：一个方面是它的可靠性或 可利用性，即计算机系统能正常工作的时间，其指标是能够持续工作的时间长 度，如平均无故障时间，另一方面是它的处理能力或效率。这又可分为三类指 标：吞吐率、利用率和响应时间。网络系统常用的性能指标为：信道传输速率 和容量、信道利用率、传输延迟、响应时间和负载能力等。 性能评价的方法大致可以分为两类： ( 1 ) 测量方法 通过一定的测量设备或一定的测量程序可以直接从计算机网络中测得各项 性能指标或与之密切相关的参数，然后对它们进行一些运算处理后求出相应的 性能指标。这是最直接也是最基本的方法，其他方法在一定程度上也要依赖于 它，测量方案和测量手段是使用测量方法的关键。缺点是这种方法只能适用于 已经存在并正在运行的系统，而且比较费时间。测量方法有可以分为两类：主 动测量和被动测量。 主动测试是针对特定的测试目标，主动实施一定的测试行为( 如发送测试 报文，获得网络延迟) 。主动测试目的性强，可提供比较全面的网络信息，例如 不同负载下的性能参数变化情况。但是测试行为会对网络的正常工作产生很大 的影响，如果不能妥善控制主动测试的测试流量，不仅会导致网络拥塞甚至瘫 痪，而且此时的测试数据往往也无法正确反映网络性能。 被动测试仅仅驻留在某个节点被动的采集或监听网络信息，不对网络产生 任何影响。但往往需要对大量的采集数据进行抽取和处理，才能获得目标数据， 并且被动测试结果仅仅在驻留节点获得，反映的网络性能不够全面，而且只能 获得当前网络状况下的静态参数。 上海交通大学硕士学位论文 ( 2 ) 模型方法 首先对要评估的目标网络建立一个适当的模型，然后求出模型的性能指标 以便对网络进行性能评估。模型中一般包括许多参数，这些参数的确定往往依 赖于对实际系统的测量结果或对系统参数的估计。与测量方法相比，模型法有 两个优点：一是不仅可以应用于已有网络的性能评价，而且也可以对尚未存在 的网络进行性能预测；二是它的工作量一般比测量方法要小，费用也相对较少。 模型法又可分为模拟方法和分析方法两种。模拟方法是用一个程序动态地 模拟一个系统及其负载。一般首先使用一个模拟语言来为系统建立模型，然后 在模拟时通过用负载驱动系统模型从而得出模型的性能指标。模拟方法可以详 细的刻画系统，得出较精确的性能指标，但是构造和使用模型时的费用较高。 分析方法则是应用数学理论与方法来研究和描述性能与系统、负载之间的 关系。为了数学上描述与计算的方便，往往要对系统模型进行一些简化和假设， 因而这种模型刻画系统的详细程度较低，得出的性能指标精度也较低。但是这 种方法理论基础强，可以明显地刻画各种因素之间的关系，而且构造和使用模 型时的费用也较低。 随着计算机技术的发展，网络的庞大和复杂化使得系统性能评价越来越重 要，也越来越困难。在某些场合，单独使用测量方法、模拟方法和分析方法中 的任何一种已无法满足需要，例如测量方法是最直接也是最基本的方法，但被 动测试反映的网络性能不够全面，主动测试的负面影响太大，更为重要的是测 量方法测量的目标性不强，由于不同的用户服务需求不同，所关心的网络性能 指标也不同，所以泛泛的性能指标测试无法反映用户的需求，此外用户大多关 心网络重负载或是一些极限状态下网络的性能，因此测量方法又必须同时使用 模拟方法和分析方法来分析网络的工作模型和负载状况。 上海交通大学硕士学位论文 1 2 局域网性能评价面临的特殊问题 可见性能评价已经成为计算机网络研究与应用的重要理论基础和支撑技 术。但相对于应用较为广泛的广域网性能评价而言，局域网的性能评价有其自 身的难点： 1 局域网流量变动幅度较大，如何提出一个准确的负载模型加以描述。 2 局域网用户对性能下降比较敏感，因而如何在性能测试中避免拥塞，维 持局域网正常运行。 3 局域网用户更关心高负载临界状态下的网络性能，因而如何测试临界状 态下的网络性能，同时又最大限度减少对网络正常工作的影响， 4 当前局域网的带宽越来越高，测试数据的准确性就很难得到保证。 5 局域网常常缺乏如同广域网一样进行大范围、长时间性能评测的软硬件 条件，因而性能测试的效率问题也必须得到重视。 排队论模型和排队分析作为当今最为成熟、最为常用的网络性能分析手段， 对于网络设计和系统分析人员进行容量规划和性能预测很有帮助，然而在许多 实际场合人们发现排队分析的预测结果与实际观察到的性能差异很大。由于排 队论模型假设基础是网络流量符合泊松分布，然而在对许多实际网络环境进行 统计之后，发现流量分布是自相似( s e l f - s i m i l a r ) 而不是泊松的。针对前三个问题， 尤其是在网络流量突发性很高的情况下排队论模型和排队分析已不再适用：与 此同时，网络流量所具有的自相似性却越来越得到重视，但准确的描述自相似 流量进而自相似性建模依然有着较大困难。 上海交通大学硕士学位论文 1 3 本论文主要研究内容 鉴于前述分析，本文总结了现有的部分自相似性研究成果，提出了一种面 向网络性能评价的自相似性分析方法，该方法将自相似网络流量的描述转变为 分数高斯噪声( f o n ) 描述，进而通过产生自相似性的负载驱动模型、分数高斯 噪声的预测和分析来解决局域网的性能评价所面临的前三个特殊问题。具体来 说： 1 通过将整个网络流量分解为所有节点的流量叠加，并把每一个节点描述为 p a r e t o 型重尾分布的o n o f f ( 通断) 信源，再将若干个这种信源加以叠加并将 叠加结果与分数高斯噪声( f d 加以对比，这样依据这一方法在网络性能测试 时，可以通过p a r e t o 型重尾分布的o n o f f ( 通断) 信源叠加的负载驱动模型 准确模拟突发性很强的局域网流量。 2 而由于分数高斯噪声( f g n ) 的平稳性，根据针对随机过程的线性最小方差 预测可以仅仅根据历史数据预测出随机过程未来的均值和方差，由于分数高斯 噪声( f g n ) 服从高斯分布，根据预测的均值和方差就可以得出其概率分布，从 而可以预测出未来网络流量超过拥塞门限的概率，实现拥塞预警： 3 同样可以通过流量预测的概率分布，判断未来网络中的负载状况，为l 临界 状态下的网络性能测评提供依据。 这样就针对前面提出的局域网的性能评价所面临的前三个特殊问题，提出 了一条从自相似负载的生成、自相似分析与预测进而得出拥塞预警的方法。 上海交通大学硕士学位论文 第2 章白相似模型及其分析 2 1 排队论与排队网络模型 2 1 1 肯达尔模型 排队论作为运筹学研究的一种手段，早期主要用于电话交换问题研究，在 1 9 5 0 年肯达尔( k e n d a l l ) 系统研究之后，成为目前研究最多也最成熟的网络性能评 估方法。所谓排队论，主要是研究“顾客”一“服务员”系统，其中最主要的两 个因素顾客到达规律和服务员服务规律，都是通过概率分布来描述的。关于排队 模型，目前通用的格式是1 9 5 3 年肯达尔( k e n d a l l ) 提出的“肯达尔模型”，通常称 之为经典排队模型。它的格式为： 氏嗯| 列s l z 其中各符号的含义如下： a ：顾客到达的规律 b ：服务时间分布 r l ：服务员的数目 s ：队列容量的大小 z ：服务规程 对于不同类型的排队，a 、b 可用如下约定的字母表示： m ：如果用于描述到达，表示泊松到达过程，到达时间间隔符合指数分布： 如果用于描述服务，则指具有指数分布的服务时间，指数分布具有马尔可夫特性 或称无记忆特性。 d ：确定性分布。表示到达间隔时间或服务时间都是固定的常数。 g ：一般分布。表示到达间隔时间或服务时间服从一般分布。 e k ：k 一爱尔朗分布。表示到达间隔时间或服务时间服从k 一爱尔朗分布。 h ：超几何分布。 l ：二项式分布。 上海交通大学硕士学位论文 z 代表的典型服务规程有 f c f s ：先来先服务。 l c f s ：后来先服务。 r s s ：随机选择服务。 p r ：优先权服务。 2 1 2 单服务员队列 单服务员队列是最简单的排队系统，图2 1 是一个单服务员排队系统。顾客 以某个平均速率 到达，平均等待顾客数是w ，而平均等待时间是t w 。服务员 以平均服务时间t 。处理到来的顾客，利用率p 是服务员忙碌的时间比率。系统 中的平均顾客数q ，包括正在被服务的和等待的顾客，一个顾客在系统中停留 的平均时间为t q ，这包括等待时间和服务时间。当p = 1 时，服务员1 0 0 的 时间都在工作，此时系统饱和，系统能够处理的最大速率为 w = 等待的顾客 t 。= 等待时间 is = 服务时间 p = 利用率 t q 2 系统中停留的平均时间 图2 1 单服务员队列及其参数 f i g u r e2 1q u e u i n gs y s t e ms t r u c t u r ea n dp a r a m e t e r sf o rs i n g l e s e r v e rq u e u e 此外还可以将单服务员队列推广到多个服务员的情况，形成多服务员队列， 上海交通大学硕士学位论文 参见文献 1 】。 2 1 ，3 基本的排队关系式 下面给出几个基本的排队关系式 表1 1 基本的排队关系式 一般关系单服务员多服务员 q - - t q ( l i t t l e 公式) p = t 5 口：2 t s 1 n w = t w ( l i t t l e 公式)q 2 w 十p“= t l = p n t a 2 t w + t sq = w + n p 对于方程p = t s 而言，考虑到达速率 对应的平均到达时间间隔是1 = t 。如果t s 大于t ，那么在时间段t 内，服务员只忙碌t s 这段时间，所以利用 率就是t s ，t = t 。对于多服务员队列也可与进行相似的推理，得到p = ( t s ) n 。 而对于l i t t l e 公式，可以考虑当一个顾客到达时，它会发现平均有w 个顾客 在它前面排队等待，当它离开队列去接收服务时，它的后面同样有w 个顾客在 等待服务，这与平均等待顾客数是一致的。另外这个顾客的平均等待时间是t 0 ， 由于顾客以平均速率九到达，在t w 时间内一共有x t w 个顾客到达了。这应该等 于这个顾客离开队列进a h t 务时队列中的等待顾客数w ，因而w = - - - t w 。通过相 似的推理可得q = t q 。 此外，容易得到一个顾客在系统中花费的时间就是他等待服务的时间加上被 服务的时间，因而有t q = t w + t 。，在任何时刻，系统中的顾客数就是等待服务 顾客数j j l 上i e 在接收服务的顾客数，单服务员队列就是q = w + p ，对于多服务 员队列为q = w + n p 。 上海交通大学硕士学位论文 2 1 4 单服务员队列的计算公式 对于单服务员队列，表1 - - 2 给出了一些性能指标的计算公式 假设： 1 泊松到达 2 服务规则为先进先出的服务 3 没有顾客从队列中被丢弃 表1 2单服务员排队公式 一般服务时间 指数服务时间 常数服务时间 ( m g 1 )( m 口 1 )( m d 1 ) 畦旧) 2 a 2 南 a = 南+ p 。= p + 盅 。：z。：j l 1 一p2 ( 1 一p ) w ：p 2 a ，一t ，( 2 一p ) l 2 鲁 1 q 2 ( 1 一p ) t q = t s + p 卜t 户s a _ ，一p t s，一p t 3 1 口“2 ( 1 一p ) r r p t s a “i 一口 图2 2 和图2 3 分别为单服务员队列几种服务时间的平均队列长度和平均排队 时间随利用率变化的曲线。指数服务时间对应的性能最差，而常数服务时间对应 的性能最好。服务时间的标准均方差c r t s 与服务时间丁j 的比值c 厂哆可以 上j 取四种不同值： c r 乃= 0 时对应于常数服务时间。 上海交通大学硕士学位论文 万。的值j 、于1 ，比指数分布服务时间的状况略好。 万黟的值等于1 ， ，is 仃，的值大于1 ， m g 1 模型。 这是最常见的情况，对应于指数服务时间。 此时显然不属于m m 1 模型，而应将其归入更为一般的 u l i l i l l o n 聃 图2 3 单服务员队列的平均排队时间 2 】 f i g u r e2 3m e a nr e s i d e n c et i m ef o rs i n g l e - s e r v e rq u e u e 1 0 - 上海交通大学硕士学位论文 2 1 5 排队网络 事实上真正的网络环境下，很少仅仅讨论孤立的排队系统，经常有涉及多个 互联排队的问题需要分析。排队网络中有两个因素使分析复杂化：通信量的分开 和合并与排队系统的串连。如图2 4 所示 圈2 4 排队网络 f i g u r e2 4 q u e u i n gn e t w o r k 我们可以将排队网络分成三个基本类型：开环网络、闭环网络和混合网络。 在开环网络中，至少要有一个来自外部的输入弧和一个去往外部的输出弧。输入 弧来自某些无限的顾客源，输出弧去往外部的接收器。在闭环网络中没有外部弧， 网络中的顾客数目为常数，所有的顾客永远循环流动。如果多类排队网络对于某 些的顾客是闭环的而对其他类型的顾客是开环的，则称为混合网络。 开环排队网络最容易分析，最基本的开环排队网络是j a c k s o n 网络。 一个具有m 个节点( 标记为i - 1 ，2 ，m ) 的j a c k s o n 网络定义如下： 1 节点i 的服务速率是队列长度相关( q l d ) 的，当队列中有n 个顾客时 服务速率为h ( n ) 。每个节点具有相互独立的负指数分布的服务时间。 2 网络是开环的，从系统外到达系统中任何节点i 的输入是泊松到达过程， 速率为r i 0 。 3 顾客在节点上得到服务后，进行一次概率选择，它要么离开网络，要么 进入另外一个结点。 假设队列长度向量的随机变量为( n l ，n 。) ，可以定义网络在状态n 的 稳定状态概率为： n ( n ) = n ( n l ，n m ) = p ( n l 一- - - n l ，n m = n m ) 上海交通大学硕士学位论文 顾客在网络中的选道概率由选道概率矩阵q = ( q i j i i j = 1 ，m ) 定义， 其中q i j 是一个顾客离开节点i 下一步到达节点j 的常数概率( 与过去的历史无 关) 。如果选道概率是状态相关的则为自适应选道，但是这里假定其为常数。顾 客离开节点i 去往网络外部的概率为： m q i o = 1 一乏g o ( 2 1 2 ) 因为网络是开环的，所以至少有一个节点i 满足q i 0 o ，并且在选道概率矩阵 q 中，至少有一行的概率和小于l 。假想有一个节点0 作为顾客的外部源和宿， 所有到达开环网络的外部顾客形成一个速率为r 的泊松流，并且每个外部顾客到 m 达节点i - 1 ，2 ，m 的概率为q o i o ，速率为r t = q o i r a 因此有r = z r ，a 在 f = 1 单位时间，到达节点f 的平均顾客数目是平均外部到达( 即r i ) 与从所有节点j 到达的平均顾客数( 即九j q i j ) 之和，因此节点i = l ，2 ，m 的通信量方程为： m 九i 2 r i - _ l t - a j q 口 ( 2 1 3 ) ，= l 在稳定状态下，网络的总体流量方程为： m r = a f q f o( 2 1 4 ) 2 1 6 排队网络的j a c k s o n 定理 j a c k s o n 定理给出了排队网络的稳定状态联合概率分布，对于一个j a c k s o n 网络，稳定状态下到达结点i 的速率为 ；，则： 1 在任何节点的顾客数量与其他任何节点的顾客数量无关； 2 节点i 所表现的随机行为就好像它接受的速率为 i 的泊松到达。 事实上，稳定状态下网络的所有随机特性都蕴涵在队列长度的联合概率分布 n ( n ) 之中，其中状态n = ( n l ，n 2 ，n m ) ，n i 是节点i 的队列长度。可以证 明j a c k s o n 网络的稳定状态概率分布为： 盯 q ( n l ，n 2 r n m ) = 兀r 。( n f ) ( 2 1 5 ) 上海交通大学硕士学位论文 其中： 姒神训) i # 1 兀) ( 2 1 6 ) 在j a c k s o n 网络中，每一个节点都可以独立的使用m m 1 或m 心d ，n 模型来 进行分析。上式中叩f ( m ) 的值就是通过对每个节点的m m 1 模型进行分析而得到的 而叩f ( 0 ) 由通过，7 f ( 玎f ) ( i 2 i ，2 ，m ) 的值进行正则化而得到的。 这样可以直接利用j a c k s o n 定理并且使用l i t t l e 公式推导出许多性能测量的 平均值。对于仅由单服务员固定速率节点组成的网络( 固定速率为l ai ) ，节点i 的利用率为p f = p q 1 ) = u i 。 1 平均队列长度 对于节点i 的独立的m m 1 队列，其到达速率为 i ，其平均队列长度l = e ( n 。) 为： q _ l i 2 尚 ( 2 1 7 ) 所以网络的总平均顾客数量为： q = e ( n l q - n 2 + + n 。) = e ( n 1 ) + e ( n 2 ) + + e ( n 。) = 缸= 薹鬲p i m ， 2 酗2 蚤鬲 旺工8 2 平均等待时间 使用l i a l e 公式可求在网络中的平均等待时间：t q = q r ，其中r = y f 是全 部的到达速率。 在每一个顾客访问期间，花费在节点i 的平均时间( 包括等级服务和接收服 务) 为： t q i ：- 旦：j 一( 2 1 9 ) 2 , i 一z i ( 1 - p i ) z 。y 上海交通大学硕士学位论文 在每一个顾客访问期间，花费在节点i 的平均等待时间为 丁w r 2 i w i 。丽p 丽i ( 2 1 1 0 )h 一万一葡f 万1 其中w i = q i p f 是队列中的顾客数目但不包括正在接收服务的顾客( 即等于队列系 统中的平均顾客数q i 减去接收服务的平均顾客数p ，) 。 令t i o 为个顾客到达节点i 和他离开网络期间的平均时间间隔( 即平均保 持驻留时间) 。使用与推导通信量方程相似的变量： 吖 t i ，0 ：t q i - g 口跏( 2 1 11 ) ；1 由于( i - q ) 是非奇异的，所以t i 0 有唯一解。 2 2 自相似性 2 2 1 自相似性简介 自相似性是分形的最主要特征，分形就是一种具有自相似特性的现象、图象 或者物理过程。事实上分形这一概念在自然界无处不在，可直到2 0 世纪7 0 年代 才由b b m a n d e l b r o t 正式提出，分形( f r a c t a l ) 一词，是b b m a n d e l b r o t 创造出 来的，其原意具有不规则、支离破碎等含义。 弭j ； 争 也，南弗。 一一，1 j猎w 一 0 图25两种分形图形 f i g u r e2 5t w o f r a c t a lp i c t u r e s 自相似现象是指把某一图形或序列在“尺寸”上放大或缩小几倍后，所得到 的结果与原图形或序列看起来是相同的。这里的“尺寸”不仅是指几何上的尺寸， 还可以是空间维数、时间等等。在本论文中最为关心的是在时间尺度上表现出自 相似性的时间序列和随机过程。如图2 6 所示，注意到左图自相似随机过程在不 同时间尺度上的波形彼此是统计特征上类似的，但并不是精确重复的。 上海交通大学硕士学位论文 岫s c h ：5 岫r p 协墨舶h 脚5 e 峭m m i 叫p ：， 图2 6 自相似与非自相似随机过程的比较 f i g u r e2 6c o m p a r i s o n o f s e l f - s i m i l a ra n dn o n - s e l f - s i m i l a rs t o c h a s t i cp r o c e s s e s 2 2 2 自相似过程定义 2 2 2 1 连续时间定义 如果对于任意实数a 0 ，随机过程a - h x ( a t ) 与x ( o 有相同的统计特征，即符合以 下三个条件： 1 e 【) ( ( t ) 】= 2 v a r 【) ( ( t ) 】 e i x ( a t ) 】 a h v a r i x ( a t ) a 2 h 方差 3 r x ( t ，s ) = 旦嘿型 自相关 a ( 所谓自相关函数r ( h ，t 2 ) 是随机变量x ( t 1 ) 和x ( t 2 ) 的联合矩，自相关是对 随机过程的两个时间关系的度量：r ( t l ，t z ) = e 【) ( ( t 1 ) x ( t 9 ) 则可称随机过程x ( t ) 是以参数h ( o 5 h 1 ) 自相似的，参数h 称为h u r s t 参 数或自相似参数，它是自相似程度的一个主要度量，或者说它是一种随机过程的 持续性的度量，它是一个随机过程的长范围相关程度的一种度量。h u r s t 参数的 定义是通过将重整化范围r s 与n 的关系画到对数图上，应该得到一条直线， 其斜率为h ，h 的取值范围为【o 5 ，1 】，其中重整化范围r s 为： 上海交通大学硕士学位论文 r 一= s h = 0 5 表示没有自相关性，h 越接近l ，持续性或长范围相关的程度越大。 关于这一点可以考察以下一个自相关随机过程：分数布朗运动f b m ( f r a c t i o n b r o w n i a nm o t i o n ) 2 2 2 2 分数布朗运动f b m 【3 】 分数布朗运动是从布朗运动得来的，所谓布朗运动，一个简单的解释是假设 x 是个均值为0 方差为1 的正态分布随机变量，则布朗运动b ( 0 可定义为： b ( 0 = x 正 v a r b ( t ) 】= t 个f b m 过程b h ( t ) 可以定义如下： b h ( t ) = x t h ( 伊0 ：0 5 h 0 5 ，如果过去的某段时间 有一个正增量，那么平均来说将来就也会有一个正增量，因此过去时间的一个增 加或减少的趋势意味着将来也会出现增加或减少的趋势，这种相关性对于任意的 t 都存在，而且相关程度随h 值增大而增大。这也正是下一章提出的网络流量自 相似性预测的一个理论基础。 2 22 3 离散时间定义 离散时间随机过程x ( t ) 定义为 x 。，t = 0 ，l ，2 ，) 。对于一个平稳时间序列x ， 上海交通大学硕士学位论文 定义m 重聚集时间序列x 细) - fx k ( m ) ，k _ 0 ，i ，2 ， ，它可以表示为： ：去 篁x ， ”i = o n 一( m 一1 ) 例如，x ( 3 定义为 x k ( 3 ) ：x 3 k - 2 + x - 3 k - 1 一+ x 3 k 可以认为x ( 1 是这个时间序列的最高放大率或最高分辨率，而过程x ( 3 是相同 过程在分辨率上缩减3 倍的结果。如果经过压缩后的过程的统计特征仍然保持不 变，那么该过程就是一个自相似过程。 事实上也可以将序列x k ( 呻中的各个点看成是过程x 的一个时间平均。对于 普通的遍历过程而言，时间平均应该等于样本空间平均，并且时间平均的方差应 该在m 变大时相当迅速的趋向于零。但对于自相似过程，方差确实趋向于零但 要比平稳遍历过程慢的多。 准确的说，如果对于所有的m = l 2 ，有 方差【x m ) 】：掣 m 自相关 r x ( m ( k ) = r x 则称具有参数p ( 0 1 ) 的过程x 是精确自相似的，参数p 与前面定义的 h u r s t 参数有关，即h = 1 - - ( p 2 ) 。对于平稳遍历过程，p = l 并且时间平均 的方差以速率1 m 衰减到零，对于自相似过程，则衰减的更慢。 而如果对于所有足够大的k 方差【神= 哥 m 自相关r 。( ”( k ) 一r x ( k )当m 一一时 则称该过程x 是相对较弱自相似的。 因此，使用这种自相似性定义则多重聚集过程的自相关就和原过程的自相关 具有相同的形式，这意味着变化的程度或突发性在不同时间尺度上是相同的。 - 二兰塑j ! ! 哒兰堡圭堂堡垦塞 2 2 2 4 分数高斯噪声f g n 所谓分数高斯噪声f g n 是由于分数布朗运动f b m 的自相关函数为 凡。= j 1 ( t 2 n + s 2 h - - h 2 h ) 显然f b m 是一个非平稳的随机过程，因而给实际应用带来不便，但是f b m 的增量过程是个平稳的随机过程，也就是所谓分数高斯噪声f g n ，记为g h 定义如下： 一个平稳高斯过程x 2 ( x k ：k = 0 ，i ，2 3 ) ，均值为u = e x k 】，方差为 o 2 - - - - e ( x k u ) 2 】， g h ( k ) = b n ( k - f1 ) - - b h ( k ) r g ，( 七) = i 1 ( i 世+ 1 f 2 一f 足f 2 + f k 一1 1 2 h ) 按照i l l 重聚集时间序列g h ( ”) 的定义： g去量。gi鳗竺掣坦趔，可以发现掣的自相关i ”= k n - - ( m 1 1册 一 函数与g h 有着相同的形式而且当k 足够大时： r g ，( j ) “h ( 2 h - - 1 ) j 目2 ( h - 2 ) ( k 一一时，o h 1 ) 因此，按照精确自相似的条件可知，分数高斯噪声f o n 是精确自相似的。 2 2 2 5 长范围相美 自相似过程最重要的特性之一就是长范围相关( l 。n g m g ed e p e n d e n c e ) ，许 多过程的自协方差c ( t ) 随t 的增加迅速衰减，如短范围相关( s h o r t m g e d e p e n d e n c e ) 过程满足： c o o - 口l “ 当f k | 一o 。时，0 a l 显然由荟z 3 f 1 ji x i 1 ，可知女c ( t ) 是有限的。 t ：0 l 一工o e 而长范围相关则具有如下的自协方差： c ( k ) f l ( | 一 当| k | 一一时，o k ；口 。) 其均值为e ) ( 】= 三k ( a 1 ) 参数k 确定这一随机变量可以取的最小值，参数a 确定这随机变量的均值 和方差，图2 7 对p a r c t o 和指数密度函数在对数一线性坐标尺度上进行了比较， p a r e t o 分布的尾部比指数分布的尾部衰减的慢的多，这也就是“重尾”的含义所 在。 重尾分布在流量自相似性研究中的意义在于： 1 许多实际测量和分析都表明描述网络信源的某些随机变量服从重尾分 布，如呼叫持续时间，w e b 文件的传输时间，p a c k e t t r a i n 模型中o n o f f 周期的长度，报文到达时间等。 2 t a q q u 等人从理论上证明了无穷多个独立的具有重尾分布f 即 p x x 卜x ，1 卢 2 ) 的更新回报过程( r e n e w a l r e w a r dp r o c e s s ) 的叠加 ( 乘以适当的收敛因子) 弱收敛于分数布朗运动b h ( t ) 并且h = ( 3 - a ) 2 4 】 上海交通大学硕士学位论文 3 w i l l i n g e r 等人在文献 5 】中指出多个p a r e t o 分布的o n o f f 信源的叠加产 生了自相似性流量，它的h u r s t 参数h = ( 3 - a ) 2 ，对于l a 2 ，有 0 5 h 1 。 f ( z ) 图2 7p a r e t o 分布与指数分布 f i g u r e2 7p a r e t oa n de x p o n e n t i a lp r o b a b i l i t yd e n s i t yf u n c t i o n s 2 2 3 自相似性对传统以太网建模的影响 尽管排队论模型和排队分析对于网络设计和系统分析人员进行容量规划和 性能预测很有帮助，然而，在许多实际场合人们发现排队分析的预测结果与实际 观察到的性能差异很大。由于排队论模型假设基础是网络流量符合泊松分布，然 而在对许多实际网络环境进行统计之后，发现流量分布是自相似( s e l f - s i m i l a r ) 而 不是泊松的。 1 9 9 4 年，l e l a n d ，w ，t a q q u ，m ，w i l l i n g e r , w ，a n dw i l s o n ，d 发表的论文“o nt h e s e l f - s i m i l a rn a t u r eo fe t h e m e tt r a f f i c ” 6 】在自相似数据通信量研究方面作出了 开创性的贡献。这篇论文研究了从1 9 8 9 到1 9 9 2 四年间以2 0 us 的高分辨率对以 太网通信量进行测量的结果，总共包括1 0 0 多万个分组，数据是从b e l l c o r e 公司 的各个以太局域网上收集的。通过大量的数据和统计分析，这篇论文改变了一直 以来的使用通信量泊松分布假设进行直接的排队分析就足以描述所有网络通信 量的论断，作者们基于多种统计检验估计出以太网通信量是自相似的并且其 ” m ” ” 炉 上海交通大学硕士学位论文 h u r s t 参数h = 0 9 。从此自相似流量方面的研究开始大量涌现： 文献 7 】统计了包含有五十多万条w e b 网页的通信量，这篇论文的研究方法 类似于上文的方法，结果显示这些w e b 网页浏览所产生的流量是自相似的，而 且如果将每个w e b 网页浏览器描述为一个o n o f f 信源发现流量数据刚好符合 一个p a r e t o 分布，在多个测量结果中，这些p a r e t o 分布的参数a 从1 1 6 到1 5 。 文献 8 考察了数字电信网络上产生的控制信令即7 号信令s s 7 的通信量， 这项研究搜集了大约1 7 亿条s s 7 信令报文，研究也显示传统的基于泊松分布的 模型不足以描述s s 7 的通信量，而自相似流量模型则是一种更好的选择。统计显 示，单个控制信令信源符合p a r e t o 重尾分布。 文献 9 】则关注于广域t c p 通信量以及基于t c p 的f t p 和t e l n e t 的通信 量研究。结论是： 1 通常使用的泊松模型在宽时间尺度严重低估了t c p 流量的突发程度。 2 交互式t e l n e t 连接的流量可以用泊松模型很好的描述。 3 对于f t p 流量而言，其数据连接的流量与泊松模型有明显的差异，突 发性比模型描述要大的多。而且数据连接的报文长度符合p a r e t o 分布。 此外还有一些研究显示如