（计算机应用技术专业论文）网络业务流建模的研究与应用.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 t e s ( t r a n s f o r m e x p a n d - s a m p l e 卜传输扩展采样过程在对宽带网络中的视频及其它 多媒体通信方式进行建模的过程中占有极其重要的地位。这种过程拥有一般边缘分布和宽 范围的自相关函数，是其他业务流模型不具备的。等效带宽理论指出，任意业务流都可以 用一个等效带宽值来刻画该业务流的流量大小，并可在实际中根据这个等效带宽值来给此 业务流分配相应的带宽。而t e s 过程作为一种业务流，也应具有相应的等效带宽。等效带 宽理论给出的等效带宽公式只有一个一般的等效带宽表达式，它并不适用于t e s 过程的等 效带宽的计算。为此，作者对t e s 和具有马尔可夫更新序列的扩展t e s 过程的等效带宽函 数进行了推导，并得到四个对应的等效带宽公式，并以t e s 过程为输入，对其排队系统进 行了仿真分析，证明了等效带宽公式的正确性。 本文所做工作除包括随机过程，矩阵论等数学工具的应用，还包括系统的t e s 建模理 论和等效带宽理论，涵盖内容广泛并且具有相当的复杂度，这些工作由于难度较大，就我 们所知是前人未曾做过的。同时，这些公式的提出，也为网络上的接纳控制和资源分配等 具体应用提供了可以有效利用的关键参数。 最后，我们将所得的理论结果应用于基于测量的接纳控制算法模型的仿真，说明了现 有的基于测量的接纳控制( m b a c ) 算法并不能获得稳定的丢包性能。在此基础上，我们利 用t e s 建模方法和t e s 的等效带宽公式，提出了一种基于t e s 模型的等效带宽分配算法，它 拥有稳定的丢包率，可以实现根据不同的q o s 等级接纳业务流或分配相应的带宽，是m b a c 算法所不具备的。之后，我们发现对于高0 0 s 等级的视频业务流，可以采用等效带宽的近 似方法来进一步降低算法的时间复杂度。 南京邮电大学硕士研究生学位论文 摘要 a b s t r a c t t e s ( t r a n s f o r m e x p a n d s a m p l e ) p r o c e s s e sa r ep a r t i c u l a r l yi m p o r t a n tf o rm o d e l i n g o fv i d e oa n do t h e rm u l t i m e d i at r a f f i cp a t t e r n sf o u n di nb r o a d b a n dn e t w o r k s s u c h p r o c e s s e sa r eh i g h l ya u t o c o r r e l a t e da n dh a v eg e n e r a lm a r g i n a ld is t r i b u t i o n s s u c h p r o c e s s e sh a v eg e n e r a lm a r g i n a ld i s t r i b u t i o na n db r o a dr a n g ea u t o c o r r e l a t i o n ， w h i c hi sd i f f e r e n tw i t ht h eo t h e rt r a f f i cm o d e l s t h et h e o r yo fe f f e c t i v e b a n d w i d t h sp o i n t so u tt h a tt h e r ei sae f f e c t i v eb a n d w i d t h sf o re a c ht r a f f i cs t r e a m t h a tc a nb ec h a r a c t e r i z e da se f f e c t i v el o a do ft h a tt r a f f i cs t e a m ，w h i c hc o u l d b eu s e da st h eb a s i so ft h er e s o u r c e sa l l o c a t i o np o l i c yo ft h en e t w o r k b e i n ga c e r t a i nk i n do ft r a f f i cs t r e a m ，t h et e sp r o c e s s e ss h o u l da l s oh a v et h ee f f e c t i v e b a n d w i d t h s h o w e v e r ，t h eg i v e ne x p r e s s i o no ft h ee f f e c t i v eb a n d w i d t h si so n l yo f au n i v e r s a lf o r m ，w h i c hc a nn o tb eu s e dt oc a l c u l a t et h ev a l u eo ft h et e sp r o c e s s e f f e c t i v eb a n d w i d t h s f o rt h i sc a u s e ，t h ea u t h o rd e r i v e st h ee f f e c t i v eb a n d w i d t h f u n c t i o nf o rt e sp r o c e s s e sa n dt h ee x t e n d e dt e sp r o c e s s e sw i t ham a r k o vc h a i n i n n o v a t i o ns e q u e n c e ，a n dg i v e so u tf o u rc o r r e s p o n d e de x p r e s s i o n so fe f f e c t i v e b a n d w i d t h sf u n c t i o n s w h a t sm o r e ，w es i m u l a t es o m eq u e u e sw i t hs u c ht e sp r o c e s s e sa si n p u t ，a n a l y s i s t h er e s u l t sa n dp r o v e dt h ec o r r e c t n e s so fi t w eu s et h er a n d o mp r o c e s st h e o r y a n dt h et h e o r yo fm a t r i xt oe x p l o r et h et h e o r yo ft e sm o d e li n ga n dt h et h e o r yo f e f f e c t i v eb a n d w i d t h s f o rt h eb r o a dr a n g et h a tt h ew o r ki n v o l v e da n dt h ec o m p l e x i t y o ft h es t u d y ，n oo n eh a se v e rd o n et h e s er e s e a r c h e sb e f o r et oo u rk n o w l e d g e m e a n w h i l e ，t h e s ef u n c t i o n sp r o v i d es o m ev a l i dk e y p a r a m e t e r sf o rt h ea p p l i c a t i o n s o fa d m i s s i o nc o n t r o la n dr e s o u r c e sa l l o c a t i o n a tl a s tw ea p p l yt h et h e o r yc o n c l u s i o nt ot h em o d e li n gs i m u l a t i o nf o rt h ea l g o r i t h m o fa d m is s i o nc o n t r o la n dp r o v et h a tt h ep e r f o r m a n c eo ft h ep a c k e tl o s sp r o b a b ili t y f o r m b a ca l g o r i t h mi sn o ts t a b l e b a s i n go nt h i s ，w ep r o p o s ea ne f f e c t i v eb a n d w i d t h a l l o c a t i o na l g o r i t h mb a s e do nt h et e sm o d e la c c o r d i n gt ot h em e t h o do ft h et e s m o d e l i n ga n dt h ee f f e c t i v eb a n d w i d t hf u n c t i o no ft h et e sp r o c e s s b e c a u s et h i s i l 南京邮电大学硕士研究生学位论文 a b s t r a c t a l g o r i t h mi ss t a b l ei nt h ep a c k e tl o s sp r o b a b i l i t y ，i ti sp o s s i b l et oa c c e p tt h e t r a f f i cs t r e a mo ra l l o c a t et h eb a n d w i d t ha c c o r d i n gt ot h ed i f f e r e n tq o sl e v e l ， w h e r e a si t sn o tp o s s i b l ef o rt h ep r e s e n tm b a ca l g o r i t h mt oa c h i e v et h i se f f o r t t h e r e a f t e r ，w ec o m et oac o n c l u s i o nt h a tf o rt h eh i g ho o sl e v e lt r a f f i cs t r e a m ， t h et i m ec o m p l e x i t yo ft h ea l g o r i t h mc a nb ed e g r a d e db yt h ea p p r o x i m a t em e t h o d o ft h ee f f e c ti r eb a n d w id t h i l l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：媪日期：拯越 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：燃导师签 醐：型爿 南京邮电大学 硕士学位论文摘要 学科、专业： 研究方向： 作 工学计算机应用技术 计算机通信与网间互连技术 者：2 0 0 4 级研究生余文斌指导教师沈苏彬 题目：网络业务流建模的研究与应用 英文题目：t h er e s e a r c ha n da p p l i c a t i o no nn e t w o r kt r a f f i c m o d e l i n g 主题词：业务流建模t e s 过程等效带宽排队系统 接纳控制带宽分配 k e y w o r d s ： t r a f f i cm o d e lt e sp r o c e s se f f e c t i v eb a n d w i d t h q u e u i n gs y s t e m a d m i s s i o nc o n t r o l b a n d w i d t ha l l o c a t i o n 南京邮电大学硕士研究生学位论文引言 引言 很长时间以来，网络流量的业务源都是用泊松过程来进行描述的。根据许多已有的马 尔可夫分析的结论和排队分析的一些基本方法，人们能够对以泊松流作为业务源的排队系 统进行深入的性能分析，并且得到等待时间，队列长度等性能参数的精确结论。同时，泊 松过程有着十分简单的相关结构，这使得泊松到达的排队系统具有十分广泛的应用。 随着网络业务类型不断增加，实际网络中业务流特性越来越复杂，表现为突发性、长 相关性或自相似性等。由于现有泊松过程传统业务流模型并不能完全反映当前告诉通信网 络业务流的特性，因此，业务流模型的研究一直是高速通信网络研究的焦点问题之一。 自从b e n j a m i n m e l a m e d 等人提出t e s ( t r a n s f o r m e x p a n d - s a m p l e 卜传输扩展采样 ( 以下文中都以t e s 表示) 过程以后，t e s 过程得到了不断的发展，成为模拟高速通信网络 业务流特征的主要的模型之一。经过这几十年的不断完善，t e s 模型越来越显示出它的优 越性，并在很多的领域取得了广泛的应用，如科研、机械、金融等领域。在网络业务流建 模方面，t e s 模型具有任意的边缘分布( 一维分布) ，和宽范围的自相关函数，这使得它 能较为完备的刻画实际业务流的统计特性。 等效带宽是对业务特征的一种描述，它决定了对于一个输入的业务流应该分配多少带 宽，以保证达到此业务流在缓存溢出概率和排队延迟等服务质量方面的要求。等效带宽已 经被应用于接纳控制和资源管理等方面。 一个业务流的等效带宽就是一个函数，该函数有两个分别代表空间和时间尺度的自由 变量。通常，我们将等效带宽函数考虑成时间变量趋于无穷时的极限形式，而只把它看作 空间变量的一元函数。对于平稳和遍历的过程，等效带宽函数的反函数( 即：给定的等效 带宽函数的空间参数值) 是以此过程作为一个排队系统的输入，并以此等效带宽作为系统 服务速率时的队列的队长尾概率 q u e u el e n g t ht a i lp r o b a b i l i t y 的渐近指数衰减率。空间参 数之所以这样命名，是因为它描绘了队长的渐近分布。通过用等效带宽函数来确定队列的 指数衰减率，我们可以很好的评估排队系统的性能。 推导出t e s 过程的等效带宽函数的解析形式，则可以在业务流建模过程中直接精确计 算其等效带宽值，而不是依靠经验的或是近似计算得到。这对研究网络中资源分配，接纳 控制等方面有很大的应用价值。为此，文中对t e s 及扩展t e s 过程的等效带宽公式进行了推 导，并对结果进行了仿真分析，以验证公式的正确性。 本文共分六章。第一章简述了几种现有的网络业务流模型，第二章概述了等效带宽理 1 南京邮电大学硕士研究生学位论文引言 论，第三章介绍t e s 业务流模型。第四章中，我们推导t t e s 以及扩展t e s 过程的等效带宽 公式，第五章中利用仿真分析证明了公式的正确性。第六章论述了等效带宽在接纳控制算 法中的应用。 2 南京邮电大学硕士研究生学位论文第一章网络业务流模型综述 第一章网络业务流模型综述 现代通信网络需要适应不同种类业务流的传输，从电话呼叫到视频和数据业务。因而 业务模型对通信网系统的性能分析，特别是网络的拥塞控制和容量评估，有着重要的影响。 传统的网络业务，由于其业务的性能单一，再生业务流模型、基于马尔可夫的业务 流模型和自回归类型的业务流模型等能准确的描述其特性，如i p p ( i n t e r r u p t e dp o i s s o n p r o c e s s ) t 1 1 、m m p p ( m a r k o vm o d u l a t e dp o i s s o np r o c e s s ) r i d 0 】、a r m a ( a u t o r e g r e s s i v em o v i n g a v e r a g em o d e l s ) 【l l 】等。这些模型均假设：当前时间t 与过去时间( t s ) ，若s 足够大，则t 时与( t s ) 时的业务流是不相关的，即仅仅考虑s 较小时业务之间的相关性，称之为短程相 关s r d ( s h o r t r a n g e d e p e n d e n t ) 模型。 随着新的网络业务的不断出现，当前通信网络的业务流越来越复杂，业务流的性能也 呈现出多样性。这就需要网络业务流模型能够捕获这些特征。自l e l a n d 对b e l l e o r e 的局 域网( l a n ) 的测试与分析结果发表后，又有许多研究工作针对其他网络，如 w a n f a s t p a c 等的策略，均表明实际业务流在很长的时间范围内都具有相关性，即业 务达到具有长程相关性l r d ( l o n g r a n g e d e p e n d e n t ) 1 2 , 1 3 】。t e s 模型、自相似与分形模型 等被认为更适合于描述当前的网络业务。业务流是通信网系统的内在行为表现，包括电话 呼叫、数据文件的传输、传送压缩视频帧到显示器件等。对业务流性能进行分析需要准确 的模型来捕获实际业务流的统计特征。 业务流由离散到达实体组成，数学上可以描述为点到达过程，由到达时刻序列 t 9 疋，瓦，组成，初始值瓦= o 。记数过程 ( f ) ) 二是连续时间非负整数值随机过程， n ( t ) = m a x f ：乙，) 是在时间区间( o ，) 内到达的业务请求的数目，到达的时间间隔过程 4 ) 二是实数值的序列，其中4 = 瓦一乙一。，因而存在关系式瓦= ：。4 ，可得 ( r ) = 疗 = 乙f 乙+ 。 = ：，4s f 己心n + l 以 。以下概述了通信网络中几类主要的业 务流模型。 1 1 再生业务流模型 由于数学上的分析比较简单，再生业务流模型很早就被研究并加以应用。但是再生模 型有一个指明的缺陷，所有非零滞后相关函数皆为零。现代通信网络中，正的自相关函数 在很大程度上能够揭示业务流的突发现象，而突发性是宽带网中的普遍现象。在排队系统 中，突发性将引起再生过程性能测量的不准确【1 4 】。泊松过程是一种典型的再生过程【1 5 1 。 泊松过程有一些分析上的优越性，首先，独立泊松过程的叠加产生新的泊松过程，即泊松 3 雨京邮电大学硕士研究生学位论文第一章网络业务流模型综述 过程的可加性；第二，泊松过程的无记忆性；第三，在应用泊松过程分析业务流性能时， 可以假设服从泊松过程的业务流物理上是由大量独立的十分普通的业务流组成，这对业务 流的分析是一个很大的优势。柏努利过程( b e m o u l l ip r o c e s s e s ) 和阶段相位再生过程 ( p h a s e t y p er e n e w a lp r o c e s s e s ) 也是典型的再生过程。 1 2 基于马尔可夫过程的业务流模型 与再生模型不同，马尔可夫业务流模型为随机序列 a 引入了相关性，因而由于 a ) 中非零自相关函数的存在，我们可以捕获业务流的突发性，马尔可夫过程将来的状态仅仅 依赖目前的状态，而与以前的状态无关，在一个简单的马尔可夫业务流模型中，马尔可夫 过程的每一跳都可以理解为信号的一次到达，因而到达时间间隔是指数分布的。o n o f f 模型广泛应用于语音业务的建模【l o 16 1 。业务流仅仅在o n 状态产生。i p p ( i n t e r r u p t e dp o i s s o n p r o c e s s ) t l 】过程也是一种两状态过程，业务流到达仅仅以服从参数名的泊松分布出现在 a c t i v e 状态。m m p p ( m a r k o v - m o d u l a t e dp o i s s o np r o c e s s e s ) 模型是调制马尔可夫模型中应 用最为广泛的一种模型。它能对语音和数据业务进行混合建模。m m p p 过程的参数能够 很容易得到。流体业务流模型 1 7 , 1 8 d p 把业务流看成一个以一定流率传输的流体，因而业务 流的数目以流体容量代替。流体业务流模型适用于业务流单元和尺度相关的情况。个体业 务流自身的性能并不重要。流体业务流模型的一个重要优点是其概念的简单易懂性。马尔 可夫调制流体模型( m a r k o v m o d u l a t e df l u i dm o d e l s ) 是流体业务流模型的一个典型应用。文 献【1 7 ，1 8 】中是该模型在v b r 压缩视频业务建模中的具体应用。马尔可夫过程类模型一般 具有负指数下降的自相关性质，不能描述长时相关性。较适合理论分析。 1 3 自回归a r ( a u t or e g r e s s i v e ) 类型的业务流模型 自回归类模型定义下一个变量作为前一个变量的一个明确的函数。这样的模型特别适 合于对v b r 压缩视频业务流进行建模。视频帧的本质是在一个视频内连续帧之间的变化 非常小，仅仅在视频发生改变时，能引起帧尺寸发生突发性的改变。a r o ) 模型是最早被 提出来的压缩视频业务模型之一【9 】。文【1 9 】中比较了a r ( 1 ) 模型和a r ( 2 ) 模型，认为a r ( 2 ) 模型比a r ( 1 ) 好些，但都不能产生足够多的大信元数帧。d a r ( d i s c r e t ea u t o r e g r e s s i v e ) u 模型是产生离散变量的静态序列，其自相关结构与a r 相似。但是它们都不能捕获业务流 的长相关性。而且在静态建模过程中需要进行大量参数的评估，因而评估效率很低。 a r m a ( a u t o r e g r e s s i v em o v i n g a v e r a g em o d e l s ) 很好地克服这个问题。文 11 】研究了a r m a 模型在v b r 业务流建模中的应用。但是a r m a 只能描述业务流的短相关，与a r 模型一 样，也不能捕获业务流的长相关性。 4 南京邮电大学硕士研究生学位论文第一章网络业务流模型综述 1 4 自相似业务流模型 近年来，通过对l a n 数据和v b r 业务等高速网络中的大量业务的精确测量发现， 这些业务中普遍存在自相似性 2 6 , 2 7 ，2 引，与业务发生的时间地点或信源编码方式无关。这提 示我们，在描述网络的突发业务传输中，采用自相似模型比传统的m a r k o v 模型更接近实 际业务的特性。 对比前面几类业务流模型的静态建模特征，自相似业务流模型的建模方式则是动态 的。生成自相似业务流的过程主要有分形高斯噪声和分形布朗运动的业务生成方法【2 0 1 。分 形高斯噪声x = ( 五，k = o ，1 ，2 ，) 为平稳高斯噪声，具有均值a = e 【五】，方差 矿= e ( 五一) 2 ，其自相关函数满足式，( 尼) = 丢 ( 尼+ 1 ) t m2 k t m + ( 七一1 ) 2 的形式。经 过计算还可以得到，0 日 0 为方差系数， 矽为标准的分形布朗运动并且满足h ( o 5 ，1 ) 。除了前面提到的两种自相似业务源的生成 方法外，还有一些其它的业务生成方法，包括基于分形a p o m a ( p ，d ，q ) 过程t 2 1 】的业务生成方 法、基于混沌映射 2 2 1 的业务生成方法、直接叠加具有重尾( h e v e y t a i l ) 特性的o n o f f 业务源、利用m g 排队模型和利用逆小波变换方法等等。 1 5t e s ( t r a n s f o r m e x p a n d s a m p l e ) 业务流模型 t e s 建模方法的产生的最初动机是为了捕获业务流的突发性【1 3 】。t e s 过程是一个具 有任意边缘分布和很宽范围自相关函数的自相关序列。它能够产生各种各样的取样路径 ( 包括循环和任意方向) 并具有各种形式( 如单调，振荡) 的自相关函数。假设有一些静 态时间序列，建立一个t e s 模型需同时达到三个目标。，( 1 ) 模型的边缘分布与时间序列 的边缘分布相匹配；( 2 ) 模型的自相关函数与时间序列的自相关函数相匹配；( 3 ) 取样路 径应与时间序列的取样路径相似。可以用解析式准确地描述业务流模型的边缘分布和自相 关函数是t e s 过程的重要性质，它为业务流量的理论研究方面提供了便利的工具，这是 前述的各种模型所没有的。t e s 提出后得到了广泛的应用。目前的许多研究与应用中， 业务流的自相关函数很复杂，如非指数下降( 包含长相关性) 或者周期性尖峰( m p e g ) 等，以前的许多模型无能为力，而t e s 却能对此进行较好的处理。文【1 2 讲述了t e s 模 南京邮电大学硕士研究生学位论文 第一苹网络业务流模型综述 型的广泛应用。 1 6 本章小结 在本章中，我们简述了现阶段网络业务流建模的研究进展，并分别介绍了再生业务流 模型，基于马尔可夫过程的业务流模型，自回归a r 类模型，自相似业务流模型，论述了 它们相应的建模特点。最后，我们介绍了在本文中加以研究与应用的t e s 业务流模型。在 第三章我们还要重点介绍t e s 建模理论与应用。 6 南京邮电大学硕士研究生学位论文 第二章等效带宽( e f f e c t i v eb a n d w i d t h s ) 理论 第二章等效带宽( e f f e c t i v eb a n d w i d t h s ) 理论 2 1 等效带宽 研究业务流模型，在于找到网络业务流量的特性规律，其目的是为了合理分配有限的 网络资源，通过配置和管理实现最优的网络性能。因此，需要寻求特征参数来表征实际业 务流量的特性，并以此为据进行网络带宽资源的分配。而等效带宽正是这样一种可以刻画 业务流流量的特征参数。 在任何多路复用系统中，由于存在多个数据流共享同一个公用输出端口，所以需要确 定每个给定的数据流在此系统中占用多少资源。这个复用器可以是一个输出容量为c 的 缓存，其中存放着多个不同的数据流。 掌握每个链接所需要的资源情况可以直接应用于接纳控制( c a c ) 和计费。事实上， 当系统资源足够多时，一个新的链接请求才可能被接受，而该链接的价格则应该同它所占 有的资源多少成比例。 对于所需要的资源有两个明显的限制：为每个连接保留峰值速率将导致确定的复用方 式，不会丢包而带宽利用率很低。同时，为每个连接保留平均速率则将导致1 0 0 的链路 利用率和不可避免的丢包。这样，在给定的q o s ( 丢包率) 下，实际应该为每个连接保 留的资源就处在峰值速率和平均速率之间，这样的资源一般则被命名为业务流的等效带 宽。而对于等效带宽的实际估算主要来源于大偏差理论的结果。 k e l l y 在文 3 】中给出的关于等效带宽的一个非常好的结果，如下所述。 令x ( f ) 为一个平稳增量过程，z o ，】表示在时间间隔【o ，】内从数据源发送来的数据 总量。则，此数据源的等效带宽为 口( = 去l 。g e ( g 州0 吖) ，o z ) o ) 。 而平均速率口( o ，f ) ，( s 专o ) 和峰值速率口( ，t ) ，( s 寸) 分别为等效带宽口( 占，f ) 的下界 和上界。若令f 专，则口( s ) = l ，一i r a 口( s ，f ) 为无限时间尺度上的等效带宽函数。 2 2 等效带宽的应用 接下来我们给出一个实例，以说明上述的等效带宽是如何应用于接纳控制，成为接纳 控制的简单而有效的基础。 设一个资源接受了1 ，2 ，个链接请求，假设资源测得第f 个链接在，时间段内的负载 量z 【f ，r + t 】，记( q ，6 j ) 代表第f 个链接请求被接受时由用户选定的对应于链接f 的系数 ( 口( 乙) ，6 ( 刁) ) ，并令r = e x p ( 【r ，f + f 】) 。则该资源的有效负载量为： ( 口+ 岛r ) 于是可以如下定义一个接纳控制：当一个新的链接请求到达资源时，如果该资源最近计算 的有效负载量低于某个阈值则接受此请求，如果高于某个阈值则拒绝此请求，同时，还应 保证，如果当前链接请求被拒绝，则其后到来的链接请求也都要被拒绝，直到有一个已有 的链接终断为止。 2 3 本章小结 本章主要介绍了等效带宽的提出，具体给出了它的概念、定义和性质，列举了等效带 宦理论在接纳控制等方面的基本应用。接下来将介绍t e s 模型。 8 南京邮电大学硕士研究生学位论文第三章t e s 模型简介 第三章t e s 模型简介 3 1 模型简介 t e s ( t r a n s f o r m - e x p a n d - s a m p l e ) 是为具有一般边缘分布和宽范围的自相关函数的时 间序列建模的一种通用方法。边缘分布和自相关函数既可以通过实验数据来估计，也可以 通过理论模型给定。对于任何给定的边缘分布和自相关函数，t e s 可以产生一个随机变 量序列，使其能够精确地匹配边缘分布函数，并且也非常接近于自相关函数。通过t e s 而生成的一个随机变量序列就称为一个t e s 过程。 一个t e s 过程可以是一个t e s + 、t e s 一过程或者是一个具有马尔可夫链更新序列的扩 展t e s 过程。一个t e s + 过程主要具有正l a g 一1 的自相关性，而t e s 过程具有负l a g 一1 的自 相关性。如果在具有突发性的业务流过程中存在着某种结构，则可以用- b 尔可夫链更新序 列来描述这种结构。 设 乙：刀= o ，i ，2 ， 代表一个t e s 过程。这个过程可以代表在视频流业务建模中的视 频帧序列大小。为了便于阅读本文，文中的表达式都以类似于文 4 中的方式而组织， w = ( 鼎) ，篡 圻= 。一u w + n9 ，n 刀= ：e 。v 彩e n ，, d ( ) = 巧1 ( 名( ) ) 忍( ) 是乙的边缘概率分布函数，( ) 是模1 运算符，( ) 是缝合函数，u o 是在【o ，1 ) 中 间的连续均匀分布随机变量， 圪：玎= l ，2 ，) 是可以在( 删，0 0 ) 区间任意分布的更新序列。 值得注意的是，无论圪具有何种分布， “ 的边缘分布总是在区间【o ，1 ) 上的均匀分布。 但是，圪的分布和缝合转化一起决定了 “) 和 乙) 的自相关结构。当更新序列是一个独 立同分布( i i d ) 的随机变量序列时，若乙= d ( w ) 则为t e s + 过程，乙= d ( w ) 则为t e s 过程。当更新序列是一个- - q 尔可夫链时，相应的过程就是一个扩展的t e s 过程，其自相关 函数范围更广。 9 南京邮电大学硕士研究生学位论文第三章t e s 模型简介 3 2t e s 建模应用 t e s 已被应用于旨在探寻较好的关于视频帧大小序列的数学模型的视频业务的建模。 一般来说，来自数据源的视频帧大小是具有自相关性的。自相关性对于一个排队系统的性 能具有很大影响。因此，对于视频业务的精确建模不仅需要捕捉其视频帧序列大小的边缘 分布函数，更重要的是还要捕捉其自相关函数的特征。t e s 是能够同时完成这两者的方 便工具。 下面简介一个t e s 建模软件应用的实例。业务流的t e s 建模软件设计如图3 1 所示， 可分为业务流的测量、t e s 模型的建立和建模过程中的统计特性的分析等三个模块。该模 型根据实际测得的业务流的数据序列自动的建立业务流的t e s 模型，然后用t e s 方法分 析该模型的统计特性。 3 2 1 业务流测量 图3 1 模型的总体流程图 图3 2 业务流测量模块流程图 业务流测量模块的主要功能，如图3 2 所示，当接受到业务流的时间序列 儡，攻，以 时，先调用m a t l a b 的h i s t 指令可以画出时间序列的概率直方图，再求出分布函数h ； 基于分布函数h ，调用m a t l a b 中的f i n v e r s e 指令可求得分布函数的反函数h 1 。 1 0 南京邮电大学硕士研究生学位论文 第三章t e s 模型简介 3 2 2t e s 模型建立 伪随机序列修正序列背景序列扭曲前景序列 、 1 ， ，、 、r、 k氙 kx五 ： 缝 ， 艺 合 l h 。l五 ) j r ： r 函 数 ll j 、7。 图3 3t e s 模型建立模块流程图 如图3 3 所示，t e s 模型建立模块主要功能有： ( 1 ) m a t l a b 里面的r a n d 指令产生伪随机序列，满足了 乙 是在区间【o ，1 】间的均匀 分布； ( 2 ) 根据一定的修正序列密度工，来得出修正序列值巧【一o 5 ，0 5 】。其中工是一个阶 梯密度，圪是作为k 定义在【厶，r 】上的均匀分布变量的综合，其中混合概率为丑，【厶，r 】 满足咣厶也； ( 3 ) 选择t e s 的类型，我们可以得到前景序列玑； ( 4 ) 扭曲模块分为两个子模块：一个是缝合模块，一个是业务流输入模块。逢合参数f 的选择，表示了对背景序列的平滑程度。把缝合模块的输出值作为业务流输出的时间序列 的分布函数的反函数的自变量，从而得出前景序列瓦。 3 2 3 统计特性分析 统计特性分析模块的主要功能，是对经过t e s 方法处理的时间序列数据的统计特性 进行分析，据此对t e s 模型进行调整，以达到更好的效果。具体简述如下： ( 1 ) 画出前台序列的统计特性图，如取样路径、概率直方图、自相关函数等。取样路 1 1 雨京邮电大学硕士研究生学位论文 第三章t e s 模型简介 径运p l o t 指令即可得到，概率直方图则可由h i s t 指令完成，而自相关函数有a u t o e o r r 指令 实现，自相关函数图形的准确性可由现成的自相关函数公式进行验证； ( 2 ) 把时间序列的统计特性图与前台序列的统计特性图进行叠加； ( 3 ) 由统计特性图可以看出模型的设计性能如何，如果相应的自相关函数和取样路径 不是很匹配，就要重新回到3 2 2 节，主要是对参数工、善的重新选择。对修正序列阶梯 密度的选择，开始于k = i ，若不能达到效果，则选择k = 2 ，如此，逐渐增大，直到找到 满足要求的最小的k 为止。 由上可知，t e s 建模的关键是对合适的缝合参数善的选择以及对修正序列密度工的 启发式方案的选定。启发式方案并不意味参数选择的盲目性。它是基于如下几个原则进行 从：( a ) 修正密度越大，自相关函数的数量级越低；( b ) 修正密度关于原点越不对称，取 样路径和自相关函数越易产生波动；( c ) 善是为了平滑取样路径而设的，当孝由两边向o 5 靠近时，自相关函数的数量级将随着增加。模型的设计是基于视觉反馈的，为了使模型的 自相关函数和取样路径满足需求，使用者不断地调整参数可能循环到前面任一步。这种启 发式的设计完全由使用者自行控制，使用者需要足够的耐心。当然，也可以用自适应滤波 的方法代替视觉反馈，这种算法是基于最小均方误差准则的。 3 3 本章小结 本章介绍了t e s 建模理论的思想方法和t e s 过程的概念。t e s 过程可以分为t e s + 过 程、t e s 一过程，和具有马尔可夫链更新序列的扩展t e s 过程。它们的数学描述略有不同， 但都具有任意的边缘分布函数和宽范围的自相关函数。在此基础上，本章还列举了以 m a t l a b 设计t e s 建模软件的应用实例。在下文，我们将要利用第二章的等效带宽理论， 对t e s 过程的等效带宽函数的解析形式进行推导，以方便研究t e s 过程的流量特性。 1 2 南京邮电大学硕士研究生学位论文第四章t e s 以及扩展t e s 过程的等效带宽公式 第四章t e s 以及扩展t e s 过程的等效带宽公式 t e s ( t r a n s f o r m e x p a n d s 锄p l e ) 传输扩展采样过程在对宽带网络中的视频及其 它多媒体通信方式进行建模的过程中占有极其重要的地位。这种过程拥有一般边缘分布和 宽范围的自相关函数，是其他业务流模型不具备的。等效带宽理论指出，任意业务流都可 以用一个等效带宽值来刻画该业务流的流量大小，并可在实际中根据这个等效带宽值来给 此业务流分配相应的带宽。而t e s 过程作为一种重要的业务流，也应具有相应的等效带 宽。已有的等效带宽理论给出的是一个一般的等效带宽表达式，形式如下： 峭) 去l o g e ( p 匹：而) 该表达式是一个概念性的定义式，只能一般性地描述业务流过程的等效带宽，并不能具体 地给出业务流过程的实际等效带宽值，因此有必要推导t e s 过程的等效带宽公式。鉴于 此，作者对t e s 和具有马尔可夫更新序列的扩展t e s 过程的等效带宽函数进行了推导， 并得到四个对应的等效带宽公式。基本过程如下：首先观察上面的等效带宽定义式，注意 到该表达式中包涵着一个对业务流各个时间分量的求和，这在数学上是难以处理的，所以 我们需要对求和式进行变换，以期获得数学上易于处理的形式。好在我们可以利用t e s 业务流的各个时间分量的递推公式和过程的平稳性对求和式进行变换，得到一个新的求和 式 拍一吲1 哪( p 匹。降万o ) 屯( 以七) = 忑1 - ! ) g e ( p k 帕+ l 靠i 口= 击) 此时我们借助随机过程中条件概率的方法，以及矩阵论中矩阵构造的方法，将求和构 造成矩阵相乘，使它变得易于计算，化解了求解过程中的难题，从而得到了最终的等效带 宽公式。推导包括有效时间范围的t e s 过程的等效带宽和无限时间范围的t e s 过程的等效 带宽两部分，具体过程如下。 4 1 有限时间范围等效带宽的推导 根据文 3 】中给出的定义，z ：力= 0 ，1 ，) 在k 个单位时间的有限时间范围内的等效带 宽为， 南京邮电大学硕士研究生学位论文第四章t e s 以及扩展t e s 过程的等效带宽公式 口( 啪) = 忑11 0 9 层( p 残知) 。 ( 4 1 ) 为 获得t e s 辽程阴寺双市苋，找们口j 以布f j 用又【9 j 甲q t e s 阴万法采j ；匪导( 4 1 ) 薹j - - 种方便解。我们首先将单位间隔【。，1 ) 离散为整数m 个等间隔 。，击) ， 击，云) ，和 号，1 ) 。这样原来的t e s 过程的更新序列概率密度函数也被离散为 屯= 剥i = 0 巧 ，+ 秘等) ， ， ll o h “ j 其中：丸= 1 ，m = 0 ，1 ，m l 。假设 以：胛= j ，2 ， 为一独立同分布的离散随机变 量序列，使 p ( 以= 署) = 九 朋= o ，1o , m 一1 ，此时即为一个q t e s 更新序列。而自相关的马尔可夫链更新序列将在第 4 3 节中讨论。 接下来我们定义另外一个离散随机变量序列f g ：刀= 0 , 1 ，2 ，l 女n - f ： g = 0 的矩阵a o 相似于，与随机阵户的乘积，即 1 8 南京邮电大学硕士研究生学位论文 第四章t e s 以及扩展t e s 过程的等效带宽公式 其中矩阵z = 讲昭【z ，拦， 么= z ) 中z 一1 r p ：! z a z 。由命题，有 彳：，z p 。z 一1 而p 是一个随机矩阵，故也是一个随机矩阵。 容易证明矩阵日+ 是不可约的和非负的，矩阵日+ q ，d h + g 。d 也是如此。令 ，= p ( 日+ e ，。日+ q 。) 为其谱半径，即以；= ( 而，z 2 ，锄) o 为特征向量的矩阵圩+ q ，d h + q d 的最大特征值。 则 h + q p 日+ q ，d = r z w z 一， 其中矩阵z =