（信号与信息处理专业论文）网络自相拟业务产生的研究.pdf

电子科技大学硕士毕业论文 摘要 现行网络业务的测试和分析表明：已有模型在描述实际网络业务时，忽略了 业务中一个重要的特性一一自相似性。实际上，网络业务采用“自相似”或“分 形”模型更适合于描述网络业务的真实情况。另外，随着研究的不断深入，需要 一种可控的主动自相似业务源，这样既可以提高研究的效率，也可以摆脱被动测 量带来的不确定性。 本文对现有自相似模型进行了深入研究，著用计算机进行了仿真验证，并运 用模型分析网络业务的合并与分解及网络视频业务。也对自相似业务的产生原因 做出了初步的解释。 论文第二章在给出了自相似序列数学的定义，并给出了其在数学与物理上的 一些特征，其后介绍了怎样检测一个序列是否是自相似的，并对各种检测方法进 行了扼要的比较。 研究自相似序列的合并和分解，有利于理解自相似性对网络性能的影响。第 四章在一定程度上解决了这些问题。另外，还利用模型进行了带宽分配、接入控 制、业务预报方面的工作。 实际网络业务里现出长相关的特性，但对于目前网络业务的主体，就其单个 业务来看，是具有短相关特性的。为什么多路这类业务在网络传输过程中会导致 自相似的特性，第五章对其原因给出了初步的解释。 关键词：自相似；长相关；h u r s t 参数 塑竺i 塑型些丝主竺盟! 壅一 a b s t r a c t m a n ym e 鹊u r e m e m sf r o mt h ew o r kp a c k e tn e t w o r k sh a v eb e e nc o l l e c t e da n d a n a l y z e di nt h ep a s ts e v e r a ly e a r s t h e s es t u d i e sp r o v et h a tt r a d i t i o n a lm o d e l sn e g l e c t a ni m p o r t a n c ec h a r a c t e r i s t i c - - s e l f - s i m i l a r i t y i nf a c t ，t h et r a f f i cm o d e l sw h i c hh a v e l o n g - r a n g ed e p e n d e n c e a l em o r es u i t a b l ef o rd e s c r i b i n gt h e r e a l l yt r a f f i cp r o c e s s ，s u c h a st h es e l f - s i m i l a ro rf r a e t a lm o d e l m o r e o v e r , w en e e da1 ( i n do ft r a f f i cm o d e l st l l a t c a nb ec o n t r o l e df r e e l yi nt h er e a s e a r c h w cn o to n l yc a ni n c r e a s et h ee f f i c i e n c y ，b u t a l s oc a n g e ta w a y f r o mt h e p a s s i v ei n d e t e r m i n a t i o n i nt h ep a p e r ，s e l f - s i m i l a rt r a f f i cm o d e l sa r es t u d i e dd e e p l y t h e nw es i m u l a t et h e m o d e l sw i t h c o m p u t e r m o r e o v e r ，t h e t r a f f i cm o d e l sa r eu s e dt o a n a l y z e t h e a g g r e g a t i o na n dd e c o m p o s i t i o no ft h en e t w o r kt r a f f i c s ，e t c t h el a s t ，w ep r o p o s ea s t a n d p o i n to n t h e p h y s i c a lb a c k g r o u n do f t h e s e l f - s i m i l a rp h e n o m e n a i n c h a p t e r 2o f t h e p a p e r , w eg i v et h em a t h m a t i c d e f i n i t i o no fs e l f - s i m i l a rp r o c e s s ， g i v eo u ti t ss o m e c h a r a c t e r i s t i c so nt h em a t h e m a t i cw i t l lp h y s i c sa n di n t r o d u c eh o wt o e x a m i n et h ep r o c e s si fi ti st h es e l f - s i m i l a rp r o c e s s t h el a s t ，w ec o m p a r es o m e e x a m i n a t i o nm e t h o d s c o n c i s e l y i th a sa ni m p o r t a n tm e a n sf o r a g g r e g a t i o na n dd e c o m p o s i t i o no fs e l f - s i m i l a r p r o c e s s w er e s o l v et h e s ep r o b l e m si nac e r t a i nd e g r e ei nc h a p t e r4 m o r e o v e r ，w e m a k eu s eo ft h es e l f - s i m i l a rt r a f f i cm o d e l st oa l l o tn e t w o r kb a n d w i d t ha n df o r e c a s t n e t w o r kt r a f f i c s o m eo ft h et r a f f i c sh a v eb e e n p r o v e dt oh a v e t h ep r o p e r t yo f s e l f - s i m i l a r i t y b u t i nt h e r u n n i n gn e t w o r k ，t h em a i n l yp a y l o a dc a nb ed e s c r i b e db yt h es h o r t r a n g e d e p e n d e n tt r a f f i cm o d e ls u c c e s s f u l l y t h e nw h ym a n yo ft h es h o r t - r a n g ed e p e n d e n t t r a f f i ci nt h en e t w o r kc a ns h o ws e l f - s i m i l a r i t yi nt h en o d e 7 w h a t st h ep h y s i c a l b a c k g r o u n do f t h ep h e n o m e n a ? w ep r o p o s e as t a n d p o i n ti nc h a p t e r5 k e yw o r d s ：s e l f - s i m i l a r i t y ；l o n g r a n g ed e p e n d e n c e ；h u r s tp a r a m e t e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： ! 耋逵垒日期：矽够年多月，r 汨 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：这笸盎导师签名：量曼塾醯 日期：。跏7 年；月l o 日 电子科技大学硕士毕业论文 第一章绪论 对于自相似过程( s e l f s i m i l a rp r o c e s s e s ) 的研究开始于上世纪中叶。首先 是上世纪五十年代h e h u r s t 对水库储水量的研究i l 】。他发现当把储水量观测值 以时间为横坐标画成曲线时，当前一时间段的曲线性状总与若干年前的曲线间有 着惊人的相似之处。这种现象也在大气观测、棉花成交量等领域出现。随着对这 些现象的深入研究，人们进一步发现在很多看似随机的事件中存在着某种确定性 的成分，而简单的动力系统亦存在着无规则的复杂运动。从那时起，人们在许多 实验中都发现了它并且将它运用到包括天文学、地理学、电子学、化学以及环境 科学等众多领域中。其中研究自相似过程的开创性工作归于k o l m o g o r o v 及 m a n d e l b r o t 0 1 近年来，随着研究的不断深入，人们越来越关注这类过程。 对于网络自相似的研究始于1 9 8 7 年，从那时起d v w i l s o n 等开始使用一种 精密的网络监测设备，对b e l l c o r em o r r i sr d 中心( m r e ) 的若干个以太网中 的业务流进行了深入研究。“5 ”。其后，在1 9 8 9 年更将该设备的时间分辨率由 1 0 0 9 s 提高到2 0 a 6 ，并在随后的三年中进行了更为系统的研究分析。对他们所得 到的数百万个实际网络传输的数据包的统计分析表明，l a n 业务的统计特性是基 于泊松或贝努利过程的传统业务流模型所无法描述的，突出表现为突发没有明确 的长度，在不同的时间尺度下表现出相同的突发特性，业务是长相关的( l o n g r a n g ed e p e n d e n c 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 n p r o c e s s ) ，a r 过程等，这些模型只能处理短相关( s h o r tr a n g ed e p e n d e n c e ) 业务。 原有的模型对于网络流量控制、拥塞控制、排队性能的估计、包( 信元) 丢 失率的预测等方面过于乐观，导致理论与实际的巨大偏差，这就需要寻找一种新 的模型，对上述问题有较好的解决方案。由w e l e l a n d 与d y w i l s o n 等提出这 种特性更适于采用自相似模型来描述“1 。经过大量的实验研究与分析，自相似模 型较好的解决了上述问题。但由于自相似问题数学上固有的难度，目前的研究仍 以仿真测量和数值方法为主。 下面是用传统的模型p o s s i o n 模型、自相似( 分形) 模型与实际测量网络的 比较图，从下面的图形可以很清楚的知道，p o s s i o n 模型与真实的网络业务模型 有很大的差异，不适合于描述具有长相关特性的网络业务流，而用自相似( 分形) 模型却能较好的描述它。 电子科技大学硕士毕业论文 p o i 4 辫o n w 飞 n 训v v ， r 瑚r 糊霉_ 1 抽厂1 嘲弼r 飞 t i m eu n i t = 1 0 0s e c o n d s 图卜1 利用p o s s i o n 模型产生的数据与测量得到的网络数据在不同时间尺度下的示意图 2 &1罐广_嗣1罐r_1掣誊1燮，1_若i 螽_弋习_嗣广螂1嗣掣磊1，i掰，d挈 ，翻要j翅霹，乎置嘲翻曩1d擎 ，j銎1，d夏埘，型科戮2 州，n彳暑，l_jit t i _ j m 电子科技大学硕士毕业论文 f r 叠嚏嘲 油 呔 严 - 慨m j n j d t m eu n i t = 1 0 0s e e o n c l s ； 图1 2 实际网络测量络数据与利用f r a c t a l 模型产生的数据在不同时间尺度下的示意图 良鞠，i嘲罚，_墨两0z，磺翳，馨弼0i封譬置罐l翻蜀_，啪譬l， 崭_i1雉1篁1，斛广，越1r j麓1j署1，警&哪戮季 ，n胃暑o=，jt 皇王型垫丕堂堡主望些丝苎 一 第二章自相似的定义及其检测 在传统通信网( 如电话网) 业务中，常假设业务到达过程服从p o i s s o n 分布、 到达间隔服从负指数分布。在最初研究a t m 网络时，也曾采用过此模型。并且， 随着研究的深入引入了各种推广的p o i s s o n 过程和b e r n o u l l i 过程。这些模型的共 同特点是只存在短时相关性，即当时间尺度增加时，统计上单位时间内得到的信 元数将趋于白噪，其相关函数趋于0 函数。或者可以认为这些模型所表示的业务 流在各个时间尺度下具有不同的特性。而实际网络业务流的大量业务与这类模型 存在较大偏差。实际业务流在各个时间尺度下表现出相似的突发特性( 相关函数 上表现为长相关特性) 。因此，本文首先从自相似随机过程( 长相关过程) 开始介绍。 2 1 自相似的含义 分形( f r a c t a l ) 一词最早由美籍法国数学家芒特勃罗”1 ( b e n o i t b m a n d e l b r o t ) 于1 9 6 8 年提出。根据他本人解释，该词具有”支离破碎“、”极不 规则”的含义。他在研究海岸线等曲线时，发现这类极不光滑的曲线具有”自相似 性”，即取出该图形的任何一个部分，放大到原来的尺度后，所得的图形与原图 形惊人的相似。用不同的步长单位去测量这类曲线的长短，结果也不同，因为所 用的步长越小，图形的精细结构就越明显，曲线就显得越崎岖，因此总长度也越 大。进一步研究揭示了这类”病态图形”的另一个重要性质：它们是”分维”的，它 们的维数并非整数。最初人们对于这类既非线，又非面，也非体的几何图形无可 奈何，只好用”分形来形容它们。后来大家才发现，其实自然界广泛的存在着分 形的事物，”整形”的东西反而是一种特例。 分形论的自相似概念，最初指形态或结构的自相似性。也就是说，在形态或 结构上具有自相似性的几何对象称为分形。 如果一个对象是分形的或自相似的，进行合理的放大，其部分和整体的形状 是相近的。 由于在自然界、社会和思维领域广泛存在着分形现象“，这引起了分形的飞 速发展，自相似是分形的一个重要特征，对于时间序列，它表示在不同的时间尺 度下表现出相同的统计特性。 自从l e l a n d 对b e l l c o r e 的局域网的测试与分析结果发表后”，又有许多 针对其他网络的测量如w a n 。1 、v b r 。1 、视频会议“、f a s p a c “”等，这些结果均表 明实际网络业务流具有长时相关性。因此这些网络业务应采用能够表征长时相关 4 电子科技大学硕士毕业论文 性的模型，例如自相似过程模型。在信号处理中，我们也经常遇见一些具有长时 相关性的信号如分形信号( f r a c t a ls i g n a l ) 或l f 信号( 即功率谱为幂函数的形 式) 。从此自相似信号进入了网络业务分析中。 自相似的数学描述“ 设x ( t ) 是随机过程，r ( t ) 是该随机过程的相关函数。如果i 。r ( f ) = o o ，则 称x ( t ) 是长相关过程。物理意义是指x ( t ) 的当前值与它的所有历史有关。自相 似过程是长相关过程的一种简单模型“。它用二阶矩性质描述长相关过程，只需 要一个h 参数。该参数便于估计，而且能得到h 参数准确的置信区间。对于离 散函数，如果。，( 七) = o 。，则称x ( t ) 是长相关过程；相反，如果。r ( ) = c o 成立 或在频域内当五号c o ，o p 1 ，可等效表示为： 厂( 五) 2 - p 厶( 五) 其中f ( 2 ) 为谱密度函数，厶( 五) 为缓变函数。 ( 2 - 2 ) ( 2 - 3 ) 称满足上述条件( 2 2 ) 或( 2 - 3 ) 的过程是渐进自相似过程。 为了更好的理解自相似过程，下面给出几个比较重要的定义和定理“4 。“1 ： 定义1 广义平稳的离散随机过程 以) 。 ：一称为严格二阶自相似过程，且 电子科技大学硕士毕业论文 具有自相似系数( h u r s t 系数) h = i b 2 ，o b 1( 2 - 4 ) 定义2 称 墨”) 。 ：为 瓦 。圳1 2 的m 阶聚集过程，若： z ”= 以m ( 2 5 ) 它的自相关系数记为，“( ) 。 定义3 广义平稳的离散随机过程 以 。 ：称为渐近二阶自相似过程，且具 有自相似系数( h u r s t 系数) h = i b 2 ，0 b l ( 2 6 ) 定义4 广义平稳的离散随机过程 以 。 ：称为强渐近二阶自相似过程，且 具有自相似系数( h u r s t 系数) h = 卜b 2 ，0 b 1 ，如果它的自相关函数对任意k 1 均满足 熙等= c 。 ( 2 _ 7 ) 式中，c 为一常量。 定理1 m “1 若 以 。，l ：为一强渐近二阶自相似随机过程，自相似系数为 b ，则 l i m 罢：c l ( 2 - 9 ) ( 2 ) 以的m 阶叠加过程满足： v a r x ( ”) = 口2 m 一， ( 3 ) 以的谱密度函数满足： ( 2 1 0 ) s ( 厂) = e l p 2 彬- 1 1 2 1 i f + l p ( 2 1 1 ) f ； 对于以满足这三个条件中的任一条件的，则称以是自相似的，而且以上三 个命题等价。对于定理2 的证明，可以参考有关文献“”1 。 自相似参数h 又称为h u r s t 参数，是描述自相似特征的唯一参数。对于h 有 3 个不同物理意义的取值范围，o h l 2 表示负相关，i 2 0 ，令k = 1 ，对以r 为计数间隔，信号x 的n 个计数样 本施以正交小波变换，从最精细的尺度开始，依次取各个尺度，记j = l ，计算盯： 依下面公式估计在此分辨率下信号的h u r s t 参数 电子科技大学硕士毕业论文 c ：旦一一；r l _ 一 ( 2 一1 8 ) _ 一r a n ( m ) 丽 ” 求，满足如下方程的正根： 估计h u r s t 参数； c 。n ( m ) t ：r 2 ( k ) f l “= o ( 2 1 9 ) m - m r ( 七) = 1 0 9 2 ( | i ) + 1 2 ( 2 2 0 ) 令k = 七+ 1 ，a t = 2 ，获得序列x 新的n 个样本计数过程后进行正交小 波变换，计算；：( 露) ，根据定理3 和( 2 1 7 ) 式检验在( s ： 1 ，2 ，3 ，三 ) 各尺 度下h u r s t 参数的一致性，若v m s 有i 蠢一( 后一1 ) ；：( 七) 一0 5 1 占( j 为一致 检验偏差设定值，如占= 0 0 1 ) ，则认为新序列通过一致性检验，则转向。否则， 修正方差： 2 i 2a 2 盯f ( 七) = ( 1 一口) 盯，( 七) + 口仃t + l ( k - - 1 ) ，口( o ，1 ) o = 2 ，3 ，上) ( 2 2 1 ) ，= ，+ 1 ，对各尺度下方差序列进行移位： 巧( _ j ) = 吐，( k - 1 ) ( j = l + l ，) ( 2 2 2 ) 仃；( ) ：z ( ) ，2 ( ，：l ，2 ，) 重复一，直至i ( h ( k ) 一h ( k 1 ) ) 日( t ) l f ) f 1t 一，l a 2 ( 3 - 1 ) 即f “，口均服从p a r e t o 分布，具有有限均值= ( x ) f ) p ，t _ o 。有很大的不同，或 者说式( 3 1 ) 中的分布函数比负指数分布有更重的拖尾( h e a v yt a i l ) 。可以证明f 1 3 】， 当叠加的业务源个数趋于无穷时，总的业务是渐近自相似的，且满足 。口一1 ，h 2 ( 3 一a ) 2 。以上分析表明，突发业务处于突发状态的持续时间的分布 f 聿 电子科技大学硕士毕业论文 拖尾越重，其自相似系数越大。通常自相似业务的系数h 在o 5 到l 之间，表示 它在长时间尺度下具有正的相关结构，或者说当业务在前一时段处于突发状态时 它在后续时刻更可能持续其突发状态。 3 1 2 统计模型 统计模型是从其统计特性下表现出的性质( 长相关) 方面入手，建立模型， 进行仿真，这类模型比较精确和灵活，但没有明确的物理意义。 基于分形高斯噪声和分形布朗运动的业务生成方法 分形布朗运动( f r a c t i o n a lb r o w n i a nm o t i o n ，f b m ) 及分形高斯噪声( f r a c t i o n a l g a u s s i a nn o i s e ，f g n ) 是m a n d e r b r o t 2 8 】和v a n n e s s 于1 9 6 8 年提出的一种统计 自相似的数学模型，他同时也给出了自相似的产生方法。由此方法产生的自相似 业务称为分形布朗运动。 定义1 分形高斯噪声x = ( x k ，k = 0 ，l 2 ) 为一平稳高斯噪声，具有均值 = e ( 毪) ，方差盯2 = 研( 以一) 2 】，其自相关系数满足( 2 2 ) 式，可以证明： r ( k ) h ( 2 h 一1 ) k 2 “2 ，( k _ ，0 h 1 ) ，经过计算还可以得到，o 5 i 阶消失矩，即有 l t v ( t ) d t = o ，= o ，l ，r l ( 3 7 ) 电子科技大学硕士毕业论文 且小波系数 ) 是零均值互不相关的随机变量，具有方差 v a r 砰= 盯2 2 ，其中，参数y 满足o y 2 r ，则x ( t ) 具有时间平均谱 s a r o ) = 盯2 二。2 一”ig ( 2 1 c o ) 1 2 ( 3 8 ) r s ，( c o ) 是近似1 f 的或称广义l f 的，即： 口2 i r s a r o ) 盯2 。r ( 3 9 ) 其中，盯2 及盯2 。是满足0 盯2 l 盯2 。 o ) ( 3 1 5 ) 为了分析的方便我们经常采用一个参数的形式：f ( x 1 = l 一1 ( 1 + x ) 8 其相应的概率密度函数是：f ( x ) = a ( 1 + x ) ”1 。 很容易可以看出一个p a r e t o 分布存在k 阶矩，需要口 k 例如：o t l ，那么e ( x ) = 1 ( a - 1 ) ；口 2 ，那么e ( x 2 ) = 2 ( a 一1 ) 一2 ) 】。 因此无论是多大，一个p a r e t o 分布不可能有所有的矩，因此拉氏变换不存在。 ( 2 ) 韦伯分布 w e i b u l l 密度函数为： 厂( x ) = c 咿一4 x ( a - 1 ) e 0 7 4 7 ，( x ，口， o )( 3 1 6 ) 均值为：e ( x ) = f l f ( 1 l a ) l c t ， 方差为：v a r 【x 】= 卢2 e 2 f ( 2 a ) - f ( 1 a ) 2 l a l a 。这里r ( ) 是r 函数。 1 9 电子科技大学硕士毕业论文 本文以p a r e t o 分布的o n o f f 模型来产生自相似流。 根据前面的讨论，m 个o n o f f 数据源叠加后能够描述实际的网络业务流， o n 或者o f f 的长度的分布函数决定了叠加后业务流的相关性。我们在一台p c 机上，生成了m 个数据源叠加的业务流，然后测量了这些合成业务流的相关性。 由于用o n o f f 模型产生自相似业务流所固有的难度，我对其算法进行了近 似的处理： 1 对p a r e t o 分布进行截尾处理，因为在实际产生p a r e t o 分布序列时，会产 生少数的极大数；理论的重尾分布拥有无穷大的尾部，即，c d f 的x 可以取无穷 大，这显然不符合实际情况，因为文件或者传输时间的长度总是有上限，所以我 们需要引入截尾重尾分布( t r u n c a t e dh e a v y t a i l e dd i s t r i b u t i o n ) 也就是为x 规定 一个上限，如果x 的取值大于该上限就重新取值或者取它的上限，这样所有的x 都不会大于这个上限我们在实际中用的也是截尾重尾分布。 2 对o n o f f 源的个数只能取一个有限的值，而且目前由于条件的限制， 只能在微机上进行运算，考虑到运算速度的原因，我们取m = 5 0 个o n o f f 源进 行叠加。每个源的长度为2 0 0 0 0 个数值，计算时间大约为1 5 分钟。 下面列出了仿真的结果： 图3 1 所示口= 1 5 时，h = ( 3 一a ) 1 2 = 0 7 5 的自相似业务流。 t h er e s u l l 。f o m o 开m e t h o d 序3 1 j 的长度 图3 - 1 口= 1 5 时叠加产生的自相似业务流 分别采用v t 法和r s 法检测上述产生的自相似流的效果， 电子科技大学硕士毕业论文 图3 0 2 ( a ) v - t 法h = 0 7 6 9 3图3 - 2 ( b )r s 法= 0 7 2 5 6 从计算机仿真的结果来看，尽管不是尽如人意，但可以看出，其产生的自相 似业务流还是符合理论的推导的。 用o n o f f 模型的叠加产生的自相似可以解释产生自相似的一部分原因：经 检测发现，若文件大小符合重尾分布( p a r e t o 分布是重尾分布的一种) ，则对应 的文件传输均导致链路层的自相似性，而与所用的传输协议( 如w e b 、n f s 、f t p ) 等无关。这种模型包含明确物理意义，是其它模型无法具有的，它能帮助我们深 入地了解自相似的本质，可以更有针对性地在网络的特定层处理自相似问题。该 模型应用于队列分析中，取得了很好的效果果。缺点是：这种自相似业务只是渐 近自相似的，且需要m 个源( 晰寸o d ) 的叠加，而且建立模型的计算复杂度将 超过o ( n 2 ) 3 2 2f b m 与f g n 模型的实现 f b m 的概念最早由m a n d e l b r o t 提出，是一般布朗运动的“分形”扩展。 f b