（计算机科学与技术专业论文）网络流量的自相似特性以及生成方法的研究.pdf

国防科学技术大学研究生院学位论文 摘要 自相似特性是目前计算机网络( 包括局域网和广域网) 所具有的一个普遍特性，自相 似业务量对计算机网络的管理和控制有着非常重要的影响。本论文围绕网络流量的建模问 题，在业务量的统计特性分析、自相似过程描述、序列生成、多分形分析方面进行了系统 深入的研究。主要工作包括： ( 1 ) 对自相似流量的建模和控制研究中存在的问题进行了全面的概括和总结。 ( 2 ) 分析了计算机网络中流量( 业务量) 的统计特性，验证了网络流量普遍存在的自相 似性，讨论了几种h u r s t 参数的计算方法。 ( 3 ) 对我们常用的网络仿真器n s 2 里的业务量合成方法的有效性( 主要是自相似特性) 进行了验证。 ( 4 ) 分析几种著名的自相似过程和几种有代表性的流量序列生成方法，并说明了它们 各自的优缺点。 ( 5 ) 基于r m d 算法，提出一种新的序列生成方法，用c 语言实现并分析了它的精确 性和效率。 ( 6 ) 应用多重分形的分析方法对网络实际流量和n s 2 仿真流量进行了分析。 关键词：计算机网络，流量分析，自相似，流量模型，长相关性，分形过程，n s 2 序列生成，多重分形分析 里堕型兰堇查奎兰竺窒兰堕兰生堡奎： a b s t r a c t s e l f - s i m i l a rp r o p e r t yi so n eo ft h ek e ys t a t i s t i c a lc h a r a c t e r i s t i c si nt h ec o m p u t e r n e t w o r k s ( i n c l u d i n gl a na n dw a n ) s e l f - s i m i l a rt r a f f i ch a sas i g n i f i c a n ti m p a c to nn e t w o r k m a n a g e m e n ta n d c o n t r o la sw e l la sp e r f o r m a n c ee v a l u a t i o n t h i sp a p e rc a r r i e so na ne x t e n s i v e i n v e s t i g a t i o na n dd e e pr e s e a r c ho nm o d e l i n gs e l f - s i m i l a rt r a f f i ci nm a n ya s p e c t sl i k es t a t i s t i c a l a n a l y s i so ft r a f f i c ，d e s c r i p t i o no fs e l f - s i m i l a rp r o c e s s ，g e n e r a t i o no fs e q u e n c e s ，m u l t i f r a c t a l a n a l y s i sa n ds oo n t h em a i nc o n t r i b u t i o n si nt h i sp a p e ra r ea sf o l l o w s ： 1 ) s u m m a r i z et h eo v e r a l li s s u e si nt h ea r e ao fs e l f - s i m i l a rm o d e l i n ga n dc o n t r 0 1 2 ) a n a l y z et h es t a t i s t i c a lc h a r a c t e f i s t i c so f t h et r a f n ci nt h ec o m p u t e rn e t w o r ka n d p r o v et h e f a c t t h a ts e l f - s i m i l a r i t yi sac o m m o np r o p e r t y d i s c u s st h ei s s u eo ne s t i m a t i n gt h eh u r s t p a r a m e t e ro fs e l f - s i m i l a rt r a f e i c 3 ) d i s c u s st h ev a l i d i t y ( s e l f - s i m i l a r i t yf i r s to fa 1 1 ) o ft h en s 2s i m u l a t i n gt r a f f i c ( 1 i k eu d p a n dt c p 、 4 、s u m m a r i z es o m eo ft h es e l f - s i m i l a rp r o c e s sa n ds e l f - s i m i l a rt r a f i l eg e n e r a t i o nm e t h o d s 5 、p r o p o s ean e wm e t h o dt og e n e r a t es e i f - s i m i l a rt r a f f i cb a s e do nr m dm e t h o d a n a l y z e i t sa c c u r a t e l ya n dp r o m p t l y 6 ) a p p l yt h em e t h o do fm u l t i f r a c t a la n a l y s i st oa n a l y z et h ef r a c t a lb e h a v i o ro fs e l f - s i m i l a r t r a f f i ci nc o m p u t e rn e t w o r k sa n ds i m u l a t i n gt r a c ei nn s 2 k e yw o r d s ：c o m p u t e rn e t w o r k s ，t r a f f i ca n a l y s i s ，s e l f - s i m i l a r , t r a f f i cm o d e l i n g ，l o n g r a n g ed e p e n d e n c e ，f r a c t i o n a lp r o c e s s ，m u l t i f r a c t a la n a l y s i s ，t r a f f i cg e n e r a t i o n ，n s i l 国防科学技术大学研究生院学位论文 图表目录 图1 1 万兆以太网作为城域网骨干网络的示意图3 图2 1b e l l c o r e 局域网流量统计图，1 1 表2 1 自相似过程的特性与参数1 4 图3 1n s 2 功能模块示意图1 9 图3 2n s 2 中合成流量的示意图2 0 图3 3 网络仿真模型2 0 图3 4 聊限协议聚合量( o 1 0 0 0 0 s ) 2 1 图3 5f r p 协议聚合量( 0 1 0 0 0 s ) 2 1 图3 6f r p 聚合量( 0 2 0 0 s ) 。2 1 图3 7n = 3 0 0 ! u 咂t 协议聚合量( o 1 0 0 0 0 s ) 2 2 图3 8n = 3 0 0 t e i n e t 协议聚合量( 0 l o o o s ) 2 2 图3 9n = 3 0 0t e l n e t 协议聚合量( 0 2 0 0 s ) 2 2 图3 1 0n s 2 中t c p 流量自相关函数2 3 图3 1 1t c p 流量的l o g ( v a r y v a r x ) 一l o g m 图2 4 图3 1 2 指数分布o n o f f 模型自相关函数2 5 图3 1 3 指数分布方差时问图。2 5 图3 1 4 不同时间尺度下p a r e t o 分布的聚合量2 6 图3 1 5n = 1 0 0 时p a r e t oo n o f f 模型的自相关函数与方差时间图2 7 图3 1 6 不同参数下p a r e t o 聚合量的自相关函数2 7 表3 1h u r s t 参数估计表一2 8 图4 1f f r 方法流程图3 3 图4 2r m d 方法流程图3 4 图4 3r m d 算法的前三步执行情况3 5 图4 4 传统r m d 算法的生成顺序3 6 图4 5 改进r m d 算法的计算顺序( 虚线为流出顺序) 。3 7 图4 6 改进r m d 算法生成的序列片断一” 表4 1 改进r m d 算法生成序列的h 参数估计( 方差时间方法) 3 8 表4 2 改进r m d 算法与r m d 算法运行时间对比( p i l 4 5 0 ，1 2 8 m ) 3 8 图5 1 l a n 业务量的1 0 9 瓯( 鼋) 一一l o g m 图和多重分形谱函数4 2 表5 1 真实业务量序列的自相似特征和多分形特征 表5 2 模拟实验数据及处理结果 4 2 4 3 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下送行的研究工作及取得 的研究成是。尽我所知，除了文由特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示测意。 学位论文题目：囝鉴逾量鲍自塑丝赞，哇丝区生盛互这盟堑枣 学位论文作者签名：勉 日期：年1 1 月日 学位论文版权使用授权书 本人羌垒了解国防科学技术大学有关保留，使用学位论文的规定。本八授硬 匡防科学技术大学可以保留并向国家有关部1 或机构送交论文的复印件和电j 疋档允许论文被查阅和借阆；可以将学位论文的全部或部分内容编入有关数据 厍进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授板书。、 学位匏又题目 旦垒鎏量塑自i 曼型挂：睦丝丛垒亟复垄盐堑童 学位论文作者签名：垄丝 口崩2 ，卅斗年j 1 月心日 作者指导教师签名 拿牮 日期：j c z 年，7 月佗。 国防科学技术大学研究生院学位论文 第一章绪论 本章概述了计算机通信网络的现状及其发展趋势，然后从不同的角度介绍了计算机通 信网络的业务种类和业务量特性，然后概述了网络流量生成的一般方法、准则以及一些传 统的业务量模型。围绕业务量的自相似特性，对自相似网络流量的生成技术的研究现状进 行了总结，并分析了面临的主要问题。最后介绍了本论文的主要研究内容和结构安排。 1 1 计算机网络现状及其发展趋势 众所周知，当今的通信网络正在飞速的发展。目前的计算机网络已经渐渐融合了诸如 传统的计算机网络、无线网络、有线电视网络( c a 孙，) 、综合数字网( i d n ) 、综合业务数 字网( i s d n ) 以及宽带综合业务数字网( b i s d n ) 等等多种网络形态，并朝着全球化、 宽带化、个人化、综合化和智能化的方向发展。基于计算机通信网络的各种各样的应用譬 如电子邮件、文件共享、视频会议、视频点播等也越来越走进人们的生活，通信网络的发 展使人们自够以更为自然和直接的方法来获取信息，进行沟通。 1 ，1 1b i s d n 和a t m 从八十年代中后期开始，国际电信联盟( r r u - - t ) 开始制定有关b i s d n 的规范。 在建议1 1 2 1 中规定了异步传输模式( 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 d n 的网络总体、网络能力、网络性能、网络互通、网络资源管理、业务、信令、用户网络接 口( u n i ) ，网络节点接口( n n i ) 、o a m 原则、a t m 适配等各个方面。至今，国际电联 已为b - - i s d n 及a t m 研究制定了大体完善的建议【5 7 引l 。 b i s d n 的目标就是要实现现有以及未来可能出现的各种电信业务，包括从几十k 的 话音业务到上百兆的图像和高速数据业务。为了实现这一目标，以a t m 为基础的b i s d n 具有与传统的电话网络和分组网络显著不同的特点。首先，为了提高网络的效率和资源利 用率，降低运行和维护管理的复杂度，b - - i s d n 将网络建设和业务种类相分离，使网络实 现与业务无关；其次，由于各种业务的信息传输速率变化很大，b - - i s d n 利用了统计复用 和a t m 虚连接的概念为各种业务灵活分配带宽及各种资源，同时分别保证各自业务的服 务质量：此外，a t m 的信元是固定长度的短分组，实现了信息的高速交换，网络功能也得 到了简化。 b i s d n 的基本构成包括宽带传输，交换网络、接入网络( 包括互连单元) 和网络管 理系统。传输网络由光纤网络构成，传送方式采用同步数字系列( s d h ) 或波分复用( w d m ) 第1 页 国防科学技术大学研究生院学位论文 技术：交换网络主要由a t m 骨干交换机构成；接入网络以a t m 接入设备为基础，采用多 重接入方式如非对称数字用户环路( a d s l ) 、光纤分配网络以及光纤和同轴电缆混合 ( h f c ) 接入用户。 然而，到目前为止，b i s d n 一直未能实用化，其原因一方面是太复杂，另一方面 这种在链路层交换的体制无法实现不同网络的互通互连，甚至n - - i s d n 和b - - i s d n 之间 也不能互连。尽管b - - i s d n 未能得到普及发展，a t m 却在9 0 年代得到了发展的机会。9 0 年代初f d d i 问世以后，在局域网、校园网、企业网方面没有速度超过1 0 0 m b p s 的网络。 闰r m 在这个领域找到了发展空间，在9 0 年代中这一段时间得到很大发展，并进入了实用 化阶段，商用化的a t m 产品大量出现，很多国家业已建设了a t m 骨干网络，并提供多种 高速实时业务。a t m 的应用也进入到局域网、无线网络和卫星网络等领域【6 2 “】。 在9 0 年代后期，随着快速以太网和千兆以太网的发展，价格昂贵的a t m 逐渐退出这 一舞台。 1 1 2 万兆以太网 以太网技术( 8 0 2 3 ) 与令牌总线( 8 0 2 4 ) 、令牌环( 8 0 2 5 ) 曾一起成为局域网领域 的三大标准。但是今天，以太网技术已经从这三大标准中脱颖而出，成为局域网的主流技 术，并在城域网甚至广域网范围得到了进一步的应用。 由施乐( x e r o x ) 、d i 【西t a l 以及i m e l 共同推出的d i x 以太网标准在首次公布时就没有 添加任何版权限制，他们的想法是让其他人能够方便地得到以太网技术，进而生产以太网 产品。i e e e 组织也成立了专门的研究小组，广泛吸纳科研院所、生产厂家、个人会员参与 研究讨论。这些举动得到了众多服务提供商的支持，使以太网很容易融入到新产品开发中。 以太网还具有如下特点： 以太网结构简单、管理方便、价格低廉。由于没有采用访问优先控制技术，简化了访 问控制的算法，从而简化了网络的管理，并降低了部署的成本，因而得到了广泛的应用。 以太网技术的持续改进满足了用户不断增长的需求，以太网技术在发展过程中得到了 不断的改进，如物理介质从粗同轴电缆到细同轴电缆、双绞线、光纤的不断变化，网络功 能从共享以太网到全双工、交换以太网的进步，传输速率从1 0 m 到1 0 0 m 、1 0 0 0 m 乃至1 0 g 的提升，极大地满足了广大用户对各类应用的需求。 万兆以太网技术的研究始于1 9 9 9 年底m e e 8 0 2 3 a e 工作组的成立，历时近3 年，在 2 0 0 2 年6 月正式发布了8 0 2 3 a e1 0 g e 标准p 6 1 。 在物理层，8 0 2 3 a e 大体上可以分为两种类型，种为与传统以太网，连接速率为 1 0 g b p s 的“l a np h y ”，另一种为连接s d h s o n e t 速率为9 5 8 4 6 4 g b p s 的“w a np h y ”。 其中l a np h y 还包括一种可以使用d w d m 波分复用技术的“1 0 g b a s e l x 4 ”规格。 w a np h y 与s o n e to c 一1 9 2 帧结构的融合，可以与o c 一1 9 2 电路和s o 唧s d h 设备一 第2 页 国防科学技术大学研究生院学位论文 起运行，保护了传统基础设施投资，使运营商能够在不同地区通过城域网提供端到端以太 网服务。 在数据链路层，8 0 2 3 a e 继承了8 0 2 3 星型连接、点到点连接及上述拓扑的组合， 有影响，使得升级风险极低。 以太网的帧格式及最大最小帧长度，支持多层 充分保证对已有应用的兼容性，对上层应用没 随着千兆到桌面的曰益普及，万兆以太网技术将会在汇聚层和骨干层得到广泛的应 用。就目前网络现状而言，万兆以太网首先的应用场合将是教育行业以及数据中心的出口、 城域网的骨干。 随着高校多媒体网络教学、数字图书馆等应用的开展，高校校园网将是万兆以太网的 重要应用场合，利用1 0 g e 的高速链路构建校园网的骨干链路以及各个分校区和本部之间 的连接，实现端到端的以太网访问，提高了传输的效率，有效地保证了远程多媒体教学、 数字图书馆等业务的开展。 城域网建设的深入，各种丰富的内容业务( 如各种流媒体视频应用、多媒体互动游戏) 纷纷出现，对城域网带宽提出更高需求，而使用传统的s d h 、d w d m 等技术作为骨干存 在网络结构复杂、难于维护、建设成本高等问题，在城域网的骨干层部署1 0 g e 可以简化 网络结构，降低部署成本，便于维护，通过端到端以太网来打造低成本、高性能、具有丰 富业务支持能力的城域网。1 0 g e 在城域网中的应用主要有两个方面：直接用1 0 g e 完全取 代原来的传输链路作为城域网的骨干；通过1 0 g e 的c w d m 接口或w a n 接口与城域网的 传输设备相连接，充分利用已有的s d h 或d w d m 骨干传输资源。 图1 1 万兆以太网作为城域网骨干网络的示意图 1 2 网络流量的业务种类以及业务量的特性 网络中的业务种类非常多，可以有几种不同的分类准则：按照信息的类型分为话音、 文本、图像业务和多媒体业务：按照信息的传输速率可以分为固定比特率业务和可变比特 率业务；按照时间关系可以分为实时业务和非实时业务；按照信息的传输方向可以分为交 互式业务和分配式业务；按照信道的连接方式又可分为面向连接和无连接的业务。这些分 第3 页 国防科学技术大学研究生院学位论文 类方法不是相互独立隔离的，而是相互交叉的。比如对于视频点播业务，它同时也是视频 业务和有实时性要求的业务。此外，按照上述的某一准则的分类不是绝对的。比如，对于 传统的p c m 话音业务，它是固定速率业务，而对于经过可变比特率压缩编码后的话音业 务则是可变比特率业务。 上述各种不同的分类方法是从不同角度考察的结果。对于用户来说，所关心的是业务 的内容，比如是话音、文本还是图像以及它们的最终质量，用户往往要做出主观上的评价： 而从网络建设者或运营者的角度考虑，除了要为用户提供可以接受的业务质量之外，还必 须同时考虑网络的资源利用率。他们需要将用户的主观评价转化为具体的和量化的业务参 数，并采用一定的业务控制方式来加以实现。因此，他们更关心的是业务的承载方式， 传输方式和业务量特性等。 其中业务质量要求( q o s ) 由用户提出。在a t m 网络中考察业务质量的指标般分 为两类：一类是包括与面向连接鼹络相关的呼q 控制参数，其中包括连接建立接受概率、 呼叫建立延迟和呼叫释放延迟；另一类是为分组网络定义的一套信息传输参数，其中包括 比特误码率、信元丢失率、端到端传输延迟、信元延迟抖动等。而业务量特性是指业务在 信息传输过程中业务量的变化，它一般可以通过统计的方法来描述，常用的业务量参数有 平均呼叫次数、平均呼叫保持时间、峰值速率、平均速率、速率方差、突发度、平均突发 时间等。此外，业务量的边际分布函数和自相关函数也常用来讨论业务量的随机变化。业 务量特性对网络保证业务质量有直接的影响，一般来说，用户要向网络声明这些业务量特 性的信息，网络根据这些信息以及用户提出的业务质量要求进行网络的业务量控制，满足 用户要求同时高效利用网络资源。 对于不同的业务，业务量特性相差很大。在宽带网络中，视频业务和高速数据业务已 逐渐成为宽带网络的主导业务。这些业务的业务量具有些非常重要的统计特性【23 j ：( 1 1 平均信息速率高，高速数据传输一般为几兆到几十兆比特每秒，而视频业务如压缩过的高 清晰度电视达到几十兆比特每秒；( 2 ) 业务量突发性强，有场景切换的可变速率视频业务 量的峰值速率与平均速率之b 匕般都不大于十，而高速数据如局域网仿真的突发度可达上 百甚至在这之上；( 3 ) 连接保持时间变化大，比如一些新业务如网页浏览连接持续时间变 化范围非常大，短则几秒，长则达到几个小时以上：( 4 ) 业务量具有自相似特性，或者称 长期相关性。业务量在较大的时间尺度后仍然有很强的相关性，其自相似性还表现在业务 量在很大的时间尺度上具有突发性的特性。业务量的这些特性对于业务量建模和网络的拥 塞控制有非常重大的影响，其中业务量的长期相关性意味着宽带网络中的业务量更加趋于 复杂而难以捉摸和控制，这对网络的建设者和运营者提出了更高的要求。 我们知道，业务量的复杂性往往也是由于业务的复杂性引起的。比如，i n t e r n e t 中很 大部分业务量来自w w w 业务。w w w 采用的是超文本链接方式，一个图标可能链接到本 地计算机，也可能链接到其它地方的计算机，链接的范围不受地域限制，链接的内容可以 是一段文字、一个图片或是存储的音频和视频流。用户可以是各种资源的使用者，同时也 第4 页 国防科学技术大学研究生院学位论文 可以成为资源的提供者。这些特点使得业务更具有灵活性，但同时也增加了网络中业务量 得复杂性。 不同业务的业务质量要求差别很大。一般来说，实时业务如话音、图像对于时间抖动 非常敏感，而对误码率和绝对时延的要求相对较松；非实时业务，如一些数据业务没有实 时性要求但对误码率有严格要求。实际上，业务质量要求是在人们主观感受和业务量的统 计特性的研究基础之上提出的，业务量特性同样会对业务质量要求产生一定的影响。同时， 业务的质量要求对于业务量的控制也有着直接的影响。 总而言之，计算机网络的带宽和业务种类都在飞速的增长，这种增长无可避免的带来 了许多问题，它所引发的流量的增长更是引起前所未有的关注。跟随这一变化，流量建模、 网络拥塞控制和排队分析成为研究的热点，它们的共同目标是解决各种流量汇聚带来的各 种问题，这也是本论文研究的一个大的方向和最终目标。 1 3 传统的流量模型和流量生成方法 流量建模是进行宽带网络设计和性能评估的一个核心问题。由于宽带网络需要具有提 供现有以及将来可能出现的各种业务的能力，网络的设计者就必须要考虑到这些业务的特 征及其对网络的影响。网络的设计通过建立网络模型和业务量模型对网络性能和业务质量 进行预测、分析、评估和测试。就a t m 网络而言，业务的质量是由业务量控制机制来监 测和保证的，而网络流量建模则是网络流量控制机制研究的基础之一。 进行性能分析得方法包括：解析分析、计算机仿真和实验。解析分析和计算机仿真需 要采用精确的网络流量模型，这些网络流量模型应该可以捕捉和刻画出网络流量的统计特 征。解析分析通过理论上的推导可以得出解析的结果。但解析分析往往需要做出很多假设， 这就限制了其对实际系统的描述。计算机仿真可以避免进行艰涩的理论推导而得出性能分 析的结果，这一方法在实际中得到广泛的应用，有很多重要的结论都是通过这一方法得到 的。通信系统中常用的计算机仿真方法有蒙特卡罗方法，针对于稀有事件的仿真还有重要 采样等方法【4 1 。 网络流量建模一般包含以下几条准则：( 1 ) 真实性。网络流量模型产生的网络流量应 接近真实网络流量源。网络流量模型应该刻画出真实网络流量源影响性能的主要统计特 征。网络流量模型应该具有明确的物理意义。( 2 ) 通用性。网络流量建模应考虑网络流量 模型可以对多种不同的业务均适用，不同的业务只是在参数的数值上有所差别。( 3 ) 简堆 性。网络流量模型应采用尽量少的参数，而且参数应该具有直观的意义。( 4 ) 可适配性。 网络流量模型应该容易与真实网络流拟合，网络流量参数应该可以从真实网络流量中方便 的得到。( 5 ) 理论可分析性和精确性。在不失精确性的前提下，基于网络流量模型的可分 析性对网络流量性能进行解析分析。( 6 ) 易于实现。网络流量模型应该是通过计算机仿真 或是基于硬件的网络流量生成器可以方便的实现。 第5 页 国防科学技术大学研究生院学付论文 如果一个网络流量模型能够同时具有上述这些特性，那它将是一个完美的模型。遗憾 的是，这六点是很难同时做到的。一般来说，网络流量模型的参数越多，模型就越精确， 越接近真实的网络流量源，但同时，模型也越繁琐和复杂，理论分析和计算机仿真也会越 困难。在实际的网络流量建模中往往要对网络流量模型的精确性和复杂度加以折衷。 传统的网络流量模型包含两大类，一类是马尔可夫类模型，另一类是回归模型。前者 包括开关( o n o f f ) 模型、间断泊松过程( i p p ) 、马尔可夫调制泊松过程( m m p p ) 和马 尔可夫调制流体流过程( m m f p ) 等。后者包括自回归模型( a r ) 、离散自回归( d a r ) 模型、自回归滑动平均( a r m a ) 模型、自回归综合滑动平均模型( a r i m a ) 和t e s 模 型等。马尔可夫类模型适合对语音或数据及其汇聚流量进行建模，也可以对图像源进行建 模。自回归模型适合于对视频流( 如m p e g ) 进行建模。下面我们对几个典型的模型作简 要的回顾： - 5 尔可夫模型 对于一个有限状态空间s = s l ，s 2 ，s 。) 。令x = 善。) = x 1 ，x 2 ，) ，以为时问n 时的状态，如果下一状态x 州= s f 的概率只与当前状态有关，则 x 。 构成一个马尔可夫 链。马尔可夫特性决定了状态的逗留时间服从几何分布或指数分布。 1 ) o n 0 f f 模型时最常用的语音模型。在o n 状态下产生等间隔的数据包，在o f f 状态下不产生数据量。o n 状态和o f f 状态的逗留时间为指数分布。i p p 模型类似于o n o f f 模型，不同的是在活跃状态下产生数据包的过程符合泊松分布。 2 ) 马尔可夫调制泊松过程是双随机泊松过程。底层是m 状态的马尔可夫链，在状态 k 的逗留时间服从均值为的泊松分布，而在状态& 下的数据包的到达服从均值为a 。的泊 松分布。i p p 模型是其特例。 3 ) 马尔可夫调制流体流过程与马尔可夫调制泊松过程类似，不同的是前者忽略了数 据包到达的离散特性，而看作是固定速率的连续流体，其单位是比特每秒。流体流模型的 最大优点是容易进行理论推导。 马尔可夫类模型有一个非常重要的特征是其自相关函数呈指数型。这是由于其所固有 的马尔可夫特性决定的。因此该类模型不适合对相关性很强的网络流量源进行建模。 回归类模型 1 ) p 阶自回归模型a 尺( p ) 是由序列中待求数据的前p 个值和一个滑动平均的白噪声 来确定，其表达式为： 置= 办x f _ l + 如置一2 + + 砟五1 + 。 其中是白噪声，是实数。如果q 是高斯白噪声，那么x 。将是正态分布变量。定 义b 为向后算符，即置一。= b x ，。令妒( 1 3 ) = 1 一。b - 一庐。b ，则自回归模型还可以表 示为s ，= 驴( b ) 置。其自相关函数p i = 办风一l + 0 2 o k 一2 + + 丸p k 一，于是自相关函数表 第6 页 国防科学技术大学研究牛院学何论文 不为： p k = 4 讲+ + 一p g ； 其中g 1 是妒( 日) 的根。因此，如果1 是实数，那么a r ( p ) 过程的自相关函数同样呈 指数型。 2 ) 离散自回归模型是自回归模型的离散形式。d a r ( 1 ) 是重要的一种离散自回归模型， 在文献 5 】中采用d a r ( 1 ) 对变速率会议电视流量建模。d a r ( 1 ) 定义为： x 。= k x + ( 1 一k ) k 其中 k 和) 是两个独立的随机变量序列，k 取值为 0 ，1 ) ，概率分别为 n 1 一p ， 随机变量k 的状态空间s 且p 嘭= i = 以。d a r o ) 是一个马尔可夫链，其转移矩阵为 p = p l + q p ) q 其中i 为特征矩阵，q 是一个矩阵g = 玎，。该模型的自相关函数为p k = p 。，概率 分布函数为石。d a r ( 1 ) 模型的优点是可以生成伽马型的边缘分布，该模型有均值速率、方 差、峰值速率和一阶自相关系数四个参数，参数估计非常简单。 3 ) 自回归滑动平均模型a n m a ( p ，q ) 定义为( 曰) ：= o ( b ) e ：，其中 口( 8 ) = 1 - b 曰一一0 , b 9 ，对于k q ， 其自相关函数表示为 p k = 矗n 一1 + 疵p k 2 + + 九p k 一，因此其自相关函数也按指数衰减。此外，该模型 的参数估计比较复杂，对吼需要求解一组非线性方程。在文献【6 中，采用a r m a 模型对 v b r 视频业务量建模。 4 ) 自回归综合滑动平均模型是自回归滑动平均模型的扩展。该模型可以用于对同质 非平稳时间序列建模。 5 ) t e s 模型是一种非线性回归模型。t e s 过程可以通过一下递推关系式得到： f u on ：0 卟慨。+ k ) 。，0 w = 。置象 其中，化) 是独立一致分布的随机变量序列，肼 和 【 是在 o ，1 1 2 撼j 匀分布的随 机序列而与 k ) 的概率分布矗无关。因此，选择不同的兄可以构造出不同的自相关函数随 机序列。为了得到目标序列，进行变换 e ；f 。( 嘭) 以及 x i l = f 1 ( 昕1 ) ，其中f 是实 际序列的边缘分布。该模型是迄今为止，唯一可以同时捕捉自相关函数和边缘分布的模型。 回归类模型可以对网络流量的相关函数进行描述，阶数p 和q 越大越精确。不过p 和 q 越大，参数估计和序列生成也越复杂。一般来说，回归类模型在理论上是很难进行分析 国防科学技术大学研究生院学位论文 的，一般多用于计算机仿真。不管是马尔可夫类模型还是回归类模型，其自相关函数均按 指数率衰减。因此，传统模型也常称为短相关模型。 1 4 自相似网络流量建模与生成技术的研究现状 近年来，通过对一些高速网络和v b r 业务的流量的精确测量发现，这些业务量普遍 存在长期相关性，也称自相似特性。其中，l e l a n d 和w i l s o n 等人搜集了从1 9 8 9 到1 9 9 2 年间的b e l l c o r e 以太网的实际传输的数据包【3 l ；b e r a n 和w i l l i n g e r 等人收集并分析了大量 的从i s d n 、以太网和v b r 视频业务中得到的数据【7 】；p a x s o n 和f l o y d 从广域网上收集了 原始业务数据【1 0 】；此外，h e y m a n 等人还测量并分析了a t m 网络中视频业务量的一些特性 【8 】：大量的网络流量测量数据表明：无论是局域网的流量还是广域网的流量，还是v b r 业 务量，都在相当大的时间尺度上呈现出统计自相似特性，即分形特性。而且，不论网络的 拓扑结构、用户数量、服务和利用类型如何变化，这种自相似特性始终存在。与传统网络 流量模型不同的是自相似网络流量的自相关函数不呈指数型而是双曲线型( 即慢衰减型) 。 因此，自相似模型也叫长期相关模型。 自相似性质的重要性并不仅仅在于它是许多网络中流量的个普遍特性，更重要的是 它对网络设计和性能分析有着重要的影响。许多有关网络设计、控制机制研究和性能分析 都是基于传统的流量模型，考虑到自相似特性，这些流量模型用以模拟真实网络的有效性 值得怀疑，尤其是涉及到信元丢失率和拥塞控制部分。围绕这业务量的自相似特性对网络 的设计以及性能分析的影响，国际上展开了大量的研究，这方面的文章层出不穷，在 i n f o c o m 、i c c 和o l o b e c o m 等重要国际会议上也都作为单独个专题提出。有关自相似业 务量的研究在自相似流量建模、序列生成等方面取得了一些进展： e r r a m i l l i 等人采用确定非线性混沌映射方法产生自相似事件流，并应用该方法进行性 能分析【9 】。a d d i e 等人采用了由两个一阶自回归过程来拟合自相似流量的方法【1 1 】。r y u 从 分形点过程的概念出发提出了四个自相似模型【1 2 】。w i l l i n g e r 等人提出采用具有汇聚无限方 差分布的o n o f f 过程来拟合以太网流量【1 3 j 。k a p l a n 等人提出了扩展分形布朗运动并应用 该模型对快速图像合成建模1 1 4 i 。l i k h a n o v 等人提出由叠加无限多个一致o n o f f 过程来合 成一个汇聚流量自, f n v 2 模型。其排队尾部分布呈现出幂率衰减，不同于韦布衰减 1 5 1 。 d u f f i e l d 应用大偏差理论对一个通用的长相关过程进行排队分析，结果表明排队的尾部分 布显示出扩展指数韦布( w e i b u l l ) 衰减【1 6 l 。p a r u l e k a r 在严格数学意义上应用大偏差理论对 c o x 的m g o o 类模型和分形高斯噪声研究，发现尾部分布各自呈现出韦布衰减和幂率衰 减i l ”。n o r r o s 引进了一种基于分形布朗运动的自相似模型，并且推导出排队尾部分布的下 限( 韦布衰减) 1 8 1os a i t o 等人给出了自相似业务量信元丢失概率的上界公式并应用一种基 于踪迹的仿真方法进行了验证【1 ”。h u a n g 等人还应用重要采样方法进行排队分析的快速仿 真【2 0 】。 第8 页 国防科学技术大学研究生院学位论文 在自相似序列生成方面，m a n d e l b r o t 早在1 9 7 1 年就提出了一种快速生成分形高斯噪 声序列的方法【2 1 】。h o s k i n g 又提出了了一种方法生成a r m a 序列f 2 2 】。c h e n 等人应用离散 分形高斯噪声及内插随机中点置换( r m d ) 方法精确快速的生成序列【2 。l 丑u 等人对r m d 方法的特性进行了分析【2 4 j 。 但是，自相似业务建模和流量生成仍然有许多棘手的问题需要解决： 虽然在大多数网络中都发现了流量的自相似特性，人们对自相似流量的本质还不清 楚。分形布朗运动和分形自回归滑动平均过程虽然可以对自相似过程进行精确的数学表 示，但却不具有任何物理意义。具有无限方差的o n o f f 过程的汇聚可以看作是多个具有 强突发性的用户业务量的合成，但它无法解释其它业务量( 如可变速率视频流量) 自相似 性质的原因。迄今为止，人们还没有找到一个可以完全解释自相似过程物理意义的模型。 可以说，人们对自相似性质的模糊认识在一定程度上已经成为自相似业务建模研究发展的 一大障碍。 自相似流量的生成是计算机仿真和性能评估的基础。已有的一些方法在生成效率和精 确上还不能令人满意，每种方法总是有自己的缺陷，如h o s k i n g 方法的复杂性，r m d 算法 的不够精确性且不能在线生成等。目前还缺乏快速、精确和在线的自相似流量生成方法。 总而言之，随着在更多的网络中统计发现，自相似特性已经被公认为是大多数网络的 一个普遍特性。有关自相似流量的研究已经从讨论自相似是否会对网络产生影响，而转为 建立各种自相似业务模型和寻求更完美的生成算法上来了。可以说，自相似流量的建模与 生成方法已经成了网络流量建摸的个重要的部分。 1 5 论文基本结构 网络流量的自相似特性和自相似流量的建模生成对网络设计和性能分析具有重要的 意义。本论文对网络流量自相似特性和流量的生成方法进行了深入的研究。本论文的工作 包括： 第二章首先对自相似过程的定义和特性进行了总结。给出了一个简明的二阶自相似过 程的定义。给出了检验网络流量自相似特性的几种方法，并应用这些方法，通过对真实网 络流量的考察，验证了流量的自相似特性。 第三章对我们常用的仿真工具n s 2 的流量合成方法的有效性进行了验证。 第四章针对随机中点插值方法( r m d ) 进行了研究并提出了一些新的算法，并对这 些算法应用上述的检验方法进行了分析验证。 第五章应用多重分形分析方法对网络仿真流量和实际网络流量进行了分析。该方法可 以同时刻画业务量的长期和短期行为。 本文在第六章对全文进行了总结。 第9 页 国防科学拄术大学研究生院学位论文 第二章网络流量的自相似特性 本章对自相似过程的定义、特性进行了总结，指出了以往有关自相似过程定义的不足。 通过对一些实际网络流量的测试检验，进一步明确了自相似性质的含义。 2 1 引言 自相似网络流量往往可以被描述成一个在极宽的时间尺度范围内具有突发性。这一行 为与传统的电话业务量和各种通用的分组业务量模型如泊松过程，成批泊松过程，马尔可 夫调制泊松过程和流体流过程都有很大的不同。一般的观点认为网络流量的叠加复用会减 小突发程度，产生平滑的汇聚流，然而对于自相似流量来说，复用叠加后突发性依然很强。 自相似性质可以采用不同的方式来表示：如功率谱密度在原点发散：自相关函数有不 可加性，即长期相关性：随取样时间单调增长的计数离散指数。 刻画流量的自相似特性的最重要的一个参数是h u r s t 参数h 。该参数用于描述业务量 自相似性的程度。 在本章中，第二节首先给出了自相似的严格数学定义和在网络流量建模领域的具体物 理意义，然后描述了自相似过程的几个重要特性。在第三节又给出了评价分析自相似，计 算h u r s t 参数的几种方法。在第四节对实际的网络流量进行了对比分析。最后进行了小结。 2 2 自相似过程的定义及特性 自相似就是指局部的结构跟总体的结构具有一致性，这里的结构既包括空间上的，也 包括时间上的，自相似还可以从分布意义上来定义：个连续时间统计过程z ( t 1 是自相似 的，如果z ( a t ) 和口8 z ( t ) 对于所有，0 具有相同的有限维数分布，即 d z ( a q ) ，z ( a t ：) ，z ( a t 。) 卜和h z ( t 1 ) ，a h z ( t 2 ) ，a h z 也) 。 其中n 是正整数，参数日( 妄c hc 1 ) 称作h u r s t 参数。参数h 是自相似过程最重要的 z 一个参数，它表征流量的自相似程度。一般来说，h 值越大，自相似程度越高，突发性也 越高。 下面我们给出了二阶自相似过程的数学定义。 2 2 1 自相似过程的定义 自相似就是指局部的结构跟总体的结构具有一致性，这里的结构既包括空间上的，如 第1 0 页 国防科学技术大学研究生院学俯论文 图2 1b e l l c o r e 局域网流量统计图 包括时间上的。其物理意义具体到计算机网络流量中，是指在不同时间尺度下的统计特 性具有相似性。如图2 1 所示，b e l l c o r e 的以太网流量在不同时间尺度上到达的数据包统计 第1 1 页 国防科学技术大学研究生院学忙论文 量具有很大的相似性。这些特性在排队分析和控制设计中表现出来的就是在各种时间尺度 下，网络的流量都有很大的突发性。 考察一个广义平稳( 即协方差平稳) 过程x = x o ) ) _ = x 。，x ：，) ，设x 具有恒定 均值肛= e x ，】和有限方差v a r x = c r 2 = 叫( 置一) 2 。过程x 的自相关函数定义为 r ( 七) = e 【( 墨一) ( 置+ 。一弘) 】仃2 ， k 一0 ，1 , 2 ( 2 1 ) 显然应有，r ( k