（通信与信息系统专业论文）基于综合动态理论的atm网络拥塞控制的研究.pdf

摘要 摘要 未来的计算机网络将是一种能够提供多种不同服务，以支持多种不同 应用需求，有着集成支持能力的高速分组交换网络。a t m 网络正是支持这 种综合业务数字网络的关键技术之一，已被国际电信联盟作为一项典型传 输技术加以推广。在a t m 网络中，信息流的拥塞及信息的丢失是影响网络 业务服务质量的主要原因。为了充分提高a t m 网络的性能和服务质量，设 计一个高效的拥塞控制系统是一个关键问题。本文正是以此为出发点，利 用控制理论的相关知识，实现了对三种业务的综合拥塞控制。 本文中我们改进了一个用于a t m 网络拥塞控制的算法，采用综合动态 拥塞控s j j ( i d c c ) 的方法，针对不同类型的传输实施不同的方案。i d c c 是运 用流量模型建立在非线性控制理论基础上的一种控制方案。流量模型描述 了系统的动态行为，运用信元流的概念并通过匹配队列行为达到平衡。尽 管这一模型比较简单，但是在他的基础上发展的策略却可以有效地校正模 型的错误的不精确并将网络行为控制在固定的执行范围内。 根据m i t 机制的控制思想，提出了有效活动v c 计算方法。将该方法 结合到i d c c 算法中去，不仅保持了算法原有的性能，还提高了算法的公 平性和稳定性。 关键词异步传输模式a t m ；拥塞控制；综合动态；非线性自适应；虚连接 茎生盔兰三堂堡主堂垒鲨塞 a b s t r a c t f u t u r ec o m p u t e rn e t w o r k sw i l lb e c o m eah i g hs p e e dp a c k e ds w i t c h e d n e t w o r kt h a t w i l lb ea b l et op r o v i d ev a r i o u ss e r v i c es oa st os u p p o r taw i d e r a n g eo fn e t w o r ka p p l i c a t i o n s a t mi sj u s to n eo ft h ek e yt e c h n o l o g i e st h a t s u p p o r tt h ei n t e g r a t e ds e r v i c ed i g l t mn e t w o r k ( i s d n ) ，w h i c hi sa d o p t e da sa t y p i c a lt e c h n i q u eb yt h ei n t e r n a t i o n a lt e l e c o m m u n i c a t i o nu n i o n ( i t u ) a n di s s p r e a d b u tc o n g e s t i o no f t h et r a f f i ca n dt h el o s so fd a t aa r em a i nr e a s o n st h a t a f f e c tt h eq u a l i t yo fs e r v i c e d e s i g no f a ne f f e c t i v ec o n g e s t i o nc o n t r o ls c h e m ei s c r i t i c a lt ot h ee n h a n c e m e n t so ft h en e t w o r kp e r f o r m a n c e t h ep a p e ri sb a s e do n i ta n dt h ec o n t r o lt h e o r yi si n t r o d u c e dt os o l v et h ec o n g e s t i o no fc o n t r o l l a b l e f l o 、m t h i sp a p e rp r o p o s e sag e n e r i cs c h e m ef o rc o n g e s t i o nc o n t r 0 1 i tu s e sa l l i n t e g r a t e dd y n o a n i cc o n g e s t i o nc o n t r o la p p r o a c h ( i d c c ) as p e c i f i cp r o b l e m f o r m u l a t i o nf o rh a n d l i n gm u l t i p l ed i f f e r e n t i a t e dc l a s s e so ft r a f f i c ，o p e r a t i n ga t e a c ho u t p u tp o r to fas w i t c hi si l l u s t r m e d i d c ci sd e r i v e df r o mn o n l i n e a r c o n t r o lt h e o r yu s i n gaf l u i df l o wm o d e l t h ef l u i df l o wm o d e ld e p i c t st h e d y n a m i c a ls y s t e mb e h a v i o r , u s i n gp a c k e tf l o wc o n s e r v a t i o nc o n s i d e r a t i o n sa n d b ym a t c h i n gt h eq u e u eb e h a v i o ra te q u i l i b r i u m d e s p i t et h es i m p l i c i t yo ft h e m o d e lt h ed e v e l o p e dc o n t r o ls t r a t e g yt a k e sc a r eo fm o d e l i n ge r r o re f f e c t sa n d o t h e ri n a c c u r a c i e sa n da u o w st h ee s t a b l i s h m e n to fp e r f o r m a n c eb o u n d sf o r p r o v a b l ec o n t r o l l e dn e t w o r kb e h a v i o r b a s e do nt h ei d e ao fm i ts c h e m e ，t h i sp a p e rp r o p o s e san e we f f e c t i v e a c t i v ev ca c c o u n tm e t h o d c o m b i n i n gi t t oi d c cr e m a i n st h e o r i g i n a l p e r f o r m a n c e ，a n di n c r e a s ef a i ra n ds t a b i l i t yo f i t k e y w o r d sa t m ；c o n g e s t i o nc o n t r o l ；i d c c ；n o n l i n e a rc o n t r o lt h e o r y ；v i r t u a l c o n n e c t i o n 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于综合动态理论的a t m 网络拥塞控制的研究，是本人在导师指导下，在燕山大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外 不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献 的个人和集体，均己在文中以明确方式注明。本声明的法律结果将完全由 本人承担。 作者签字张承懂 日期：”。年( 卜月j 日 燕山大学硕士学位论文使用授权书 基于综合动态理论的a t m 网络拥塞控制的研究系本人在燕山大 学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成 果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关 人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校 保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。 本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以 公布论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名：徘南瘪 日期：6 年4 月皇日 翮躲声耳 日期：庐川年助岁日 第1 章绪论 第1 章绪论 1 1 研究的目的和意义 a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) 就是异步传输模式，是国际电传联盟 i t u t 制定的标准，并于1 9 8 8 年正式为这项技术命名为a t m 技术，推荐其 为宽带综合业务数据网b i s d n 的信传输模式。在这一模式中，信息被组织 成信元( c e l l ) ，因包含来自某用户信息的各个信元不需要周期性出现，这种 传输模式是异步的。a t m 网络具有同时传输多种不同的业务形式f 如声音、 图像、数据) 和保证服务质量( q u a l i t yo f s e r v i c e ，q o s ) 的优点，成为目前国际 上的研究热点。 q o s 技术最开始即产生于对a t m 网络的研究。直到现在，q o s 领域 仍然是a t m 研究的一个热点。q o s 技术的出发点在于充分发挥网络的目标 性能，满足用户对服务的需求；同时优化对网络资源的利用。具体到a t m 网络，通信量与拥塞控制是q o s 技术的最主要的成分与基础甚至于许多 研究者己经将“q o s 技术”和“通信量与拥寒控制”这两个概念之间画上 了等号【1 o i n t e r n e t 多媒体业务的指数级、爆炸性的增长和用户对高质量、多样化 服务的需求使得“拥塞”( c o n g e s t i o n ) 成为a t m 网络发展的“瓶颈”问题。 对a t m 网络实行通信量控制与拥塞控制的技术难度要比i p 网络大。造成 这种状况的原因可以归纳为：a t m 采用了比较小的信元作为数据传输的基 本单位、这样，可以用来对信元流进行控制的比特数日就极为有限了；而 a t m 又是高速率宽带网络，如果频繁发生拥塞乃至连接中断，或者在发生 拥塞后无法及时恢复，都会造成非常严重的损失。 在a t m 网络中，为避免拥塞发生而采取的措施主要集中在两个方面： 在用户业务进入网络之前进行接纳控制，即c a c ( c o n n e c t i o na d m i s s i o n c o n t r 0 1 ) ，这个行为发生在用户网络界面叫s e t n e t w o r k i n t e r f a c e ) ；当新业务 接入到网络之中，要根据网络运行过程中的负荷情况，动态的调整用户传 燕山大学工学硕士学位论文 输速率，以适应网络的动态环境，这部分主要是针对可用比特率而言的1 2 , 3 1 。 截至目前，i t u t 定义了关于a t m 通信量和拥塞控制能力的标准，以 期获得一个简单的机制和实际的网络效率。但从实际应用的角度来看、这 个标准还是非常初级的。a t m 论坛在其“通信量管理规约版今4 0 ”中也公 布了类似的标准，较之前者有了一定的改进，但仍然没有被绝大多数的a t m 研究者认同，还需要进行大量的修订。 本章先进行拥塞问题概述，然后讨论被i t u t 和a t m 论坛采用的框架。 这些方法不适于处理突发通信量。接着要研究通信量控制与拥塞控制，即 网络为避免拥塞以便使拥塞的强度、扩散程度以及持续时间最小化而采取 的一系列动作。最后，讨论为对付突发通信量而开发的拥塞控制方法。 1 2a t m 网络对通信量和拥塞控制的需求 大多数分组交换和帧中继网络承载的是非实时数据通信量。在单个虚 电路上或帧中继连接上的通信量通常都是突发性质的，而接收系统也往往 在每一条连接上以突发的形式接收进入通信量。这样，只要在每条连接 上所需的平均数据率小于该连接的突发速率而用户网络接( u s e r n e t w o r k i n t e r f a c e u n i ) n 设汁容量稍大于所有连接上的平均数据率的总和，就可以 满足网络用户的需求。 在a t m 网络上出现的通信量模式的类型以及这些网络的传输特性，与 上述交换网络有很大的差别。分析造成这种状况的主要原因在于以下三点： ( t ) a t m 本身的速率较高非常高速的交换和传输使得a t m 网络随着 拥塞拥制和通信量控制的方式不同而有很大的变化。很多依赖于a t m 这一 特性的通信量不接受拥塞控制。例如，话音和视像通信量在网络发生拥塞 时也不能停止发送信元。 ( 2 1 信元相对较小信元的发送时间大大小于通过网络的传播时延，因 此反馈就很慢。 ( 3 ) 公平性问题a t m 网络通常可支持很大范围的应用，其所需带宽从 每秒几千比特到每秒几百兆比特。相对简单的拥塞控制方法通常只能惩罚 第1 章绪论 上述带宽范围中的一段。 在a t m 网络上的各种应用可以产生非常不同的通信量模式( 例如：恒 定比特率或可变比特率的信源) 。适用于其他网络的拥塞控制技术也难以公 平地处理这样多的种类【5 l 。 假设在一个网络中以1 5 5m b p s 的数据率传送a t m 信元。在此速率下， 每隔( 5 3 x 8b i t ) ( 1 5 0 1 0 6b p s ) = 3 x 1 0 。秒，信源向网络插入一个信元。从源用 户到目的用户传送此信元所需的时间取决于中间的a t m 交换机的个数、在 每个交换机的交换时间，以及从源站到目的站的通路中所有链路上的传播 时间。为简单起见忽略a t m 的交换时延。并假定信号以光速传输。这样， 如果源站和目的站分别位于我国大陆的最东端和最西端，则此往返传播时 延约为3 0 x 1 0 。8s 。 在这种情况下，假定从源站a 向目的站b 传送一个长文件并使用在 其他网络中都比较常用的隐式拥塞控制( 即没有显式拥塞通知，源站判断有 数据丢失时，就认为已经发生了拥塞) 。如果网络由于拥塞丢弃了信元，b 将返回一个拒绝报文给a 。这个报文将指示a 重新发送己被丢弃的信元和 所有可能的后续信元。但是，在这个网络拥塞的通知返回到a 以前，a 有 可能已经将超过4 m b 的数据发送到了网络中。这就可以解释为什么很多传 统网络中行之有效的技术，对于a t m 广域网就无能为力了。 对于a t m 网络，语音和视像信号在进行数字化后就作为一串信元流被 发送。许多用户服务，例如，语音、实时图像等，要求通过网络的时延一 定要小。一般说来，a t m 的网络可以做到这点。正如已经讨论过的，a t m 的设计就考虑到使网络内的处理和传输开销最小，因而有可能进行快速的 信元交换和选路。 但是，还有另个重要的需求，它在某种程度上与前面的需求相矛盾， 这就是向目的用户交付信元的速率必须保持恒定。但信元的交付速率又不 可避免地有某些变化，这与在网络内部和在源端u n i 的情况都有关。下面 就简要地介绍这些情况。 首先，研究目的用户怎样对付信元从源用户传送到目的用户时所产生 6 的时延变化。 燕山大学工学硕士学位论文 令d ( o 表示第i 个信元所经受的端到端时延。目的系统并不知道这个时 延的准确数值：在每一个信元上没有相关的时间戳信息，即使有，也不可 能在源站和目的站的时钟之间保持完全同步。 当一个连接上的第一个信元在f ( o ) 到达时，目的用户就在将此信元交付 给应用程序之前，将其迟延一个附加的数值v ( o ) 。这里v ( o ) 是这个应用能 够容许的信元时延偏差的估值，而且往往也是这个网络的最可能产生的时 延的大小。 从第一个信元往后所有的后续信元都要经过迟延。要想获得一个恒定 的速率，假设等于每秒r 个信元，那么从一个信元开始交付到下一个信元 开始交付的时间间隔，应当等于占= 1 r 。下一个信元应迟延一个可变的时 间矿( f ) ，它满足f ( 1 ) + v o ) = f ( o ) + p ( o ) + 6 ，因此， v o ) = 矿( o ) 一p ( 1 ) - ( f ( o ) + 6 ) 】( 1 - 1 ) 一般项的表示是： 矿( f ) = v ( o ) - f ( f ) - o ( 0 ) + 1 6 ) 】( 1 - 2 ) 如果计算出的y ( f ) 值是负的，则应丢弃该信元。结果是，数据以恒定 的比特率交付给高层，但偶尔因为有丢弃的信元而产生一些间隙。 信元时延偏差的另一个组成部分是出于网络的一些操作造成的，比如 排队、路由选路等。对于分组交换网络，分组时延偏差可以是相当可观的， 这是由于在每一个中间交换节点的排队效应，以及分析分组首部和完成路 由选择所需的处理时间造成的 6 1 。 在a t m 网络中，产生信元时延偏差的主要原因是： ( 1 ) a t m 协议的设计是将中间交换化点上的处理开销最小化。信元为固 定大小，且具有固定的首部格式，没有所需的流量控制和差错控制的处理。 ( 2 1 为了适应a t m 网络的高速率，a t m 交换机必须设计成能够提供非 常高的吞吐量。因此，在一个节点上对一个单个信元的处理时间可以忽略 不计。 a t m 网络对信元时延偏差的影响要比帧中继的情况小。能够对信元时 延偏差起明显作用的惟一因素就是拥塞。如果网络开始出现拥塞，那么或 者一些信元要被丢弃，或者在受影响的节点上排队时延要增长。 4 第1 章绪论 1 3 a t m 网络中的通信量控制 一旦连接准许控制( c a c ) 接受了一个连接，网络的使用参数控制( u s a g e p a r a m e t e rc o n t r o l ，u p c ) 功能就监视此连接、以决定通信量是否与通信量合约 相一致。u p c 的主要目标就是保护网络的资源，通过检测是否违背了己指 派的参数并采取适当的措施，可使得一条连接上的过载不至于使另一条连 接的q o s 恶化。 1 3 1 峰值信元速率算法 首先讨论峰值信元速率和相关的时变码率( c d v t ) 。简单地说，所谓遵 守合约的通信流量就是其信元传输的峰值速率不超过所约定的峰值信元速 率，而信元时延偏差都在所约定值的上限之内。 a t m 通信量管理规约提供了一个算法，此算法既可作为峰值信元速率 和c d v t 的关系的一种工作定义，也可用于使用参数控制u p c 来监视是是 否与通信量合约相一致叽 假定我们有一个指明的峰值信元速率r 以及一个容许的信元时延偏差 c d v t 极限f ，则t = 1 r 是在没有c d v t 的情况下的信元间的平均到达时 间间隔。在有c d v t 的情况下，t 是在峰值信元速率时的平均到达时间间 隔。因而峰值信元速率算法就表达为g c 删( t ，f ) 。 令在一个连接上的第一个信元的到达时间为( 1 ) 。算法将下一个信元 到达目标时间，即理论到达时间( t h e o r e t i c a la r r i v a lt i m e ，t a t ) 迸行更新。如 果信元的到达的实际时间比t a t 要晚，则属于遵守合约t a t 就更新为到 达时间加上t 。 如果信元的到达比t a t 早，但仍在t a t 的时间单位之内( 即这个信元仍 在c d v t 之内1 ，那么这个信元仍属于遵守合约，应将t a t 增加t 。若信元 过早到达f 在t a t f 之前) ，由于它在c d v t 的界限之外，因此，它属于不 遵守合约的信元，将被丢弃，在这种情况下，t a t 保持不变。 燕山大学工学硕士学位论文 1 3 2 持续信元速率算法 持续信元速率算法既可作为持续信元速率与突发容许的关系的工作定 义，也可用于使用参数控制以监视是否遵守通信量合约。 用来定义峰值信元速率监视的同样算法也可用来定义持续信元速率监 视。在这种情况下，对于持续信元速率有t 。一i r 。，是在此速率下且无 突发时的信元到达时间间隔。突发容许由t 。表示。这样，持续信元速率算 法就表示为g c r a ( t , ，f 。) 【8 ，9 1 。 突发容许并不像c d v t 那样是直接选择的。相反，它可从对通信流量 的突发性的了解推导出来。特别是，可以令t 等于在峰值速率下信元之间 的时间间隔。如果通信流量受到使用g c r a ( t ，r ) 的峰值信元速率和使用 g c 脚( t ，r 。) 的持续信元速率这两方面的约束，那么在峰值速率下的最大突 发长度m b s 应为： r， m b s = i1 + i ( 1 - 3 ) l s 一1j 在信令报文中，突发容许是用信元数编码的m b s 来传递的。m b s 可 用来导出f 。，它在g c r a 算法中用来监视持续信元速率。若给出m b s ，t 和t ，则r 。可以是以下区间中的任何一个数值： ( m b s 1 ) ( i r ) ，m b s ( t , 一丁) 为了保证均匀性，可采用最小值r ，= ( m b s - t ) ( r , - t ) 。 1 3 3u p c 的动作 网络使用g c r a 算法或某些类似的算法来确保遵守协商好的通信量合 约。最简单的策略就是在u p c 功能点使遵守合约的信元通过，同时将不遵 守合约的信元丢弃。 如果没有附加的网络资源分配给c l p = 1 的通信流量，那么被认为不遵 守合约的c l p = 0 的信元也要被丢弃。但如果用户已经对一个网络协商了两 第1 章绪论 个等级的信元丢弃优先级，那么情况就更加复杂了。这时就应该应使用如 下的规则l ”1 2 ： ( 1 ) 一个c l p = 0 的信元若遵守c l p = 0 的通信量合约，则使之通过。 ( 2 ) 一个c l p = 0 的信元若不遵守c l p = 0 的通信量合约，但遵守( c l p = o + 1 ) 的通信合约，则打上标记并使之通过。 ( 3 ) 一个c l p = 0 的信元若不遵守c l p = 0 的通信量合约，也不遵守( c l p = o + 1 1 的通信量合约，则被丢弃。 ( 4 ) 一个c l p = i 的信元若遵守( c l p = 0 + i ) 的通信量合约，则使之通过。 ( 5 ) 一个c l p = i 的信元若不遵守( c l p = 0 + i ) 的通信量合约，则被丢弃。 u p c 功能首先检查( c l p = o ) 的流是否遵守合约，然后再检查合并的 ( c l p = o + 1 ) 流。若使用了打标记选项，则不遵守合约的( c l p = 0 ) 的信元将被 打上标记，但仍看成是( c l p = 0 + i ) 流的一部分，并接受第二个检查。 1 3 4 通信量整形 g c r a 算法属于通信量管$ 4 ( t r a f f i cp o l i c i n g ) 的一种形式。通信量管制就 是调整数据流，将超过一定性能水平的信元丢弃或打上标记。还需要有一 种通信量整形( t r a f f i cs h a p i n g ) 策略作为通信量管制的辅助策略。通信量整形 用于平滑一个通信流量，以减少信元成块的现象。这可以使资源的分配更 加公平，并减少平均时延。 通信量整形的一种简单方法就是使用漏桶算法的一种形式，叫做令牌 桶( t o k e nb u c k e t ) 。g c r a 漏桶只是简单地监视通信量，并拒绝或丢弃不遵守 合约的信元。通信量整形漏桶则与g c r a 漏桶相反，它控制遵守合约的信 元流。 令牌桶的基本原理可以简单描述如下：一个令牌产生器以每秒p 个令 牌的速率产生令牌，并将其放入令牌捅中，此令牌捅的最大容量为b 个令 牌。离开信源到达的信元被放入一个缓存，其最大容量为k 个信元。要从 服务器发送一个信元，必须从桶中移走一个令牌。若令牌捅己空，则信元 必须排队等待下一个令牌。这种方式的结果是：如果已经储备了一些信元 燕山人学工学硕士学位论文 并且桶是空的，那么信元就以每秒p 个信元的平滑速率发送出去，同时在 储备的信元用完之前都没有信元时延偏差。这样，令牌桶就平滑了信元的 突发。 1 4 a b r 服务的通信量与拥塞控制 前面已经讨论了a t m 论坛发布的一些通信量管理方式和算法。这些算 法是建立在a t m 框架上的，可以为任何一种a t m 服务方式所用。除此之 外，由于a t m 各种服务方式之间存在明显的差异，因此，也存在针对某一 种服务方式通信量管理方法。 c b r ，v b r 的q o s 技术主要就是基于前面讨论述的两点：信元流特性 的通信量合约和由网络执行的u p c 。在连接准许的过程中，网络利用这个 连接提出的通信量合约来确定它是否可以建立。一旦连接建立，u p c 就可 以将超过通信量合约参数的任何低优先级信元丢弃或打上标记。从控制理 论的观点来看这是一种典型的开环控制方法，因为没有给信源提供关于 拥塞的反馈的机制。 这种开环处理方法对许多数据应用并不合适。典型的非实时应用，如 文件传送、万维网接入、远程过程调用、分布式文件服务等，并没有对通 信量特性有十分明确的定义，上述的方法便无从入手。另外，这些应用一 般都能够容忍不可预测的时延以及随时间交化的吞吐量，这也是导致原有 的方法不适用的原因之一。 考虑到这些应用的特点，为它们提供q o s 服务的方法有两种。一种方 法就是允许这些应用以相对不受控的方式共享尚未使用的容量。当拥塞发 生时，信元将会丢失，而不同的信源将会让步和减少其数据率。这种方法 与t c p 拥塞控制技术中的尽最大努力( b e s te f f o r t ) 方法很类似。在这种方法 中，信元丢弃后引起重传，网络资源利用效率不是很高。另一种处理方法 是允许多个信源共享尚未被c b r 和v b r 使用的容量，但是，可以提供到 信源的反馈，以便动态调控负荷，因而可避免信元的丢失和更公平地共享 网络的容量。这种闭环控制的方法已经成功地用于a b r 服务的通信量控制。 8 第1 章绪论 1 4 1 二进制位反馈控制算法 这种算法的操作主要集中在信源和信宿，而交换机的操作相对简单。 交换机仅仅需要支持两种简单的功能：探测解除拥塞；以二进制位的方式 向终端系统提供反馈信息。起初，b r f 采用“负反馈”机制，即仅当需要 减少速率时才向信源发送资源管理信元( r e s o u r c em a n a g e m e n t ，r m ) ，而速 率增加过程是无需r m 信元来指示的。“负反馈”机制的弊端在于如果反向 路径上由于严重的拥塞而使r m 信元丢失，源终端系统依旧保持速率的增 加过程，导致前向通路过载而发生拥塞，为了克服这一点，改用了“正反 馈”，源终端系统将每一个数据信元的e f c i 位清零，如果信宿接收到的任 何数据信元的e f c i 位都保持为零，那么返回到r m 信元中将有通知信源提 速的信息，信源在未收到正反馈信息之前，应该是持续减速的。主要的典 型方案有前向显式拥塞通知( f o r w a r de x p l i c i tc o n g e s t i o nn o t i f i c a t i o n 。，f e - c n l 如图1 1 所示，后向显式拥塞通失l l ( b a c k w a r de x p l i c i tc o n g e s t i o nn o t i - f i c a t i o n 。b e c n ) 立1 1 图1 2 所示，和比例速率控制算法( p r o p o r t i o nr a t ec o n - g e s t i o na l g o r i t h m , p r c 舢，其中f e c n 和b e c n 属于负反馈，而p r c a 属 于正反馈。 u 瑚献 图1 - 1 前向显式拥塞通知方案图l - 2 后向显式拥塞通知方案 f i g 1 - 1f e c ns c h e m e f i g 1 - 2b e c ns c h e m e 前向显式拥塞通知( f e c n ) 方式中，反馈机制利用由信元头部p t i 域携 带的“显式的前向拥塞标识”( e f c i ) 在前向通路中传递拥塞信息。当一个交 换机发生拥塞时，各经过此交换机的v c 上的所有前向传输的数据信元的 位e f c i 被置位( e f c i = i ) ，目的端交换机在接收到被标记的信元后，就返回 一个拥塞指示信元给拥塞v c 的源端，该信源按此信息相应地增加或减少 信元的发送速率。后向显式拥塞通失1 1 ( b e c n ) 的机制与f e c n 类似，但在拥 燕山大学工学硕士学位论文 塞发生时，拥塞交换机直接将该v c 拥塞的消息通过r m c e l l 反向告知源端， 而不再进行前向的消息传递。因而b e c n 方式较f e c n 方式的优越之处在 于它的反应更为灵敏，实现控制更为迅速。 1 4 2 显式速率反馈控制算法 采用显式速率反馈方案的交换机将实现三个主要功能：一是为每个连 接计算公平带宽，二是通过检测排队长度或排队增长率来确定网络负荷， 三是为信源确定实际的传输速率。下面给出了一些典型的a b r 显式速率反 馈控制算法，其中前4 个是a t m 论坛所推荐的算法。 1 4 2 1 增强p r c a 算法增强p r c a 算法( e n h a n c e dp r o p o r t i o n a lr a t ec o n t r o la l g o r i t h m , e p r c a ) 由c o n n e c t w a r e 公司的l r o b e r t s 提出【1 3 】。e p r c a 算法的特点是操作复杂度低，与e f c i 交换机兼容，算法的公平性依靠平均 允许信元速率，对公平分配速率的近似程度，以排队长度作为拥塞测量。 1 4 2 2 显式速率指示拥塞避免算法 显式速率指示拥塞避免算法( e x p l i c i t r a t ei n d i c a t i o nf o rc o n g e s t i o na v o i d a n c e ，e r i c a ) 由o h i o ) ，h 立大学的r j a i n 等人提出【l 。e r i c a 的特点是参数少，易于调整，算法的瞬时特性与初始 条件无关。它是基于速率匹配和队列控制函数的方法来分别达到有效利用 带宽和保证q o s 的要求。但是这种算法设计要求在交换器测量总的输入速 率，并假设可用带宽已知，而且没有考虑到带宽波动和网络时延的影响。 1 4 2 3 比例控制的拥塞避免算法 比例控制的拥塞避免算法( c o n g e s t i o n a v o i d a n c eu s i n gp r o p o r t i o n a lr a t ec o n t r o l ，c a p c ) 由h u g h e s s y s t e m s 公司 的a w b a m h a t 提出l l ”。c a p c 方案的特点是实现简单，稳定于自由振荡状 态，但收敛时间长且存在非公平性趋向。 1 4 2 4 基于带宽需求估计的e r 算法此算法由美国国家标准技术研究所 的n g o l m i e 等人提出【1 6 】。此算法的性能与网络规模有关，在蹰络规模较小 时表现出良好的性能，收敛快，交换机缓存占用率低，信元延时小等；但 在网络规模较大时性能下降，收敛较慢。另外，由于对排队增长非常敏感， 因此稳定性较差。 第1 章绪论 1 4 ，2 5 具有显式速率指示的拥塞控制算法具有显式速率指示的拥塞控 制算法( c o n g e s t i o nc o n t r o lw i t he x p l i c i tr a t ei n d i c a t i o n ，c c e r ) b 自麻省理工 学院( m i t ) 的a c h a r n y 提出【l ”，是最早提出的显式速率控制算法。c c e r i 算法的性能很好，对网络的动态变化具有很强的适应性，收敛快并能准 确地收敛于m a x - m i n 公平分配速率上。但是此算法明显的弱点是计算的空 间复杂度和时间复杂度高，都是o ( n ) ，肝为链路上连接的数量，显然不能 适应于大型a t m 交换机。 1 4 ，2 6p h a n t o m 算法此算法由以色列t e l - a v i v 大学的a f e k 等人提出【”l ， 其实现目标是算法的空间和时间复杂度为o ( 1 ) 。p h a n t o m 算法的实现主要 体现在以下五个方面： f 1 ) 测量链路上的公平分配速率； ( 2 ) 根据排队长度来对某些参数进行调整； ( 3 ) 改善链路利用率： ( 4 ) 解决由于最大允许信元速率的振荡所引起的问题； ( 5 ) 通过设置不增加位烈r ) 来限常5 最大排欧长度。 1 5 论文研究内容及结构安排 尽管目前对a t m 网络的拥塞控制算法进行了很多研究，也提出了很多 理论算法。但是这些研究主要集中在a b r 业务上，没有提出一个对不同业 务进行综合控制的总体框架。 本文将针对a t m 中的不同服务( c b r ，v b r ，a b r ) ，利用综合动态拥 塞控制( i d c c ) 的方法来实现拥塞控制。i d c c 是基于非线性自适应理论 并建立在流体控制模型的基础上，修正流体控制模型的错误与不精确并使 之最小化。论文主要安排如下： 第l 章简单介绍了论文研究的目的、意义及该课题的研究现状。 第2 章为a t m 网络通讯基础。介绍了a t m 网络的协议数据单元、a t m 网络连接原理、a t m 网络交换原理、a b r 流量控制模型及反馈机制等基础 知识。 燕山大学工学硕士学位论文 第3 章讨论了一些基本的结论，介绍了在网络控制中使用到的确定性 方法和统计方法，并给出了他们的数学模型。我们就可以利用它们来分析 a t m 网络的性能，实现对网络的有效控制。 第4 章提出了一种综合动态拥塞控制( i d c c ) 算法，对算法的可实现 性作了证明，最后对算法进行了仿真，证明该算法可以很好地对网络拥塞 实施控制。 第五章结合m i t 机制的控制思想，提出有效活动v c 计算方法。 针对i d c c 算法中提到的影响控制效果的虚连接数估计，介绍了一种 新的计算方法，并证明了它的有效性。 第2 章a t m 网络通讯技术 第2 章a t m 网络通讯技术 2 1a t m 的主要特征 作为快速分组交换的代表技术，a t m 从设计之初就立足完美解决信息 传输质量问题，其传递和交换方式有着如下的特点【19 j ： ( 1 ) a t m 网络的服务是基于面向连接的，通过虚电路c ) 传输数据： ( 2 ) 数据封装在5 3 字节的分组中进行传输，这些分组称为信元( c e l l ) ； f 3 ) 在同信道或者链路中的信元可能来自不向的v c ，它们以统计的方 法进行多路复用： h ) 为了满足不同服务质量( q o s ) 的要求，a t m 交换机应当能够以非平 等的方式处理同一信道内不同v c 连接中的信元流。 2 1 1 面向连接的服务 如果网络采用虚电路上的面向连接的服务方式，数据流每次都沿着相 同的路径从源端传向目的端。不同连接的数据通过虚通标志符( v p i ) 和虚通 路标志符v c i ) 来进行区别。在a t m 术语中，虚电路上的一个连接被叫做 虚通路( v i t u a lc h a n n e l ，v c ) t 2 0 纠1 。因此，在每个信元的头部都留有几个比特 表示v p i v c i ，同自带寻址信息携带的目标同源地址相比，这个地址要短的 多。其次，同一连接的信元会按照从源节点发送的顺序到达目的端，这样 省掉了目的端对接收到的数据按照编号进行重排序，同时也省掉了接收数 据的缓冲区。a t m 网络还有一个非常重要的特点就是可以通过v p i v c i 区 别对待不同的连接。也就是交换设备能够区别对待不同的连接。 基于这个特性，a t m 网络可以实现多种操作：接纳控锖4 ( 在网络无法提 供足够服务的情况下拒绝某些连接) 、拥塞控制( 限制符合一定条件连接的传 输量) 、资源分配( 协商分配给某条连接的带宽和缓冲区大小) 以及系统维护 f 监听某条连接的平均流量和突发数据流量) 。 13 燕山大学_ t 学硕士学位论文 面向连接服务的主要的缺点是：即使是传送很少的几个信元，每一次 传输都必须建立连接。此时，采用数据报网络效率就要高得多。另外，如 果某条短路或者某个节点出现故障，那么整个连接就会中断，而在数据报 网络中这样的中断仅仅对少量的数据产生影响。 a t m 论坛规定了a t m 网络提供的5 类业务 2 2 ：固定比特率( c b r ) 、实 时可变比持率( v b r - r t ) 、非实时可变比特率( v b r o n r t ) 、可用比特率( a b 鼬 和未知比特率( u b r ) 。为了保证在u b r 服务的情况下提供一个最小速率的 连接，a t m 论坛正在讨论第六种服务：有保障的帧速率( g f r ) 。 这些服务在传输参数和服务质量上面的参数各不相同：通信量参数通 过运算法则通用信元速率算法( g c r a ) 来控制信元的到达时间。在计算中涉 及到的参数有：峰值信元速率( p c r ) ；可承受的信元速率( s c r ) ；初始化信 元速率( i c r ) ；信元延迟变化容量( c d v t ) ；突发容量限制( b t ) ；最小信元速 率( m c r ) 。 p c r 是两个相邻信元之间的最短时间间隔的倒数。s c r 是长时间的平 均信元速率。i c r 就是信息源在空闲期间后发送采用的速率。c d v t 用来 衡量系统预计的信元到达周期与信元真正的到达周期之间的偏差。b t 用来 衡量在连续的信元突发事件中允许的最大信元数。m c r 是两个相邻信元之 间最大时间间隔的倒数。 对于c b r 业务来说，p c r 用于衡量最大信元速率；c d v t 则定义了可 以接受的抖动范围，侧如严格按照p c r 速率到达时相对的偏差。对于v b r 业务来说，最主要的参数是用来测量长期的传输速率以及突发情况下的 s c r 和b t 。而对于a b r 业务来说，实际的信元传输速率介于m c r 和p c r 之间。对于u b r 业务，现在还没有一个很好的参数来进行控制，当然也无 法保证q o s ”j 。 因此，c b r 基本上是周期的信元流，但是在这个信元流中有一些由于 分帧或者分组等造成的不可避免的抖动，并且这些抖动是可以接受的。v b r 是一个突发性的数据流，比如由可变速率的多媒体编解码器产生的数据。 a b r 和u b r 是没有规则的数据传输。g f r 仅仅是对u b r 扩充的一个业务。 服务质量( q o s ) 的参数( 属性) 有下面这几个：信元丢失率( c l r ) ；信元延 1 4 第2 章a t m 网络通讯技术 迟变差( c d v ) ；峰值间信元延迟变差( p e a k - t o p e a kc d v ) ；最大信元传输延 迟( m a xc t d ) ；平均信元传输延迟( m e a nc t d ) 。 这些服务参数有的是由各自终端系统与网络之间在建立连接时达成的 协议所决定的，而这个连接应当由一个明确的服务所建立的连接。但是也 有些“非协商”的q o s 属性，比如信元错误率( c e r ) 等。这些服务的种类 决定了通信量和q o s 参数。 u b r 业务需要根据具体的情况来决定仅需要从源到目标建立一次连 接。为了支持、c b r 、v b r 和a b r 业务，a t m 交换机在呼叫建立时保留 一些资源。a b r 是利用网络拥塞所提供的反馈信息来进行控制，c b r 和 v b r 业务的通信量在源端( 通过g c r a ) 进行控制，与网络的反馈无关。 2 1 2 固定信元大小 为了在物理链路中区分以比特流的方式进行传输的分组或信元，通常 采用一个特殊的比特组合作为数据分组的定界符。然而，如果信元的长度 是固定的，并且其中包含一个固定长度的差错校验序列，a t m 使用的是 c r c ) ，那么每一个节点就可以利用这些特性隐式地确定信元的边界。 a t m 的一个非常大的问题是：相对a t m 短小的信元，a t m 的信元头 非常庞大，每次连接都要被头部占去大约5 5 3 ( 9 4 ) 的带宽。但是，a t m 短小的信元在实时语音应用的时候可以减少分组延迟。假设语音采样为每 秒80 0 0 次( 也就是每次1 2 5p , s ) ，而每次采样的数据可以编码为1 个字节。 对于长度为p 的信元，就需要1 2 5 p 胪。现在a t m 信元的数据部分是 4 8 个字节，那么延迟就是1 2 5 4 8 = 60 0 0 岬( 这个分组延迟对于那些需要 传输大量实时数据的情况，比如视频传输，是很小的。) 当信元经过a t m 网络传输时，会产由于各种因素产生延时。a t m 网络中的信元通常会遇到 5 种类型的延时：在源端的分组延时( p d ) ；传输和传播延时( t d ) ；每个交换 机上的排队延时( q d ) ；每个交换机上的固定处理延时( f d ) ；目的端的抖动 补偿和分组合并延时( d d ) 。 通过电子或者光信号造成的传输延时大约在每公里4 到5 雌之间，也 燕山大学工学硕士学位论文 就是说如果源端和目的端相距10 0 0 k m ，那么t d 就会造成大约50 0 0u s 的 延时。通过交换机造成的延时主要是用来让一个信元通过的时间。如果传 送的速度为1 5 5m b p