（控制理论与控制工程专业论文）基于petri网方法的网络流量分析及仿真研究.pdf

南京理工大学硕士学位论文基于p e t r i 同方法的网络流量分析及仿真研究 摘要 计算机网络在当今世界发挥了越来越重要的作用。过去对于网络流量的研究以 泊松模型为基础，但是随着技术的发展，人们发现网络中流量的突发与结团现象越 来越明显，流量表现出了自相似的特性，传统的建模方法不再适用。本文以自相似 性为前提，使用p e t r i 网方法对网络流量进行了以下两个方面的研究： ( 1 ) 建模与理论分析。使用p e t r i 网分别建立了无限缓冲区的i p 层网络模型( 模 型1 ) 和有限缓冲区的以太网模型( 模型2 ) ，并对模型进行了基于不变量和基于可达 性的分析； ( 2 ) 实验仿真。针对本文所使用模型的特殊性，编写p e t r i 网仿真软件，首先对 不同参数下o n o f f 流量源模型的性能作了比较，然后对前述的两种网络模型进行 了仿真研究，傻用统计的方法，近似遗得出了模型l 的缓冲区平均队长以及模型2 的网络利用率等重要性能指标，在一定程度上弥补了理论分析的不足。 关键词，网络流量 自相似性p e 缸1 网h u r s t 参数仿真 第1 页 南京理工大学硕士学位论文 基于p e t r i 网方法的网络流量分析及仿真研究 a b s t r a c t c o m p u t e rn e t w o r kn o wp l a y sa l li n c r e a s i n g l ye s s e n t i a lp a r ti nm o d e ms o c i e t y i n t e r l n so fr e c e n tr e s e a r c h ，o l dt r a f f i cm o d e l ，f o ri n s t a r l c e ，t h eo n eb a s e s0 1 1p o i s s o n d i s t r i b u t i o n c a m l o te x p l a i nt h eb u r s ti r a f f i cp h e n o m e n o nw h i c hc o n t r i b u t et ot h e s e l f - s i m i l a r i t yf e a t i l r eo fn e t w o r kt r a 伍c t h e r e f o r e ，i nt h i st h e s i s ，n e t w o r kt r a f f i cw i t h s e l f - s i m i l a r i t ye s s e n c e ，i sm o d e l e db ye n g a g i n gp e t r in e tt h e o r yi nt h ef o l l o w i n gt w o a s p e c t s ： ( 1 ) m o d e l i n ga n dt h e o r e t i ca n a l y z i n g ：a ni pl a y e rn e tw i t hi n f i n i t eb u f f e r ( m o d e li ) a n dae t h e m e tw i t hl i m i t e db u f f e r o d e l ) a r em o d e l e dw i t hp c mn e tc o m p o n e n t s w ea l s oa n a l y z et h e mb yi n v a r i a b i l i t y m e t h o da n dr e s e a r c h a b i l i t y m e t h o d ( 2 ) s i m u l a t i o n ：s p e c i f i cs o f t w a r ef o rp e 砸n e tm o d e li sp r o g r a m m e dt ov a l i d a t et h e n e wm o d e l d i f f e r e n tn e t w o r kp e r f o r m a n c e sd u et od i f f e r e n tp a r a m e t e rs e t so fo n o f f m o d e la r ec o m p a r e df i r s t t h e n ，o u rt w on e wm o d e l sa l es i m u l a t e dt o c o m p e n s a t e d e f e c t si nt h e o r e t i c a la n a l y s i s s o m es i g n i f i c a n tm e t r i c s ，s u c ha sa v e r a g eq u e u el e n g t hi n m o d e li sb u f f e ra n dn e t w o r ku t i l i z a t i o no fm o d e l1 1 a r es t a t i s t i c a l l ya d p r o x i m a t e da s w e l i k e y w o r d s ：n e t w o r kt r a f f i c s e l f - s i m i l a r i t y p e t r in e th u r s tp a r a m e t e rs i m u l a t i o n 第n 页 y7 6 3 4 0 4 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：盎幽艄岁年月工泪 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 南京理工大学硕士学位论文 基于p e r i l 稠方法的髓络流量分析及仿真研究 1 绪论 1 1 论文研究的背景 在i n t e m e t 大规模兴起之前，对于网络的研究主要集中于电话网。当时，“流量” 这一概念主要是用来刻划电话通信系统在呼叫级上的统计规律，比如单位时间内到 达的呼q 数秘呼叫的保持时闻等。对于电话网络流量的建模，普遍采用以下三点假 设：( a ) 电话呼叫的到达过程为泊松过程，即电话呼叫到达间隔时间服从指数分布； ( b ) 呼叫保持时间服从指数分布；( c ) 各次呼叫之间相互独立。由于采用了发展比较 成熟的泊松模型，它具有极其“优美”的马尔可夫特性( 或称为无记忆性) ，在随机 过程学科里，对这一模型已经有十分成熟的结论，因而易于分析。由于以上的三种 假设与实际从电话网络中测得的数据能很好的吻合，所以当时对于电话网络流量的 研究已经达到了近乎完美的地步，泊松模型在相当长的段时闻内也成为研究各种 网络中流量的标准方法。 随着技术的进步，计算机网络特别是i n t e m e t 越来越成为对于整个世界的发展 不可缺少的部分。在i n t e r n e t 上，w e b 服务、文件传输和视频传输等新的网络业务 不断出现，流量来源多种多样，因而流量特性复杂多变，在不同的时间尺度上部表 现出突发与结团的现象。 在1 9 8 9 至1 9 9 2 三年间，b e l l c o r e 实验室的研究者w t t le l e l a u d 和w a l t e r w l i n g e r 等人对其所在实验室与外界之间的网络流量作了详细的记录，在对测量结 果作了数理统计之后，提出高速网络信息流具有自相似性的特点1 1 2 , 1 2 2 。图1 1 为在 不同时间尺度下所绘制的流量曲线，其中每一幅的时间单位都是后一幅的l o 倍， 可见，在各种时间尺度下，i n t e r n e t 中的信息流量都保持了明显的突发特点：而基于 m a r k o v i a n 特性的数学模型以小时间间隔采样产生的突发特性经过时间尺度的放大 后会逐渐被平滑掉。在这一新发现的带动下，随后几年里国外研究人员对一些计算 机网络系统进行了测量和分析，均发现实际网络具有自相似性 3 , 6 1 2 , 1 5 】。从此，对于 网络流量的研究进入了一个新的阶段，对于网络流量的建模与分析都把自相似性作 为重要的前提。 由于自相似性质的出现，对于i n t e m e t 上的流量已经无法继续使用传统的泊松 模型来进行研究，基于指数分布的到达间隔不再成立。在新的形势下，急需找到新 的方法来描述和分析网络中的流量特性。 1 2 两络流量研究的现状 目前，对于网络流量的研究主要集中在以下几个方面 第j 页 绪论 坝i ：论立 01 q o 瑚3 0 64 0 05 0 06 7 0 0 枷9 0 01 0 0 0 t t m e u n i k , u n i t = l o s e o o n d = b ) 0 1 锕2 0 03 4 0 05 0 06 0 07 o o1 0 9 0 t 女u n i l m ，u 穗= s e c o n d c ) o 伽2 0 0 瀚4 0 0 湖蛳瑚8 0 09 0 d1 0 0 t i m e u r n s , u 嘣z o , s e 0 0 憎 d l 0 锄2 0 0 湖4 0 05 0 06 0 0 7 0 0 阳d9 0 01 0 0 0 t - m l el _ 姗，u r 目t = 00 1 s o n d e ) 圈1 1b e l l c o r e 实验室的实测流量图( 局部) ( 1 ) 基于测量与统计的研究。由于传统模型不能描述当前网络流量的自相似性， 许多以传统模型为基础的研究成果不再适用，加之围绕自相似性流量的研究还处于 初始阶段，而实际的网络系统又急需指导，所以测量与统计的方法成为最可行的方 法。 ( 2 ) 建模与仿真。除进行精确测量之外，对网络流量研究还有部分工作是着 眼于构造一种数学模型。由于对流量突发特征的参数描述还远未能达成一致，因此 萑了誊*p蚩警d -薯誊已盥mv鼍址_珂1 m丘|t警m酋也 簟丘一誊匕al要譬也 南京理工大学硕士学位论文基于p e t r i 网方祛的网络流量分析及仿真研究 利用仿真的方法研究自相似流量对高速网络带来的影响己成为网络研究的一个重 要手段。现有的自相似业务生成方法主要有：基于分形高斯噪声和分形布朗运动的 业务生成方法1 8 a 9 ：基于f a r i m a 过程的流量生成方法f 5 ：直接叠加具有重尾特性 的0 n ，o f f 流量源阱斟；m g * 排队模型等等。 ( 3 ) 性能分析 1 0 , 1 1 , 1 3 , 2 0 2 司。对网络流量研究的另一重要方向是分析网络的性能， 而所采用的方法，舀前主要是排队论方法。过去所研究的排队行为大多是在马尔可 夫输入过程下的，在这种短相关性输入的情况下，队列长度分布的衰减是指数的， 而在目前网络信息流具有自耜似性的前提下，输入过程具有长相关性，在无限缓冲 系统里，队列长度分布的衰减慢于指数的衰减。分析这样的非马尔可夫型队列极为 重要，能使我们对自相似过程对于网络性能的影响有最基本的认识。 目前，对于网络流量的研究成果不足之处在于：对网络流量的理论研究方法较 少，除排队论方法之外，没有更常用易用的方法，研究的广度受到限制；对于刚络 中信息流特性的分析还主要集中于排队模型的少数参数上，对于与自相似性的其它 更复杂特性少有涉及；在建模方面，虽然发现流量源产生符合自相似性的流量需要 符合一定的分布特征，但多个各种类型的流量源同时工作时，产生的流量具有什么 样的分布，以及合成后流量的分布与合成前各流量源的关系仍不可知。 1 3p e t r i 网简介 p e t r i 网 3 2 5 乒5 8 1 ，简称p n ，由德国学者c a p e 西于1 9 6 2 年提出，是目前研究离 散事件动态系统的一种重要方法。p c t r i 网可用于描述和分析具有并行性、不确定性、 异步性以及分布性等特点的系统。作为图形工具，p e t r i 网具有类似流程图、框图和 网图的可视化描述能力；作为数学工具，p e t r i 网可以建立状态方程、关联矩阵等， 可以对系统进行精确的描述。 从2 0 世纪7 0 年代末期开始，p e t r i 网在欧洲成为十分活跃的研究领域，p e t r i 网理论及其应用年会一直在召开：8 0 年代初，具有工程背景的研究人员也开始了 p e t r i 网在工程领域，尤其是在自动化领域的研究。 几十年来，p e t r i 嘲理论不断发展与成熟，对于p e t r i 网的理论及应用研究，主 要集中在以下几个方面： ( 1 ) 系统的p e t r i 网模型行为特性及其分析方法的研究。系统的p n 模型特性包 括状态的可达性、令牌的有界性、变迁的活性及初始状态的可逆性等等。分析方法 主要有可达树、关联矩阵与状态方程、不变量分析等： ( 2 ) p e t r i 网的扩展。基本p e t r i 网还可以扩展为多种高级形式，如着色p e t r i 网、 赋时p e t r i 网、随机p e t r i 网、广义随机p e t r i 网及面向对象p e t r i 网等，它们可以用 于描述具有特殊性质的系统： 第3 页 绪论硕士论文 ( 3 ) p e t f i 网模型的简化技术。对于复杂而庞大的系统，使用p e t r i 网具有一定 的困难，因为模型的状态空间大小将随着系统规模呈指数性增长，大型系统的模型 必须经过简化才可能进行分析，简化的方法除了用高级p e t r i 网取代基本p e t f i 网外， 主要有层次化与模块化两种方法； ( 4 ) p e t t i 网计算机软件包与工具的开发。由于p e t r i 网的复杂性，其实际应用 必须依赖于计算机，仿真是研究p e t r i 网模型的重要方法。 i 4p e t r i 网在网络流量方面的研究现状 计算机网络中流量具有并行性、不确定性、异步性以及分布性等等特点，而p e t r i 网本身正适合研究这类系统，但一直以来，研究者们极少使用p e t r i 网对网络流量 进行研究，原因主要在于： ( 1 ) 随着p e t r i 网模型规模的增大，对其分析的复杂性成指数规模增长，而在 计算机网络中要想形成一定的流量，就要有很多主机不断地发送与接收数据，网络 的规模就要比较大，对这样大型的系统建立的p e t f i 网模型势必非常庞大，对这种 模型的分析几乎是不可能的； ( 2 ) 研究网络中由于数据的传输而产生的流量，必然要引入时间的概念，在 p e t r i 网中考虑时间就要使用赋时p e t r i 网或随机p e t r i 网，由于网络系统的不确定性， 经常要引入随机的时间间隔，所以问题往往会集中于随机p e t f i 网。当随机p e 谢网 中引入的随机延时服从指数分布时，可以将其可达图同构于一个马尔可夫链，而这 是随机过程理论中的经典内容，因此可以容易地得到系统各状态的稳态概率等关键 参数。由于自相似性的发现，指数分布型的延时不再适用于网络中的实际情况，如 果在随机p e t r i 网中引入非指数型的延时，由于失去了经典理论的支持，即使是很 小型的模型，对其分析也将十分地困难。 由于以上的原因，在自相似性的前提下，基于p e t r i 网的网络流量研究成果少 之又少。到目前为止，仅有的一些研究主要集中在： 1 ) 使用p e t r i 网对两络结构的建模。文献 4 7 介绍了网络中数据发送端、数 据传递单元以及其它各种数据处理单元的建模方法，并给出一个小型令牌环网的随 机p e t r i 网模型；文献 4 9 使用随机p e t r i 网方法建立了一个小型“客户机n 务器” 系统模型，并在指数型延时的假设下，对模型做了简单的分析。 ( 2 ) 使用p e t f i 网对网络中单个数据源的研究。文献( 5 4 使用p e t r i 网方法研究 了近似自相似流量的马尔可夫模型，并对一个处理自相似业务到达的简单队列系统 进行了研究。但由于模型中过多地引入了马尔可夫性质的假设，尽管分析过程得到 了一些简化，所生成的数据流并不具有明显的自相似性。 第4 页 南京理工大学硕士学位论文基于p e t r i 网方法的网络流量分析及仿真研究 1 5 论文的主要工作及研究内容安捧 目前，由于网络流量的自相似性已被普遍接受，时延服从指数分布的马尔可夫 随机p e t r i 网不再适用，因而在本文中，流量源发出数据的时问间隔采用其它类型 的分布，所以本论文的焦点集中于使用广义非马尔可夫随机p e t r i 网对网络流量进 行分析与仿真的问题。本文中首先建立两种不同网络的广义非马尔可夫随机p e t r i 网模型，分别为无限缓冲区的p 层网络模型和有限缓冲区的以太网模型，并对这 两种模型做了尽可能的理论分析；由于理论分析方法的不完善，仿真研究是必需的， 在本课题的研究过程中，针对研究的特殊需要而设计了一款简单的广义非马尔可夫 随机p e t r i 网仿真软件，并使用该软件对o n o f f 流量源以及上述的两种模型进行 了仿真研究。 论文内容安排如下： 第2 章，详细介绍p e t r i 网的基本概念、性质和分析方法，以及与本文研究密 切相关的随机p e t r i 稠的概念及分析方法。 第3 章，介绍随机过程，特别是自相似随机过程的基本知识，最后给出自相似 流量的几种重要建模方法。 第4 章，使用p e t r i 网分别建立无限缓冲区口层网络模型和有限缓冲区以太网 模型，并对两种模型进行基于状态空间和基于不变量的分析。 第5 章，首先介绍用于本课题研究的p e t r i 网仿真软件的设计方法，接下来使 用所编制的仿真程序对不同参数下的o n o f f 流量源模型的性能作了比较，最后对 第4 章中所建立的两种模型进行仿真，并根据仿真的统计数据得出近似的结论。 第5 页 南京理工大学硕士学位论文 基于p e t f i 咧方法的网络流量分析及仿真研究 2p e t r i 网 在本文绪论中已对p e 廿i 网做了简单地介绍，本章详细介绍p e t r i 及其高级形 式一随机p e t r i 网的基本概念、性质以及分析方法。 2 1p e t r i 髓筒介 2 1 。1p e t r i 嘲的基本概念 定义2 i t 5 6 l 一个最典型的p e 撕网可以表示为一系列元素集的组合： p n = ( p , t , f , w , m ，m 。) ， ( 2 ，1 1 ) 其中p = p 1 ，p ：，p 。) 是有限位置节点集，n 为位置节点个数；t 兰 t ，f ：。，) 是有限变 迁节点集，m 为变迁节点个数；p n t = 庐；f 是有向弧集，它包括两部分，即从p 到t 的输入弧与从t 到p 的输出弧；w 是有向弧的权函数集；m 是状态标识，m 。 是初始状态标识。 p e t f i 网还拥有图形化的表现方法，即p e t r i 网图，图2 1 就是一个简单的典型 p e t r i 网图。 q 价 一 图2 ，lp e t r i 网图示例 在图中，圆圈表示位置节点；竖线表示变迁节点；有向弧表明了位置和变迁之 间的输入与输出关系；如果一条弧由一个位置节点指向一个变迁节点，则称该位置 为这个变迁的输入位置，弧称为输入弧：如果一条弧由一个变迁节点指向一个位置 节点，则称该位置为这个变迁的输出位置，弧称为输出弧；圆圈中的小黑点被称为 令牌“o k e n ) ；状态标识m 被定义为一个向量m = 【，l ( p ，) ，m ( p ：) ，m ( p 。) r ，m ( p f ) 为当前状态下位置p ，中的令牌数。 2 1 2p e t r i 网的运行 以上定义的是p e t r i 网的静态结构，p e t r i 网的动态特性是在其运行过程中体现 出来的。在p e t r i 网的运行过程中，令牌将被作为一种资源来传递，输入位置中的 令牌将减少，输出位置中将增加。 p e t r i 网中的个变迁节点t 被认为是具有发射权或称为使能的，如果其满足如 p c t f i 网 硕士论文 下的条件： ( a ) 对变迁t 的每一个输入位置p ，) ，位置中包含的令牌数m ( p 。) 不少于对 应有向弧( p i , f ) 的权重w ( p ，t ) ，即m ( p f ) w ( p ，t ) ； ( b ) 对变迁t 的每一个输出位置，位置的容量k ( p j ) 足够再加入新的令牌，即 k ( p 。) m ( p ；) + w ( f ，p 。) ，其中m ( p ；) 为位置p ；中包含的令牌数，w ( t ，p ：) 为有向弧 ( f p ；) 的权； ( c ) 对变迁t 的每一个既为输入又为输出的位置p 。l ( t ) c 、o ( t ) ，位置p ，同时 满足上述两个关系式，即位置p 。的容量k ( p ：) m ( p f ) + w ( t ，p j ) ，m ( p ) w ( p i ，r ) 。 如果以上条件都满足，变迁t 将执行“发射”动作，实现令牌的转移。发射后 令牌的转移服从以下规则： ( a ) 从变迁节点t 的各个输入位置中减去令牌，而且： 减去的令牌数= 各输入位置至变迁节点t 的输入有向弧的权； ( b ) 在变迁节点t 的各个输出位置中加入令牌，而且： 增加的令牌数= 变迁节点t 至各输出位置的输出有向弧的权。 所以，在变迁节点t 完成发射后，位置p 的状态标识即令牌数r e ( p ) 将按如下规 则变化到新的令牌数t n ( p ) ： m ( p ) = m ( p ) 一w ( p ，t ) p 6 ，o ) ，p 硭o ( t ) m ( p ) + w ( ，p )p 0 ( 帅匹m ) ( 2 1 2 1 m ( p ) 一w ( p ，t ) + w ( t ，p ) p i ( t ) n o ( t ) m ( p ) o m e 脂 p e t r i 网之所以可以用来模拟离散事件系统，关键就在于其动态特性，即其可运 行性，各个变迁的触发既可有严密的逻辑关系，又可完全地相互独立。依据变迁和 令牌的不同形式和特性，从基本p e t r i 网又可扩展出很多新型p e t r i 网，比如本文 后面将要经常提到的随机p e t r i 网就是在变迁中引入了随机的延时。 2 1 3p e t r i 网的基瘁性质 ( 1 ) 可达性5 团 定义2 2 l 对给定初始标识为m o 的一个p e t r i 网( n ，) ，可达集r ( n ，) 定 义为此p e t r i 网在初始状态标识m 。下按照发射规则可到达的所有状态标识的集合。 可达性是研究p e t f i 网时所关注的最基本盼和最重要的性质，是基于状态空间 分析方法的基础。 ( 2 ) 有界性1 5 6 】 定义2 3 ：对给定初始标识m 。的一个p e u i 网( n ，m o ) ，如果对任一可达状态标识 r ( n ，m o ) 和任一位置节点p ：，相应于状态标识m 下的p e t r i 网，位置节点p ，中 第8 页 南京理工大学硕士学位论文基于p e t r i 网方 去的网络流量分析及仿真研究 的令牌数满足m ( n ) k ，其中k 为有限正整数，称此p e t r i 网为k 一有界的a ( 3 ) 安全性1 州 定义2 4 ：对给定初始标识m 0 的一个p e t r i 网( n ，? t 。) ，如果对任一可达状态标识 mr ( n ，i t 。) 和任一位置节点p 。，相应于状态标识m 下的p e t r i 网，位置节点p 。中 的令牌数满足m ( p 。) s 1 ，称此p e t f i 网为安全的。 ( 4 ) 活性0 5 6 1 定义2 5 ：对给定初始标识r n 。的一个p e t r i 网( n ，m o ) ，如果对任一可达状态标识 m r ( n ，r r 。) ，都可找到一个发射序列，在由此导出的新令牌分布m + 下可使某个变 迁节点t 为使能，称其此变迁节点t 是活的：如果该p e t r i 网( n ，m 。) 中每一个变 迁节点都是活的，则称此p e t r i 网是活的。 ( 5 ) 死锁临。1 定义2 ，6 对给定初始标识m n 的一个p e t r i 网( n ，m o ) ，如果对任一可达状态标识 m r ( n ，m 。) ，某变迁节点t 都不具有发射权，则称此节点死锁。 ( 6 ) 冲突5 卿 定义2 7 ：对给定初始标识扰。的一个p e t r i 网( n ，r n 。) ，冲突是指这样一种现象， 如果p e 砸网的两个或多个变迁节点同时处于使能即具有发射权的状况，但由于共 享某些输入位置节点，使一个变迁的发射导致另一个变迁的不能发射。 2 1 4 随机p e t r i 网 在本课题中要把p e 缸网与网络信息流相联系，必然要引入时间的概念且与随 机过程有关，基本p e m 网只具有平面的结构，要想引入时间的概念，就要使用一 种高级的p e t r i 网一随机p e t r i 网，它是本课题研究的重要内容。 在连续时间随机p e t r i 两中，一个变迁从可发射到发射需要延时，这个延时被 看成是一个随机变量z 。，且服从某种分布函数( ( x ) = p ( 五x 。在不同类型的随机 p e t d 网中，这个分布函数的定义不同。 如果分布函数满足：f = l - e ，即此分布为负指数分布，其中的旯表示了变 迁的平均发射速率。由于指数分布时延的无记忆性，所以一个随机p e t r i 网的状态 空间和马尔可夫链等同，这样的随机p e t r i 网也称为m a r k o v i a ns t o c h a s t i cp e t r i 网， 即马尔可夫随机p e t f i 网，特别她，一个k 有界的随机p e t r i 网，状态空间等同于一 个有限马尔可夫链，从而可使分析过程得到很大的简化，为了对随机p e t r i 网进行 分析，需要同时应用基本形式p e t r i 网的分析方法和马尔可夫链的分析方法。 一般情况下，所说的随机p e u i 网均指这种变迁的发射延时服从指数分布的p e t r i 网；而在很多情况下，变迁的延时不是这样简单，可麓是服从其它类型的延时，这 样的p e t r i 网称为非马尔可夫随机p e t r i 网( n o n m a r k o v i a ns t o c h a s t i cp e mn e t ) ，如 第9 页 p e t r i 网 硕士论文 果其中还包含瞬时变迁，此称为广义非马尔可夫随机p e t r i 网，它的状态空间不可 以简单地使用马尔可夫链来同构，对它的分析比较复杂，甚至有可能得不到明确的 解析解及稳态概率。 2 1 5p e t r i 网示倒 p e t r i 网是一种基于图论的方法，有一定的抽象性，为助于理解，本节使用p e t r i 网建立一个典型的排队网络模型，详细讲解p e t r i 网各种基本元素在其中代表的意 义。 图2 ，2 单输入单月务中心排队网络的p e t r i 阿模型 如图2 2 所示，这是个经典的单输入单服务中心排队网络模型，这种模型曾 经是用来研究网络中流量的普遍标准，假定输入的“顾客”即流量的到达是一个泊 松过程，到达的时间间隔服从指数分布，而“顾客”的离开即数据的转发时间间隔 也服从指数型的分布。 图中共有三个位置节点和两个变迁节点。两变迁节点的发射均有延时，且延时 长度服从指数分布，所以这是一个随机p e u i 网模型。流量单位以令牌来表示，只和 互代表输入，昱代表排队缓冲区，五代表服务台，只是流量输出地。初始状态下， 只中占有一个令牌，正处于使能态，经过指数型的延时之后，互发射，令牌由一 个变为两个，一个进入排队缓冲区巴，而另一个回到只，使互的使能条件继续满 足，扶而构成一个无穷数据源：进入昱的令牌即在其孛等待服务台乃的处理，经 过指数型的延时之后，疋发射，完成服务，将数据转发至b 。 在这个简单的模型中，显然五和疋都有机会发射，因而网是活的：所有由置和 五发出的流量最后都要到达b ，只要此p e t r i 网模型运行的时间足够长，只中的令 牌数目将无限上升，因此网是无界的，不安全的。 2 2p e t r i 瞬的分析方法 2 2 1 基本p e t r i 同的分析方法 对于基本p e t r i 网的分析主要有两种方法，是基于可达性的分析，二是基于 不变量的分析。 2 2 1 。l 基于可达性的分析 第1 0 页 南京理工大学硕士学位论文 基于p e t r i 网方法的网络流量分析及仿真研究 前面已经介绍过可达性的概念，现在把这一概念作一些扩展，首先介绍可达图 的概念： 定义2 8 1 5 6 ：对给定初始标识川。的一个p e t r i 网( n ，m o ) ，把从初始状态标识开 始，能够达到的所有可能的标识以及产生这些标识的变迁用一个图形表示，图中的 节点为状态标识，节点之间用表示变迁的带箭头的线戴弧连接，带箭头的线起端所 连接的标识，通过由该线所代表的变迁的激发，产生该线末端所连接的标识，这样 的图称为可达图。 若p e t r i 网是无界的或p e t f i 网所描述的系统具有无限个状态，则可达树将无限 扩展，为此，引入覆盖性的概念，用有限表达式来表现无限可达树： 定义2 9 【5 明：若v p p ：( p ) 溉( p ) ，则标识m 2 覆盖n ，表示为m 2 m 。 有了“覆盖性”的定义，可构造覆盖树，用于在有限的树形结构中表示无限的 可达树。首先引入符号翻表示“准无限大”，用于表示任意大的令牌数，它有以下 性质( k 是任意正数) ：k m ( p ) 成立的p ：用仞取代m ( p ) ；以t n 为一节点，从m 至m 画一有向线， 并将其记为t ，并将m 记为“n e w ”； ( 5 ) 除去m 的“n e w ”标志，回到步骤( 2 ) 。 对于图2 2 所示的模型，其覆盖树如图2 3 所示，设状态标识m 。= ( 1 ，0 ，0 ) ， m j = ( 1 ，翻，0 ) ，m ：= ( 1 岔，) ，则其可达图如图2 4 所示。 通过基于可达树的分析，可以对p e z r i 网模型可能达到的所有状态有清楚的了 解，对于本节中所使用的模型来说，系统离开m 0 状态之后将很快处于m ，状态并且 不再返回，这正是网络中的实际情况，排队网络在工作一段时问之后中，也必然进 入相对的稳态。 2 2 1 2 基于不变量的分析 基于不变量的分析是一种依据简单的线性代数方程来研究p e t r i 网性能的方法。 在介绍这种方法之前，先引入关联矩阵的概念； 设p e t f i 网包含n 个位置节点和丑1 个变迁节点，则其关联矩阵d 是一个i i l 行n 第l l 页 p e t f i 网 硕士论文 列的矩阵。设略是关联矩阵d 的元素，其中i 2 1 ，2 ，m ，j = l ，2 ，n ，且略必 为整数，其数值和正负反映了p e t f i 嘲中第j 个位置节点和第i 个变迁节点间的关 联状况，并且：如果“d u = 0 ”，表示“从位置p ，g u 杰迁t ；不存在有向弧”；如果“d d 2 一w ”，表示“位置p ，是变迁的输入，且有向弧的权为w ”：如果“d = w ”，表示 “位置p ，是变迁的输出，且有向弧的权为w ”。 ( 1 ，0 ，0 ) ii ( 1 ，脚，0 ) 。 ( 1 ，翻，o ) ( 1 甜翻) i i 互i 疋 ( 1 ，翻，0 9 ) 圈2 32 l5 节p e m 网模型的覆盖树 圈2 42 1 5 节p e t r i 网模型的可达图 对于给定p e t r i 网的关联矩阵d ，基于其元d 的含义，可导出元d 。的关系式为： iw ( p ，t ，) p j ( ) ，p 芒d ( i ) 铲 一w ( p j , t 冀p ，p 苫篡篱嚣 渊， 9 l i ) + w ( r i ，)p f 0 0 i ) r l f ( 岛) 、 l 0 o t h e r s 其中j ( ) 为变迁节点t 。的输入位置集合，o ( ) 为变迁节点的输出位置集合。 为引入不变量的概念，首先介绍p e t r i 网的状态方程： 定义2 1 0 l 给定包含n 个位置节点和m 个变迁节点的一个p e t r i 网，d 是其关联矩 阵，他为一个已知状态标识，帆+ ，为经过一次运行之后的状态标识( 次运行就是 南京理工大学硕士学位论文基于p e m 网方法的网络流量分析及仿真研究 激发一个变迁序列) ，x 为激发记数向量，它是一个( m t l ) 向量 在这一次运动中变迁t 的激发次数，有如下方程： m t “2 m k + d u t ，k 0 其第i 个元素表示 下面介绍不变量，不变量分为p 不变量和t 不变量，定义分别为： 定义2 1 1 ：一个p 不变量为一( n + 1 ) 非负整数向量x ，并满足： x 7 d = 0 而一个t 不变量是个( m + 1 ) 的非负向量y ，并满足： d ) ，= 0 将式( 2 ，2 2 ) 两边左乘，得n x 7 + l = ，+ x r c u t 。由( 2 3 3 ) 有 一，+ l = x 1 玳t ，k 0 特别地，从k = 0 开始递推有： ( 2 ，2 2 ) f 2 2 3 ) ( 2 2 4 ) ( 2 2 5 ) x r r = ，强= x 7 m ，= 一= ，m = 常数，即 工7 m = x t = 常数( 2 2 、6 ) 上式表明由p 不变量加权的所有位置节点中令牌数之和为常数，或者说，p 不 变量的非0 元素是相应的位置节点中令牌数的权值，使得在任何从可达的m 下 所有位置中的令牌数加权之和为常数，称这些位置节点被p 不变量覆盖。 假设通过激发某一变迁序列，p e t r i 网从初始标识又回到初始标识。由式( 2 2 2 ) 得： 掰o = t o + c u ( 2 2 7 ) 必有c u = 0 ，因此，u 为一t 不变量，即y = u ，这表明t 不变量中的非负元素 为将p e t r i 网的标识从出发经一系列变化而返回m 。的变迁序列中相应的变迁激发 的次数。但是，t 不变量中并不表明这些变迁激发的先后次序。 p e t r i 网的不变量不是唯一的，我们称那些不是其他不变量线性组合的不变量为 基本不变量。若关联矩阵d 的秩为r = r a n k ( 1 ) ) ，则其有( n r ) 个基本p 不变量和( m r ) 个基本t 不变量。 不变量可用于分析p e z r i 网的某些性能。比妇，若p e t r i 翮的每一位置节点都被 p 不变量覆盖，则p e t r i 网是有界的，而t 不变量则是使p e u i 网回到初始状态的 变迁序列。 2 2 2 髓：机p e t r i 嗣的分析方- i 去 这里所指的随机p e t r i 网是指一般的马尔可夫随机p e t r i 网，对于非马尔可夫随 机p e t r i 网的分析技术到现在还没有形成统一而成熟的方法，虽然已有人提出过一 些方法，但都有一定的局限性，并不通用，只能适用于某些特定模型。对于马尔可 夫随机p e t r i 网的分析技术虽然不能解决非马尔可夫随机p e t r i 网的问题，但是有 第1 3 页 p e t n 丽颈士论文 定的参考价值，所以在这里仍然有必要做简单的介绍。 对于随机p e t r i 网的分析要比对于一般p e t r i 网的分析复杂一些，但要以般的 分析方法为基础，先建立起模型的可达图，再得到相应的马尔可夫链并就此进行分 析。所以最后是把问题转化为马尔可夫链的问题，采用随机p e w i 网方法的优点是 其简化了马尔可夫链的产生，尽管仍然要面对着问题的巨大维度，但是随机p e t r i 网仍提供了所研究系统的更紧凑更具逻辑性的描述。 对随机p e t r i 网模型分析的最终目的是得到可达图中各状态存在的稳态概率， 分析的具体步骤如下： ( 1 ) 建立系统的p e t r i 网模型，并将指数分布时延与变迁关联； ( 2 ) 将所有状态作标记，如、n 、m ：、m 州，q 是状态的总数，产生 可达图r ( r a o ) ，将图中的每一弧都给定该弧所对应的变迁的激发率五，从而得到连 续时间马尔可夫链； ( 3 ) 使用各变迁的激发率构造连续时间马尔可夫链的转移率矩阵q ，根据经典 随机过程的处理方法，即可得到任一时刻系统处于任一状态的概率。( 具体内容参 见本文3 1 5 节) 2 。3 本章小结 本章详细介绍了p e t r i 网，重点介绍基本p e t r i 网的概念、分类、性质和分析方 法，并初步讨论了与本课题研究相关的随机p e 血网及其基本分析方法。 第1 4 页 南京理工大学硕士学位论文基于p e t r i 网方法的网络流量分析及仿真研究 3 网络流量建模 本课题使用p e t r i 网方法来研究网络中的流量特性。作为建模、分析与仿真的 基础，本章介绍随机过程，特剐是自相似随机过程的基本知识，最后给出自相似性 流量的几种重要建模方法。 本章内容安排如下：第一节介绍随机过程的基础知识；第二节弓 入鲁相似性的 概念，并介绍长相关过程与重尾过程两种与自相似性密切相关的随机过程：第三节 介绍如何产生具有自相似性质的流量。 3 1 1 随机过程的几个基本概念 定义3 1 l 设对每一个参数t e t ，x 心国) 是一随机交量，称随机变量族x ，= x ( t ，0 3 ) ， t e t ) 为一随机过程，其中t 是一实数集，称为指标集。( t d 可能取值的全体所构 成的集合称为状态空间。 参数t t 般表示时间或空间。参数t 常用的有三种：( 1 ) z = n o = ( 0 ，1 ，2 ， ， ( 2 ) 五= z = ，一2 , - 1 ，o ，1 ，2 ，) ，( 3 ) 瓦= 【a ，b ，其中a 可以取一一或o ，b 可以取 + 一。当t 取可列集( z 或e ) 时，通常称坼为随机序列。 定义3 2 ；设 x ( t ，纠) ，t e t ) 是一随机过程，为了刻画它的概率特征，通常用至q 随机 过程的均值函数、方差函数、协方差函数( 相关函数) 以及有限维分布函数族及特征 函数等概念： ( 1 ) 均值函数：随机过程 x ( l 删) ，t t 的均值函数定义为 m ( t ) = e ( x ( t ) ) ( 3 1 1 ) ( 2 ) 方差函数：随机过程i x ( t , 脚) ，t et ) 的方差函数定义为 d ( t ) = e ( x ( t ) 一m ( t ) ) 2 )( 3 1 2 ) ( 3 ) 协方差函数：随机过程 x ( t c o ) ，t t 的协方差函数定义为 r ( s ，0 = c o y ( x ( s ) ，x ( t ) )( 3 1 3 ) ( 4 ) 相关函数：随机过程 x 代脚) ，t t 的相关函数定义为 晰，皇等器磊铲 ， ( 5 ) 有限维分布族：设( n 为任意整数) ，记 f ( ，t 2 ，2 n ；x l ，而x n ) = p ( x ( t 1 ) x a ，x ( t 2 ) x 2 x ( ) 曼) ， 其全体 f ( q ，t 2 ，j 。；玉，而， 。) ，t l ，t 2 ，t ，n 1 )( 3 1 5 ) 第1 5 页 网络流量建模 硕士论文 称为随机过程的有限维分布族。 3 1 2 随机过程的分樊5 9 随机过程x ，= x ( t ，翻) ，t t ) 按其概率特征，可以分为阻下几类： ( 1 ) 独立增量过程 定义3 3 t 对1 t 2 f 。，t j t ，1 s f s n ，若增量 x ( t i ) ，x ( t 2 ) - x ( t a ) ，x ( t 3 ) 一x ( t 2 ) ，x ( “) 一x ( 0 一。) 相互独立，则称 x ( t ，删) ，t t ) 为独立增量过程。若对一切0 5 t ) 取值的概率与过去状态x 。( 5 r ) 取值无关，或简单地说，己知现在，将来与过去无 关( 条件独立) ，则称此性质为马尔可夫性( 无后效性) 。具有这种性质的过程称为马 尔可夫过程。 定义3 4 1 随机过程( x ( t ，0 9 ) ，t t ) ，若对任意f 1 t t 。 t ，五，1s i n ，及 a cr ，总有 p ( x 。a i x ；i = x l ，x ；2 = x 2 ，x 。= 工n ) = p ( x 。ea l x 。= 矗) ， ( 3 1 6 ) 则称此过程为马尔可夫过程，简称马氏过程。 称p ( s ，x ；t ，a ) = p ( x ，a i x ，= 动( j 0 ，( x 儿，x ，x 。)