（计算机应用技术专业论文）自相似业务接纳控制研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着i n t e m e t 的迅猛发展，网络流量迅速提高，新型业务层出不穷，这些业 务对服务质量( q o s ) 均有严格的要求，这就要求m 网络能够提供相应的机制以 便在高效地提高资源利用率的同时确保业务的q o s ，呼叫接纳控匍j ( c a c ) 就是 其中一种十分重要的机制。另一方面，网络业务具有普遍的自相似和长相关特 性。目前，对q o s 接纳控制研究，主要有基于模型的和基于测量的两种方法，基 于模型的c a c 机制中，传统的接纳控制的研究已经趋于成熟，而基于自相似模 型的接纳控制的研究则刚刚开始，必将成为今后的研究热点。 c a c 算法的优劣将直接决定网络综合性能，错误地准许过多的业务流将导 致部分业务流不能满足业务流的服务质量要求，而不必要地拒绝业务流将导致 资源浪费，造成资源利用率低下。c a c 与用户的业务流模型有很大关系，研究 自相似业务下的接纳控制，可以充分考虑业务流的自相似特性，提高自相似业 务流量管理机制的效率，更好地提供自相似业务下的q o s 保障。 本论文深入研究基于自相似业务模型和网络演算的接纳控制方法，提出的 接纳控制方法通过充分考虑网络业务的自相似特性，很好地满足用户的服务质 量要求，达到较高的利用率。本文的主要研究工作及成果如下： l _ ) 分析q o s 基本体系结构，研究自相似模型下的q o s 参数的计算方法； 2 ) 有效带宽是接纳控制的主要依据之一。本文研究自相似业务模型下有效 带宽的计算方法，给出了f b m 模型和q 稳定自相似模型下的有效带宽计算方 法，分析了有效带宽与其它性能指标的变化关系。提出了基于有效带宽的接纳 控制算法，并利用o p n e t 仿真验证了算法的可行性和有效性： 3 ) 流量整形作为最常用的流量监管技术，本文研究并推导出了f b m 模型和 a 稳定自相似过程( l f s n ) 流量整形令牌桶参数计算公式； 4 ) 研究了基于网络演算的自相似业务接纳控制方法，针对网络接纳控制中 的资源预留问题，基于网络演算理论，深入研究了i e t f 推荐的服务曲线分配方 法的实现机理及其存在的问题，针对该问题，提出了两种不同的给定到达曲线、 最大时延和缓冲区大小约束条件下服务曲线分配方法，推导出了各种方法不同 情况下需要预留的带宽和缓冲区长度的计算公式。 关键词：q o s 接纳控制；业务自相似特性；有效带宽：网络演算；流量整形 西南交通大学硕士研究生学位论文第1 i 页 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e ta n dt h eq u i c ki n c r e m e n to ft h e n e t w o r kt r a f f i c ，m o r ea n dm o r en e ws e r v i c e sr e q u i r e ds t r i c tq u a l i t yo f s e r v i c e ( q o s ) g u a r a n t e eh a v eb e e ne m e r g e do nt h ec u r r e n tn e t w o r k ，a sar e s u l to ft h a ti pn e t w o r k m u s tb eo f f e r e dc o r r e s p o n d i n gm e c h a n i s mf o rg u a r a n t e eq o sw h i l ei m p r o v i n g u t i l i z a t i o nh i g h - e f f i c i e n t l y c o n n e c t i o na d m i s s i o nc o n t r o l ( c a c ) i so n eo ft h e m e t h o d sf o rq o sg u a r a n t e e o nt h eo t h e rh a n d ，n e t w o r kt r a f f i cp r o c e s s e se x h i b i t u b i q u i t o u sp r o p e r t i e so fs e l f - s i m i l a r i t ya n dl o n g - r a n g ed e p e n d e n c e ( l r d ) a tp r e s e n t t h e r ea r et w ok i n d so fm e c h a n i s m sf o rq o s b a s e dc a c ，n a m e l ym o d e l b a s e dc a c a n dm e a s u r e m e n t b a s e dc a c i nt h em o d e l b a s e dc a cr e s e a r c h t r a d i t i o n a lc a c i sn e a r l yn a t u r e ，w h i l et h es t u d yo nc a cb a s e do ns e l f - s i m i l a rm o d e lh a sju s tb e g u n ， a n di tw i l lb et h er e s e a r c hf o c u si nt h ef u t u r e t h eq u a l i t yo fc a c a l g o r i t h md e t e r m i n e st h ec o m p r e h e n s i v ep e r f o r m a n c eo ft h e n e t w o r kd i r e c t l y p e r m i t t i n gt o om u c ht r a f f i ci n t ot h en e t w o r kw i l ll e a dt ot h ef a c t t h a ts o m et r a f f i cc a nn o tm e e tt h e i rq o sr e q u i r e m e n t ；o nt h ec o n t r a r y , r e f u s i n gt h e t r a m cw r o n g l yw i l lc a u s et h ew a s t eo fr e s o u r c e sa n dr e s u l ti nl o wu t i l i z a t i o n i th a s g r e a tr e l a t i o n s h i p sb e t w e e nc a ca n dt r a f f i cm o d e l ，a n dt h r o u g ht h es t u d yo fc a c b a s e do ns e l f - s i m i l a rt r a f f i cm o d e la n dc o n s i d e r a t i o no ft h et r a f f i cc h a r a c t e r i s t i co f s e l f - s i m i l a r i t y , t h ee f f i c i e n c yo ft r a f f i cm a n a g e m e n tm e c h a n i s mc a l lb ei m p r o v e d a n dt h eq o sg u a r a n t e eo fs e l f - s i m i l a rt r a f f i cb e s to f f e r e d s e l f - s i m i l a rt r a m cm o d e l b a s e da n dn e t w o r kc a l c u l a t i o n b a s e dc a cs c h e m e sa r e d e e p l ys t u d i e d t h ec a ca l g o r i t h m sp r o p o s e di nt h i st h e s i sc a nb e s tm e e tu e r s q o s r e q u i r e m e n ta n da c h i e v eh i g h e ru t i l i z a t i o nt h r o u g hf u l l yc o n s i d e r a t i o no f t h e c h a r a c t e r i s t i co fs e l f - s i m i l a r i t yo fn e t w o r kt r a f f i c t h em a i nr e s e a r c hw o r k sa n d a c h i e v e m e n to ft h et h e s i sa r ea sf o l l o w s ： 1 ) t h eq o sa r c h i t e c t u r e sa r ea n a l y z e da n dt h em e t h o d so fq o sp a r a m e t e r s c a l c u l a t i o nb a s e do ns e l f - s i m i l a rt r a f f i ca r es t u d i e d 。 2 ) e f f e c t i v eb a n d w i d t hi st h em a i nb a s i so fc a c t h ew a yt oc o m p u t ee f f e c t i v e b a n d w i d t hb a s e do nf b ma n d0 【一s t a b l es e l f - s i m i l a rp r o c e s si sr e s e a r c h e d a n dt h e v a r i a n c e so fe f f e c t i v eb a n d w i d t hw i t ho t h e rc h a r a c t e r i s t i ce x p o n e n ta r es t u d i e d 西南交通大学硕士研究生学位论文第1 il 页 t h r o u g ht h e o r e t i c a la n a l y s i sa n ds i m u l a t i o n c a cb a s e do ne f f e c t i v eb a n d w i d t hi s p r o p o s e d ，a n d t h e f e a s i b i l i t ya n de f f e c t i v e n e s s o fc a ca r ep r o v e dt h r o u g h s i m u l a t i o n 3 ) t r a 衔cs h a p i n gi st h em o s tc o m m o nu s eo ft r a f f i cc o n d i t i o n i n gt e c h n o l o g y p a r a m e t e r sc o m p u t i n gm e t h o d so ft o k e nb u c k e tu s e dt os h a p et h es e l f - s i m i l a rt r a 伍c b a s e do nf b ma n dl f s na r es t u d i e di nd e t a i l 4 ) s e l f - s i m i l a rt r a f f i cc a cb a s e do nn e t w o r kc a l c u l u si sd e e p l ys t u d i e d b a s e do n n e t w o r kc a l c u l u s ，t h e i m p l e m e n t a t i o n m e t h o df o rr e s o u r c er e s e r v a t i o n r e c o m m e n d e db yi e t fa n di t sp r o b l e ma r es t u d i e di nd e t a i l f o rs o l v i n gt h i s p r o b l e m t w oo p t i m a la l l o c a t i o ns c h e m e sf o rn e t w o r kr e s o u r c ec o n s t r a i n e do nt h e a r r i v a lc u r v e ，m a x i m u md e l a ya n db u f f e rs i z ea r ep r o p o s e d ，a n dt h ed e s i r e dr a t ea n d b u f f e rs i z eo ft h e s es c h e m e sa r ed e r i v e d k e yw o r d s ：q o sc a c ；s e l f - s i m i l a rt r a f f i c ；e f f e c t i v eb a n d w i d t h ；n e t w o r k c a l c u l u s ；t r a f f i cs h a p i n g 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使j 【 j 学位论文的规定，同意学校保留并向国 家有关部门或机构送交论文的复印件和电了版，允许论文被查阅和借阅。本人授权西南交 通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密 2 不保 年解密后适用本授权书； 使用本授权书。 ( 请在以上方框内打“”) 学位论文作者签名：乍贰鼙、指导老师签名：v 舅茗吠涵 日期：湘s 、虫 日期渺分、厂、f 厂 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： ( 1 ) 禾m j 用o p n e t 和m a t l a b 仿真分析了自相似有效带宽界与性能指标之间的 关系。以数学理论为基础推导出了f b m 模型下实时有效带宽的计算方法，利 用迭代思想推导出了自相似聚合流有效带宽的计算方法： ( 2 ) 给出了基于有效带宽的接纳算法，通过仿真证明了接纳算法的有效性。 分析了f b m 模型下和a 稳定白相似模型下的接纳算法性能。 ( 3 ) 推导出了自相似业务下漏桶参数的计算方法，基于最新的网络演算理 论，深入研究了基于端到端时延约束的有效带宽和基于缓冲区长度约束的等效 容量的计算公式，给出了基于网络演算的自相似业务接纳控制算法，最后通过 实例验证了本文分析结果的正确性及有效性。 西南交通大学硕士研究生学位论文第1 页 第l 章绪论 1 1 研究背景和研究意义 1 1 1 研究背景 随着计算机技术和因特网的进一步发展，人们不但对于网络所能实现的诸 如电子邮件、远程登录、文件传输等功能具有很高的兴趣，更对网络电话、视 频点播的新兴的多媒体业务表现出了越来越大的热情。应用的要求不断高涨促 使在网络的设计中不但要考虑单一的数据传输，更要考虑到某些业务传输的实 时性和抖动性等指标，即保证业务的服务质量( q u a l i t yo f s e r v i c e ，q o s ) ，典型 特征为“高带宽、低延迟、低抖动和低分组丢失”。然而，众所周知，因特网协 议都是提供一种尽力而为的服务( b e s t - e f f o r ts e r v i c e ) ，由于网络资源是有限的， 需求是相对无限的，网络不可能保证每个用户所期望的服务质量，而是尽可能 地提供最好服务，这就是因特网自诞生起的特有机制。无论是现在或是将来很 长的一段时间都将继续存在，这本身就和提供可靠q o s 的服务产生了一定的矛 盾，这也引发了对一系列问题的研究。接纳控制作为一种预防性的流量控制手 段是实现网络q o s 保障的重要手段，实施接纳控制的网络，要求用户在请求接 入网络时将自己的通信量传输特征和要求的服务质量告诉网络，网络根据用户 的通信量特征和网络现存的资源情况，决定是否接纳用户的连接请求。接纳算 法包括两个过程：( 1 ) 数值计算；( 2 ) 笋t j 断接纳过程。 接纳控制与用户的业务流模型有很大关系。对自相似业务，采用许多原有 的接纳控制算法d 2 3 1 所得的结果无法令人满意。对业务流量模型特性的研究表 明，业务流量具有自相似性或长相关性 4 1 ，即在很长的时间尺度上都存在流量 突发，聚合流量不会随着聚合尺度的增加而很快地平滑掉，这意味着多个业务 源同时以峰值速率持续发送数据的可能性是不能忽略的，而这种情况会使网络 性能急剧下降。实际业务流量的自相似性对根据泊松分布特性而设计的网络性 能有很大的影响f 5 6 ，7 , s l ，使网络的原有的m a r k o v 模型基础上的协议、策略及其 评价方法不够准确。自相似特性是一个对网络工程( i n 流量测量、缓冲区分配、 接纳控制、速率控制等) 致关重要的特性，如果忽略网络流量的自相似和长相 西南交通大学硕士研究生学位论文第2 页 关特性，将会高估系统的性能，造成不准确的网络资源分配。 由r l c r u z t 9 ，i o 开创并由c s c h a n g 和j y l eb o u n d e c 等人i n 1 2 1 3 1 发展起 来的网络演算( n e t w o r kc a l c u l u s ) 是一种网络队列系统性能定量分析的重要而 有效的新型数学工具，是基于最小加代数( m i n p l u sa l g e b r a ) 的一组结论。应用 网络演算可以建立更为准确的网络模型和简单明了地计算网络极端情况下的 性能。网络演算被广泛应用于网络q o s 研究的建模和理论分析中，如利用网络 演算建立的确保速率服务和延迟速率服务的关系模型o l ，基于网络演算的参数 区分网络服务的接纳控制模型i t 2 ，将网络演算作为数学工具，研究漏桶模型下 的接纳控制模型 1 3 1 。目前把新型的网络演算理论应用到自相似业务的接纳控制 算法中还很少，基于网络演算的自相似接纳控制有重要的研究价值。 业务的白相似性对接纳控制有何影响? 针对业务的自相似性，应该采用怎 样的接纳控制方案? 自相似模型下的接纳控制算法的性能如何? 针对上述问题，本课题研究自相似业务下的接纳控制，基于网络演算的接 纳控制，以便保障现代网络业务的q o s 。 1 1 2 研究意义 本课题的研究意义主要体现在下列两个方面： ( 1 ) 考虑流量的自相似特性，提高接纳控制算法的有效性 接纳控铝1 ( c o n n e c t i o na d m i s s i o nc o n t r o l ，c a c ) 只有在网络资源充足的情况 下才会接纳新应用请求，防止了网络的拥塞；另外，c a c 的一个目标是尽量 提高接入用户请求数目，这也就相应的提高了网络资源利用率。提出一个有效 的c a c 算法在保证q o s 中具有重要的意义。目前的接纳控制算法都是以短相 关性流量为背景提出来的。而现代网络的自相似、长相关特性，促使我们必须 重新设计新的接纳控制方法，以便充分考虑网络流量的自相似等特性，提高算 法的有效性。本文提出的c a c 算法考虑业务的自相似、突发特性，c a c 根据 用户在呼叫申请中所提出的自相似模型以及其所需要的q o s 参数计算出其有 效带宽，根据此有效带宽作出是否接纳该用户。 ( 2 ) 基于网络演算的接纳控制，既是资源预留的主要工具，又可以优化资源分配， 提高资源利用率 对于具有长相关特性的自相似输入业务流，经过漏桶整形后输出业务流的 自相似性明显增强 t 4 1 ，并且负载越重时，输出业务流的自相似增强的越多，从 而将加速网络性能的恶化，因此应提出适应于白相似业务的新的整形策略。 西南交通大学硕士研究生学位论文第3 页 网络演算是最近1 0 多年在国外发展起来的- f - j 网络分析理论，它提供一 种简单明了的方法来计算网络极端情况下的性能，能有效地进行网络定性和定 量分析，有利于使用确定性到达曲线和服务曲线【1 5 】推导出最坏情况下 ( w o r s t c a s e ) 缓冲区队列长度和延迟大小，从而提供严格的、强有力的q o s 需 求服务保证。接纳控制中，需要分配的资源是带宽和缓存区，其中带宽的分配 尤为重要。由网络演算服务曲线的概念可知，分配带宽就是分配服务曲线中的 速率。把新型的网络演算理论应用到接纳控制中就可以很好地提高网络资源利 用率。 1 2 国内外研究现状 目前，对q o s 接纳控制的研究，主要有基于模型的和基于测量的两种方法。 基于模型的c a c 机制中，传统的接纳控制的研究已经趋于成熟，基于自相似 模型的接纳控制的研究是目前研究的热点。如何衡量网络资源是实现c a c 算 法的关键，因此有效带宽的概念被提出来解决这个问题。在接纳控制机制中， 要求每个业务源提供描述其业务特征的参数，c a c 则利用这些参数来确定一 个新的连接建立请求是否被接纳，这种类型的c a c 机制通常被称为基于模型 的c a c 机制。c a c 的判决与用户的业务流模型有很大关系，传统的业务模型 假设用户的业务流模型为泊松过程、马尔可夫调制泊松过程m m p p 和马尔可 夫调制流体过程m m f p 等，并在此基础上发展出了许多不同的c a c 模型。 目前，国内外学者提出了多种基于模型的c a c 机制，典型的有： ( 1 ) 等效带宽法 1 6 - 2 7 。该方法利用了等效带宽的概念，等效带宽被定义为在 一个排队系统中能够满足各个连接所要求q o s 的最小服务速率。等效带宽最初 是在网络的接纳控制中提出的，其主要思想是用来估计满足一定q o s 要求的所 需带宽。当一个请求到达时，网络计算其等效带宽，并在当前可用带宽足够时 允许其接入。在传统的业务模型中，把等效带宽认为具有可加性。在许多文献 中，给出了基于不同业务模型的等效带宽计算方法，文献 1 6 ，1 8 ，2 3 研究了基于 传统短相关模型的有效带宽，如单个和多个中断流体过程( i f p ) 业务源的等效带 宽、单个和多个马尔可夫调制流体过程( m m f p ) 业务源的等效带宽。传统的业 务模型对业务流的突发性估计不足，乐观地估计了分组的丢包率，造成服务质 量的低下。长相关模型考虑了业务流的自相似性，根据长相关模型合理地计算 有效带宽，能有效地降低分组丢包率，提高了q o s 。传统的有效带宽的研究已 西南交通大学硕士研究生学位论文第4 页 经趋于成熟，基于自相似模型的有效带宽的研究是目前研究的热点。文献 1 ，2 4 】 研究了基于自相似模型有效带宽，如基于f b m 模型的有效带宽和基于a 一稳定 分布自相似模型的有效带宽。g r o s s g l a u s e r 提出了一种带宽分配方法 2 6 1 ，但是 该方法只讨论了自相似排队系统的带宽分配下界；因此在某些情况下，所分配 的带宽会低于连接实际所需带宽，从而导致无法确保用户所要求的q o s 。s t a t h i s 基于有效带宽的概念提出了一种自相似通信量的接纳控制算法【2 】，但是该算法 只考虑了同种通信量源和带宽分配的下界，这对于实际应用是不够的。文献 3 】 中只考虑了f b m 模型下排队系统的要求带宽的上界，所估计的带宽太保守， 链路利用率低。姚正林f 2 7 ，利用了大偏差理论对渐近自相似数据流进行了分析， 并提出了相应的c a c 算法，但计算复杂，不便于实时控制。文献 1 按照溢出 概率上界得出的a 稳定自相似模型的有效带宽上界来对业务流分配带宽，接纳 算法把聚合流的有效带宽上界和队列中的服务速率进行比较来确定是否接纳 一个新业务流的连接请求，这种方法高估了业务流的有效带宽，因此导致网络 资源利用率低。因此，需要有一种有效的接纳控制方法能对具有长相关和突发 特性的业务流进行处理。自相似的普遍存在性给目前的接纳控制方法既带来新 的困难，同时也带来了新的机遇。 ( 2 ) 高负荷业务近似法 2 8 , 2 9 1 。高负荷业务近似法其基本思想是利用排队系统 队长分布的尾部特性来建立相应的接纳控制机制，这种近似方法在业务强度较 大的情况下，能够取得较好的效果。该算法相对来说过于保守。 ( 3 ) 信元丢失率上界法 3 0 - 3 4 。该方法的出发点在于给出计算排队系统信元丢 失率上界的方法。当新的连接建立请求到达时，计算接纳该连接后系统的信元 丢失率上界，若该值小于所要求的c l r 则接纳该新的连接，否则拒绝。例如， s a t i o 提出了一种基于a n a 和m n a 两个参数的信元丢失率上界方法【3 们，其中 a n a 代表在固定时间间隔内到达的平均信元数，m n a 代表在相同固定时间间 隔内到达的最大信元数。此算法由于要进行大量的卷积运算，从而无法满足 c a c 实时性的要求。 ( 4 ) 快速带宽分配法【3 5 3 9 。快速带宽分配法专门用于突发业务的传送，其主 要思想是，当一条虚连接建立起来的时候，各相关交换机内的路由表相应地被 更新，但此时并不给该虚连接分配带宽资源。只有在发送端准备传送一段突发 业务的时候，网络才试图为这段突发业务的传送分配必要的资源。 ( 5 ) 时窗法t 4 0 4 1 1 。时窗法基于这样一种概念，即在一段固定的时间内，业务 源所允许传送的信元被限制在一个最大数目之内。这一段固定的时间，称为帧 西南交通大学硕士研究生学位论文第5 页 或时窗。 ( 6 ) q r e n 博士提出了一种基于业务源流量描述符的c a c 机制【4 2 】，该机制 利用用户提交的业务源流量描述符获取相应的业务模型，并利用高斯近似方法 计算所需的带宽。该机制还对业务模型进行了改进，以便获得更好的统计复用 增益。该机制的优点在于：只依赖于用户提交的业务源流量描述符，并且简单 易行，满足实时性要求。但同时该机制也存在着以下两个明显的缺陷：第一， 该机制利用业务源流量描述符所获得的业务模型不是一种严格意义上的“最坏 情况业务到达模型，因此在某些情况下，所分配的带宽会低于连接实际所需 带宽，从而导致无法确保用户所要求的q o s 。第二，该机制与仿真结果相比较， 仍然十分保守，从而导致较低的资源利用率。 ( 7 ) 北京邮电大学王兵等提出了一种基于自相似业务模型的公平性接纳算 法【盯l 。在接纳判决过程中引入概率接纳机制。可以保证业务的公平性接纳。 综上所述，在当前的自相似业务环境下，基于短相关的q o s 接纳控制存在 诸多问题，信元丢失率上界法由于要进行大量的卷积运算，从而无法满足c a c 实时性要求，高负荷业务近似法只有在业务强度较大的情况下才能得到较好的 效果，而且它们与等效带宽法相比较均过于保守。基于等效带宽的c a c 中， 基于传统模型的等效带宽方法对业务流的突发性估计不足，从而导致无法确保 用户所要求的q o s 。提出适用于自相似业务的接纳控制算法是现在研究的热 点。 1 3 本文的研究工作及论文内容安排 针对上述研究工作中存在的问题或不足，我们课题研究小组在导师的带领 下对自相似网络控制机制进行了研究。由于自相似业务研究目前还缺乏一套完 整有效的研究方法和体系，研究人员必须从网络技术和工程实际的角度出发， 在现有的数学理论和工具中，选择适用于自相似业务研究的方法，建立一个包 括业务流量的建模分析、性能评价以及网络控制机制及应用研究的体系。 论文在比较了几个基于不同模型的c a c 机制的基础上，引入了适应于长 相关特性的q o s 接纳控制方法，分析当前的网络模型，就当前的基于模型的 c a c 算法分析其优势及其不足，并提出了基于自相似业务的接纳控制算法， 包括自相似业务有效带宽的计算，参数的选择以及接入的判断等方面。根据迭 代思想，推导出了已接纳业务聚合流所需的有效带宽，通过m a t l a b 和 西南交通大学硕士研究生学位论文第6 页 o p n e t 相结合的仿真方法研究了有效带宽随h u m t 系数、特征指数和缓存区的 变化情况，分析了有效带宽公式在接纳控制中所适用的环境，证明了利用有效 带宽进行接纳控制的有效性。基于网络演算理论，研究了自相似业务流量整形 及基于网络演算的自相似业务接纳控制。 论文的内容安排如下： 第l 章绪论介绍了课题背景、国内外研究情况、研究意义及本论文的主要 研究内容； 第2 章研究q o s 模型的相关理论、框架模型和q o s 接入控制策略：研究 了有效带宽的计算方法；分析了目前存在的主流c a c 控制算法，比较基于模 型的接纳控制策略之间的异同，指出其缺点并提出应该改善的地方； 第3 章在介绍网络业务自相似特性、自相似特性对网络的影响、以及常用 的自相似模型的基础上，重点研究了自相似业务条件下接纳控制度量参数的计 算方法，为后面的接纳控制算法设计提供理论依据； 第4 章研究了自相似各种模型下的有效带宽计算方法，分析了它们的适用 环境，给出了一种自相似实时有效带宽计算方法，给出本文研究的接纳控制算 法并通过仿真验证该算法； 第5 章以正t f 的确保服务应用为背景，研究了网络演算在确保服务接纳 控制中的应用方法，基于较新的网络演算理论，研究了基于端到端时延约束的 有效带宽和基于缓冲区长度约束的等效容量的计算方法，给出了基于网络演算 的接纳控制算法，最后通过实例验证了本文分析结果及算法的正确性及有效 性。 结束语部分对本论文的主要工作进行总结，指出论文需要进一步完善的地 方，并提出课题相关的进一步研究的个人见解。 西南交通大学硕士研究生学位论文第7 页 第2 章q o s 接纳控制相关技术 传统的i n t e m e t 只提供“尽力而为”服务。随着i n t e m e t 网络流量的迅猛增长， 以及一些具有实时要求的新业务如视频会议、i p 电话、多媒体传输等的不断涌 现，需要在i n t e m e t 中引入新的控制机制来有效地提供端到端服务质量的控制 和保证，服务质量( q o s ) 正成为当前研究的热点。本章系统地分析q o s 相关技 术，并着重研究基于模型的c a c 算法的数学模型、度量参数等。 2 1i pq o s 体系结构 q o s 即服务质量，在r f c 2 3 8 6 t “1 中用来刻画网络在传输数据流时要求满足 的一系列服务需求，具体可以量化为带宽、延迟、延迟抖动、丢包率、吞吐量 等性能指标。此处的服务具体是指数据包流经过若干网络节点所接受的传输服 务，强调端到端( e n d t o e n d ) 或网络边界到边界的整体性。反映了网络元素在保 证信息传输和满足服务要求方面的能力【4 5 】。 图2 - 1i pq o s 实现模式 目前，关于提高网络q o s 的服务模型及相关协议主要包括：基于资源预留 西南交通大学硕士研究生学位论文第8 页 的集成服务( i n t s e r v ) 资源预留协议( r s v p ) 模型、基于优先权机制的区分服务 ( d i f t s e r v ) 模型、流量工程( t e ) 和多协议标签交换( m p l s ) 、基于网络拓扑结构 及流的q o s 路由和约束路f l j ( c b r ) 。在口上一种实现q o s 的模型如图2 1 所 示。接纳控制在q o s 中起重要作用。q o s 接纳控制实际上是指q o s 根据自身 拒绝呼叫的标准，对某一终端接入网络的呼叫进行限制。如果满足接入要求， 则允许该呼叫接入网络，即对该呼叫授予接入权；如果认证失败，则予以拒绝， 该呼叫不能接入网络。当前，接纳控制主要源于两种思路：一是资源预留，二 是优先权。前者主要针对单个流的特征类型描述o o s ，后者则通过聚集流的特 征类型描述q o s 。资源预留机制根据应用通信量和q o s 请求，在网络上预先 保留一定的资源( 带宽和缓冲区等) ，避免网络突发通信量对某些重要应用传输 产生影响。优先权机制是对不同用户类的聚集流特征给出相应的服务级别( 即 优先权) ，每个级别的流得到不同的优先权服务，从而保证网络的q o s 。但要 充分发挥效率，两者都必须与相关的路由机制和调度策略相结合。 2 2q o s 接纳控制基本框架 接纳控制方案主要由流量描述、接纳标准和测量过程三个基本部分构成。 流量描述是一组表示一个流量源的特征参数，典型的流量描述机制是令牌桶和 流量模型。测量过程是衡量网络动态变化量逻辑的实体，并提供对接纳控制算 法的测量信息。一般说来，在测量过程中常用时间窗口、点采样和指数平均等 3 种机制衡量测量过程。接纳标准是接纳控制方案接受或拒绝流的规则，接纳 控制的具体接纳标准主要是速率和、等值容量、可接受区以及时延和带宽约束 等。接纳控制方案通过接纳控制标准作出接纳控制决策，保证q o s 。接纳控制 方案通常提供确定型和统计型两种不同的服务类型。确定型通常利用整个网络 的预留状态和资源信息保证端到端服务；统计型则以一定的概率保证端到端服 务，能够提高网络的利用率，对当前网络状况可以提供不精确的测量。 ( 1 ) i n t s e r v 接纳控制 i n t e r n e t 上的应用并不能进行资源预约，1 9 9 4 年i e t f 提出了i n t e r n e t 综合 服务体系结构( i s a ) t 舶4 7 1 ，定义了实现应用q o s 保证的结构。i s a 为上层应用提 供所要求的端到端q o s 保证，并根据服务数据包的q o s 要求，选择服务类型。 i n t s e r v 模型包括确保服务和可预测服务两类面向实时通信量的服务。它们在受 控共享链路中集成，即在原来i n t e m e t 的尽力服务基础上，增加确保服务 ( g s g u a r a n t e e ds e r v i c e ) 和负载受控服务( c l sc o n t r 0 1 1 0 a ds e r v i c e ) 。假设网络 西南交通大学硕士研究生学位论文第9 页 资源是可以显式管理，那么资源预留和接入控制就是实现这种服务的关键。服 务模型包括一系列服务提交，服务提交由派生的服务实体分类，它们与单个流 的q o s 或混合流的可利用资源聚集相关。混合流的服务提交要求网络必须在各 个流之间合理地分配资源，资源分配是通过逐个流协商的。 i n t s e r v 模型的特点是资源预留，其原理是对于每一个需要进行q o s 处理 的数据流，通过一定的信令机制，在其经由的每一个路由器上进行资源预留， 以便实现端到端的q o s 业务。对于有q o s 要求的应用，数据传输前必须先通 过r s v p 4 驯建立通信路径，并预留能满足q o s 要求的资源。当传输路径上的路 由器接收到相应的r s v p 请求信令时，检查是否有足够的资源满足这次传输的 q o s 要求。当确信有能力满足q o s 要求后，发送确认信令，并把r s v p 请求 传送至路径中下一路由器节点。当有中间节点不能满足相应请求时，便向接收 方发送拒绝信息，拒绝此r s v p 请求。接纳控制可以保证所有被接受的业务请 求q o s 要求都可以得到满足。 ( 2 ) d i f f s e r v 接纳控制 d i f f s e r v 的基本机制是在网络边缘路由器上根据某一业务的q o s 要求将该 业务映射到一定的业务类别中，随后利用分组中的d s 字段，唯一地标志这 一业务所需的服务类别。网络中的各个节点将根据该字段，对各种业务类别采 取预先设定好的服务策略，保证相应的时延、传送速率和抖动等q o s 参数。 d i f f s e r v 域的入口路由器根据口分组头部的d s 字段中d s c p 值，把数据包划 分为若干类，与转发机制( p h b ) 一一对应。d i f f s e r v 模型一般有快速转发( e f ) 和保证转发( a f ) 两种不同的业务类，分别对应不同的转发机制。 d i f f s e r v 结构模型通过检查位于口包中的d i f f s e r v 域标志，进行会话分类 和聚合，实现可扩展性。p 包被分类并标记，以接收一个特别的基于每一跳的 转发行为。在沿途的节点上，通过复杂的分类、标记、策略控制和流量整形操 作，网络资源被分配给不同q o s 特性的会话。 d i f f s e r v 的结构模型把网络分成不同的域，只在域的边缘进行接纳控制， 核心骨干路由只进行转发，不再保留业务流的状态信息。该模型不提供端到端 的q o s 保证，而将q o s 限制在不同的域范围内实现，不同的域间通过服务等 级协议( s l a ) 进行协商。s l a 是业务提供商为每个用户建立的相应服务标准协 议，指定用户在特定等级的业务中可以发送的业务量。一旦业务流进入网络， 专门的路由器就根据其业务类型分别对待，这与综合业务方式以每一流为依据 不同，整个网络要满足所有s l a 的要求。 西南交通大学硕士研究生学位论文第10 页 2 3 有效带宽的概念及其计算方法 2 3 1 带宽、瓶颈带宽与有效带宽 带宽主要包括两个含义：链路速度和网络端到端数据传输速度。随着 d w d m 技术的出现与发展，光链路的速度已经达到了1 0 g b i v s 的数量级甚至 更高。有人认为，现阶段主干网络的带宽已经不再是通信的瓶颈，甚至出现了 “带宽过剩”的提法( 美国存在大量未得到充分利用的光缆) 。另一方面，由于接 入技术的滞后，很多用户还是通过m o d e m ( 不大于5 6 k b i v s ) 访问i n t e m e t 。更重 要的是，对于口网络的通信终端而言，数据传输速度并不等同于链路速度。口 网络要经过多层复杂的协议处理，协议以及协议的具体实现对传输速度都有很 重要影响，比如口层的路由器队列管理，t c p 的缓存机制等。主要考虑端到 端的通信带宽。 瓶颈带宽( b o t t l e n e c kb a n d w i d t h ) 与路径相关。 定义2 1 ：( 路径) 发送和接收主机之间一系列存储转发链路构成的逻辑连 接，用于在发送和接收主机之间传递分组。 假定网络路径由h 条链路组成，其中每条链路的带宽为最，则瓶颈带宽 可定义为： 定义2 2 ：( 瓶颈带宽) 当路径中没有其它竞争流量负载时，网络路径能够提 供给数据流的最大的层吞吐量，可以表示为b = m i n 置。 i = 0 ，1 ，爿 定义2 3 ：( 有效带宽) 主机沿路径在给定点实际上能及时传输的最大速率， 即在已知流量负载下连接能提供的稳定可用的最大传输能力1 。 有效带宽时刻动态改变，以瓶颈带宽为上界。d o v r o l i s 等人则在协议层次 上定义路径的瓶颈容量与有效带宽路径容量是在没有背景流量的情况下，路径 能给予一个流的最大口层吞吐量，有效带宽则是在给定背景流量负载下路径 能提供给一个流的最大m 层吞吐量。 2 3 2 常见的有效带宽计算方法 在接纳控制算法中，在判决是否接入时，使用有效带宽进行判别是非常普 西南交通大学硕士研究生学位论文第1 1 页 遍的一种方法。对于突发业务，等效带宽等于峰值速率，这种等效带宽计算方 法虽然可以很快地计算出来，但是会造成低的带宽利用率。文献 1 6 根据信元 丢包概率定义了有效带宽，假定业务到达为两状态的马尔科夫过程，给出的有 效带宽计算方法为：c ：a - b + x ( a - - b ) + 4 b a pp ，其中口：一1 n ( 占) ( 1 - p ) 尸， z 口 b 为缓存区大小，为信元丢包概率，肛为平均到达率，p 为利用率，p 为到达 的峰值速率。 ( 1 ) 等效带宽理论 假定n 个相互独立的业务流，b 为缓存区大小，服务速率c 大于业务流 的平均速率，即c 以，根据大偏差理论，可以得出： n = l p a 。o ) b e x p ( 一b t r ) 亨口。( 仃) c n = l 其中a 。( t ) ) 表示在时间( 0 ，t 】内业务流n 到达的网络流量，o 为一个有限数， 则第n 个业务流的有效带宽为】： 11 口。( 盯) = 2 - ii m - l o g e e x p ( c r a 。( f ) )( 2 1 ) 仃l - - - o o f ( 2 ) 基于单o n o f f 流体模型的有效带宽计算方法 当处于o n 态时，系统以峰值速率r p c a i ( 产生媒体流；当处于o f f 态时，系 统不产生媒体流。系统在o n 态和o f f 态的逗留时间分别服从参数为九，p 的 指数分布。通常用参数( r p c a l ( 入d 来描述一个o n o f f 模型。两态( o n o f f ) 流 体流模型缓冲区中媒体流长度的分布函数可近似表示为 5 2 1 ： f ( x ) = l p 和( 2 2 ) 其中z 。=! 兰竺! ! 二竺竺! 给定缓冲区大小k ， ( c 一尺胛t ) c 包丢失率p l p