（计算机应用技术专业论文）基于网络演算的网络建模方法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着技术的进步，通信系统得到了极大的发展。高速网络的应用和普 及使一些性能要求高的应用成为可能。这些应用对网络的吞吐量、时延、 时延抖动和丢包率等方面的网络性能有严格的限制。因此，i e t f 提出了确 保服务模式来为这些应用提供确保性能服务，i n t s e r v 就是其中最重要的一 种。如今的i n t s e r v 分组交换网络已成为i n t e r n e t 的基础通信设施。相对于只 提供数据服务的传统通信网络，i n t s e r v 网络可以为多种业务提供各种类型 的服务，包括数据、语音、视频和其他数据流服务。其中实时通信服务必 须能够为用户传送的数据信息提供传送时延、时延抖动、吞吐量和丢包率 等方面的性能保证。然而，网络性能的分析，特别是端到端性能的分析一 直以来都是公认的复杂问题。 网络演算是一门能够解决网络复杂闯题的新兴理论。该理论是基于最 小加代数论建立起来的。应用网络演算，可以更容易地理解i n t s e r v 网络的 基本特性、窗口业务流控制、数据调度以及计算缓冲区和时延等性能指 标。同样，端到端最大时延、时延抖动、最大队列长度和有效带宽也可以 方便地应用网络演算来推导。 本论文深入研究基于网络演算的网络建模和性能分析方法。论文首先 介绍一些基本的网络演算概念，重点介绍其中两个最重要的分析工具：到 达曲线和服务曲线。应用到达曲线直观地分析一些经典的网络业务模型， 如：漏桶算法模型、通用信元速率算法模型、恒定比特率业务流模型和可 变比特率业务流模型等。然后论文介绍了用一个简单的速率延迟服务曲线 来抽象表示所有的分组调度器。基于这些分析工具和基本规则，推导当到 达业务流分别是漏桶算法业务流、通用信元速率算法业务流、恒定比特流 和可变比特流时的时延界、队列长度界和有效带宽。并在分析结果的基 础上讨论了网络演算在i n t s e r v 资源预留、接纳控制和性能分析等方面的应 用。 一堕童奎望奎兰亟主堡窒生兰堡笙奎 笙! ! 夏 _ _ _ _ - - - - - - _ _ - _ _ _ _ _ _ _ _ - - _ _ _ _ - _ - _ _ - _ _ _ _ _ 一 本论文还使用网络演算作为分析工具来研究服务策略的性能问题。在 归纳总结已有文献中提出的能够在分组交换网络中为每个连接提供端到端 性能保证的服务策略基本原理的基础上，用网络演算中的服务曲线来模拟 各种服务策略，并用网络演算理论分析工具来推导这些服务策略提供的性 能保证，说明它们的机制、相似之处和不同之处。还讨论了服务策略分析 中的问题及其解决方法，最后在一个总的框架中研究和比较这些服务策 略。 论文中用一些应用实例证明了本论文中分析结果的正确性和有效性， 所有推导的结论都适用于网络规划和设计以及网络优化。 关键词：q o s 服务质量；网络性能分析；网络演算；端到端时延； 时延抖动；有效带宽 西南交通大学硕士研究生学位论文第1 i i 页 a b s t r a c t w i t ht h et e c h n o l o g i c a la d v a n c e s ，c o m m u n i c a t i o ns y s t e m sh a v eb e e n g r e a t l yr e v o l u t i o n i z e d t h ea d v e n to fh i g hs p e e dn e t w o r k i n gh a si n t r o d u c e d o p p o r t u n i t i e sf o rs o m ed e m a n d i n ga p p l i c a t i o n s t h e s ea p p l i c a t i o n sh a v e s t r i n g e n tp e r f o r m a n c er e q u i r e m e n t si nt e r m so ft h r o u g h p u t ，d e l a y , j i t t e r ，a n d l o s sr a t e s o ，i e t fp r o p o s e ds o m eg u a r a n t e e ds e r v i c es c h e m e sa i m i n ga t p r o v i d i n gg u a r a n t e e ds e r v i c e sf o rv a r i o u sa p p l i c a t i o n s ，a n do n eo ft h em o s t i m p o r t a n ti si n t s e r v t o d a y sp a c k e t - s w i t c h i n gi n t e g r a t e d - s e r v i c e sn e t w o r k s p r o v i d et h ec o m m u n i c a t i o ni n f r a s t r u c t u r ef o rt h ei n t e r n e t u n l i k et r a d i t m n a l c o m m u n i c a t i o nn e t w o r k sw h i c ha r ed e s i g n e dt oo f f e ras i n g l et y p eo fs e r v i c e ， i n t e g r a t e d - s e r v i c e sn e t w o r k sa r ea b l et oo f f e rm u l t i p l es e r v i c e sf o rv a r i o u s t y p e so ft r a f f i c ，s u c ha sd a t a ，v o i c e ，v i d e oa n d8 0o n s oi n t e g r a t e d - s e r v i c e s n e t w o r k sh a v et os u p p o r tr e a l - t i m ec o m m u n i c a t i o ns e r v i c e st h a ta l l o wc l i e n t s t ot r a n s p o r ti n f o r m a t i o nw i t hp e r f o r m a n c eg u a r a n t e e se x p r e s s e di nt e r m s o fd e l a y , j i t t e r ，t h r o u g h p u t ，a n dl o s sr a t e h o w e v e r ，t h ea n a l y s i so fp e r f o r - m a n t e s ，e s p e c i a l l yt h ee n d t o - e n dp e r f o r m a n c e sh a sb e e na no p e nc o m p l e x p r o b l e m n e t w o r kc a l c u l u si sas e to fr e c e n td e v e l o p m e n t st h a tp r o v i d ed e e pi n - s i g h t si n t of l o wp r o b l e m se n c o u n t e r e di nn e t w o r k i n g t h ef o u n d a t i o no fn e t - w o r kc a l c u l u sl i e si nt h em a t h e m a t i c a lt h e o r yo fm i n - p l u sa l g e b r a w i t h n e t w o r kc a l c u l u s ，w ea r ea b l et ou n d e r s t a n ds o m ef u n d a m e n t a lp r o p e r t i e so f i n t e g r a t e d - s e r v i c e sn e t w o r k s ，w i n d o wf l o wc o n t r o l ，s c h e d u l i n ga n db u f f e ro r d e l a yd i m e n s i o n i n g b ya p p l y i n gn e t w o r kc a l c u l n s ，t h em a x i m u me n d - t o - e n d d e l a yb o u n d ，t h ei n 越x i l n u i nb a c k l o gb o u n d ，j i t t e ra n de f f e c t i v eb a n d w i d t ho f i n t s e r vg u a r a n t e e ds e r v i c e se a r lb ed e r i v e d i nt h i sp a p e rw er e s e a r c hd e e p z yo nt h em e t h o do fm o d e l i n ga n da n a l y s i s 西南交通大学硕士研究生学位论文第页 n e t w o r k sb a s e do nn e t w o r kc a l c u l u s w ef i r s ti n t r o d u c et h eb a s i cn e t w o r kc a l - c u l u sc o n c e p t s t w oo ft h em o s ti m p o r t a n ta n a l y s i st o o l sa r ea r r i v a lc u l v e s a n ds e r v i c ec u r v e s t h e nt h ec o n c e p t so fl e a k y - b u c k e t ，g e n e r i cc e l lr a t ea l g o - r i t h m ( c c r a ) ，c o n s t a n tb i tr a t e ( c b r ) f l o w ，v a r i a b l eb i tr a t e ( v b r ) f l o w a r e d e s c r i b e di nt h ea p p r o p r i a t ef r a m e w o r k ，o fa r r i v a lc l l l w e s w es h o wt h a ta l l r 舭b a s e dp a c k e ts c h e d u l e r sv a nb ea b s t r a c tb yas i m p l er a t el a t e n c ys e r v i c e c u r v e a n db ya p p l y i n gt h e s ef u n d a m e n t a lr u l e so fn e t w o r kc a l c u l u s ，b o u n d s o nd d a y , b u f f e ra n de f f e c t i v eb a n d w i d t hf o rl e a k yb u c k e t ，g c r a ，c b ra n d v b rc a l lb ed e r i v e da n ds o m ep r a c t i c a le x a m p l e sa r eg i v e n w ea l s od i s c u s s a p p l i c a t i o no fn e t w o r kc a l c u l u st or e s o u r c er e s e r v a t i o n ，a d m i s s i o nc o n t r o la n d p e r f o r m a n c ea n a l y s i si ni n t s e r vn e t w o r k s t oa d d r e s st h ep e r f o r m a n c ei s s u e so fs e r v i c ed i s c i p l i n e s ，i nt h i sp a p e r ， w ea l s oa p p l yt h en e wa n a l y s i st e c h n i q u eo fn e t w o r kc a l c u l u sa p p r o a c h w e s u r v e ys e v e r a ls e r v i c ed i s c i p l i n e st h a ta r ep r o p o s e di nt h el i t e r a t u r et op r o - v i d ep e r - c o n n e c t i o ne n d - t o - e n dp e r f o r m a n c eg u a r a n t e e si np a c k e t - s w i t c h i n g n e t w o r k s w eu s eo n eo ft h eb a s i cn e t w o r kc a l c u l u st o o l s k n o w n 够s e r v i c e c u r v e ，t om o d e ls e r v i c ed i s c i p l i n e s w ed e r i v et h e i rp e r f o r m a n c eg u a r a n t e e s t h e yc a np r o v i d ew i t ht h eb a s i ca n a l y s i st o o l so fn e t w o r kc a l c u l u s ；w ea l s o d e s c r i b et h e i rm e c h a n i s m s ，t h e i rs i m i l a r i t i e sa n dd i f f e r e n c e s v a r i o u si s s u e s a n dt r a d e o i t si na n a l y z i n gs e r v i c ed i s c i p f i n e sf o rg u a r a n t e e dp e r f o r m a n c es e t - v i c ea r ed i s c u s s e d ，a n da g e n e r a lf r a m e w o r kf o rs t u d y i n ga n dc o m p a r i n g t h e s e d i s c i p l i n e sa r ep r e s e n t e d t h ev a l i d i t ya n de f f e c t i v e n e s so ft h ea n a l y t i cr e s u l t sa r ev e r i f i e dw i t h a p p l i c a t i o ne x a m p l e s t h er e s u l t sp r e s e n t e dh e r ep r o m i s et ob ea p p l i c a b l e f o rn e t w o r kd e s i g na n do p t i m i z a t i o n k e yw o r d s ：q o s ；n e t w o r kp e r f o r m a n c ea n a l y s i s ；n e t w o r kc a l c u l u s ； e n d - t o - e n dd d a y ；j i t t e r ；e f f e c t i v eb a n d w i d t h 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇 编本学位论文。 本学位论文属于 i 保密口，在年解密后适用本授权书； 2 不保密口。使用本授权书。 ( 请在以上方框内打”) 学位论文作者签名： 日期： 指导老师签名： 日期； 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工 作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均己在文中作了明确的说明。本人完全意识到本声明的法律结果由 本人承担。 本学位论文的主要创新点如下： 1 将新兴的网络演算理论应用到网络性能计算中，更为准确地评价网 络性能； 2 ，深入研究基于网络演算理论的网络业务建模方法，建立网络性能评 价数学模型，确定各项性能指标并提出计算方法； 3 ，在研究各种服务策略工作原理的基础上，应用网络演算理论工具分 析其工作方式及其性能( 时延界、时延抖动、数据积压界等) 的计算。 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 本论文主要针对传统基于随机排队论的网络建模方法的局限性，研究基于 新兴的网络演算( n e t w o r kc a l c u l u s ) 理论的网络建模方法。本文的研究范围涉 及到网络演算，分组交换网络、综合服务( i n t s e r v ) 网络、服务镱略( s e r v i c e d i s c i p l i n e s ) 本课题的研究结果可以应用于网络规划与设计和网络分析与优化。 1 1 研究背景 随着网络向高速化综合化方向发展，高速网络传输技术成为目前网络研究的 热点。国内外研究人员围绕高速网络的业务拥塞控制、流量监测、带宽分配及网 络性能评价等课题开展了大量工作，其中建立一个能准确籀述网络业务( t r a f f i c ) 和分析网络性能的模型是所有这些研究工作的基础。网络业务模型及其性能评价 是网络技术研究的重要基础和步骤，它一直作为一个活跃的研究领域倍受网络研 究人员的关注。传统的网络分析模型通常是采用随机排队论等方法来研究，使得 相应的队列系统及网络性能评价易于数学解析由于网络测量技术的限制，在很 长一段时间内，网络研究人员并不能得到大量实际的网络业务数据进行分析研 究，所以研究人员很少从统计意义上考查这些传统模型与网络实际业务的拟合程 度，导致在网络研究过程中，不断有研究人员对传统模型的有效性提出质疑 近十年里，随着网络应用的发展，i n t e r n e t 中网络会议、音视频传输、网上 娱乐等多媒体服务所占的比例越来越高，使得现代网络业务的复杂性和突发性 已非传统通信网所能比拟。这些多媒体应用对网络的性能如时延界限、时延抖 动有效带宽等有严格的限制”，如音频和视频回放”( p l a y - b a c k ) 应用需要一 定的带宽，不能容忍数据报的到达晚于系统的回放时间。为此，i e t f ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ) 提出 i n t s e r v ”，提供确保服务( g u a r a n t e e ds e r v i c e ) 和负载受控服务( c o n t r o l l e d l 0 a ds e r v i c e ) 两种服务方式，其中应用最广的是确 保服务，它能提供严格的时延和带宽保证i n t s e r v 的性能指标是网络性能分析和 西南交通大学硕士研究生学位论文第2 页 接纳控制等的基础，传统的方法是采用随机排队论等方法来研究，很难获得简洁 明了、实用性强的分析结果，特别是对于端到端的网络性能分析，传统的方法就 更加无能无力了能否揭示现代网络业务的真实特性并为网络研究提供一个正确 有效的性能分析模型，成为现代网络技术的关键。由于传统业务模型和分析模型 描述能力上的欠缺，诞生了网络演算这门理论。网络演算”是最近l o 多年在国外 发展起来的- - f 7 网络分析理论，它提供一种简单明了的方法来计算网络极端情况 下的性能。网络演算是一组基于最小加代数卷积和反卷积运算的定义与结论，如 何利用这些结论来进行网络分析与设计是一个值得研究的问题。特别是如何利用 其在分析网络端到端性能方面的优势来分析和评价网络性能更是具有重要的研究 价值和实用价值。 1 2 基于网络演算的网络建模方法的优势 当今的世界是一个网络的世界，能提供各种应用服务的网络将世界各地连接 成一个整体。因此，如何设计一个令人满意的网络，以及如何有效地管理和维护 现有的网络，具有重要的研究意义。国内外的研究人员都在这个方面投入了大量 的精力。在网络设计方面，当设计一个新的网络时，设计人员必须解决如何计算 网络节点的缓冲区长度；如何选择合适的调度策略等。而对于一个已经存在的网 络，网络管理和维护人员要能够对网络的各项性能指标做出正确的评价 传统的网络分析理论是采用随机排队论等方法来研究，没有考虑与实际网络 的拟合程度。特别是随着网络应用的发展，需要网络提供能够保证端到端性能的 确保服务。现代网络的这些特性对网络的分析、设计、控制和管理产生了巨大影 响。另外，由于存在“只为突发数据付费一次( p a yb u r s to n l yo n c e ) ”现象，数 据通过多个节点时的最坏时延要比各个节点的最坏时延的简单累加要小，需要研 究更精确的端到端性能的计算方法。最近十多年国外发展起来一门新的分析网络 中确定排队系统的理论一网络演算它是一种网络队列系统性能定量分析的重要 而有效的新型数学工具，可以被看作是用于计算机网络的系统理论，也可应用于 并发系统和数字电路等的分析。这是一组基于最小加代数( m i n - p l u sa l g e b r a ) 卷积和反卷积运算的定义与结论，应用网络演算可以建立更为准确的网络模型和 西南交通大学硕士研究生学位论文第3 页 简单明了地计算网络极端情况下的性能。现代网络的一些特性，如：。整形器保 持到达限制不变( s h a p e r sk e e pa r r i v a lc o n s t r a i n t s ) ”、“只为突发数据付费一 次( p a yb u r s t so , l yo n c e ) ”1 等也能够用网络演算更为准确的描述和理解。同 样，通过对网络进行等效模拟，可以很容易地分析网络的端到端性能。因此网络 演算技术近年来取得了较大的进展，尤其是最小加代数( r a i n - p l u sa l g e b r a ) 的引 入，使得到达曲线、服务曲线等演算工具更具有一般性，并且性能界限表示形式 更加简洁”1 。网络演算在服务策略的性能分析方面也有独特的优势。为了保证服 务质量( q 0 8 ) ，需要对网络中的数据流采用一定的服务策略”1 。无论是在综合 服务( i n t s e r v ) 还是在区分服务( d i f f s e r v ) 中，都涉及到服务策略。服务策略 对q o s 保证至为重要，它能够为每个连接提供端到端的服务质量保证。网络演算是 计算端到端延迟确定性上界的重要而有效的方法”，应用网络演算理论中的服务 曲线可以精确地模拟各种服务策略并方便地分析其端到端性能指标，而这正是传 统随机排队论分析方法的欠缺之处。 总而言之，传统的基于随机排队论的网络分析方法已不能精确地刻画网络的 业务及其性能特性，迫切需要研究适合现代网络应用的网络业务建模方法，研究 网络性能，确定各项性能指标并提出相应的计算方法而网络演算具备了从理论 上分析服务质量( q o s ) 控翩机制所必需的业务流的流量特性模型、路由器的调 度策略及性能界限这三个基本要素。所以网络演算被广泛应用于网络q o s 研究的 建模和理论分析中。而本课题将主要研究基于网络演算的i n t s e r v 网络的业务模型 和性能评价模型。 1 3 国内外研究现状 网络演算是目前国际上网络理论研究的热点，但国内关于网络演算 的理论及其应用的研究工作还比较少。网络演算理论由r l c r u z ”“1 等 人开创并由c s c h a n g “2 1 4 和j y l eb o u n d e c “”等人发展起来。其 中p a r e k h 、g a l l a g e r o 1 ”和c r u z ”“1 做了大量的基础研究工作，提出基于到达 曲线和服务蛀线的分析方法和一些网络环境中的重要定理和结论。s a x i o w a n o “扩 展了这些研究结果，并给出相应的应用规则使之可应用于更为普遍的网络环境 西南交通大学硕士研究生学位论文第4 页 中。b o u d e e ”深入研究并总结关于网络演算的结论和定义，将之发展完善并系统 化为网络演算理论体系，即实用于网络环境性能分析的系统理论。 网络演算又分为确定网络演算和统计网络演算。确定网络演算 ( d e t e r m i n i s t i cn e t w o r kc a l c u l u s ) 提出了一个精巧的网络最坏情况性能分析 框架，可用来推导各种链路调度算法的时延和积压( b a c k l o g ) 的上界”。，可以 方便地计算多个网络节点的端到端时延和队列长度。但确定网络演算没有考虑 统计复用带来的好处，通常会高估实际的流量资源需求，存在资源利用率低的 缺点。为此，最近几年研究人员提出了统计网络演算“1 ( s t a t i s t i c a ln e t w o r k c a l c u l u s ) ，它能克服确定网络演算豹缺点，但使用比较复杂 i n t s e r v 是i e t f 为了满足当今高速发展的i n t e r n e t 网络中的各种多媒体应用对 网络性能的严格要求”1 而提出的确保服务模式。它提供两种服务方式：确保服 务( g u a r a n t e e ds e r v i c e ) 和负载受控服务( c o n t r o l l e d - l o a ds e r v i c e ) 。前者提 供真实的确定的服务质量保证，而后者提供的是近似的保证。其中应用最广的是 确保服务，它能提供严格的时延和带宽保证i n t s e r v 是目前常用的网络服务质量 策略之一，其性能分析，特别是端到端的性能分析是一个没有很好解决的问题。 而i n t s e r v 的性能指标是网络性能分析和接纳控制等的基础，传统的方法是采用随 机排队论等方法来研究，但对于端到端的网络性能分析，传统的方法显得无能为 力目前网络服务质量相关的研究很多”，但这些研究( 特别是国内) 大多只 涉及网络服务质量的一般性概念，以及资源预留协议r s v p 的原理及工作方式， 很少涉及至u h t s e r v 确保服务下的性能参数如最大端到端时延界，最大队列长度 界、基于端到端时延约束的有效带宽和基于缓冲区长度约束的等效容量等性能参 数。而孵络演算在这些性能参数的分析上有独特的优势，所以研究其在i n t s e r v 网 络中的应用具有重要的实用价值， 在服务策略方面，通过国内外大量的研究，已经有了比较成熟的理论成果， 提出了许多类型的网络服务和服务策略。常见的网络服务包括尽力服务( b e s t - e f f o r ts e r v i c e ) ，实时服务( r e a l - t i m es e r v i c e ) ，确定性服务( d e t e r m i n i s t i c s e r v i c e ) ，统计性服务( s t a t i s t i c a ls e r v i c e ) ，确保性能服务( g u a r a n t e e dp e r - f o r m a n c es e r v i c e ) ，预报服务( p r e d i c t e ds e r v i c e ) ；常用的服务策略有：先 进先出f i f o ( f i r s t i n - f i r s t - o u t ) ，静态优先级( s t a t i cp r i o r i t y ) ，最小期限 西南交通大学硕士研究生学位论文第5 页 优先e d d ( e a r l i e s t - d u e - d a t e ) 陋”，虚拟时钟( v i r t u a lc l o c k ) ”。，公平排 队f q ( f m rq u e u e i n g ) 8 ”，加权公平排队w f q ( w e i g h t e df a i rq u e u e i n g ) 或 分组化通用处理器共享p g p s ( p a c k e t i z e dg e n e r a l i z e dp r o c e s s o rs h a r i n g ) ”“， 自时钟公平排队s c f q ( s e l f - c l o c k e df a i rq u e u e i n g ) ”1 ，最坏情况公平加权公平 排队w f 2 q ( w o r s t - c a s ef a i rw e i g h t e df a i rq u e u e i n g ) 9 “，基于时延的最小期 限优先d e l a y - e d d ”4 ；基于时延抖动的最小期限优先j i t t e r - e d d ，停走型服 策略s t o p - a n d - g o i ”，层次轮询h r r ( h i e r a r c h i c a lr o u n dr o b i n ) 9 “，速率受 控静态优先级r c s p ( r a t e - c o n t r o l l e ds t a t i cp r i o r i t y ) ”等。国内外的科研人员对 这些服务策略的实现原理、工作方式及其提供的性能保证都进行了比较深入的研 究。在早期的研究工作中，通常是基于单个节点和周期性的业务流来分析网络的 性能”4 ，所以提出的服务策略相对简单，在提供性能保证方面的能力也有限。并 且经典的随机排队论分析研究的通常是多个业务流的平均性能指标而不是端到端 性能。近年来随着网络测量技术的进步，研究人员发现网络流量具有突发性，并 且越来越多的网络应用要求在更为复杂的网络环境中的端到端性能得到保证。所 以确保性能服务得到了重视，这类服务提供的是基于每条连接( p e r - c o n n e c t i o n ) 的端到端性能保证9 叫。在文献 2 0 ，2 3 ，2 4 ，2 6 ，2 8 - 3 1 1 中提出了许多在高速网络 环境中可基于每条连接提供性能保证的服务策略。许多新的关于服务策略性能分 析的方法和技术也在文献f 2 5 ，3 5 - 5 0 4 e 有讨论。l - i z h a n g 将这些服务策略及其性能 加以概括总结和全面比较”“，并讨论在设计确保服务策略中的难点和解决方法。 尽管服务策略和相关的性能问题在过去已经得到广泛的研究，但应用新兴的网络 演算理论来建立其服务曲线模型，研究其端到端性能方面的工作还很少 1 4 本文的主要研究工作及论文内容安排 本课题的目标是对网络演算在网络建模和网络性能评价中的应用进行研究， 具体研究网络演算的适用场合，具体的应用方法。针对传统网络业务模型和分析 方法的欠缺和不足之处，研究如何利用网络演算建立网络业务模型，基于网络演 算的i n t s e r v 网络建模方法。确定网络性能评价模型及其参数指标，提出各项指标 的计算方法，并与传统网络业务模型下的各项参数指标及其计算方法进行对比。 西南交通大学硕士研究生学位论文第6 页 本文在分析总结i n t s e r v 网络原理与实现方法的基础上，深入研究了网络演算技术 在i n t s e r v 网络性能分析与设计中的应用方法，通过建立通用网络性能评价模型， 对网络进行性能评价或算法优化，推导出了i n t s e r v 确保服务下的最大端到端时延 界、最大队列长度界和网络有效带宽等性能参数的计算公式，通过具体的应用 实例，验证了计算结果的正确性和有效性。这些分析结果是i n t s e r v 网络接纳控 制”1 网络性能分析、网络设计等应用的基础。此外，本课蘧还涉及到确保服务 下服务策略( s e r v i c ed i s c i p l i n e s ) 的工作原理及其性能指标( 时延、时延抖动、队 列长度等) 的计算方法。多媒体等实时应用要求提供确保服务，确保服务需要用 到比f m o 、静态优先级等更为复杂的调度策略，通过这些调度策略来保证端到端 的q o s 保证。服务策略的性能分析对于选择合适的网络服务策略具有十分重要的 意义，也是网络优化设计及性能评价的关键。本论文将在归纳总结已有的提供确 保服务的服务策略基本原理和工作方式的基础上，研究如何用网络演算中的服务 曲线来模拟各种服务策略，以及如何应用用网络演算理论分析工具来分析这些服 务策略提供的性能保证。 本论文的内容安排如下，第2 章主要回顾网络演算理论的发展，介绍网络演 算基本定义、结论和分析方法。建立网络演算中的分析模型，本论文的研究工作 都要围绕这个分析模型展开。举出在两络性能分析中几个重要的性能指标如：时 延，缓冲区大小，有效带宽、等效容量、时延抖动等的定义及其分析方法。 第3 章主要是关于分组交换同络的分析。概述分组交换网络的特征和其传送的 数据业务流。应用到达曲线来分析分组交换网络中的几种最主要的业务模型：漏 桶算法模型、信元速率算法模型、恒定比特率业务流模型以及可变比特率业务流 模型的特性以及随时间变化的规律。并用服务曲线来等效分析分组交换网络中的 网络结点，说明几乎所有的网络( 包括复杂网络、简单网络和单个结点 都可以 用一个被称之为速率延迟( r a t e - l a t e c y ) 陆线的服务曲线来模拟。然后应用第二章 中的方法和结论分别分析分组交换网络中的几种业务模型的各项性能指标：如时 延、队列长度和有效带宽。 第4 章主要研究网络演算在i n t s e r v 网络中的应用，包括其在资源预留、接纳 控制、性能分析等方面的应用。如r s v p 的具体的实现方法，如何计算网络的有 效带宽，如何有效地实现资源预留，如何计算给定资源条件下的网络性能等等。 西南交通大学硕士研究生学位论文第7 页 这些问题是制约网络应用发展的关键技术问题。本章在这方面进行了深入的研 究，通过研究网络演算在网络资源预留和接纳控制中的应用方法，推导出了基于 端到端时延约束的有效带宽和基于缓冲区长度约束的等效容量的计算公式，两者 均可作为接纳控制时有效带宽的计算方法。并且通过具体的应用实例，验证了本 章分析结果的正确性和有效性。 第5 章主要是关于服务策略( s e r v i c ed i ：s d p l i n e s ，也称为调度策略) 的工作 原理及其性能的计算。研究内容包括：恒定工作服务策略：基于时延的最小期 限优先( d e l a y - e d d ) ”，虚拟时钟( v c ) 删，通用处理器共享( g p s ) ”“， 加权公平排队w f q ( 也称为分组化通用处理器共享p g p s ) ”，白时钟公平排队 ( s c f q ) ，和最坏情况公平加权公平排队w f 2 q 。”；非恒定工作服务策略： 基于时延抖动的最小期限优先( j i t t e r - e d d ) ”，停走型服务策略( s t o p - a n d - g o ) 。”，层次轮询( h r r ) 等。研究这些服务策略的实现原理和工作方式，基 于网络演算的各种服务策略的性能分析；研究各种服务策略的时延、时延抖动、 缓冲区长度和应用不同服务策略下的q o s 保证；并通过比较传统方法的分析结果 和网络演算方法的分析结果阐明网络演算的优势。 西南交通大学硕士研究生学位论文第8 页 第2 章网络演算技术基础 网络演算( n e t w o r kc a l c u l u s ) 是最近1 0 多年发展起来的用于进行分组交换 网络资源需求分析的理论，由r l c r u z “1 1 开创并f i t p a r e k h 、g a l l a g e r “1 ”、c s c h a n g “。“和j y l eb o u n d e c “”等人发展起来。网络演算是一种网络队列系 统性能定量分析的重要而有效的新型数学工具，主要被应用于确定排队系统的分 析中最初提出这种技术的耳的是解决网络服务质量( q o s ) 的资源预留问题9 ”， 经过s a r i o w a n “”和b o u n d e c ”1 等人将之发展完善和系统化，网络演算已经可以广泛 地应用于各种类型网络的性能分析，特别是在网络端到端性能分析方面有其独特 的优势。 网络演算是基于最小加代数( m i n - p l u sa l g e b r a ) 的一组结论，包括最小加代 数下的卷积、反卷积等。网络演算中基本的分析工具为：到达曲线和服务曲线。 它采用包络方法来描述网络业务的到达和服务，其中到达曲线限制了业务流的到 达过程，而服务曲线则限制了网络节点的输入、输出行为“网络延迟的上界由 进入睡线与服务曲线问的水平方向上的最大距离所决定，数据的积压上界由两条 曲线间的垂直方向上的最大距离决定。网络演算具备了从理论上分析q o s 控制机 制所必需的业务流的流量特性模型、路由器的调度策略及性能界限这三个基本要 素。所以网络演算被广泛应用于网络q c s 研究的建模和理论分析中，如利用网络 演算建立的确保速率服务和延迟速率服务的关系模型”，基于网络演算的参数区 分网络服务的接纳控制模型”，将网络演算作为数学工具，计算端到端的网络性 能指标从而更准确地对网络整体性能做出科学的评价等 网络演算又分为确定网络演算和统计网络演算。确定网络演算 ( d e t e r m i n i s t i cn e t w o r kc a l c u l u s ) 提出了一个精巧的网络最坏情况性能分析 框架，可用来推导各种链路调度算法的时延和积压的上界“，可以方便地计算多 个网络节点的端到端时延和队列长度。但是确定网络演算没有考虑统计复用带来 的好处，通常会高估实际的流量资源需求，存在资源利用率低的缺点为此，最 近几年研究人员提出了统计网络演算“7 “删( s t a t i s t i c a ln e t w o r kc a l c u l u s ) ， 西南交通大学硕士研究生学位论文第9 页 它能克服确定网络演算的缺点，但使用比较复杂。下面首先介绍一些必要的网络 演算相关定义，然后介绍本文用到的网络演算结论。 2 1 网络演算基本概念 本节主要介绍网络演算”“1 ”相关定义和结论。网络演算是关于计算机网 络中确定排队系统的分析工具，它是基于最小加代数的理论体系。 定义2 1 1 广义增函数集合 设函数，( ) 连续且存在一阶导数，则广义增函数集合定义为： f = f ( t ) l f ( o ) o ，v ust ，( ) f c t ) ，t 【o ，+ o 。) ) ( 2 - 1 ) f o = f ( t ) l f ( t ) f f ( o ) = o ) 定义2 1 2 最小运算 ，a g = m i n b ，虬, g f( 2 - 2 ) 最小加卷积的形式类似于传统卷积法，但意义不同，其定义如下： 定义2 1 3最小加卷积( m i t t - p l u sc o n v o l u t i o n ) 设函数，和9 为两个非负的广义递增时间函数( 其值可能取无穷大) ，函数， 和9 的最小加卷积运算为旧 ( ，o g ) ( t ) 2o 恶乏。 ，0 一s ) + 9 ( s ) ) ( 2 - 3 ) ( 当t o 与最小加卷积运算不同的是，当t o 时，函数( ，e g ) ( t ) 的值并不必须为0 。 下面为了更方便地说明网络演算中的基本分析工具：服务曲线和到达曲线， 假设有一个可以被看作黑盒的系统s ，它的一端用于接收输入的数据，另一端 在经历一定的延迟后输出处理后的数据。可以用一个累积( a c c u m u l a t i v e ) 函 数，( t ) 来作为输入函数，它是指时间【o ，司内输入的数据比特数。用函数o ( t ) 来表 示系统s 的输出，通常取x ( o ) = 0 ，o ( 0 ) = 0 。 定义2 1 ，5到达曲线( a r r i v a lc u r v e ) 给定一个定义域为t20 的广义增函数a ，当且仅当v s t ：z ( t ) 一i ( s ) o ( 亡一s ) 时，称。为j 的到达曲线，或者说j 受限于到达曲线n ( 即。一s m o o t h 嘲) 也可以表示为”5 ” x c t ) ( foa ) ( t ) ( 2 - 5 ) 特别地，如果到达曲线为 a ( t ) = m i n ( p t + mr