（应用数学专业论文）基于阈交理论的自相似网络业务控制研究.pdf

中文摘要 随着计算机通讯业务的曰益发展，提供业务服务质量保证( q o s ) 成为一个重 要的研究方向，而网络拥塞检测和控制是保证( q o s ) 的关键技术在网络业务性 能评价的研究过程中，网络业务传统模型如f l u i d - f l o w 模型、p a c k e t - t r a i n 模型、 m a r k o v 。m o d u l a t e dp o i s s o n 过程、批到达m a r k o v 过程等所描述的业务序列具有短 时相关性( s h o r tr a n g ed e p e n d e n c e ) ，当时间标度增加时，统计上单位时间内到达 的数据包将趋于白噪声近年来，各国研究人员对以太网业务和v b r 视频业务 的研究结果表明：实际网络业务普遍存在统计上的自相似性，具有长相关性( 1 0 n g r a n g ed e d e n d e n c e ) 由于传统业务模型描述能力的欠缺，他们引入了如分数布朗 运动、f a r i m a 过程等模型，d u 蚯e l d 提出了在长相关业务f b m 下应用大偏差 ( l a r g ed e v i z t i o n ) 分析队列长度尾分布性质的方法但由于其业务模型相当复 杂，这使得基于业务模型预报的网络控制因计算的繁杂而变得相当困难 由于网络性能评价中，通过优化带宽分配解决拥塞和溢出等问题时，我们更 关心的是网络业务超出某一阈值的情况，而阈值以下的业务显然与要解决的问题 关系不大因此我们提出采用阈交的方法，该方法可以不考虑业务的概率分布， 避开业务模型数学处理的困难，是一种可行的新方法作为一种阈交问题，有关 阀值选取的研究是重要的通过对阈值选取的研究，我们就可以在一定范围内近 似估计出网络业务到达这一随机数据超阈值部分在整体网络随机数据中所占的 比例，及其对网络拥塞的影响，从而使网络业务在保证服务质量的同时尽可能的 减少缓存区，以达到节省空间的目的，实现合理的资源配置 本文提出采用方差分析的方法构造一个阈值的能量函数，并研究了超阈值能 量函数的性质并以p a u g t l i s ( 3 0 0 0 多个数据) 和p a u g t l 1 0 0 ( 3 0 0 0 0 多个数据) 为例进行实证分析，进而得出规律，为阈值的选取提供一定的依据 在此基础上，我们进行了阈交理论应用于网络控制的可行性研究，并与基于 预报的控制理论进行对比，结果表明该理论可以更好的满足实时控制的要求同 时我们还给出基于阈交理论的一个动态带宽分配算法，以完成对实际业务进行实 时控制的目的 关键词：闽交问题 网络控制 阈值穿越强度可行性研究 动态带宽分配算法 a b s t r a c t p r o v i d i n gt h eq u a l i t yo fs e r v i c e ( q o s ) h a sb e c o m e a l li m p o r t a n tr e s e a r c hf i e l d w i t l lt h ed e v e l o p m e n to fn e t w o r kc o m m u n i c a t i o i l s n e t w o r kc o n g e s t i o n d e t e c t i o na n d c o n t r o li so n eo f t h em a j o r a p p r o a c h e si np r o v i d i n gq o s t r a d i t i o n a l l y , m a n yc o m p l i c a t e d s t o c h a s t i cm o d e l s ，w h i c hd i s c r i b et h es h o r t r a n g ed e p e n d e n c e ，w e r ei n t r o d u c e dt o m o d e lt h en e t w o r kt r 碰c ，s u c ha sp o i s s o n p r o c e s s ，t h ef l u i d f l o wm o d e l ，t h ep a c k e t - t r a i nm o d e l ，t h em a r k o v - m o d u l a t e d p o i s s o n p r o c e s s ，t h eb a t c h a r r i v a lm a r k o vp r o c e s s ；a n ds oo n t h r o t l g ht h es t u d yo f n e t w o r k t r a f f i c ，r e s e a r c h e r ss h o w e dt h a t t h en e t w o r kt r a f f i c a c t u a l l y h a s s e l f - s i m i l a r i t y s t a t i s t i c a l l ya n dl o n gr a n g ed e p e n d e n c e r e c e n t l yf b mp r e s e n t e db yd u 伍e l da n d f a r i m a p r o v i d eab e t t e rw a y i nm o d e l i n g 也en e t w o r kt r a f f i c t r a i 五cp r e d i c t i o n a n d a d m i s s i o nc o n t r 0 1 h o w e v e r , t h e s em o d e l sa r et o oc o m p l i c a t e dt ob eu s e dp r a c t i c a l l y , w h i c hm a k e si td i 伍c u l tt oc o n d u c tn e t w o r kt r a f f i cc o n t r o lb a s e do nn c t w o r kt r a f f i c p r e d i c t i o nd u e t ot h ec o m p u t a t i o n a lc o m p l e x i t y o p t i m i z i n g t h eb a n d w i d t ha l l o c a t i o na n da d m i s s i o nc o n t r o la r eo f t e nu s e dt oe a s e t h en e t w o r kt r a f f i cc o n g e s t i o na n dt h i n sp r o v i d eq u a l i t yo fs e r v i c e t 0d os o w ea r e m o r ei n t e r e s t e di nt h en e t w o r kt r a f f i c st h a te x c e e ds o m et h r e s h o l dv a l u e a n dp a yl e s s a t t e n t i o nt o 也en e t w o r kt r a f f i cb e l o wt h et h r e s h o l dv a l u es i n c es u c ht r a f f i cd o e sn o t c a u s em u c hd i 伍c u l t y i nn e t w o r k t r a f f i cc o n t r 0 1 w e p r o p o s e af c a s i b l e t h r e s h o l d c r o s s i n gm e t h o dt h a td o e sn o tt a k et h es t a t i s t i cd i s t r i b u t i o no f t h en e t w o r k t r a f f i ci n t oa c c o u n t , a n da v o i d sm em a t h e m a t i c a ld i f f i c u l t yi np r o c e s s i n gp r e v i o u s m o d e l s t h es e l e c t i o no ft h et h r e s h o l dv a l u ei sc r i t i c a lh e r ef o rt h et h r e s h o l d c r o s s i n g m e t h o d t h r o u g h t h es t u d yo ft h et h r e s h o l ds e l e c t i o n w ec a ne s t i m a t et h ep r o p o r t i o n o f 也ea r r i v a lt r a f f i ct h a te x c e e d st h et h r e s h o l dv a l h e a n di t si m p a c to nn e t w o r k c o n g e s t i o n t h i sc a n b eu s e dt oe s t i m a t et h eb u f f e rs i z en e e d e di ns t o r i n gu n p r o c e s s e d p a c k e t si np r o v i d i n gt h eq u a l i t yo f s e r v i c e s p e c i f i c a l l y , w ed e s i g n a ne n e r g yf u n c t i o no ft h et h r e s h o l d u s i n gv a r i a n c e a n a l y s i sf o rh i g h s p e e dn e t w o r kt r a f f i c w ec o n d u c te x t e n s i v ea n a l y s i so ft h ed a t a p a u g t l l s ( 3 0 0 0 d a t ai t e m s ) a n dp a u g t l l 0 0 ( 3 0 ，0 0 0d a t ai t e m s ) f r o mb e l l c o r e ，w e o b t a i ns o m er e g u l a r i t yi ns u c ht r a f f i c s ，w h i c h p r o v i d e s t h eb a s i sf o rt h r e s h o l d s e l e c t i o n b a s e do nt h r e s h o l d - c r o s s i n gm e t h o d ，w es t u d i e dt h ef e a s i b i l i t yf o rn e t w o r k c o n t r 0 1 o u rm e a s u r e m e n ta n da n a l y s i ss h o w 也a ti ti s p o s s i b l e t o c o m p u t et h e t h r e s h o l dv a l u ei nas h o r tt i m e a n dt h e nw ed i s c u s s e dh o wt oa l l o c a t ed y n a m i c a l l y b u f f e r sb yt h r e s h o l dc r o s s i n gm e t h o d ，a n d g a v et h ea r i t h m e t i c k e yw o r d s ： t h r e s h o l dc o r s s i n gm e t h o d ， c r o s s i n gm t e n s i r y , t h r e s h o l dv a l u e ， n e t o r e kc o n t r o l ， f e a s i b i l i t ys t u d y d y n a m i c a lb u f f e r sa l l o c a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得垂壅盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：柳订吲 签字日期：也j年，月牛日 学位论文版权使用授权书 本学位论女作者完全了解鑫鲞盘鲎有关保留、使用学位论文的规定。 特授权苤鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：和1 7 谮砂， 签字日期：h 弓年，月牛日 导师签名： 纠杀1 乞 签字日期：2 剑) 年f l 月c 7 f 日 天津大学硕士学位论文第一章序论 第一章序论 近年来，计算机网络特别是i n t e m e t 的发展速度倍受关注从i n t e m e t ， i n t r a n e t 到e x t r a n e t ；由e d i ，e c o m m e r c e 到e m e d i a ，e b a y 和智能岛，到处是网 络之潮国内的计算机厂商和电信厂商都开始转向计算机网络，国外的厂商在网 络大潮下更是纷纷进军网络市场网络是新纪信息产业的机会和挑战，我们必须 抓住这个机会，发展相关技术，提高科技水平与实力 与此同时，研究人员、相关的研究组织和标准化机构对网络研究投入极大热 情，产生了很多研究成果本章将介绍网络业务预报与控制技术的研究情况和作 者的研究工作 第一节飞速发展的网络 数学作为自然科学的基础科学经过了漫长的发展时期，但是其理论体系的形 成与高速发展是在近3 0 0 年完成的其他科学的理论体系形成也经过了较长的 时期科学学的研究表明【i l ，科学知识的发展速度成指数形式，越现代的科学发 展速度越快计算机科学经过几十年的发展，已经初具规模计算机学科从发展 的初期就是直接由社会需求推动的由于美苏军备竞赛的需要，冯诺依曼等研 制了电子计算机；i n t e m e t 的雏形a r p a n e t 同样是为了满足美国军事部门的需要， 随着技术的发展计算机和计算机网络走向社会、走向商业商业目标与用户需求 成为计算机和网络技术发展的主要动力 数学、电子学、材料科学的发展为计算机技术的飞速发展提供了坚实基础， 商业的推动大大加快了其发展速度，使得计算机科学与技术的发展获得了前所未 有的高速微处理器按照所谓摩尔定律的速度发展，而网络的发展速度比摩尔定 律还要快得多网络用户与网络应用呈爆炸性增长，新的网络技术层出不穷： ( 1 ) 局域网技术由共享的1 0 m b p s 发展到1 g b p s 以上经过几年的发展，局 域网由共享的1 0 m b p s ，发展为交换式1 0 m b p s ，再发展为1 0 0 m b p s ，现在1 0 0 0 m b p s 网已经成为成熟的产品网络带宽的迅速提高为宽带网络应用提供了可能，也使 得网络业务测量和控制变得困难 天津大学硕士学位论文 第一章序论 ( 2 ) a t m 等b i s d n 技术开始得到广泛使用，国外服务商已向用户提供宽带 网络接入服务，并提供v o d 等新型业务，使得网络业务统计性质发生变化 f 3 、在i po v e ra t m ，m p o a 等技术基础上，m p l s 2 】经过发展成为行业标准， 为业务分析和控制提出新课题 f 4 ) 各种新型网络传输和接入技术迅速发展，c i s c o 等公司已经开始使用i p o v e rs d h s o n e t 技术，正在进行i po v e rf i b e r 的研究l u c e n t 等开展了密集波 分多路复用( d w d m ) 等技术的研究这些新技术的采用将影响未来业务的行为 与控制方式 ( 5 ) 新型网络协议的发展目前的i n t e m e t 网络协议只支持尽量递交服务， 不能提供服务质量保证，而且在不同协议层次重复进行纠错等操作，协议的效率 较低针对传统协议的问题，研究人员提出r s v p 3 1 等协议 ( 6 ) 随着网络技术的发展，网络业务的构成也在发生变化网络业务已经由 e m a i l 和f t p 为主转向w w w 和视频等业务占主要成分 ( 7 ) i e t f 的i n t s e r v 工作组，提出了d i f f s e r v 4 1 d i f f s e r v 是i e t f 在q o s 领域 所做的最新尝试，它避免了高复杂性目前，d i f f s e l w 仍在不断发展，其相关概 念，模型的定义大多处于讨论阶段到现在为止，d i f f e r v 的体系结构己比较明 晰，在此基础上有关服务提供的相关问题，包括服务定义、设置、管理等细节也 在逐步清晰化 尽管网络研究人员针对现有网络技术，特别是现有的i n t e r a c t 技术的不足之 处进行了许多改进，但是无法在原有技术基础上解决网络地址空闯不足、缺乏对 服务质量的控制等根本性问题为了解决这些问题，美国政府和一些大学与研究 机构提出并开始实行新的i n t e m e t 研究计划，这些计划主要有i n t e m e t 2 、n g i 、 v b n s 等，其目标是研究新一代高速、确保服务质量的网络技术 第二节网络业务的自相似性 1 2 1 网络业务自相似性的发现 随着宽带网络服务需求的激增，国内外研究人员围绕高速网络的业务拥塞控 带l j ( c o n g e s t i o nc o n t r 0 1 ) 、带宽分配( b a n d w i d ma l l o c a t i o n ) 、呼叫准入控制f c a l l a d m i s s i o nc o n t r 0 1 ) 永l 网络性能评价开展了大量工作，其中建立能够准确描述网络 业务的行为的模型是所有这些研究工作的基础网络业务模型及其性能评价是 网络研究的重要基础和步骤，一直受到研究人员的关注 天津大学硕士学位论文第一章序论 计算机网络性能评价是由电话网络的评价技术发展起来的1 0 0 多年前，天 才的工程师e r l a n g 为了计算电话交换机的容量与阻塞概率等关系式，在相应的 概率论理论还不完善的条件下，提出了e r l a n g 公式，并且一直应用于电话网络 的规划等方面传统的话务模型常假定业务达到过程为p o i s s o n 过程，到达间隔 服从指数分布 六七十年代，a r p a n e t 开始发展，以l k l e i n l o c k 5 】为代表的研究人员开始对 计算机网络进行性能评价研究，并取得了一系列研究成果由于网络测量技术的 落后和限制，大部分性能评价工作对业务的统讦特性进行假设，网络业务模型在 很长一段时间都采用传统的话务模型或其改进形式在最初研究a t m 网络时 代，采用的也是p o i s s o n 过程，随着研究的深入逐步引入了一些较为复杂的随机 模型，如f l u i d f l o w 模型【6 】、p a c k e t - t r a i n 模型 7 】、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 l 8 j 、批到达马尔科夫过程1 9 】等这些模型的共同特点是所描述的业务序列 具有短时相关性( s h o r tr a n g ed e p e n d e n c e ) ，当时间标度增加时，统计上单位时间内 得到的数据包数将趋于白噪声由于它们一般假定业务的到达模式具有马尔科 夫性，使得相应的队列系统性能评价易于数学解析 近年来，随着网络研究的深入与测量技术的发展，不断有研究人员对传统模 型的有效性提出置疑i l o 川随着现代网络技术的飞速发展与网络应用范围的扩 大和新型网络业务的不断出现，使得网络业务的突发性和复杂性大大超过传统通 信网为了合理描述网络业务的真实特性必须提供一个新的正确有效的模型 通过对大量网络测量数据的分析，九十年代初期，由美国贝尔实验室和 b o s t o n 大学研究人员组成的小组对以太网业务和v b r 视频业务1 1 3 】进行了分析 研究结果证明：实际网络业务普遍存在统计上的自相似性，该特性与业务发生的 时间地点或编码方式无关通过采用分形思想进行分析，他们发现：实际网络业 务序列的自相关函数随时间间隔增大呈双曲函数衰减，不同于传统模型实际网 络业务具有长相关性( 1 0 n gr a n g ed e p e n d e n c e ) 这一发现揭示了现代网络业务的真 实特性，标志着网络业务建模和性能分析进入一个新阶段在这个发现的带动 下，各国研究人员对其他网络业务进行了测量和分析，均发现了网络业务具有自 相似性主要的测量研究活动有： ( 1 ) p a x s o n 等测量了大量广域网业务数据，并对其中的f t p 等t c p 业务进行了 详尽的分析，指出p o i s s o n 模型不适合描述广域网业务【1 4 】 ( 2 ) g i t 的m u k h e i j e e 小组对全美的n s f 网的骨干交换机进行了测量，发现 n s f n e t 业务具有长相关性【l ” ( 3 ) 贝尔实验室对七号信令的c c s n 网络系统进行了观测，d u f f y 1 6 1 等进行分析， 同样发现了业务的自相似性 天津大学硕士学位论文 第一章序论 f 4 ) c t m h a 等人研究了w w w 业务的自相似性，并分析了其自相似性产生的原 因【1 7 , 1 8 ( 5 ) k p a r k 等人研究了文件大小、传输协议与网络业务自相似之间的关系0 9 1 ， ( 6 ) h e y m a n 等人测量并分析了a t m 网络传输视频会议业务时的一些特性【2 0 】 这些测量与分析工作都揭示了网络业务具有统计上的自相似性由于传统 业务模型描述能力的欠缺，它们不能描述业务的自相似性当业务源增加时，按 照传统模型得到的结论是聚集业务越来越平滑；而对于自相似业务其聚集业务的 突发性将更突出而不是减少【1 2 】最近的研究结果表明【1 2 , 1 3 ，业务的自相似性对网 络系统的性能产生了意想不到的影响，自相似业务研究对网络时间、控制和分析 有重要意义 1 2 2 自相似过程的定义 自相似性是分形( f i a c t a l ) 的重要特征分形理论是m a n d e l b r o t 于七十年代中 期创立的，它总结了自然现象中不规则形态的自相似规律，进而用来解释复杂现 象和系统的几何特性和复杂性m a n d e l b r o t 对分形给出了一个形象的定义1 2 ”：其 组成部分以某种方式与整体相似的形态( s h a p e ) n t t 做分形分形描述了自然界中 很广泛一类物质的基本特性：局部与局部、局部与整体在形态、功能、信息、时 间与空间等方面具有某种意义上的自相似性，自然界存在的许多结构都具有这种 潜在的几何规律性，也称之为标度不变性( s c a l ei n v a r i a n c e ) 如果把一个分形物 体分裂开来，无论怎样分裂，它的各个小部分，看起来总与原来的整体相似海 岸线是解释分形这种自相似性最常用的例子在现实世界中，大量存在的是统计 自相似、渐进自相似和随机自相似，它们的特点是自相似性在一定的标度范围内 存在 网络业务量在数学上可以表征为一个随机过程，它蕴涵着统计意义上的自相 似性业务在不同时间尺度上的统计相似性，表现为突发没有明确的长度，而且 呈现丛集的特点，传统业务模型显然不能描述该特性我们对一个典型的m p e g v b r 业务序列在不同时间尺度的业务统计量进行聚集图1 1 中的( a ) ( c ) 分别描 述了m p e g 序列在三个不同时间尺度上的业务统计量从图中可以看出，尽管 时间尺度在增大，业务的统计量在增加，但是直观上它们具有类似的结构：业务 都呈现了较强的突发性，而且突发呈现嵌套的特点，作为对比，我们给出同样三 组时间尺度上根据p o i s s o n 过程得到的业务统计量如图1 1 ( a ) ( c ) 可以看出， 随着时间尺度的增大，聚集的业务将变平滑，不具有标度不变性，因此传统业务 模型与实际业务特性差异较大 天津大学硕士学位论文第一章序论 自相似随机过程理论是研究自相似业务的重要理论基础1 9 6 8 年， m a n d e l b r o t 在其著名论文“f r a c t i o n a lb r o w n i a nm o t i o n s ，f r a c t i o n a ln o i s e sa n d a p p l i c a t i o n s ” 2 2 l 中明确提出了第一个自相似过程的模型一一分数布朗运 动f b m ( f r a c t i o n a lb r o w n i a nm o t i o n ) ，并在水文学研究中得到了应用【2 本节采 用贝尔实验室的定义和描述来介绍自相似过程的概念和性质 实际网络业务传统p o s s i o n 模型 j6 j 删毗州椭 ( b ) m j o ( c ) ( c ) 图1 1 自相似业务与传统业务模型在不同时间尺度上的统计图比较 第三节本领域研究现状 近年来，自相似网络研究逐渐引起各国研究人员的重视，该领域的研究较为 活跃，许多国际性的会议都设有专题进行讨论虽然多数研究人员认为采用自相 似模型比传统模型更准确，但是也存在一些不同意见2 7 1 随着自相似业务的物理 _ 概一 从 “一 天津大学硕士学位论文 第一章序论 解释和对其产生原因的理解的深入，以及自相似性和长相关性对f 网络性能影响的 实例越来越多，业务的自相似性和长相关性已得到了网络研究人员的广泛认同 目前，该领域的研究工作大致可以分为三类：( 1 ) 网络业务特性的深入分析 与解释：( 2 ) 自相似网络业务下的网络系统性能评价：( 3 ) 自相似网络业务环境 下的网络业务预报与控制技术研究本节将对该领域的研究工作进行综述，介绍 其中的重要成果 1 3 1 网络业务特性的深入分析与解释 上一节中，我们对有关网络业务的自相似性的测量分析工作进行了介绍，在 贝尔实验室的发现 1 2 1 的推动下，研究人员对网络业务进行更广泛的测量分析和解 释，并试图从不同的数学角度进行分析通过对测量业务的深入分析，网络研究 人员发现了一些新特性，其中一个重要发现是许多描述网络业务的随机变量都服 从方差无穷的重尾分布( h e a v y - t a i l e dd i s t r i b u t i o n ) ，例如业务源的o n o f f 周期的 时间长度、数据包的到达间隔时间、w w w 文件的传输时间、呼叫的持续时间等 2 8 , 2 9 具有无穷方差的重尾分布描述了取值变化性很强的物理现象，它们具有高 可变- n ( h i g h v a r i a b i l i t y ) ，m a n d e l b r o t 也把该特性称为诺亚效应【2 2 1 ，传统模型使用 的负指数分布不能描述这种特性重尾分布的业务将加大网络拥塞的可能性 t a q q u 等在理论上证明了无穷多个独立的重尾分布的更新报酬过程( r e n e w a l r e w a r d ) 的叠加弱收敛于分形布朗运动【3 0 】，因此是自相似的这一理论揭示了高 可变性与自相似性之间的关系，可以看作自相似性的一种物理解释w i l l i n g e r 等 2 9 从贝尔实验室的业务数据中针对不同的源地址和目的地址对的独立业务数 据进行了分析研究结果表明：每个源一目的地址对产生的业务符合o n o f f 模型，而且o n 、o f f 的周期长度服从重尾分布将这两个结论结合，我们可以 对网络业务的自相似性作出合理解释，并为网络业务控制提供基础 t a q q u 和w i l l i n g e r 等人进一步对贝尔实验室测量的数据进行了深入分析，提 出业务多重分形属性口1 1 ；g a oj i a n b o 等人也从多重分形的角度对长相关业务进行 了分析【32 1 但是如何将多重分形用于网络控制有待进一步研究 另一方面，m as h e n g 和j ic h u a n y i 3 3 , 3 4 】以及s o s t r i n 9 1 3 5 1 等人在小波域对网络 业务进行研究，得到了很有特色的成果，受到很大关注在选择了适当的小波变 换后，在小波域其小波系数不再长相关，这样就可以采用传统的短相关时间序列 分析技术进行分析，并研究合适的网络控制技术小波域的研究为自相似业务分 析与控制提供了一条新路，人们可以在小波域对网络系统性能进行研究 天津大学硕士学位论文 第一章序论 1 3 2 自相似业务下的网络系统性能评价 由于自相似过程比传统p o i s s o n 过程更难进行数学解析，因此渐进分析与计 算机仿真成为自相似业务下网络性能研究的重要手段通过快速生成具有自相 似性的业务序列是进行仿真研究的有效方法目前常用的自相似业务生成方法 有基于分数高斯噪声和分数布朗运动的生成方法【3 q ；基于f a r i m a ( p ，吐g ) 模型的 业务生成方法；基于多个分数更新过程叠加的生成方法【3 8 】：直接叠加具有重 尾特性的o n o f f 源【3 9 】等方法虽然通过传统的仿真方法可以得到定条件下 的网络性能指标，但是为了得到现代网络需要的1 0 。9 或更低的信元丢失率等性能 指标，需要采用重要采样( i s ) 技术h o ，4 1 4 2 】h u a n g 等人对长相关业务下的队列 系统进行了i s 仿真 4 3 朋】为了进一步改进i s 技术并扩大其应用范围，j u n g s h i a n l i t 4 玎、a a k y a m a c t 4 6 1 、z h a m s z f i 和t o w n s e n d 4 r 1 分别从不同方面提出改进i s 的 方法 另一方面，国内外研究人员采用大偏差理论和极值理论对网络系统的渐进性 质进行了广泛研究 m g r o s s g l a u s e r 和j c b o l o t 4 8 】深入研究了业务长相关对网络性能的影响； b e l l c o r e 的a n e i d h a r d t 和j l w a n g 分析了多时间尺度对自相似业务排队分析的 作用1 4 9 】 n d g e o r g a n a s 【5 0 】等研究了自相似业务的聚合与分裂的闻题，指出自相似业 务聚合后仍为自相似业务也就是说在骨干网上传输的业务仍然会具有自相似 性我们必须采取新的适合自相似业务的控制技术，才能提供一定的服务质量 g e o r g a n a s 还与n l i k h a n o v , b t s y b a k o v 对输入过程为自相似过程的队列系统的 缓冲区溢出等进行了研究，给出了溢出概率的上下界 s l , s 2 他们的研究结果表 明，随着缓冲区的增加，溢出概率并非按负指数方式迅速下降而是下降的很慢 n o r r o s 根据分形布朗运动提出了正则自相似业务模型【5 3 1 ，对服务质量参数 进行了分析他利用大偏差技术推导出在稳态下队长尾分布( p ( 驴x ) ) 为韦布尔 ( w e i b u l l ) 分布d u m e l d 等也给出了相近的结论 5 4 】这些研究都以分数布朗运动 为输入过程，而我们课题组使用f a r i m a ( p , 吐口) 过程作为队列的输入，得到了相 近的结论1 5 这一方面说明了f a r i m a 过程在研究长相关业务时的有效性，另 一方面说明在极限条件下，长相关特性对队列长度的渐进性质有重要影响 在d u f f i e l d 等人工作的基础上，n r a n a n a n d 给出了长相关输入过程队列的尾 分布的一个更紧的上界f 5 引，并进行了数值计算j c h o e 与n s h r o 岔5 7 , 5 8 利用极值 理论研究了队列尾分布的界，使用了流模型，同时给出了分布的上下界，并给出 天津大学硕士学位论文 第一章序论 了数值解和应用举例 1 3 3 自相似网络业务环境下控制技术研究 常用的控制技术分为基于模型的控制、基于等价带宽的控制、基于测量的控 制和基于预报的控制等 o h i os t a t eu n i v e r i s t y 的r j a i n 研究组在a b r ( a v m l a b l eb i tr a t e ) 业务控制方 面进行了长期深入的研究，提出了a b r 的等价带宽计算方法，删论坛的 e r i c a 推荐标准等 5 9 , 6 0 , 6 1 但是r j a i n 的a b r 控制技术依赖a t m 的信令机制， 采用的是利用a t m 的管理维护信元传递控制信息的反馈控制，在以i p 为基础的 宽带网络中，存在严重的运行效率问题e m c h i u s s i 与y t w a n g 等1 6 2 朋】也对a b r 业务的拥塞控制等进行了研究，并分析了其队列性能由于a b r 业务对实时性 的要求不高，针对a b r 业务研究的控制方法，对v b r 业务特别是实时v b r 业 务是无效的 h u i z h a n g 与e k _ n i g h t l y 对v b r 业务控制进行了深入研究 6 4 , 6 5 , 6 6 】他们提出 了d b i n d 和r e d v b r 等技术来保证v b r 业务的服务质量其主要方法是建 立业务的包络和进行业务描述符的再协商，有效的对业务特性进行描述，并动态 调整业务的网络资源需求d b i n d 技术虽然通过业务的包络对业务进行控制， 仍然是基于模型的控制方法，需要合适的参数集来描述业务j w a l r a n d 等人对 业务的有效带宽分配技术进行了研究1 6 7 ，6 8 ，给出了优化分配方法和示例 基于模型的业务控制技术一般都需要用户或网络应用程序描述其对网络资 源的需求，给用户增加了负担甚至根本无法按照控制算法的要求描述其实时性网 络业务m g r o s s g l a u s e r 等研究了基于测量的业务控制吲7 0 】，提出了r c b r 方法 和基于测量的呼叫准入控制的基本框架，证明了业务测量的统计有效性他们证 明业务的瞬时测量值，经过适当处理后可以描述业务流的统计特性，使得网络设 备可以自己发现业务的服务需求，并在测量的基础上进行网络控制，他们还给出 了业务控制时使用的参数的选择条件与使用范围s a n q il i 7 j 】和s j a m i n 等【7 2 】分 别研究了基于测量的业务建模和控制技术s j a r n i n 等提出了等价漏桶滤波器来 描述业务流，并利用该漏桶的令牌生成速率和漏桶深度等参数计算每个服务优先 级的业务的平均延迟，在其基础上推导出进行呼叫准入控制的延迟判据，还对提 出的控制算法，进行了多种网络拓扑和负载条件下的仿真，证明了其控制算法的 有效性基于测量的网络控制技术方面可以减轻用户描述其业务特性的负担， 另一方面通过动态资源分配技术提高了网络资源的利用率但是如果业务存在 长相关时，m g r o s s g l a u s e r 等将业务的最近历史测量值作为其未来行为的指示的 天津大学硕士学位论文第一章序论 处理方法，就可能带来较大的误差，给网络控制带来不利影响 网络业务的预报可以采用不同的预报技术和方法，可以应用于网络控制的不 同方面国内外研究人员使用的业务预报技术可分为三类：基子a r m a 等时间 序列传统模型的预报技术、神经网络预报技术和模糊预报技术以及这些技术的混 合我们认为传统模型基础上的预报不能反映业务的长相关性质，会给网络控制 带来不利影响 基于业务预报的网络控制研究集中于动态网络带宽分配领域s a n q il i 【7 3 较早进行了动态带宽分配研究，对m p e gv b r 业务的统计特性进行分析后，我 们认为业务的低频成分决定业务的特性，并根据低频成分进行业务预报，并根据 预报值进行带宽分配，取褥了一定的效果，但是他们对业务频率的划分缺乏物理 解释，很难精确区分哪部分属于低频成分w m o h 等【7 4 使用神经网络进行业务 预报，在预报的基础上进行动态带宽分配，并将结果与理想分配情形进行比较， 以确定分配方法的效果但是很难判断根据某一个或几个业务流训练的神经网 络对其它业务流的适应性，对m p e gv b r 视频这类高突发而且具有很强长相关 和短相关的业务，训练效果更难以保证b q i u 7 5 】使用了模糊技术来进行业务预 报与拥塞避免北邮的庞其祥等【_ 7 6 】也使用模糊预报技术研究了动态带宽分配 这些研究没有考虑业务的长相关性质，采用传统的短相关模型作为预报或训练的 基础，没有全面反映业务的真实统计特性，在其基础上进行的带宽分配可能过于 乐观，并导致网络拥塞 g i t 的a a d a s 等人 7 7 , 7 8 使用线性预报进行动态网络带宽分配，并在m p e g 视频流的帧级进行了业务预报，在预报的基础上研究了带宽分配等网络控制技术 t s r a n d h a w a 等人【7 9 】使用l m s 滤波器进行v b r 业务估计和预报这些预报都 只是对单个m p e gv b r 业务流进行了预报和带宽分配，与真实网络上的聚合业 务由一定差距 基于长相关模型的业务预报有些研究人员认为太复杂【3 3 】，我们课题组经过研 究发现，采取一定的措施后，可以实现基于f a r i m a 模型预报的实时网络控制 我们认为对长相关业务的预报可以比近期历史测量值更好的反映其未来行为，可 以与基于测量的控制技术结合，进行基于预报的网络控制我们课题组对自相似 业务的预报进行了深入研究，在预报技术的基础上，提出了基于业务预报的呼叫 准入控制技术1 8 5 8 6 】【8 7 还有一些研究人员【8 0 , 8 1 , 8 2 5 3 | 对i n t e m e t 的拓扑结构、路径选择和业务的动态 特性进行了研究，力图在网络总体方面进行改进，使i n t e r n e t 能够达到用户需要 的服务质量 这些研究工作还处于发展过程中，是研究人员的一些阶段性看法和结论如 天津大学硕士学位论文 第一章序论 何解决业务自相似带来的问题，更好的对网络进行控制，满足用户的服务质量需 要才是研究的真正目的 通过以上研究工作可以看出，业务的自相似性对网络业务建模、性能评价和 控制都产生了重要影响该领域的研究工作已经开始与网络应用相结合，着眼于 如何解决问题但是，在研究方法和手段上还存在一定问题，自相似业务研究仍 然缺乏大量有效的数学方法和技术手段，围绕自相似性的数学解析难度非常大 自相似网络业务的深入研究，需要数学界的新发展 在现阶段，我们需要在已有工具和手段的条件下，进一步对具有工程意义的 问题进行深入研究，尽可能解决问题 第四节课题背景与论文工作 随着高速宽带网络的迅速发展，提供保证一定质量的通讯服务( q o s ) 成为一 个重要的研究方向，而网络拥塞检测和控制是保证的q o s 主要关键技术国内 外大量研究表明传统的网络控制技术不适合自相似网络业务，为了提供一定的服 务质量，课题组作了基于f a r i m a 模型的自相似网络业务预报与准入控制以及 以f a r i m a 为模型的业务队长尾分布分析等研究工作，并已取得一定的成果 【8 5 【8 6 】【8 7 】 但是由于业务模型相当复杂，这使得基于业务模型预报的网络控制由于计算 的繁杂而相当困难 鲫d u f f i e l d 提出了在长相关业务f b m ( 分数布朗运动) 下， 应用大偏差理论( l a r g ed e v i a t i o n ) 分析队列长度尾分布性质的方法p “张连芳 等人证明了大偏差技术也适用于f a r b 4 a 业务尾分布的渐进分析，并给出大偏 差在分析队列系统时的重要结论【5 5 】但由于数学解析的复杂性，实用的参数估计 方法很难得到因此本文引进随机过程理论中的阈交方法，从另一个角度分析和 讨论了自相似网络的拥塞控制，并在此基础上作了可行性研究 由于在网络性能评价研究中，通过优化带宽分配解决拥塞和溢出等问题时， 我们更关心的是网络业务超出某一阈值的情况，而闽值以下的业务显然与要解决 的问题关系不大我们提出采取闽交的方法可以不考虑业务的概率分布，避开业 务模型数学处理的困难，是一种可行的