（计算机应用技术专业论文）自相似特性及atm网络流量控制研究.pdf

华中科技大学硕士学位论文 摘要 近几年的研究表明，无论是在局域网或是广域网，用自相似过程对网络流量进行建 模可以更糟确地反映网络流量的变化。自相似流量给网络带来了更大的突发性，它严 重影响到网络的传输性能和流量控制策略，因此在进行a t m 网络管理和流量控制时必 须考虑到它所带来的影响。自相似业务源的监测、数学建模、参数估计和排队分析已 成为a t m 网络流量控制和业务量管理中不可缺少的要素。 传统的流量模型的共同特点是只存在短期相关性，而a t m 网络上的流量具有突发 性和长相关性，用传统模型分析该网络存在偏差，必须采用具有自相似特性的模型。 自相似流量模型的排队性能分析有很大的困难，可利用的结果还比较少，因此大 部分的性能分析结果都是基于仿真实验基础之上得到的。利用流量模型，生成数据序 列，然后作为排队系统或拥塞控制机制的输入，进行性能分析。因此，流量模型的序 列生成是非常重要的。 自相似流量序列生成算法有快速傅立叶变换法( f f t ) 、随机中点鼹换法( r m d ) 和基于c h o le s k y 分解理论的h o s k in g 方法。基于随机中点置换法r m d 算法，提出一 种新的序列生成方法，减小了算法的空间复杂度，并使之能够在线生成序列，用c 语 言实现并分析了它的精确性和效率。 a t m ( 异步传输模式) 网络中a b r ( 可用比特率) 业务采用基于速率的流量控制机 制。e f c i ( 二进制算法) 和e r i c a ( 显式速率算法) 流量控制机制在自相似v b r 业务背 景下的性能受到很大的影响，通过仿真，对这两种机制的性能进行了比较。 关键词：流量分析，自相似，长相关性，序列生成 华中科技大学硕士学位论文 a b s t r a c t r e c e n tr e s e a r c hh a ss h o w nm a tm en e t w o r kf i o wm o d e l e dw i t hs e j t 、- s i m i la 1 p r o c e s s b o t hi nl a na n dw a n c a nr e n e c ta c c u r a t e l yi t sc h a n g e s t h es e l f _ s i m i l a rt r a 街cb r i n g st h e n e t w o r km o r eb u r s t y i ti n n u e n c e san e t w o r kt od e l i v e rf u n c t i o na 1 1 dn o wc o n n d ls t r a t e g y s e r o u s l y ，t h e r e f o r ew h i l ec a r r y i n go nt h ea t mn e l w o r km a n a g e m e n ta n dn o wc o n t r o l h a v et oi nc o n s i d e r a t i o no fi t si n n u e n c e m o n i t o r ，m a 廿l e m a t i c sm o d e l ，p a r 啪e t e re s t i m a t e a 1 1 d q u e u i n ga i l a l y s i so fs e l f - s i m i l a rs e r v i c es o u r c ea r ci n d i s p e n s a b l e f a c t o ro fn o w m a n a g e m e m i na t m t r a d i t i o n a lt a m cm o d e l i se x i s t ss h o r tr a j l g ed e p e n d e n c e ，b u tn o wi na t mi se x i s t s l 0 n gr a t l g ed e p e n d e n c ea n da b n 】p t a n a l y z i n gt h a tn e t w o r ke x i s t e n c e d e v i a t i o nw j t ht h e t m d i t i o n a lm o d e l ，h a v et oa d o p tt os e l f - s i m i l a rm o d e l q u e u i n ga n a l y s i so f s e l f s i m i l a rm o d e l i sv e r yd i 岱c u l t ，a v a i l a b l er e s u l ti ss t i l ll e s s ，s o g r e a tp a r to fr e s u l to fp e r f b r n l a n c ea n a l y s i sa r eb a s e do ns i m u l a t i o n m a k eu s eo fn o w m o d e l ，m a k ed a t as e q u e n c e t h e nr e g a t di ta si m p o r to fq u e u i n gs y s t e mo rc o n g e s t i o n c o n t m lm e c h a n i s m ，c a r 】呵o np e r f b n l l a i l c ea n a l y s i s t h e r e f o r e ，t h e s e l f - s j m i l a rt r a m c g e n e r a t i o ni sv e r yi m p o r t a n t s e l f s i m i l a rt r a m c 嚣n e r a t i o nm e t h o d si n c u d ef f t ，r m da n dh o s k i n g p r o p o s ea n e wm e 1 0 dt o g e n e r a t es e l f - s i m i l a rt r a m cb a s e do nr m dm e t h o d ，d e c r c a s es p a c e c o m p l e x i t y ，a n 8 l y z ei t sa c c l l r a t e l ya 1 1 dp m m p t l y a t mf o r 衄1a d o p t e dt h er a t e - b a s e da b r ( a v a i l a b l eb i tr a t e ) n o wc o n t r o lm e c h a n i s m t h ep e r f o n n a i l c eo ft h ee f c ia n de r i c ao v e rs e l f - s i m i l a rt r a 瓶cb a c k g r o l l i l dj sa l s o c o m p a r e db ys i m u l a t i o n k e y w o r d s ：t r a m ca n a l y s i s ，s e l f s i m i l 码l o n gr a n g ed e p e n d e n c e ，1 1 r a m cg e n e r a t i o n i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：朝彰咕 1 日期：卯d6 年聋月巧同 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密囱。 学位论文作者签名：扒影肇 日期：硼口6 年印月西日 指导教师签名： 哳阂弓多 闷期：7 ，p 拇 ，月7 日 华中科技大学硕士学位论文 1 1 课墨研究背景 1 绪论 众所周知，当今的通信网络正在飞速的发展。目前的计算机网络已经渐渐融合了 诸如传统的计算机网络、无线网络、有线电视网络( c a t v ) 、综合数字网( i d n ) 、综 合业务数字网( i s d n ) 以及宽带综合业务数字网( b i s d n ) 等等多种网络形态，并朝 着全球化、宽带化、个人化、综合化和智能化的方向发展。基于计算机通信网络的各 种各样的应用譬如电子邮件、文件共享、视频会议、视频点播等也越来越走进入们的 生活，通信网络的发展使人们能够以更为自然和直接的方法来获取信息，进行沟通。 八十年代中后期开始，国际电信联盟( 1 t u t ) 开始制定有关旷l s d n 的规范。在 建议i 1 2 l 中规定了异步传输模式( a t m ) 是解决实施b i s d n 目标的传递方式。到1 9 9 7 年底，基于a t m 技术的b i s d n 建议已基本出齐，共有近6 0 份建议书，其中涉及到 b i s l ) n 的网络总体、网络能力、网络性能、网络互通、网络资源管理、业务、信令、 用户网络接口( u n i ) ，网络节点接口( n n t ) 、o a m 原则、a t m 适配等各个方面。至今， 国际电联已为r i s d n 及a t m 研究制定了大体完善的建议i i “。 b l s d n 的目标就是要实现现有以及未来可能出现的各种电信业务，包括从几十k 的话音业务到上百兆的图像和高速数据业务。为了实现这一目标，以a t m 为基础的 b i s d n 具有与传统的电话网络和分组网络显著不同的特点【4 j 。首先，为了提高网络的 效率和资源利用率，降低运行和维护管理的复杂度，b i s d n 将网络建设和业务种类相 分离，使网络实现与业务无关；其次，由于各种业务的信息传输速率变化很大，b i s d n 利用了统计复用和a t m 虚连接的概念为各种业务灵活分配带宽及各种资源，同时分别 保证各自业务的服务质量【5 l ；此外，a t m 的信元是固定长度的短分组，实现了信息的 高速交换，网络功能也得到了简化嘲。 b t s d n 的基本构成包括宽带传输交换网络、接入网络( 包括互连单元) 和网络 管理系统。传输网络由光纤网络构成，传送方式采用同步数字系列( s d h ) 或波分复 用( w d m ) 技术；交换网络主要由a 1 m 骨干交换机构成；接入网络以a 倒接入设备为 1 华中科技大学硕士学位论文 基础，采用多重接入方式如非对称数字用户环路( a d s l ) 、光纤分配网络以及光纤和 同轴电缆混合( h f c ) 接入用户。 9 0 年代初f d d i 问世以后，在局域网、校园网、企业网方面没有速度超过1 0 0 m b p s 的网络。a t m 在这个领域找到了发展空间，在9 0 年代中这一段时间得到很大发展，并 进入了实用化阶段，商用化的a t m 产品大量出现，很多国家建设了a t m 骨干网络，并 提供多种高速实时业务。a ，f m 的应用也进入到局域网、无线网络和卫星网络等领域 4 j 。 1 9 9 3 年，b e l c o r e 的科学家对局域网经过近三年的观测和分析后，发现以太网的 业务流量与已有的数学模型存在非常大的偏差，在不同的时间尺度上表现出相似的特 性，具有这些特性的业务称为自相似业务。如图1 1 所示，b e l l c o r e 的以太网流量在 不同时间尺度上到达的数据包统计量具有很大的相似性。他们的研究成果表明：以太 网业务具有长期相关性，而传统业务是短期相关的。与此同时，b e r k e 】e y 的研究人员 在广域网中r t p t c p 分组的到达间隔及分组长度均表现出有别于传统的泊松类随机过 程的特性。所有这些研究表明，通信网中的各种随机过程并不能用泊松类的随机过程 来描述，很多随机过程在本质上表现了自相似的特性【l 。 芭 寻 垂 妄 毫 芷 t j f l eu n i t su n i t = 1s e c o n d c ) 兰1山j_童皇端正 华中科技大学硕士学位论文 1 0 0 芒 o 8 0 量6 0 琶4 0 上 葛 2 0 o 琶 佰 3 墨 1 0 薹 5 星 0 o1 0 02 0 03 0 04 0 05 0 06 0 07 0 08 0 09 0 01 0 0 0 t i m eu n i t 3u n i t = 01s e c o n df d ) 01 0 0 2 0 0 3 0 04 0 05 0 06 0 07 0 08 0 0 9 0 0 1 0 0 0 t 1 n l eu n i t s u n i t = o 0 1s e c o n d ( e 1 图1 1 b e l lc o r e 局域网流量统计图 在过去的几年里，大量通信网络的研究机构都已注意到，各种具有突发特性的业 务源都在一定的时间尺度下呈现出自相似特征，a t m 网络中传输的的数据业务、视频 业务等也具有自相似性，它严重影响到网络的传输性能和流量控制策略。对自相似业 务源的监测、数学建模、参数估计和排队分析已成为a t m 网络流量控制和业务量管理 中不可缺少的要素】。 用短期相关模型分析a t m 网络交换机性能、连接接纳控制和拥塞控制等得出的结 论往往过于乐观，根据这些结论设计的a t m 网络无法满足用户的q o s 要求。例如，用 传统的m a r k 。v 模型分析 t m 交换机溢出概率，得到的结论是：随着缓存区容量的增 长，a t m 交换机溢出概率呈负指数的下降规律，因此增加缓存容量可以有效地改善信 元丢失率。然而在实际网络测试中发现：交换机的溢出概率并不随缓存长度增加呈指 数规律下降，其下降速度要相对慢得多，增加缓存容量并不能有效降低丢失率1 1 2 】。因 此自相似业务及其对a t m 网络性能影响的研究是近年来学术界关注、研究和争论的一 个热点。 华中科技大学硕士学位论文 1 2a 删网络的业务源类型及特性 业务源通常被分为三大类；数据、语音和图像。 l 、数据源 数据源主要来自一些面向计算机的服务，如x 2 5 、文件传输、终端仿真等。该业 务源的特点是对信元丢失率敏感，但对时延要求并不严格。最简单的数据源类型是贝 努利模型，即在离散时间轴上，每一时隙产生信元的概率为p ，与过去的概率无关。 这样信元的产生时间就形成一个更新过程，两个相继信元产生的间隔时间服从指数分 布。当我们改变间隔时间的分布，就得到不同的更新过程。例如间隔时间服从指数分 布，则更新过程为泊松过程。如果将单个信元产生扩展为成批信元产生，则简单泊松 过程扩展为复合泊松过程。批信元的长度服从某种通用分布，通常假定为几何分布( 该 种情况下，各表达式容易求解) 。 2 、语音源 随着电话的广泛普及，语音业务应用频繁。语音业务的q o s 要求不同于数据业务： 时延是至关重要的参数，却能容忍一定的信元丢失率。最简单的模型是c b r ( c o n s l a n t 一 j tr a t e ) ，即产生信元的速率固定。众所周知，每一次通话总有一部分时间处于安 静状态( 大于6 0 6 5 ) 。说话状态下的持续时间通常服从指数分布，安静态持续时间 的概率密度函数( p d f ) 近似为两项平衡几何分布( t w op r o p e r l yb a 】a n c ed g c o m e t r i c ) 。 语音源的特性随编码方案的不同而不同。在宽带网上传送语音业务可有几种方 式：6 4 k b t s 的p c m 格式，a d p c m 的语音压缩模式( 利用压缩编码，如数字间插和信元 丢失) ，分组格式( 用g 7 6 4 分组语音协议) 。同样，汇聚语音的突发性也依赖于编 码方案。例如，一个3 2 k b t s a d p c m 编码的p s i 链路上，汇聚流表现强烈的突发性，这 是由于汇聚业务的正相关性造成的。 3 、图像流 图像将成为i s d n 的主要业务成分。图像业务比语音业务复杂得多，在会议电视、 可视电话和广播电视等应用网络中需要很大的带宽，因此人们对于图像压缩编码有极 4 华中科技大学硕士学位论文 大的兴趣。图像业务流的统计特性受多重因素影响，如：所传送图片的特性、图片间 的相关性、所提供业务的特性和图像的编码方梨 等。图像编码方案有需帧缓存和不 需帧缓存两种类型f 1 ”。前者是对相继图片的差异进行编码，后者对图片单独编码。 对图像建模的重要环节是对其自相关函数的分析。自相关函数也受到上述诸因素 的影响，因此依据侧重点不同，图像建模会有多种方案。例如m a g l a r i s ( 引建立的可 变比特流模型是根据需帧缓存的图像编码方案。他的试验结果【1 4 壤明对于一幅没有突 然变化的图片来说，其比特率的概率密度函数呈现“钟”的形状，自相关函数只影响 连续帧的数量，对其它特性影响不大。而在非帧缓存的情况下，相应的自相关函数含 有周期性的成分，它会重复地出现峰值。这是由于连续图片往往比较相似，具有强烈 地自相关性。 对于用户来说，所关心的是业务的内容，比如是话音、文本还是图像以及它们的 最终质量，用户往往要做出主观上的评价：而从网络建设者或运营者的角度考虑，除 了要为用户提供可以接受的业务质量之外，还必须同时考虑网络的资源利用率。他们 需要将用户的主观评价转化为具体的和量化的业务参数，并采用一定的业务控制方式 来加以实现。因此，他们更关心的是业务的承载方式，传输方式和业务量特性等。 其中业务质量要求( o o s ) 由用户提出。在a t m 网络中考察业务质量的指标一般分 为两类：一类是包括与面向连接网络相关的呼叫控制参数，其中包括连接建立接受概 率、呼叫建立延迟和呼叫释放延迟；另一类是为分组网络定义的一套信息传输参数， 其中包括比特误码率、信元丢失率、端到端传输延迟、信元延迟抖动等。而业务量特 性是指业务在信息传输过程中业务量的变化，它一般可以通过统计的方法来描述，常 用的业务量参数有平均呼叫次数、平均呼叫保持时间、峰值速率、平均速率、速率方 差、突发度、平均突发时间等。此外，业务量的边际分布函数和自相关函数也常用来 讨论业务量的随机变化。业务量特性对网络保证业务质量有直接的影响，一般来说， 用户要向网络声明这些业务量特性的信息，网络根据这些信息以及用户提出的业务质 量要求进行网络的业务量控制，满足用户要求同时高效利用网络资源。 对于不同的业务，业务量特性相差很大。在a t m 网络中，视频业务和高速数据业 务已逐渐成为主导业务【i ”。这些业务的业务量具有一些非常重要的统计特性： 华中科技大学硕士学位论文 ( 1 ) 平均信息速率高，高速数据传输一般为几兆到几十兆比特每秒，而视频业 务如压缩过的高清晰度电视达到几十兆比特每秒； ( 2 ) 业务量突发性强，有场景切换的可变速率视频业务量的峰值速率与平均速 率之比一般都不大于十，而高速数据如局域网仿真的突发度可达上百甚至在这之上； ( 3 ) 连接保持时间变化大，比如一些新业务如网页浏览连接持续时间变化范围 非常大，短则几秒，长则达到几个小时以上； ( 4 ) 业务量具有自相似特性，或者称长期相关性。 业务量在较大的时间尺度后仍然有很强的相关性，其自相似性还表现在业务量在 很大的时间尺度上具有突发性的特性。业务量的这些特性对于业务量建模和网络的拥 塞控制有非常重大的影响，其中业务量的长期相关性意味着宽带网络中的业务量更加 趋于复杂而难以捉摸和控制，这对网络的建设者和运营者提出了更高的要求。 不同业务的业务质量要求差别很大。一般来说，实时业务如话音、图像对于时问 抖动非常敏感，而对误码率和绝对时延的要求相对较松；非实时业务，如一些数据业 务没有实时性要求但对误码率有严格要求。实际上，业务质量要求是在人们主观感受 和业务量的统计特性的研究基础之上提出的，业务量特性同样会对业务质量要求产生 一定的影响。同时，业务的质量要求对于业务量的控制也有着直接的影响。 总而言之，计算机网络的带宽和业务种类都在飞速的增长，这种增长无可避免的 带来了许多问题，它所引发的流量的增长更是引起前所未有的关注。跟随这一变化， 流量建模、网络拥塞控制和排队分析成为研究的热点，它们的共同目标是解决各种流 量汇聚带来的各种问题。 1 3 传统的流量模型和流量生成方法 流量建模是进行宽带网络设计和性能评估的一个核心问题。由于宽带网络需要具 有提供现有以及将来可能出现的各种业务的能力，网络的设计者就必须要考虑到这些 业务的特征及其对网络的影响。网络的设计通过建立网络模型和业务量模型对网络性 能和业务质量进行预测、分析、评估和测试。就a t m 网络而言，业务的质量是由业务 量控制机制来监测和保证的，而网络流量建模则是网络流量控制机制研究的基础之 华中科技大学硕士学位论文 b 进行性能分析的方法包括：解析分析、计算机仿真和实验。解析分析和计算机仿 真需要采用精确的网络流量模型，这些网络流量模型应该可以捕捉和刻画出网络流量 的统计特征。解析分析通过理论上的推导可以得出解析的结果。但解析分析往往需要 做出很多假设，这就限制了其对实际系统的描述。计算机仿真可以避免进行艰涩的理 论推导而得出性能分析的结果，这一方法在实际中得到广泛的应用，有很多重要的结 论都是通过这一方法得到的。通信系统中常用的计算机仿真方法有蒙特卡罗方法，针 对于稀有事件的仿真还有重要采样等方法。 网络流量建模一般包含以下几条准则。 ( 1 ) 真实性。网络流量模型产生的网络流量应接近真实网络流量源。网络流量 模型应该刻画出真实网络流量源影响性能的主要统计特征。网络流量模型应该具有明 确的物理意义。 ( 2 ) 通用性。网络流量建模应考虑网络流量模型可以对多种不同的业务均适用， 不同的业务只是在参数的数值上有所差别。 ( 3 ) 简单性。网络流量模型应采用尽量少的参数，而且参数应该具有直观的意 义。 ( 4 ) 可适配性。网络流量模型应该容易与真实网络流拟合，网络流量参数应该 可以从真实网络流量中方便的得到。 ( 5 ) 理论可分析性和精确性。在不失精确性的前提下，基于网络流量模型的可 分析性对网络流量性能进彳亍解析分析。 ( 6 ) 易于实现。网络流量模型应该是通过计算机仿真或是基于硬件的网络流量 生成器可以方便的实现。 如果一个网络流量模型能够同时具有上述这些特性，那它将是一个完美的模型。 遗憾的是，这六点是很难同时做到的。一般来说，网络流量模型的参数越多，模型就 越精确，越接近真实的网络流量源，但同时，模型也越繁琐和复杂，理论分析和计算 机仿真也会越困难。在实际的网络流量建模中往往要对网络流量模型的精确性和复杂 度加以折衷。 华中科技大学硕士学位论文 传统的a t m 网络流量模型包含两大类，一类是马尔可夫类模型，另一类是回归模 型。前者包括开关( o n o f f ) 模型、间断泊松过程( t p p ) 、马尔可夫调制泊松过程( m m p p ) 和马尔可夫调制流体流过程( m m f p ) 等。后者包括自回归模型( a r ) 、离散自回归( d a r ) 模型、自回归滑动平均( a r m a ) 模型、自回归综合滑动平均模型( a r t m a ) 和t e s 模 型等。马尔可夫类模型适合对语音或数据及其汇聚流量进行建模，也可以对图像源进 行建模。自回归模型适合于对视频流( 如m p e g ) 进行建模。下面对几个典型的模型作 一个简要的介绍： 1 、马尔可夫模型 对于一个有限状态空间s = 置，s 2 ，s 。) 。令x = x 。) = i ，墨，) ，以为时 间n 时的状态，如果下一状态瓦+ l = j ，的概率只与当前状态有关，则 也 构成一个 马尔可夫链。马尔可夫特性决定了状态的逗留时间服从几何分布或指数分布。 o n o l i f 模型时最常用的语音模型。在o n 状态下产生等间隔的数据包，在o f f 状 态下不产生数据量。o n 状态和o f f 状态的逗留时间为指数分布。i p p 模型类似于o n 0 f f 模型，不同的是在活跃状态下产生数据包的过程符合泊松分布。 马尔可夫调制泊松过程是双随机泊松过程。底层是m 状态的马尔可夫链，在状态 k 的逗留时间服从均值为的泊松分布，而在状态下的数据包的到达服从均值为五 的泊松分布。i p p 模型是其特例。 马尔可夫调制流体流过程与马尔可夫调制泊松过程类似，不同的是前者忽略了数 据包到达的离散特性，而看作是固定速率的连续流体，其单位是比特每秒。流体流模 型的最大优点是容易进行理论推导。 马尔可夫类模型有一个非常重要的特征是其自相关函数呈指数型。这是由于其所 固有的马尔可夫特性决定的。因此该类模型不适合对相关性很强的网络流量源进行建 模。 2 、回归类模型 p 阶自回归模型爿月( p ) 是由序列中待求数据的前p 个值和一个滑动平均的白噪声 来确定，其表达式为： 华中科技大学硕士学位论文 关函数不呈指数型而是双曲线型( 即慢衰减型) 。因此，自相似模型也叫长期相关模 型。 自相似性质的重要性并不仅仅在于它是许多网络中流量的一个普遍特性，更重要 的是它对网络设计和性能分析有着重要的影响。许多有关网络设计、控制机制研究和 性能分析都是基于传统的流量模型，考虑到自相似特性，这些流量模型用以模拟真实 网络的有效性值得怀疑，尤其是涉及到信元丢失率和拥塞控制部分。 围绕业务量的自相似特性对网络的设计以及性能的影响，国际上展开了大量的研 究，这方面的文章层出不穷，在l n f o c o m 、l c c 和g 1 0 b e c o m 等重要国际会议上也都作 为单独一个专题提出。有关自相似业务量的研究在自相似流量建模、序列生成等方面 开展了一些研究。 f r r a m i 】i 等人采用确定非线性混沌映射方法产生自相似事件流，并应用该方法 进行性能分析。a d d i e 等人采用了由两个一阶自回归过程来拟合自相似流量的方法。 r y u 从分形点过程的概念出发提出了四个自相似模型。w 儿1 i n g e r 等人提出采用具有 汇聚无限方差分布的( ) n o f f 过程来拟合以太网流量。 在自相似序列生成方面，m a n d e l b r o t 在1 9 7 1 年提 x 华中科技大学硕士学位论文 和精确上还不能令人满意，每种方法总是有自己的缺陷，如h 。s k i n g 方法的复杂性， r m d 算法的不够精确性且不能在线生成等。目前还缺乏快速、精确和在线的自相似流 量生成方法。 1 5 论文研究内容 流量的自相似特性和自相似流量的序列生成对a t m 网络管理和流量控制具有重要 的意义。论文对网络流量自相似特性和流量的生成方法进行了深入的研究，并对a t m 网中自相似流量背景下的a b r 流量控制机制进行了探讨，主要的研究工作包括： ( 1 ) 对自相似过程的定义和特性进行了总结，给出了一个简明的二阶自相似过 程的定义。给出了检验网络流量自相似特性的几种方法，并应用这些方法，通过对真 实网络流量的考察，验证了流量的自相似特性。 ( 2 ) 对常用的仿真工具n s 2 的流量合成方法的有效性进行了验证。 ( 3 ) 对自相似流量的序列生成算法随机中点插值方法( r m d ) 进行了研究并提出 了新的算法，最后对改进算法应用上述的检验方法进行了分析验证。 ( 4 ) 研究了具有自相似性的v b r 业务背景下 t h 网中的a b r 流量控制机制，比 较分析了两种流量控制机制在自相似条件下的性能。 华中科技大学硕士学位论丈 尺坶分析方法和方差一时间分析方法虽然可以给出h u r s t 参数的测量值，但是却 无法给出该测量值的置信区间。极大似然估计法基于上一节的自相似过程的特性( 3 ) ， 从频域的角度给出参数h 的测量值及其置信区间。 设厂( 旯，p ) 为归一化方差情况下自相似随机序列的功率谱。，( 五) 为自相似随机 序列的周期图，即： m ，= 杰 善x ， b 旧 为估计h u r s t 参数，寻找最小化式的口 胛) = 揣 b 其中口= ( 口2 ，h ，岛，哦) ，岛，眈表征自相似序列的短期相关结构。例如， 对于分形布朗运动的估计，仅需要向量口的前两个分量。经过推理，口的近似极大 似然估计可以由最小化下述似然函数得到 w ) = 去l 吖( 枷m + 竿 ( 2 1 6 ) 其中，x 为由随机变量序列组成的向量，a 为相应的协方差矩阵。 近似极大似然估计方法的最大优点是它给出了h 测量值的置信区间，而且它简化 了极大似然估计方法的复杂性。 从运算效率和准确性来看，上述三种方法中方差一时间分析方法是准确性与运算 效率都比较好的种方法2 ”。而且它对边缘分布为正态分布的信息流的参数估计比较 有效，所以该方法得到比较广泛的应用。此外，此方法经过一定改造后，还可以对业 务量进行在线的检测2 8 1 ，为业务量控制提供参数。 另外，在文献【2 9 】中介绍了另外一种利用小波分析的估计方法。小波分析在分形 信号和分形参数估计中显示出其多分辨时频分析的独特优势，因而基于小波的h u r s t 参数估计方法得到了一定的应用。 需要注意的是，判断网络流量是否具有自相似性和估计 1 u r s t 参数的着眼点是有 华中科技大学硕士学位论文 所差别的；前者需要长期检测数据，计数阊隔应该尽可能小，得到韵分析结果才有可 靠性；而后者则要求用尽可能少的流量数据准确估计产生流量的自相似程度，便于为 网络为其分配传输带宽和缓冲资源。 2 2 2 业务的自相似性的检验 网络业务量的自相似性在很多文章中都有研究。下面对几种典型的业务序列进行 自相似的检验，这些序列均来源于实际的网络或相关数据源。 其序列的名称以及统计参量如下所述。 ( 1 ) b e l l c o r c 的l 。a n 内部网络流量：数据集名称p a u gt l ，共3 1 4 ，2 8 1 个数据， 序列均值1 3 8 1 9 字节每l o 毫秒，序列峰值为1 3 4 1 8 字节每1 0 毫秒，标准方差为2 2 2 6 9 字节每1 0 毫秒，峰值与均值之比为9 7 1 0 1 ，h u r sc 参数为o 8 0 0 4 。 ( 2 ) b e 【jc o r e 的l a n 内部业务量：数据集名称为p o c tt l ，菇有1 7 5 ，9 6 1 个数 据，序列均值为3 6 2 7 ，4 字节每 0 毫秒，序列峰值为1 3 2 7 6 字节每l o 毫秒，标准方差 为3 7 0 5 9 字节每1 0 毫秒，峰值与均值之比为3 6 5 9 9 ，i i u r s t 参数为0 8 3 6 3 。 ( 3 ) b e l l c o r e 的l a n 外部流量：数据集名称为o c t e n t l ，共有4 3 4 ，2 5 0 个数 摄，序列均值为9 3 5 字节每1 0 0 毫秒，序列峰值为1 0 5 8 0 字节每1 0 0 毫秒，标准方差 为4 0 4 字节每1 0 0 毫秒，峰值与均值之比为1 1 3 1 9 5 ，h u r s t 参数为0 8 3 5 0 。一 ( 4 ) b e l l c o r e 的i 。a n 外部流量：数据集名称o c t c x t 4 t l ，共有2 l o ，3 9 4 个数 据，序烈均值为6 9 5 9 字节每l o o 毫秒，峰值与均值之比为3 1 8 6 9 7 。l l u rs ，参数为 o 9 6 4 4 。 ( 5 ) m p e g j 数据集：电影“星球大战”，共1 4 ，5 1 1 个画面组( ( ；( ) p ) ，序列均 值为4 2 4 8 2 信元每画面组，穿歹l j 峰值为2 1 4 7 s 信元每画面组，标准方差为1 6 5 5 4 信 元每画面组，峰值与均值之比为5 0 5 1 l ，序列l u r sl 参数为0 8 8 7 l 。 ( 6 ) m p e g i 数据集：电影“辛德勒名单”剪辑，共有6 1 8 7 个画面组，序列均值 为3 6 8 2 7 个信元每画面缉，序列峰值为1 6 “3 信元每画面组，标准方差为1 3 3 7 4 信 元每画面组，峰值与均值之比为4 5 7 3 5 ，h u r s t 参数为o 8 9 4 6 。 观察这些序列片断，可以发现，不论是局域网数据还是m p e g 数据，其产生的流 量突发性都非常强，峰值速率与平均速率之比大多在十倍与百倍之闻，其中序列3 的 华中科技大学硕士学位论文 3 仿真实验中流量分析 n s ( n e t w o r ks i m u l a t o r ) 是一种可扩展、易配置、可编程的事件驱动的网络仿 真软件，n s 支持多种基本的协议，如t c p 协议、一些路由协议的多点发送协议等。n s 目前的版本为2 ，即n s 2 ( n e t w o r ks i m u l a t ( ) rv e r s i o n 2 ) 。 l 洲l 的网络仿真软件的开发始于1 9 9 0 年5 月对s k s h a v 的r e a l 网络仿真程序的 修改。9 1 年夏天，对仿真描述语言进行了修改，称为t c p s i m 。1 9 9 4 年1 2 月，m c c a n e 用c + + 重写了t c p s 】m ，称为n s 。 n s 是一个功能强大的仿真工具，并且由于它是开源的，在世界上得到了广泛的应 用。目前，已经有5 0 多个国家的6 0 0 多个研究机构正在使用它。 3 1n s 2 基本介绍 3 1 1n s 2 的安装和基本组成 n s 能在大多数u n t x 平台下运行，f r e eb s u 、i 1 n u x 和s u n h r i s 。在w n d o w s 系列平台山也可以，但稳定性不够好。本文选择的平台是i i n u x ，因为n u x 是一种 免费的系统，且稳定性好。本文所选择的平台1 jn u x 是r e dh a t 9 ，0 。 具体的安装步骤见文献【3 0 。 n s 2 的主要由以下的功能模块组成。 ( 1 ) t c l ：r c l 提供了一个强有力的平台，可以生成面向多种平台的应用程序， 拚议，驱动程序等等。它与t k ( t 0 0 1 k i t ) 协作，可生成g u i 应用程序，可在p c 、u n i x 和m a c i n t o s h 上运行。t c l 还可用来完成与网页相关的任务，或是为应用程序提供强 有力的命令语言。 ( 2 ) t k ：与，i c l 协调工作的图形工具包。 ( 3 ) ( ) t c 】：m o b j e c tt c l 的简称，是t c t k 面向对象编程的扩展。 ( 4 ) r c lc 1 ：此目录下含t c l c + + 的接口，v i c 、v a t 、n s 、rl p p l a y 、和n a m 都 会用到。 华中科技大学硕士学位论文 p a r e t o0 n 0 f f 模型，e x p o n e n t i a lo n o ff ，仿真或实际测量文件输入一共四种流量 生成方法。图3 2 所示为n s 2 中两种基于两种传输协议的流量合成的示意图。 目前通用的仿真模型为n 个发送节点，一个路由节点和一个接收节点，还有连接 节点间的链路组成，如图3 3 所示。发送端到路由节点的链路延时为一，路由节点到 接收节点的链路延时为乩，路由节点队列长度为b 。在本节当中，将对n 个发送端 s e n d e r 给予不同的传输层协议和不同的应用层协议和业务模型，然后在路由节点检测 到达的数据包的统计特性，以此来验证仿真实验中数据的自相似特性。 1 1 i m 蒙r c 辜三c n r r 轴l i _ s s i l 聃h i 曲i c d 钍p | ，i i e n l i l i s 一一一一一一一一一1一一一一一一一一一1 ：a p l l j c a i i - l l ， l ：1 ，r i m c ， e x p n e n t i 辅i 一一一一一一一一一一j 一一_ i ! ，! 一一 a 譬c “洲d p ，j a p p i i c a t i o n h ? ip 卜 图3 2n s 2 中合成流量的示意图 圈33 网络仿真模型 3 2 1 模拟t c p 流量的自相似特性的分析 在目前的广域网上，t c p 的流量占了大约9 0 的份额，所以目前大多数流量控制 都是针对t c p 协议设计的。对t c p 进行仿真模拟的一个n s 2 示例脚本片断如下： s e ts r c 【n e wa g e n t c p f u l l t c p 】 2 4 华中科技大学硕士学位论文 图3 6f t p 聚合量( o 2 0 0 s ) 实验二：其它配置不变，对n = 2 0 ，n = 3 0 0 时分别仿真。 实验三：实验一其它配置不变，把协议变为t e l ne 1 i ，n = 3 0 0 进行仿真，得到的 聚合量如以下图3 ，7 一图3 ，9 所示。 实验四：当应用层协议变为t 融，n e t 时，对n = 2 0 ，1 0 0 分别仿真 x 华中科技大学硕士学位论文 实验l 4 的结果分析如下所述。 ( 1 ) 自相关函数如图3 1 0 所示。 n - 2 0f t p 聚合量的自相关函数n - 2 0 t e l n e t 自相关函数 n = 1 0 0f t p 聚合量的自相关函数n = 1 0 0t e l n e t 自相关函数 n = 3 0 0f t p 聚合量的自相关函数n = 3 0 0t e l n e t 自相关函数 图3 1 0n s 2 中t c p 流量自相关函数 结果显示w 2 产生的t c p 流量的自相关函数都在o 值附近抖动。也就是说胳2 中 实现的t c p 流的聚合量不具备有自相似性。 ( 2 ) 方差时间图 根据上一节的方差时间估计方法，可以画出实验数据的方差时间图，如图3 1 1 所示。图中实线为流量数据序列的方差时间图，虚线为拟合直线。这里采用线性均方 l 估计来拟合直线，因为i - o 时，y 1 ：l o g i 。芝= o ，爿= l o g l 。( ) = o ，拟合直线必过 一剿 一骢一 一v萝= 华中科技大学硕士学位论文 原点，设拟合直线为y = 硝：均方误差p = e ( 】，一硝1 ) 2 ，若常数a 使得y = 耐与x 1 正交，即点 ( y 。一硝) 爿 = o ，则均方误差达到最小= e ( y 一硝) x ) ，此时 口= 鬻，羔刊喝肭 可得：芝= = 埘h 得口= 1 一日，h = ( 3 一口) 2 = ( 2 + ) 2 。由此可得到h u r s t v a r 直 参数的估计值。利用这些公式，可以算出以上实验数据的h u r 吼参数均在o 5 以下， 也就是说n s 2 中的t c p 聚合流不具备有自相似特性，与自相关函数图像显示的结果相 符。 n = 2 0f t p n = 1 0 0f t p 曩“墨r - _ ，嬲立：耋基三薹翌盐童。蔓二 j 蔓澍、鬈- 蔓 j 。封、群i 浮澍。、藤 机乜垂； 一- 簪粤- - - 霹黧寥翟菠攀i 曩。嚣 。 鬻 、 攀耄 勰、 n = 2 0t e l n e t n = 1 0 0 t e l n b t 冀i 囊 、。、- 纂 蠹= ；囊凄 n = 3 0 0f t p n = 3 0 0t e l n e t 圈3 。l lt c p 流量的1 0 9 ( v a r y v a r x ) l og i l l 图 一n 华中科技大学硕士学位论文 3 2 2 模拟u d p 流量的分析 在本节对n s 2 中基于u d p 传输协议的指数和p a r e t 0 0 n 0 f f 源进行了仿真实验。 实验五：其它参数与实验一不变，传输层协议变为u d p ，应用层如下设置： 得到自 s e tt r a 俏c n e wa p p l l c a t i o n t r a f n c ，e x p o n e n t i a l 】 $ t r a 所c ( $ i ) s e tb u r s i _ t i m t5 0 m s $ t r a f f i c ( $ i ) s e ti d i e j i m e - 5 0 m s $ t r a 伍c ( $ i ) s e tr a t e 一1 0 0 k $ t r a 俏c ( $ i ) s dp a c k e t s i z e 一2 0 0 0 图3 1 2 指数分布0 n o f f 模型自相关函数 图3 1 3 指数分布方差时间图 实验结果表明：自相关函数一直在0 值附近，而h u r s t 参数只有o 5 多一点点 说明基于指数分布的( ) n 0 f f 模型不具备有自相似特性。 实验六：与实验五相比，其它参数不变，应用层变为： s e tt r a f n c n e wa p p l i c a i i o n 厂r r a 币c ，p a r c t o