（计算机应用技术专业论文）abr业务的流量控制算法研究.pdf

华中科技大学硕士学位论文 摘要 界步传输模式( a t m ) 作为宽带综合业务数字网的重要实现技术，越来越受重视。 在a 州网络中，信息的拥褰及丢失是影响网络她务服务质量的主要原因。自适应比特 速率( 躺r ) 、监务是矗，l 黢务枣唯一一穗霉疆袋建反馈凝裁进行渡爨接裁约照务，它熬 流量控制是a t m 网络中一种肖效的拥塞控京l 枫制帮流量管理手段。黼此，a 8 r 监务静溅 量控制成为a t m 网络研究的一个热点问题。 a t m 论坛采纳了基于速率的a b r 流量控制机制，给出了基于速率的流量控制模型， 毽并没蠢绘出具体的实现冀法。对基翦被a 州论坛接荐酶几个典鍪的基于e r 反馈模囊 静控铡簿法进行了瞧能魄较，强终壤系统煮发分辑了信深、蓿稽终蠛系统在流量控疑 中所起的作用，并给出了交换机在流量控制中的功能。 反馈延时对算法的有效性有重要作用。e r i c a 算法与同类的其它算法相比，具有 在缓襻队列长度和信源端的允许信元速率稳定性和瞬态响应性方蕊的优势，但该算法 我爱镶惩怼霹逶一步城小。在酥i e 矗算法孛只鸯绩源产生资源罄遴薅源( r 麓) ，瑟纛冀 法进行改进，通过交换枫和信源交互发出r m 傣元，能更快的将网络酌拥塞信息反馈给 源端，以便对拥塞作出反威，有效的减小了反馈延时。仿真证明，该算法能更有效的 减轻搁感，在快速收敛和减小缓存队列长度方颇具有良好的性能。 美键词：舅步抟输禳式，岛适应 l 蒋韭务，流量控制，反羧惩对 华中科技大学硕士学位论文 a b s t r a c t a t ma sab r o a d b a i l d i n t c g r a t e ds e r v i c e sd 磷t a ln e t w o r kt e c h n o l o g yt oa c h j e v e i m p o r t a l l ta n d 盯o w i n ga t t e n t i o n t h e1 0 s sa i l dc o n g e s t i o no f i n f o n n a t i o na r em a i nr e a s o n s t h a ta f 诧c tt h eq u a l 时o fs e i c ei na t mn e t w o r k a v a i l a b l eb i tr a t e ( a b r ) s e r v i c ei st h e o n l yo n et y p eo f t r a l 弧ct h a tc a l lb ec o r l t r o l l c dl l s i n gt h ef e e d b a c km e c h a l l i s m ，a n da b r n o w c o n t m li sa ne f e c t i v em e a s l l r ema t mn e t w o r kc o n g e s t i o nc o m r o la n d 仃a f i cm a n a g e m e n t h e r e f o r e ，a b rf l o wc o n t r o lb e c o m eah o ti s s u eo fa t mr e s e a r c h a t mf o r u ma d o p t e d b a s e do nt h er a t eo fa b rf l o wc o n t r o lm e c h a n i s m s g i v e nm ef l o wc o m r o lm o d e lo f r a t e b a s e d ，b u td i dn o tg i v es p e c i 蠡cr e a l i z a t i o na l g o 删硼s i n 仃o d u cr a t c - b a s e dt r a m c c o n t r o lm o d e ，a n di n 扛0 d u c es o m ea l g o r h h mr e c o n l m c n d c db ya t mf o n l m f r o me n d s y s t e m ，a 1 1 a l y z em ea c t i o no fs o u r c ea f l de n ds y s t e mi i l t r a 衔cc o n t r o l ，a n dg i v e nt h e f u n c t i o n so fs w i t c h e si nf l o wc o m r 0 1 d e l a yo ff 色e d b a c ki si m p o r t a n ti nm ee f f b c t i v e n e s so fa l g o r i t l l m s ，e r i c ac o m p a r e d w i t ht h eo m e ra l g o m h m s ，s t a _ b i l 时a n dq u 墩r e s p o n do fb u 艉rq u e u el e n 百ha n da c rj s b e n e r b u tf e e d b a c kd e l a yd e c r e a s ef m h e r e r i c aa l g o r i m mo n l yg e n e r a t er mb ys o u r c e s y g t e m ，i m p r o v e m e n t st ot h eo r i 百n a lm g o r i t h m s ，s w i t c h e sn o t i 玲i n gs o u r c e sd i r e c n y ，t h i s a l g o r i t h md e c r e a s e st h ed e l a yo fc o n t r o le f e c t i v e l 弘s i m u l a t i o ni n d i c a t e st h a t 山i sa l g o r i t h m h a sg o o dp e r f o h n 锄c ei na l l e v i a t i n gc o n g e s t i o n 确i n e d i a t c l y ，d e c r e a s i n gq u e u el e n g t ho f s w i t c hc a c h ea ndc o n v e r g i n gf a s t k e y w o r d s ：a t m ，a v a i l a b l eb i tr a t es e i c e ，n o wc o n 廿0 l ，d e l a yo ff e e d b a c k l j 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 ，扣i 学位论文作者签名：一一协 日期：a 占年牛月硝 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密区 ( 请在以上方框内打“”) 学位论文作者签名：，彗岛 日期：击厕6 年华月对日 指导教师签名： 宵，和参 日期：刎箨r 月7 日 华中科技大学硕士学位论文 质量要求是流量控制的基础。 1 9 9 3 年，a t m 领域开始寻找一种可以动态分配带宽并防止信元丢失的传输机制， 以使网络中c b r 和v b r 连接剩余的链路带宽得到有效利用，同时使用户可以得到一种 无延时保证但具有严格丢失率保证的服务类型。显然这种服务需要根据网络带宽动态 调节信源的发送速率，而这只有通过反馈控制才能实现。1 9 9 4 年，a 删论坛提出了a b r 业务。 对用户来说，很多的应用都没有固定的带宽要求，或者根本就不可能事先知道带 宽要求。这些用户希望获得尽量多的带宽，尽可能快的利用网络空闲带宽以及保证 q o s 。而对于运营商，则希望最大限度的提高网络利用率，充分利用恒定比特率( c b r ) 和可变比特率( v b r ) 业务的剩余带宽。因此，a b r 业务就是为了迎合网络用户和网络 运营商的这些要求而产生的。a b r 连接并不强制网络为其分配固定的带宽，网络可以 通过反馈控制动态调整分配给每个a b r 连接的带宽，其中反馈是通过资源管理( 刚) 信元完成的8 】。 a b r 流量控制是为了提高链路利用率、降低信元丢失率，并实现带宽的公平分配， 同时在实现上要具有较低的复杂度。上述目标之间具有很强的相关性，一方面性能的 提高往往以其它方面性能的降低为代价。另外，由于a t m 网络中存在着大量具有不同 路由和不同长度的a b r 连接，以及a t m 网络的高带宽和长距离( 会引起大的反馈延迟) ， 使反馈控制和公平分配计算难度很大。以上这些因素决定了a b r 流量控制算法的多样 性，在实现上不仅需要在性能和复杂度上进行折衷，而且需要在不同目标上进行折衷。 正因为如此，1 9 9 6 年4 月，a t m 论坛在业务管理规范4 o 【9 l 中仅给出了a b r 业务及其流 量控制机制，并没有限制a b r 流量控制的具体算法。a b r 流量控制是目前a t m 业务管 理领域的研究热点，已经提出了很多具有不同特点的a b r 流量控制算法。并不断有新 的算法出现在通信领域的文献中”5 1 。 a b r 流量控制算法宜接影响着a t m 交换机的性能，以及交换机之间的互操作性， 因此深入而全面的掌握a b r 流量控制原理并设计有效的控制算法，无疑对优化a t m 交 换机的性能是有所帮助的。 华中科技大学硕士学位论文 1 。2 国内外研究瑰状殛发展熬势 a t m 论坛在开始制定a b r 流嫩控制规范融，有基于信誉( c r e d n ) 和基于速率薅 种方案。鏊于信誉豹方案是出哈锑大学h 。t k l m g 教授善先提出静【旧，并褥到 d i g i t a l 、b n r 、f o r e 、a s c o m t i m e p l e x 、s 眦、b r o o k t r e e 和m i t 8 u b i s h i 等公司的支持 。基于邃攀的方案爨凌鼙。t o r o j a 公司蘸n 。y i n 帮疆 l u e h y j 首先捷爨鹃，并寄 多家公司的代表进行了广泛的讨论和修改。 对于这爨耱方案，缓多学者遴孬了大豢靛魄较磷究，基予蕊誉懿方寰簧求鼹餐个 连接排队，这在大型交换机实现时会引起极高的复杂度。而基于速率的方案则不要求 一宠要对每令连接蓑 酞。因此，爨予复杂度秘灵活搜寅匿的考崽a t m 论坛最终采躅了 基于速率的方案。 基于速率的流量控制方案又分为二进制使反馈【2 0 l ( e f c i ) 和鼹式速拳反馈川( e r ) 两种。二迸制位反馈利用信元头中的一位来指示是否存在阻塞。信源在接收到反馈信 息时，按照事先约定的舰则去增加或减小速率。在显式速率反馈中，可以确切地给出 信涿允诲发送钧速率。二遴稍锭凝续静优煮是实瑰篱单，餐性能不如显式速率控割。 二进制位反馈和显式速率反馈又都可以进一步分为前向反馈和厝向反馈。前向反馈是 摇爱续售惠憨蘧浍连接簸径自羲蓍传辕至l 蔷 x 华中科技大学硕士学位论文 无论是什么样的算法，都是在性能和复杂度上进行权衡和折衷。a b r 流量控制算法主 要通过硬件实现，显然高复杂度算法需要高硬件代价。但随着半导体工艺的发展，势 必打破现有的性能和复杂度之间的平衡，从而激发人们研究更合理的a b r 流量控制算 法。 当今对a b r 业务的流量控制研究的热点还有虚信源虚信宿( v s v d ) 【2 5 1 和多播业 务的流量控制。a t m 论坛唧已经把虚信源虚信宿作为a b r 流量控制的一种结构选择，并 为v s v d 制定了初步的规范。当网络中采用具有v s v d 功能的交换机时，a b r 连接将被 分割为多个独立的a b r 控制段，这种分段控制的主要优点是缩短a b r 反馈控制环的长 度，从而改善系统的控制性能。 尽管a t m 论坛支持v s v d ，并已经做了不少工作，但目前对v s v d 交换机的研究仍 然需要进一步完善，表现在： ( 1 ) v s v d 对a b r 性能和交换机复杂度( 主要是缓冲器的要求) 的影响； ( 2 ) v s v d 所涉及的调度问题； ( 3 ) v s v d 对不同a b r 阻塞控制算法的影响，及如何改变算法以适应v s v d 环境； ( 4 ) v s v d 对非a b r 业务的影响； ( 5 ) 设计与实现问题。 而多播的流量控制由于 x 华中科技大学硕士学位论文 种流量控制算法的性能，为选择具体的算法提供了参考。 ( 3 ) e r i c a 算法在响应时间和稳定性方面具有良好的控制性能，经过分析该算法 可以进一步减小反馈延时。给出一种新的思想，通过交换机和信源交替发出信元，更 快地反馈拥塞信息给信源，使得原算法收敛性更快，响应更灵敏，缓存队列的长度也 有一定程度的减小。 华中科技大学硕士学位论文 连接释放时间指从用户发出释放请求消息起到收到释放确认止的那段时间。 3 、呼q 阻塞概率 呼叫阻塞概率指在一段时间内呼叫被拒绝的比例。它不仅与网络资源有关，还与 呼叫的随机到达过程及呼叫持续时间的分布有关。 4 、误码率 该参数主要取决于传输系统的性能。如果不在a t m 网的从l 层进行差错控制，则 电视、图象业务能承受的误码率在1 0 。l 1 0 1 3 间。如在a a l 层进行差错控制并在信元 级实现1 位纠错，则电视、图象业务能承受的误码率在1 0 而一1 0 。7 间。 5 、信元丢失率 信元丢失率定义为在一段时间内丢失的信元数与用户发送的信元总数之比。在 a t m 网中造成信元丢失的主要原因有：传输时遇到缓存器溢出而丢失；传输中发生无 法纠正的误码而被迫丢弃该信元；信元被错送到别的信宿等。 6 、信元插入率 指原来应送至别的信宿去而错送到本连接来的信元数与本连接用户发送的信元 数之比。误传信元可能回引起同步丢失和额外增加本连接的业务流量。 7 、信元转移时延 指信元第一比特进入网络起至信元最后一个比特离开网络止的那段时间。 8 、时延抖动 各个信元的转移时延是不等的，相对于平均转移时延，存在有一个随机变化的差 值。这个相对于平均转移时延的变化值称为时延抖动。时延抖动可能会给电话、视频 业务的定时恢复带来困难。 2 。3 流控制的参考模型 a t m 网络流量控制主要在网络的入口处，即在用户一网络接口( u n l ) 处限制进入 网络的数据量，以防止网络负载过重出现拥塞( 如图2 1 所示) 。除了在网络入口处 的流量控制以外，网络节点上也可以采取一系列辅助措施，如拥塞时选择性地丢弃 信元以保证高优先级连接的质量，帧丢弃( 将a a l 数据单元丢弃) 等 2 6 。 华中科技大学硕士学位论文 图2 1 用户一网络接口处的流量控制图 2 4a 硼网络流量控制方法 1 、连接接纳控制 连接接纳控制( c a c ，c o n n e c t i o na d m i s s i o nc o n t r 0 1 ) 是在连接建立阶段网络 所执行的一组操作，用以接受或拒绝一个a t m 连接。 连接请求只有在网络具有足够的可用资源以满足用户业务的服务类型、流量合同 以及服务质量要求时才能被接受，这种可用资源能够按所要求的业务质量将新的连接 在整个网络范围内传送，井同时保证网络中已建立的连接的业务质量。对于每个连接 请求，c a c 函数应能从流量合同中取得如下信息以对连接接受拒绝作出决定： ( 1 ) 描述业务流量特性的源流量参数； ( 2 ) 所要求的q o s 类型及可接受的q o s 参数值； ( 3 ) 信元时延变化容限，这种变化是由终端设备( t e ) 或用户基地设备( c p e ) 引起的，它可能会改变已协商好的业务流量限制； ( 4 ) 所要求的一致性定义。 另外，在给用户分配网络资源时，可考虑网络已有的负载，这样就能 x 华中科技大学硕士学位论文 t t utl3 7 1 建议中定义了两个等价的通用信元速率算滋( g e n e r i cc o l l r a t e a l g o r i t h m ) ，努裁孵徽寝调度( v s ) 算法帮连续狡杰添撩( l b ) 葵法。g e 触使拜l 两 个实数参数i 和l ( 分剐代表增量值和极限值) ，还露一组中间变量，被表示为g c r a ( ，l ) 。 当一个傣元至达时，v s 算法计算傣元的骥论到达鞋阉t a t ( 豫r e t c a n yp r e d i c t e da r r i v a lt i m e ) 。假定在业务源激活时送出等间隔的信元( 两个棚邻的蹭离为i ) ， 妞巢售元鲍至g 达封闽涝嚣予l a t l ( l 代表一令容羧簸) ，刚该售元楚一致静；否囊箔 元将会过早到达，这时信元被认为是不一致的。 连续获签( 滤) 舞法霹蔽被看终是令蠢袋蜜豢豹潺桷算法，该漏捅醴每单位辩 间一个容量单位的连续速率向外渗遴。同时镣当一个一致性傣元到达时其容辍增加厶 当畜一令信元弱这对，如采满橘里的信元数小于，粥该信元就是一致的，露刚就建 不一致的。濑桶的最大容量为l + i 。g c r a ( i ，l ) 用于提供对已髓定流量参数的一致性的 正式定义。 尽管滚爨一致搜是按照g e r 矗来定义懿，毽是撮撰l u t 3 7 l 建议，网终提供卷 在提供u p c n p c 控制时可以不采用这一算法。实际上，网络提供者可以使用任一u p c k 您，只要英经韪灌燕连接熬晒s 要求，特臻怒憝够鬟供对一数往连接的透鞠往。 5 、用法参数控制 翔法参数控稍( u p c ，u s a g e 弛r a l i l e t e rc o n t r o ) 在塌户一网络接口处避行，主 要是在信元流量大小和信元迷路的宥效性等方丽监毫嫩和控制a t m 连按的流量，以加强 每个a t m 连接与其已协商好的流量合同之阐的一致牲，防此终端设备恶意或无意的 滥用流量，影响已经建立连接的q o s 。 一个理想的u p c 算法应该具有如下特性： ( 1 ) 够捡漫l 绦露l 法瓣浚量状态； ( 2 ) 对参数违例作出快速的响应； ( 3 ) 实瑗简单。 u p c 算法所做的操作可以是： ( 1 ) 锭元通过； 华中科技大学硕士学位论文 ( 2 ) 给信元加标签( 对网络操作者是可选的) ，信元加标签操作仅仅是将c i ，p ( 信 元丢失优先级控制) 为o 的信元的c l p 改写为1 ； ( 3 ) 信元丢弃。 6 、信元丢失优先级控制 当用户使用信元丢失优先级( c l p ) 比特产生不同优先级的业务量时，就需要实 施优先级控制。通过对c l p = o 和c l p = o 十l 的业务流进行控制、分配足够的资源以及作 出适当的路由选择，网络操作者可以向c l p = o 和c l p = l 的信元流提供不同的q o s 。 如果网络操作者选用7 加标签功能，那么在c l p = o 业务流上由u p c n p c 控制所识 别出的不一致的c i 。p = o 信元被转换为c l p = 1 信元，并在c l p = o 十1 业务流进入u p c n p c 控制之前与用户送出的c l p = 1 业务流合并。在已合并的c l p = o + l 业务流中由u p c 朋p c 功能确定为不一致的信元被丢弃掉。 t m m l ( 传输监控机，t r a n s m i s s i o nm o n i t o r i n gm a c h i n e ) 首先对c 【。p = o 的信元 进行一致性检验，对于一致性信元让其通过；对不一致的信元加标签，并与c l p = l 的 信元合并进入t m m 2 进行一致性检验，对于一致性信元让其通过，对不一致性信元丢 弃。 7 、反馈控制 反馈控制( f e e d b a c kc o n t r 0 1 ) 是网络和用户所采取的一套操作，这些操作根据 网络单元的状态来调节a 嘲连接的业务流量。它主要是针对a b r ( a v a i l a h leb i tr a t e ) 业务而提出的。a t m 论坛采用端到端基于速率控制的方法，它定义了以下两种模式。 ( 1 ) 二进制反馈模式。这种模式的反馈控制机理是：当一个网络节点检测到拥 塞时，它把a 1 、m 信元中的e f c i ( e x p l i c i tf o r w a r dc o n g e s t i o ni n d i c a t i o n ) 置位。 当目的端检测到e f c i = 1 的信元时，表明网络发生了拥塞。目的端返回给源端一个带 有拥塞指示的r m ( r e s o u r c em a n a g e m e n t ) 信元，源收到r m 信元后降低它的速率。当 没有r m 信元收到时，源速率以缺省值增加。 ( 2 ) 显式速率反馈模式。这种模式的反馈控制机理是：虚连接上的每个网络节 点为该虚连接分配一个可用带宽的公平份额( f a i rs h a r e ) 。源端周期地传送一个包 含初始带宽份额的r m 信元。当r m 信元通过一个网络节点时，若r m 信元中当前存储 1 4 华中科技大学硕士学位论文 的可用带宽份额大于网络节点可提供的带宽份额，则将r m 信元中当前存储的可用带 宽份额更新为该网络节点可提供的带宽份额。当r m 信元到达目的端时，目的端将此 控制信元返回源端。这样，源端根据该虚连接中瓶颈最严重的网络节点可提供的带宽 份额调整其速率。采用这种模式的反馈控制方法有e p r c a 、e r i c a 、c a p c 剐等。 流量管理是保证网络正常运行和保证用户服务质量的关键。对于a t m 网络来说， 提供良好的业务管理( 包括突发性业务和非突发性业务) 是很重要的。然而尽管a t m 论坛已经制定了一些流量规范，但还存在不少问题有待研究，如动态u p c 问题；网络 节点处的缓存管理问题；点对多点问题等。 2 5 本章小结 本章探讨了a t m 网络流量控制的机制，对a 珊论坛定义的业务模型和服务质量进 行了介绍。分析了具体的流量控制方法，对于网络中的不同地方和不同业务要采用不 同的流量控制方法。 a b r 业务流采用的是端到端的基于速率的反馈控制机制，包括二进制和显式速率 两种模式，二进制模式的算法简单，但会引起源端速率的大幅振荡，显式速率的公平 性和稳定性好，但算法复杂。 华中科技大学硕士学位论文 3 1 溅控制原理 3 擞壁务的流量控制 3 1 1 滚攘髓鬟壁 矗搿论坛弱l 手u i 帮选择藿予速率熊闭嚣爱馈控镄终袁矗嘲鹚中勰r 漉量控裁静 标准，并定义了如图3 1 所涿的a b r 的流量控制模型。 嘲3 1a b r 反馈授制模型 程a b r 流量控豢中，傣滋发送数据信元的鲻辩瞧发送前蠢雕馆元( 其孛包括信 源豹当麓状态霸请求带宽等镶惠) 。交蓑辍在浚爨魏信元辩，读敬蔟中秘蓿爨，荠 结合当前交换机的状态。如湖3 1 所示，a b r 反馈控制模型不同的算法进行流量控制 和带宽公平分配计算，然后根据计算结果设置或修改r l 信元中的内容，发出r m 信元。 信宿仅处理r m 信元阻塞指承艇，并向信源发隧r m 信元。信源接收到后向眺信元， 疆攥其孛瓣爱壤信惠来调整镶嚣豹发送速率。 基予滚率豹流量控制机制可简单概括如下： 信源终端系统实时调节数据的传输速率，使其接近网络允许值； 网络本身由一系列交换机组成，交换机用它们当前的负载信息确窀网络的运行状 态( 包掇诗冀绩源竞诲速率) ，露磊将之作为蔽馈鼹资源管理( 嘲) 谊元送绘信源； 渊髅元由癌源生戚，掺杂在数据信元孛游纛连接黄送至l 信宿终端系统； 信宿终端系统将跏信凭作简单处理后返回络信源终端系统，为信源调节速率提 供参考。 华中科技大学硕士学位论文 3 1 2 柏r 流量擦制参数 在建立a b r 连接时，a b r 业务源要与网络协商几个运行参数，其中有p c r ，m c r 和t c r ( 初始信元速率) 。 在数据传输阶段，信源可用处于p c r 和 l c r 之间的任意值为速率发送信元，将这 动态变化的速率称为允许信元速率( a c r ) 。 裰连接建立时或经过较长豹空阑间隔之稻，连接上的a c r 值被设定为1 c r 。为了 篙幸艺攒述，我稍浴强定义蕊信元兢范中静渤记符，用n r m 表示每n r m 个信元中将有 一令麓错元，n 狲豹姣省篷为3 2 ，下瑟列出勰r 参数豹含义与俸糟，其中有些参数 疑蛰囊露寇戆，有些是露定豹渊。 峰健傣元速率( p e r ) ：镶源被兔谗传羧懿最大速率。 最小傧元速率( m c r ) ：傣源要求的最小发送速率。 允许信元逋率( a c r ) ：当前信源被允许的发送速率。 韧始信元速率( i c r ) ：债源在连接建立后或在间断发遴一段时间后的初始发送 速率。 舆有c l p 标签的信元速率( t c r ) ：用于限制信源发送c l p = 1 ( 低优先级) 信元 的速率。 n r 孺：表示在两个f 黼信露之闯，最多允许发遴的数据倍元数。 赫r 撰；液示在两个f 聪信嚣之阗，至痧发送的数据信元数。爝予控涮r 黼信元苇拜数 据售元之瓣熬繁宽分鼯。 羊糯：瘸予限刳发送鞭令f 滕售元豹对趣闻辫，擎搜是黻s 。 速率增加因子( r i f ) ：用于控制信源发送速率的递增量。 速率减小因子( r d f ) ；用于控镱4 信源发送速率的递减数。 a c r 减小时间因子( a d t f ) ：袭示a c r 遴率减小到i c r 之前，发送r m 信元之间 的允许时间间隔。 瞬时缓冲器风险因子( t b e ) ：用于限制信源在启动期间，接收到第一个返回的 b 糊信元前所发送的信元数量。 黼信元丢炎数( c 黼) ：嗣予限锖信源在采接i | 受到b r 黼信元期阀发遴的f j 1 4 数量。 7 华中科技大学硕士学位论文 保险减小因子( c d f ) ：用于在c r m 事件发生时控制a c r 的减小量。 往返的确定时间( f r t t ) ：表示r m 信元从发出到返回时所用传输时间的确定部 分，包括线路延时和交换延时。 3 1 3 刚信元格式 a b r 流量控制中，r m 信元起着至关重要的作用，所以下面对r m 进行介绍。r m 信元 的完整格式见表3 1 。 表3 1r m 信元格式 名称大小说明 a t m 首郝5 字节p t l = 1 l o 协议标识( i d )l 字节i d = 1 表示a b r 业务 方向( d i r )1 字节前向d i r = o ，后向d i r = 1 后向通告( b n )l 字节b n = l 交换机生成的l i m 佰兀 阻塞指示( c i )1 字节c i = l 网络拥塞 不增加指示( n i )l 字节n l = l 网络轻度拥塞 请求应答( r a ) 1 字节 兼容i 3 7 1 保留 3 字节 显示速率( e r )2 字节 当前信元速率( c c r )2 字节 最小信元速率( m c r ) 2 字节 队列长度( q l )4 字节 兼容i 3 7 l 系列号( s n ) 4 字节兼容i 3 7 l 保留2 9 字节 保留5 比特 差错检验( c r c l o )1 0 比特 每一个r m 信元有规则的5 字节信头，净荷类型p t i 景为1 】o 表示信元为r m 信元， 一个字节长度的协议i d 号由a 职连接设定，方向比特位( d l r ) 用来区分r m 信元是 前向还是后向，后向标识位仅在交换机生成b e c n 信元时才有用； 华中科技大学硕士学位论文 c l 位和n 】位最初虽是为耜对速率标记交换机定义的，但e r 交换枧也可分别用它 鬟表示嘲络楚子疆度摇塞耱邋渡藏塞； 定义r a 、q l 和s n 是为了保持与i t u t 的捺荐规范1 3 7 1 兼容，a 硎论坛没有具 体使用它们； 当前信元速率( c c r ) 被信源用来表示信元速率的当前值。有些交换机将它作为 分配可鼷辫宽懿参考蓬，露蠢魑交换壤校本不绩强该域羚毽，塞己溅爨v e 上的信元 速率，凇r 域是冗余静，将之定义在魏信元串烹簧是方便交换枫鹣焱援； e r 、c i 和n i 携带主要的网络反馈信息给信源，e r 域中的值是允许信源生成信元 流的最大速率。当v c 上存谯多个交换机时，棚鬃程度最为严重的交换机所确定的反 馈信息最终到达信源。数据傣元的债头中也有擞式翦怒朔塞标识( e f c i ) 位，该比特 霞被经耱攘塞戆交获掇登鬣，傣密终蠛系统警存每个数据壤元载e 粒 状态，当返誉 跏信元时，将最新豹e f c i 状态傻用硎信元豹e i 位反馈给信源，倍源从网络接收到 r m 信元质，依据e r ，c i 和n i 的值及相关的信源参数值调节a c r 的大小。r m 信元中 与速率翁燕的域( e r ，c c r 和m c r ) 中的值均用1 6 位浮点数表示，而在连接建立时速 率参数楚用2 4 位整数形式遴撂秘鬻熬。蘸者掰袭零憨最太速率范豳不一致，翦者绞 为1 。8 泌，屠者约为7 。撼b p s 。 3 2 交换机和终端行为 3 ，2 1 终壤好隽 嬲赫论坛在它裁订静t 醚4 。o 中定义了终端豹行为，其主要肉誊麴下所述。 l 、倍源 信源在发送n r m 1 个数搬信元后，必须发送一个前向r m 信元，但是当信源的发 送信元速率银低l 重，蕊个魏国烈傣元盼间隔时阗会缀长，这会弓l 起网络靛反馈信息 延逶。戮梵，弓| 入7 参鼗静m 彝貔l l l ，燕定当豢麓一令蓠海r 醒信元发送密彳r l l 整s 惹， 立即发送颛的前向r m 信元，而且两个前向跚倍j 己之间至少应有m r m 个其它信元。发 出最后一个前向r m 信元后，如果没有传输其它臌向r m 信元，则等待中的后向r m 信 元的优先级高于数据信元。以上髓够保证不会造成带有反馈信息的艏向r m 信元的延 l 窖 华中科技大学硕士学位论文 迟。 当a c r 减小到i c r 之前时，若超过参数a d t f 给出的时间没有发送任何速率内的 前向r m 信元，则信源重新发送前向r m 信元探测网络的负载状态，同时将a c r 的值减 小到初始值i c r ，如果a c r 低于i c r ，则保持不变。 如果已经建立的链路断开或者网络的拥塞非常严重，那么带回反馈信息的r m 信 元就会阻塞于网络，使信源端无法知晓当前的网络状态，同时信源还不断的发送信元， 使得网络更加拥塞。因此，引入了参数c r m 和c d f 。当发送了c r m 个前向r m 信元后没 有收到一个后向的r m 信元，便认为网络拥塞，使用保险减小因子c d f 减小信元的发 送速率，参数是在连接建立时与网络协商决定的。 信源工作时从a c r = i c r 开始，然后根据网络得到的反馈动态的调整a c r ，并且一 直保证在协商确定的m c r 到p c r 之间。通过上一节对r m 信元的介绍，我们知道了由 r m 信元中的拥塞指示位c i 、不增加位n i 和显式信元速率字段e r 来反馈网络信息。 规则如下： 当c i = 0 、n i = o ，则a c r = m a x m c r ，m i n e r ，p c r ，a c r 十r i f p c r ： 当c i = l 、n i = 0 ，则a c r = m a x m c r ，m i n e r ，a c r ( 1 一r d f ) ： 当c i = o 、n i = 1 ，贝ua c r = m a x m c r ，m i n e r ，a c r ： 当c i = 1 、n i = l ，贝9a c r = m a x m c r ，m i n e r ，a c r ( 1 一r d f ) 。 线性的增加和指数级的减小，使得没有拥塞的时候信源发送速率缓慢地增加，但 出现拥塞指示时则将速率迅速地减小。该种调节速率的方式能保证达到公平性准则的 要求捌。 2 、信宿 信宿终端的主要工作是将每个前向r m 信元转换成后向r m 信元，既将d i k 位置l 。 正常条件下，不改变n i ，c i 或e r 字段，如在最后一个数据信元中收到了e f c i 信号， 则将c i 位置l 。但是，目的站发生了拥塞。它可以把前向r m 信元转换成后向洲信元 时将c i 或n i 位置l ，或者减小e r 的值。 3 2 2 交换机的反馈方式 交换机提供速率控制反馈到信源以调整它的发送速率，有三种反馈信息的方式： 华中科技大学硕士学位论文 l 、桥记e f e i a 矧数擐信元逶过交换藏葬雩，交换援霹辩镶元蓥蘸( 使震受蔚类登字段) 孛戆萎 式前向镧塞指示e f c i 进行设嚣。这将引起目的端系统在b 麟信元中将c 位置1 。 2 、标记相对速率 交换机可赢接对一个经过的r m 信元的c i 做戏n i 位进行设置。嚣这种位的设置 是在一个藏彝r 鲢信元中，则当在基的蛄出瑷髂元簿头传输时，该僚将在媚应静居向 瓣绩元中保持置l 。著在个逶过煞嚣囱黼谂元孛设置其孛静一像，弱可获褥更获 的结果。骚得到最快的结槊，一个交换机可产嫩一个将c i 位或n i 位置l 的后向r m 信元，而不需要等待一个邋过的后向r m 信元。 3 、桥记显式速率 交换辍鹱穗礁戆诗霎爨瓣绩元发送速率戆麓凝篷，隽了镬各令交换援麓够蛰目工 作，只对前向r w 后向r m 巾e r 的避行减小。 3 3 基平速率的流量控湖算法 3 3 。l ：滚裁位茬镶控镧算浚 这种算法的操作主要鬃中在信源和信稽，黼交换机的操作相对简单。交换机只需 监测信元缓冲区队列长度米检测阻塞，当队列妖魔超过阀值时，交换机通过标记数据 信元标头中的e f c i 位将拥挤信息传递给其后继交换桃。下露介绍几种热型方案，其中 f e e k 秘b 阮n 属予受极髓菠馈，露反馈售惑只袋健簸速率减小。露p 怼a 剐溪于正极 性反馈。 1 、前向显式阻塞通知 前向鼹式阻塞通知( f e c n ) 利用数据信党头中的显式前向阻塞指示( e f c i ) 位在 传输方内上传送阻塞信息，嚣阮i 是信元负荷类溅播示符( p t i ) 中的第二位。当交换 疑隧塞嚣誊，宅荛辑有售元豹耗i 凌鬟为l ，镑搿接浚鬟其有l 霞= l 茨售元螽，蒋接 指定的时间间隔向相应信源殿圈阻塞通知信元。储源接收到反馈信息厝，减小信元的 传输速率。如果在指定的时间中没有接收到阻塞通知信元，则信源将增加其传输速率， 直到达到峰值速率。 2 l 华中科技大学硕士学位论文 2 、反向显式阻塞通知 反向显式阻塞通知( b e c n ) 方案与f e c n 方案基本相似，区别是阻塞交换机可以 直接向信源发回阻塞通知。显然，b e c n 比f e c n 对阻塞的反应要快。而且对端系统的 故障及端系统之间的不一致性有更强的适应性。但是b e c n 对交换机硬件有更高的要 求，交换机不仅能产生b e c n r m 信元，而且能够滤出同一连接在其它交换机上产生的 多余r m 信元。 3 、比例速率控制算法 在比例速率控制算法( p r c a ) 中，信源发送信元时，从第一个开始每n 个信元发 送一个e f c i = o 信元( 其余为e f c i = 1 ) 。参数n 为预先设定的，它影响控制响应时间 和反向链路利用率。信宿每接收一个e f c i = 0 信元，就产生并发回一个r m 信元，当信 源接收到r m 信元时，按比例增加信元速率。处于阻塞状态的交换机把e f c t = o 的信元 改为e f c i = 1 或删除反向链路上的删信元，由于信源在发出信元时是连续减小其信元 速率，因此每个阻塞的连接都会减小其传输速率，直到交换机阻塞消失。 以上三种二进制位反馈控制算法都使用e f c i 来指示阻塞。f e c n 和b e c n 所遇到的 最大问题是，反馈信息在送往信源的过程中，遇到更严重的阻塞而使信源经过很长时 间才能接收到反馈信息或根本接收不到反馈信息，那么信源将继续增加信元传输率， 从而迸一步加重阻塞，直到使网络陷入瘫痪。解决的办法是采用正极性反馈方( 如 p r c a ) ，反馈信息只引起信元传输速率增加，当接收不到反馈信息时，信源减小传输 率，直到m c r 。但是尽管p r c a 方案改善了负极性反馈方案可能存在的网络崩溃现象， 但与f e c n 和b e c n 一样，仍然存在公平性问题，即经过交换机多的连接要比经过交换 机少的连接有更多的机会通过阻塞点。对阻塞点多的连接将进行更多次的控制，从而 使其速率被限制得更低，产生不公平。解决的方法有两种：一种是对每条连接排队， 另一种是智能( 选择) 阻塞标识。 3 3 2 显式速率反馈控制算法 采用显式速率反馈方案的交换机将实现三个主要功能：是为每个连接计算公平 带宽，二是通过检测排队长度或排队增长率来确定网络负荷，三是为信源确定实际的 传输速率。 2 2 华中科技大学硕士学位论文 i 、增强p r c a 算法 此算法由e o n n e c t w a r e 公司的l r o b e r t s 提出。信源在发送数据倍元时将其 氍w l 设置为o ，每发送n 个信元就发送一脒信元。在r 艟信元中，将信源期望的速率 放在e r ( 显式速率) 域，c c r ( 当前信元速率) 域取为允许信元速率( 埘r ) ，c i ( 阻 塞标志) 置为0 。该算法要求交换帆在对所肖源端平均信元速率估计的基础上，试图 公半的、平搀的把竞许发送速率( 驻式速率) 分配给所有源端。希望的公平速率是一 个估计的a c r ，它可被送给所有的源端以便众部a b r 业务量不超过网络的a b r 容量。 在交换瓤中，弱焉掰数熬较警堙毽戆方法在掰有逐揍上诗冀平均竞诲信元速率 ( m a c r ) ： 函l 盎e r = ( 1 一珏) 唪瓣矗c r + 镬# c r 通常a 取为l 1 6 。谯计算姒c r 的基础上，进一步计算连接的公平分酉已带宽： 公平分配带宽= 8 域a c r ，透常取= 7 8 交换机滥视其排队长度，当r m 倍元从信宿返网时，如果处于阻塞状态，则 e r = m t n ( e r ，公平分配带宽) 。 e p r e a 算法韵特点建操作复杂度低，与e 蕊i 交换梳兼容，算法的公平性依靠m a c r 对公平分配速率的近似糕度，以排队长度作为阻塞检测量。e p r c a 算法还脊一个变形， 帮鑫遥瘦魄爨速率燕铡( 矗p r e ) 【3 “，矗p r c 与e p r c a 的不同点佼农于a p r c 楚敬攥酞长 度的变化为阻塞检测量。 2 、鬓寿魄铡控裁瓣辍塞遴受舅法 此算法由 l u g h e s s y s t e m s 公司的a w b a r n h a t 提出删。与e r i c a 算法相似，具有 毖铡控制的隧寨避免算法( e a 踅) 毽跫赘基标裂鼹率竣置葱略低予l ，著计算受棼霹 予z ，在因子z 1 两种情况下，公平分配带宽的计算采用不同的形式，在欠负 荷( z 1 ) 时： 公平分配带觉一公平分配带宽女x ( e r f ，l + ( o 1 ) r d n ) 其中r 积( o 2 ，o 8 ) ，氆是斜率。黔为最小允许减小量，常设为o 5 。 华中科技大学硕士学位论文 c a p c 方案的特点是实现简单，稳定于自由振荡状态，但收敛时间长且存在非公平 性倾向。 3 、基于带宽需求估计的e r 算法 此算法由美国国家标准技术研究所( n l s t ) 的n g o l m i e 等人提出【1 引，它是对每 个v c 的前向r m 信元中的a c r 值计算指数加权平均值，得到平均允许信元速率( m a c r ) ， 即m a c r = m a c r + ( a c r m a c r ) a v f ，其中a v f 为a c r 变化因子，如取1 1 6 。当负荷因子 l 。f = 输入速率目标速率 1 时，那么多余的带宽按下式进一步分配： 撇c r = m a c r + m a i r 其中m a i r 为m a e r 的速率增量，如取0 5 m b p s 。当检测到排队长度的导数为正时， 即排队的输入带宽大于输出带宽，这将导致交换机进入阻塞状态。此时如果检测到阻 塞，则e r 值按下式计算： e r = m a c r 州r f m r f 为减小因子，如取0 9 5 ：否则，e r = 姒c r 。 此算法的性能与网络规模有关，在网络规模较小时表现出良好的性能，收敛快， 交换机b u f f e r 占用率低，信元延时小等；但在网络规模较大时性能下降，收敛较慢。 另外，由于对排队增长非常敏感。因此稳定性较差。 4 、具有显式速率指示的阻塞控制算法 此算法由麻省理工学院( m i t ) 的a c h a r n y 提出，是最早提出的显式速率控制 算法。 具有显式速率指示的阻塞控制算法( c c e r i ) 交换机监视所有连接的速率并计算 公平速率。如果一个连接的期望速率小于公平速率，则此连接被赋予此期望速率。如 果期望速率大于公平速率，则把此r m 信元中的期望速率改成公平速率并把r m 信元