（控制理论与控制工程专业论文）广义预测拥塞控制算法及仿真研究.pdf

j “义预测拥采控制算法及仿真硎究 摘要 a t m 是一种面向连接的、分组交换和统计复用技术。然而，当多个突发业务同时到 达一个节点时，缓存队列长度迅速增加，在极短的时间内出现缓冲溢出，或高速链路接 入慢速网络中引起输入链路速率大于输出链路速率，则导致网络拥塞。拥塞一旦发生， 传输延时增大，信元丢弃率迅速上升，拥塞持续时间过长，还会导致整个网络崩溃。因 此，有效地控制网络拥塞，是提高网络资源利用率和改善网络服务质量的首要任务。 a t m 论坛采用基于速率的反馈控制方法作为实现拥塞控制的标准算法，但论坛只给 出该算法设计的指导性建议并未明确规定具体实施方案。目前经验设计的缺点是不能保 证资源分配的公平性，易使源端发送速率产生不稳定的震荡，也没有系统的性能分析理 论依据。基于线性控制理论的方法几乎都没有综合考虑传输延时的随机时变特性、饱和 非线性和用户数的动态变化等不确定性。这些因素的存在，不仅限制了常规反馈拥塞控 制算法的应用，而且还导致网络的大范围震荡，并且模型阶次难以确定，由此给基于模 型的分析方法带来很大的困难。 本文针对上述问题，首先，建立了单瓶颈节点的网络流模型，该方法只需考虑网络 链路延时，将其他延时( 如排队和交换延时) 和不确定性看作为系统的扰动。然后，设计 了广义预测拥塞控制算法。保证了闭环系统的全局稳定性和稳态公平性，并设计了自适 应预测拥塞控制算法，提高了系统对用户数动态变化的鲁棒性。最后，仿真研究结果表 明，本文所提算法在性能上优于已有算法：改善了系统的暂态性能，增强了对不确定性 的鲁棒性，提高了网络利用率，实现了带宽分配的公平性。 关键词：a t m 网络：显式速率；拥寒控制；流控制；广义预测控制；通信量管理。 墨堡型塑塞苎型簦些墨堕壅翌! 望，_ 一 a b s t r a c t a t mi s8c o n n e c t i o n o r i e n t e d ，p a c k e ts w i t c h i n g ，a n d a t a t i s t i c a l l y m u l t i p l e x i n gt e c h n o l o g y h o w e v e r ，w i t h m a n y b u r s tt r a f f i cs i m u l t a n e o u s l y a r r i v i n ga tan o d e ，t h eq u e u el e n g t hm a yb e c o m el a r g e ra n db u f f e r o v e r f l o wi n am o m e n t ，o r h i g h s p e e d l i n ki se m e r g e di n t os l o w e ro n e ，t h e r ew i l l b ei n c o n g e s t i o n o n c en e t w o r k sc o n g e s t e d ，t h et r a n s f e rd e l a yg r o w su pa n dt h er a t i e o fe e l ll o s si n c r e a s e sr a p i d l y a n dt h es u s t a i n e dc o n g e s t i o nw i 1lb r i n go nt h e b r e a k d o w no ft h en e t w o r k i naw o r d ，i ti st h ef i r s tt a s kt oc e n t r e lc o n g e s t i o d e f f i c i e n t l y t oi n c r e a s er e s o u r c eu t i l i z a t i o na n d i m p r o v e t h eq u a l i t yo f s e r v i c e s a t mf o r u ms e l e c t sr a t e - b a s e df e e d b a c kc o n t r o la st h es t a n d a r da l g e r i t h m i t m e r e l yp r o v i d e ss o m ec o n s t r u c t i v es k e t c hw i t h o u td e t a i l e dp l a n t h ed i s a d v a n t a g e o ft h ee x p e r i m e n t a la l g o r i t h m si st h a tt h e ya 1 1d o n tg u a r a n t e et h ef a i r n e s s a n dc a u s et h eo s e i l l a t i o ni nq u e u eo fn o d e so ra l l o w e dc e l lr a t eo fu s e r s ，a n d l a c k so ft h e o r e t i c a lp e r f o r m a n c ee v a l u a t i o n l i n e a rc o n t r o lt h e o r yb a s e dd e s i g n d o e s n tc o m p l e t e l yc o n s i d e rt h eu n c e r t a i n td e sc a u s e db yt i m e v a r y i n gt r a n s f e r d e l a y ，s a t u r a t e dn o n 一1 i h e a r t t ya n dd y n a m i c a lv a r i e t yo fu s e r s t h e s ef a c t o r sn o t o n l yr e s t r i c tt h eu s eo ff o r m a lc o n t r o la l g o r i t h m sb u ta l s or e s u l ti nl a r g e s c a l e v i b r a t i o n a 1 1t h e s ef a c t o r sm a k ei th a r dt od e c i d et h es y s t e mo r d e r ，w h i c hb r i n g s t h ed i f f i c u l t vi ni m p l e m e n t i n gm o d e l b a s e da p p r o a c h t h et h e s i sf i r s tb u i l d su dt h en e t w o r kf l u i dm o d e lo fs i n g l eb e t t i e n e c kn o d e i t o n l y t a k e st h el i n kd e l a yi n t oa c c o q n t ，a n dt h i n k so t h e r s ( q u e u i n ga n d s w i t c h i n gd e l a y ) a n du n c e r t a i n t i e sa sd i s t u r b a n c e a n dg e n e r a l i z e dp r e d i c t i v e c o n g e s t i o nc o n t r o la l g o r i t h mi sp r e s e n t e d ，w h i c he n s u r e sg l o b a ls t a b i l i t yo f c l o s e d l o o ps y s t e m ，a n dt h e na d a p t i v eg e n e r a l i z e dp r e d i c t i r ec o n g e s t i o nc o n t r o l a l g o r i t h mi sp r o p o s e d ，w h i c hi m p r o v e st h er o b u s t n e s st od y n a m i c a lv a r i e t yo f u s e r s t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h m se n h a n c et h et r a n s i e n t p e r f o r m a n c e ，a n di n c r e a s er o b u s t n e s sa g a i n s tu n c e r t a i n t y ，a n di m p r o v en e t w o r k s u t i l i z a t j o n a n dr e a l i z ef a i r n e s so fb a n d w i d t ha l l o c a t i o ni ns t e a d ys t a t e k e y w o r d s ：a i mn e t w o r k s ；e x p ji c i tr a t e ( e r ) ：c o n g e s t i o nc e n t r e i ；a v a iia b i e b i tr a t e ( g p c ) ；f i o wc e n t r e i ：g e n e r a iiz e dp r e d ic t iv oo o n t r o i ；t r a f f i cm a n a g e m e n t 广义预测拥塞控制算法及仿真研究 0 前言 异步传输模式( a t m ) - 出称为信元中继，是一种以固定长度的信元为基础的分组交换和 统计复用技术，是一种为了多种业务设计的面向连接的传输模式”j ，其设计是以效率为 代价来换取灵活性。a t m 采用的信元长度为5 3 个字节，由5 个字节的信元头和4 8 个字 节的有效载荷组成。较小的信元长度使交换机能够接收和处理大批量的信元，而定长的信 元减小了各种延时( 传输、队列和交换机处理) ，降低了信元丢弃率，提高了网络利用率， 使网络能够支持更高的传输速率。 在a t m 网络中，当两个突发业务同时到达一个节点，队列长度迅速增加，导致缓冲 区溢出，或当慢速网络引入更高速率的链路，造成输入链路速率大于输出链路速率时， 就产生了拥塞【2 j 。此外，由于a t m 网络传输速率高和业务种类多，网络流量具有突发性 和波动性，即使在设计很好的网络中，也是经常发生拥塞的，进而导致网络整体性能下 降。拥塞一旦发生，传输延时增大，信元丢弃率迅速上升，拥塞持续时间过长，还会导 致整个网络崩溃。因此必须进行拥塞控制以保护网络，降低拥塞的严重性和持续时间， 使网络性能不至于严重下降或使网络免于崩溃。因此，拥塞控制是保证a t m 网络正常运 行的关键。 a t m 论坛通信量管理规范采用基于速率的反馈控制方法作为实现拥塞控制的标准算 法，但论坛只给出该算法设计的指导性建议并未明确规定具体实施方案。由于a t m 论坛 所推荐的拥塞控制算法都是基于经验逻辑的算法，没有系统的性能分析和评价的理论体 系，同时算法也不能保证资源分配的公平性，还容易使源端发送速率产生不稳定的震荡， 因此这几种推荐算法在实际应用中并不能很好地解决服务质量与高速性之间的矛盾。近 年来利用控制理论方法分析或设计拥塞控制机制尤其是速率调节算法已经成为研究热 点。但是，目前己提出的基于线性控制理论的拥塞控制算法几乎都没有综合考虑传输延 时的时变特性、饱和非线性和用户数的动态变化等不确定性。这些因素的存在，限制了 常规反馈拥塞控制算法的应用，而且还导致网络的大范围震荡，并且使得模型阶次难以 确定，由此给基于模型的分析方法带来很大的困难。因此，设计有效的拥塞控制算法成 为通信网络理论研究和应用开发的重要环节。 广义预测拥塞控制算法及仿真研究 1 绪论 1 1a t m 的发展 随着信息社会的发展，早期的电话电报业务已经不能满足人们对各种信息的需求， 于是便出现了许多新型的电信业务，这些业务包括声音、图像、文字和数据等各种信息 的传输和处理业务。每一项业务至少需要有一个传输这项业务的网络，因此出现了诸如 数据通信网、移动通信网、图像通信网和计算机局域网等通信网络。每一种网络都是为 一种特定的业务需求而专门设计的，各种网络的传输速率和特性各不相同。这种用许多 专门网络来提供不同电信业务的方式对于用户和网络管理部门来说，都存在许多弊端如 经济性差、效率低、使用不便、运行费用高和发展新业务困难等。此外，每一网络的规 模都是按照某一种特定的业务类型设计的，即使网络有空闲的资源也不能为其他类型的 业务所使用，因此造成网络资源和资金的极大浪费1 3j 。为了克服上述网络的缺点，必须 从根本上改变网络之间的隔离状况，用一个单一的网络来提供各种不同类型的服务业务， 实现完全开放的系统互联和通信。计算机和通信技术的迅猛发展导致这两个领域逐渐合 二为一，而且数据、话音以及图像传输所使用的也是相同数字技术，这些技术的不断融 合发展，为解决上述问题提供了技术保证。这个能够同时传输和处理各种数据类型的单 一网络称为综合业务数字网( i s d n ) ，引入i s d n 后，用户只需提出一次申请，仅用一条用 户线就可将多种业务终端接入网络并按照统一的规程进行通信。 i s d n 实现了端到端的数字连接，能够支持包括话音、图像、文字和数据在内的各种 业务。通过一个标准的用户一网络接口( u n i ) ，现有的用户电话线就可以提供两条 6 4 k b i t s 的信息信道及一条1 6 k b i t s 的信令信道，简称为2 b + d 信道，如需传送更高速 率的信息，可利用2 0 4 8 m b i t s 或i 5 4 4 m b i t s 的一次群信道。然而，i s d n 还存在一定 的缺陷，首先，一些最吸引用户的业务( 如视频业务) 其速率往往都超过一次群速率；此 外，i s d n 在网络结构方面存在着分离性，它注重的仅是在u n i 上的业务综合，而在其交 换网内仍然是由电路交换和分组交换等若干分离的网络实体提供业务服务。显然，这种 业务综合是不完全的，并且影响到系统的可靠性、运行成本及系统的维护。 为了克服i s d n 的局限性，又发展出宽带i s d n ( b i s d n ) ，b - i s d n 能够提供超过一次 群速率的信道，能够满足全部现有和未来可能出现的业务需要，这些业务有低速的f 如遥 控、遥测、告警、话音、传真和低速数据等) ，中速的( 如高保真声音、可视电话和高速 数据等) ，以及高速的( 如高质量图像、高清晰度电视等) ，这些业务都以相同的方式在网 络中传输和交换，共享网络资源。8 - i s d n 具有良好的灵活性、高效性和经济性，并且能 够适应新技术和新业务的需要，网络资源能够得到充分有效的利用。1 9 9 3 年，国际电信 联盟一电信标准化分会( i t u t ) 选择a t m 技术作为b - i s d n 的交换方式【4 】。 1 2 a i m 标准和规范5 】 广义预测拥塞控制算法及仿真研究 目前有两类制定b - i s d n a t m 标准和规范的团体：正式的标准团体和工业论坛。正式 的国际标准团体有国际电信联盟一电信标准化分会( i t u t ) ，其前身为国际电报电话咨询 委员会( c c i t t ) 、美国国家标准协会( a n s i ) 和欧洲电信标准化协会( e t s i ) 。有四个主要的工 业论坛目前活跃在b - i s d n a t m 规范领域：a t m 论坛、i n t e r n e t 工程任务组f i e t f ) 、帧中 继论坛和s m d s 行业组( s i g ) 。其中a t m 论坛是目前在a t m 规范领域越来越具有影响力的 一个工业论坛。a t m 论坛是由一些厂商、用户和想要保证标准的互操作能力而又不想在 标准中进一步增加实施细节的专家组成的独立小组。a t m 论坛的目标是推动a t m 技术的 普及应用，加快社会对b - i s d n 和a t m 的接口、协议或其他方面的认可。a r m 论坛成立于 1 9 9 1 年1 0 月，a t m 论坛设有三个委员会：技术委员会、市场意识委员会，和最终用户委 员会。技术委员会制定出一些实现规范，并分成许多技术性的“主题专家”小组委员会， 其中业务管理工作组( t m g ) 成立于1 9 9 3 年5 月，提出了一系列通信量管理规范，本文主 要以a t m 论坛“通信量管理规约4 1 版”为基础进行拥塞控制算法的研究。 1 3a t m 网络拥塞控制的研究现状 1 。3 1 拥塞控制的原因 a t m 论坛定义了六种服务类型：固定比特速率( c b r ) j 报务、可变比特速率( v b r ) 服务包 括实时可变比特速率( r t v b r ) 服务和非实时可变比特速率( n r t v b r ) f l 暖务、可用比特速率 ( a b r ) h 匣务，不定比特速率( u b r ) 服务和保证帧速率( g f r ) 服务。这些业务的特性差别很大， 用户对这些业务的服务质量的要求亦不同。如果说嬲络的核心是交换，那么交换的核心 是控制。如果从控制论角度将用户对业务的服务质量要求视为目标函数，那么a t m 要处 理的是一个非线性约束条件下的多目标随机控制问题。 在a t m 网络中，当两个突发业务同时到达一个节点，队列长度迅速增加，导致缓冲 区溢出而不能保证服务质量( q o s ) ；当慢速网络引入更高速率的链路，造成输入链路速率 大于输出链路速率时，就产生了拥塞问题b 】。由于a t m 网络传输速率高和业务种类多， 网络流量具有突发性和波动性，即使在设计很好的网络中，也是经常发生拥塞的。拥塞 一旦发生，传输延时增大，信元丢弃率迅速上升，拥塞持续时间过长，还会导致整个网 络崩溃。因此必须进行拥塞控制以保护网络，降低拥塞的严重性和持续时间，使网络性 能不至于严重下降或使网络免于崩溃。拥塞控制是a r m 网络中一项关键技术。 a t m 网络拥塞可定义为这样一种状态，用户对网络提出的负荷要求接近或超过了保 证通信规约所规定的q o s 的网络资源的设计极限。负荷要求之所以超出了设计极限是因 为资源被过度预订了，或是因为网络内部发生了故障。在a t m 网络中可能发生搠塞的资 源有交换机端口、缓冲区、传输链路、a t m 适配层( a a l ) 并d 连接准许控制( c a c ) 处理器。资 源要求超出了网络能力也称为瓶颈或约束。一拥塞发生的时间可以是：信元级、突发级和 呼叫级。拥塞发生的空间可以是在单个资源内部，也可以是在多个资源内部。应用特点 广义预测拥塞控制算法披仿真研究 如连接模式、重传策略、确认策略和流量控制等，都可以决定拥塞的影响。而网络特点 也决定对拥塞的反应，如排队策略、服务调度策略、丢弃策略、路由选择、传播延时、 处理延时和连接模式等。此外，对拥塞的反应也可能发生在时间或空间上。由于应用特 点、网络特点、拥塞检测和反应的组合数量巨大，拥塞控制问题的定义是困难的。一种 拥塞控制方案在某种应用、网络特点和一定级别中工作良好，而对不同特点或不同级别 的拥塞可能表现很差。本文主要研究信元级的、交换机输出端口缓冲区和单瓶颈节点的 拥塞控制问题。 a t m 网络中用户在请求建立连接时，需要与网络协议一个保证其q o s 的通信量约定， 并且在整个连接期间一直保持这个通信量约定，不改变其q o s 保证。在a t m 论坛定义的 六种服务类型中，c b r 和v b r 服务与其它服务相比具有较高的优先级，因此它们在连接 建立时，网络为其预留带宽。而当一个a b r 连接建立时，没有带宽预留，a b r 连接只能 利用未被c b r 和v b r 连接使用的剩余带宽。如果仍有剩余带宽未被使用，则可以被u b r 和g f r 连接使用。由于u b r 和g f r 两种服务基本上可利用a b r 流控制协议实现，因此， 在进行拥塞控制设计时可以这样认为，由各种信源产生的网络流量仅由c b r 、v b r 和a b r 连接产生。为保证c b r 和v b r 连接的q o s ，即使在网络处于拥塞状态时，c b r 和v b r 源也 不可能降低它们的传输速率。只有a b r 源可以根据反馈信息调整它的速率以改善网络状 态，本文所研究的a t m 网络拥塞控制就是a b r 流的拥塞控制问题。a b r 源利用资源管理 ( r m ) 信元搜集网络状态信息。r m 信元有两种：前向r m ( f r m ) 信元和后向r m ( b r m ) 信元。所 谓前向是指从信源到信宿的方向，后向是指从信宿到信源的方向。 拥塞控制可分为拥塞管理、拥塞避免及拥塞恢复三种类型。拥塞管理是指尽可能使 网络不进入拥塞状态，缺点是可能导致网络链路利用率降低。拥塞恢复是在网络进入严 重拥塞区时，必须丢弃违约的信元，立即终止一些低优先级业务，使网络从严重拥塞中 得以恢复，这种方法缺点是不能保证a b r 流的数据完整性。拥塞避免的目的是避免严重 拥塞，使网络进入轻度拥塞区而又不必丢弃信元，又可以保持较高的网络资源利用率。 本文所研究的拥塞控制算法采用的就是拥塞避免机制。 1 3 2 拥塞控制算法的发展1 6 j 目前已提出的a t m 网络拥塞控制方法可以分为两种方法：预防式的和反应式的【7 “j 。 预防式的拥塞控制方法目的是防止网络在运行时资源被过度预订。而反应式拥塞控制方 法的目的是在拥塞发生时减少拥塞的严重性和持续时间，或是在拥塞将要发生时阻止拥 塞的发生。 预防式的拥塞控制方法是一种静态资源分配，如连接准许控制( c a c ) 、准许和强制带 宽( a d m i s s i o n a n db a n d w i d t h e n f o r c e m e n t ) 一j 和计价带宽分配( p r i c i n g b a n d w i d t h a l l o c a t i o n ) 1 1 0 等方法。预防式的拥塞控制方法在连接建立阶段执行，而反应式拥塞控制 方法是在信息传输阶段起作用的。两种方法通常综合运用。反应式拥塞控制方法运用反 馈机制调整信源发送速率来动态地分配网络资源，因而反应式拥塞控制方法又称为基于 4 。义预测拥塞控制算法披仿真讲究 反馈的拥塞控制方法，这种方法又可以分为两种方法：基于信用( 窗口) 的方法和基于速 率的方法【1 。1 9 9 6 年a t g 论坛将基于速率反馈的拥塞控制算法作为标准算法。 基于速率反馈的拥塞控制方法有二值( b i ) 算法和显式速率( e r ) 算法两种方法。b i 算法 使用r m 信元中的a 位或衍位来反馈网络状态信息，而e r 算法则通过r m 信元的e 兄域 在交换机和信源之间双向交流网络状态信息。e r 算法需要交换机为每个连接计算e r 值， 实现起来要比b i 算法复杂一些，但算法性能要好于b i 算法。b i 和e r 算法的优点是算 法简单，响应快，但是存在难以克服的缺陷，即源端发送速率存在较大的跳跃现象，并 且由于v b r 业务具有突发性和波动性，使算法不可避免地出现振荡，并且两种算法都不 能考虑网络带宽延时积的影响，使网络速率、利用率和交换机缓冲区队列呈现强烈的振 荡现象，因此，这两种算法都不具有稳定性，不能满足高速网络的需要。这些算法都是 基于经验逻辑的算法，没有系统的性能分析和评价的系统理论。最近，人们利用网络流 理论，建立了信息流在交换机缓冲区的队列模型，在此基础上，基于控制理论方法，设 计了不同的可保证性能的拥塞控制算法。基于控制理论的拥塞控制算法能够考虑网络带 宽延时积的影响，并能利用成熟的控制理论对算法进行理论性分析，实现算法的稳定性， 且保证公平性。因为基于控制理论的拥塞控制算法能够直接控制交换机缓冲区队列长度， 所以这类算法往往能够实现很高的网络利用率。 1 3 2 1 二值算法 b i 算法分为两种：前向显式拥塞指示( f e c n ) 算法i 12 】和后向显式拥塞指示( b e c n ) 算法 u 3 1 。 f e c n 算法是一种端一端的反馈控制系统。d e c b i t 算法和比例速率控制算法( p r c a ) 目口 属于这种算法，它们都是运行于信源的算法。d e c b i t 算法1 1 4 j 是一种负反馈控制算法，交 换机测量缓冲区队列长度，如队列长度大于某一高阀值则宣布发生拥塞，而队列长度小 于某一低阀值则宣布解除拥塞。如发生拥塞，交换机将数据信元头中的e f c i 位置l ，信 宿则根据此信息反馈给信源一个a 位置l 的b r m 信元，信源收到此信息后则以积式减少 的方式降低速率：当信源没有收到b r m 信元时，则以和式增加的方式增加速率。此算法 优点是算法简单，交换机计算量小。但是算法没有考虑由于网络延时或拥塞造成的r m 信元延时或丢失，如信源在固定的周期内没有收到r m 信元，则继续增加速率，使网络发 生拥塞或使拥塞更加严重。而且，信源同时增加或同时减少速率，结果发生拥塞时速率 下降迅速，而拥塞解除后速率增加却很慢，使网络流量呈现出较大的波动性。 p r c a 算法【l 副则使用正反馈控制，控制方法基本与d e c 算法相同，只是信源在发送数 据信元时，每隔w 个数据信元的e f c i 位不置位，其余数据信元的e f c i 位全置位，这样 在数据信元通过交换机时，如没有拥塞，则第n 个数据信元的e f c i 不会被置位，信宿 收到e f c i 位为0 的数据信元后，则反馈给信源一个c ，位为0 的b r m 信元。如信源没有 收到b r m 信元，则不断地减少发送速率，如信源收到a 位为o 的b i n 信元的正反馈信息 时，则增加它的发送速率，信源减少的速率、增加的速率都与它当前的速率成定的比 广义预测拥塞控制算法仿真i i j | 究 例，因而称为比例速率控制算法。p r c a 算法虽然克服了d e c b i t 算法因b r m 信元丢失而 产生的不断增加速率的问题，但p r c a 算法最严重的缺点是存在公平性问题即“压制 ( b e a t d o w n l 问题”。所谓“压制”问题是指这样一种情况，假设在一个多节点网络中， 各节点拥塞的状况相同，那么经过节点多的虚通路( v c ) ，其e f c i 位被置位的概率要比经 过节点少的v c 大，那么这样的v c 获得增加速率的机会就少。 在b e c n 算法中，如网络发生拥塞，交换机直接将r m 信元发送给信源，通知信源减 少速率，否则不发送r m 信元。信源在接收到b e c n 拥塞指示这一反馈信息后，将速率减 少一半。如果在规定的周期内信源没有收到r m 信元，信源将速率增加一倍但是不能超过 峰值信元速率( p c r ) 。这种算法也存在不公平性问题，即收到b e c n 指示的信源不一定是 造成拥塞的信源。 二值算法的缺点是反馈信息仅能通知信源是增加速率或是减少速率。更重要的是二 值算法是基于窗口流控制设计的，反应时间太慢，要很多个往返延时才能使网络达到优 化运行点，因此易引起网络振荡。二值算法也没有充分地利用r m 信元中丰富的网络状态 信息，因此，又发展出了基于速率的流控制的显式速率( e r ) 算法m j 。 1 3 2 2 显式速率算法 e r 算法相对于二值算法，有很多的优越性。职算法能够充分利用r m 信元中的网络 状态信息，可以直接通知信源应采取的传输速率。而且算法的收敛速度快，网络能够快 速到达最优运行点，信源的初始速率对其没有影响。e r 算法经历了下列算法的发展： 1 m i t 算法”邯：算法运行于交换机和信源，是一种端一端控制系统。信源发送的r m 信元中含有它的当前速率( c c r ) 和期望速率( e r ) 。交换机根据c c r ，计算公平分享( 圃， f s 的初值设置为可用带宽与活动连结数之比，e r 值小于f s 的v c 称为轻载v c ，轻载v c 数变化时，f s 等于链路带宽减去轻载v c 所占用带宽后的剩余带宽与不是轻载的v c 数的 比值。任何期望速率小于这个f s 的v c s ，交换机不改变其e r 值，信源收到信宿发回的 b r m 信元，就将其中的e r 值作为当前速率。而期望速率大于公平分享的y e s ，交换机就 将其b r m 信元中的e r 值改为公平分享值，并且设置一个减比特。信宿将b r m 信元返回 给信源，信源收到后就按照b r m 信元指示的速率调整它的传输速率。如果返回的b r m 信 元中的减比特被清除了，信源在下一个f r m 信元中的e r 域可以要求更高的期望速率， 否则使用当前速率作为期望速率。这种算法的缺点是交换机必须知道活动v c s 的总数目 和低负载v c s 的总数目，这需要在交换机中保留一个列表，而且，计算公平分享也需要 迭代计算，有”个连接就需要n 次迭代计算，这样就大大地增加了交换机的计算量，这 个计算时间对于大型交换机来说是难以容忍的。 2 增强的p r c a 算法( e p r c a ) “州：e p r c a 算法综合了p r c a 算法和m i t 算法的优点，运 行于交换机和信源，是一种端一端控制系统。信源发送e f c i 位设置为零的数据信元， 每个r m 信元含有期望的e r 和c c r ，以及一个a 比特。信源初始化f r m 信元中的e r 域为p c r 且a 比特位为零。交换机首先是用平均的指数权计算平均允许信元速率 。义预测拥塞控制算法及仿真研究 ( m a c r ) 。然后再乘以7 8 得到愿根据此值设置r m 信元中的e r 域。如果队列长度超 过某个阀值，交换机设置b r m 中的a 位。信宿监测数据信元头中的e f c i 位，如果e r c i 位被置位，就标记后向r m 信元中的a 位。信源在收到a 置位的b r m 信元之后，按比例 减少速率。如果口没有置位，以和式增加速率但不能超过e r 值。这种算法的缺点是， 拥塞指示是通过判断队列长度是否超过某一阀值而得到的，这种判断拥塞方法也存在不 公平性问题即“压制”问题：开始传输信息时间较晚的信源获得的带宽比开始时| b j 较早 的信源得到的带宽少。即使改变拥塞指示为队列增长速率，这个问题依然存在。再有， 如果反馈延时比较大，算法的响应时间太慢，不能适应网络状态的变化。 3 ，o s u 拥塞避免算法口o ：算法运行于交换机和信源，信源定期发送f r m 信元，交换 机以固定周期测量它的输入速率，并与预先设定的日标速率相比较计算当前的负载系数 z = ( 输入速率) ( 目标速率) ，目标速率设置为链路带宽的8 5 - - 9 5 。交换机将z 插进 f r m 信元再传送给信宿。信宿仅简单地将此信元返回给信源，信源收到b r m 信元后，将 其速率设置为其当前速率除以z 。这种算法与e p r c a 算法相比，减少了控制参数，并且 易于设置。但是，在复杂的网络中，o s u 算法的收敛速度不快，而且算法对信源发送r m 信元的周期非常敏感，最后算法与当前的a t m 通信量管理标准不兼容。 于是，在o s u 算法的基础上，又发展出了显式速率指示拥塞避免( e r i c a ) 算法。 4 e r i c a 算法【2 1j ：交换机测量两个参数：活动信源数和可用带宽，并计算负载系数z 。 公平分享( 网为目标信元速率( t c r ) 除以活动信源数。信源发送的f r m 信元含有期望的 显式速率( e r ) 和当前信元速率( c c r ) ，交换机将信源的当前速率除以负载系数，将此值与 f s 比较，选择最大值再与b r m 信元的e r 值比较，选择最小值设置e r 值。这种算法的 缺点是每个信源收到的是一个均分的目标速率，这导致交换机队列长度下降缓慢。再有， 即使交换机处于拥塞状态，信源速率还是有可能超过e r 值。 5 e r i c a + 算法【2 2 】：由于e r i c a 算法没有考虑延时且控制周期比较大，在测量计算 中存在很大的误差，如目标利用率被设置成较大的值，那么队列会变得极大而导致拥塞， 因此，对e r i c a 的个简单改进就是增加一个队列阈值，也就是带队列控制的e r i c a 算 法。如果队列超过此阈值时，降低目标利用率。目标利用率一旦降低，队列将会迅速减 小。因此，这个改进保证了在队列小时也能获得较高的网络利用率，在队列很大时能迅 速减小队列。其算法基本上与e r i c a 算法相同，不同之处在于计算a b r 可用带宽的方法 不同，它在计算可用带宽时考虑了v b r 业务和队列延时的影响。 二值算法和多值算法的优点是算法简单，易于实现，缺点是两种算法都使得源端发 送速率发生较大的跳跃，并且多数算法( e r i c a + 算法除外) 没有考虑v b r 业务的突发性和 波动性给可用带宽和缓冲区队列长度带来的影响，使算法不可避免地出现振荡。此外， 上述算法都没有考虑网络延时( 链路传输、交换机处理和缓冲区排队延时) 的影响，使得 交换机或源端计算e r 值或发送速率时所依据的不是当前的网络状态信息，增加了算法 的调节时间。再有a b r 信元速率、缓冲区大小和链路带宽都具有饱和非线性，使得控制 系统含有非线性反馈环节，即使是单节点的系统，也很难对这种算法进行理论分析。而 实际网络是多节点互相连接的复杂大系统，这些非线性的反馈环节相互作用，会产生某 广义预测拥塞控制算法及仿真研究 些不期望的或不规律的特性，使得上述算法不能提供合理的性能分析工具，只能从仿真 实验中加以验证。而基于线性控制理论的拥塞控制算法，综合考虑网络延时和v b r 的影 响而建立了信元流模型，经过对信元流模型进行线性化处理，可以直接控制缓冲区的队 列长度，提高了网络利用率，并可采用成熟的控制理论方法对算法进行性能分析。 1 3 2 3 基于线性控制理论的拥塞控制算法 近年来，基于模型的线性控制理论分析、设计方法己广泛地应用于拥塞控制算法的 设计，已经取得大量研究结果，并提出许多可供参考的性能分析框架，如p i d 控制、最 优控制理论和自适应控制等等。a b r 拥塞控制系统虽然是一个非线性的反馈控制系统， 但是在一定的假设下，把非线性系统线性化，利用线性控制理论设计拥塞控制是可行的。 1 p 控制器1 23 】：交换机测量其输出端口的缓冲区队列长度p 和输入总信元速率r ， 则可以建立网络模型和p 控制器为：q ( h ) = m a x q m 一1 ) + r ( n 一1 ) 一日】+ n 。0 ) 和 r ：( n ) = b k q ( n ) 。b 为链路带宽，世为正的比例常数，行，为高斯自噪声，用其表示流 量近似值与实际值的误差。r ，为第i 个信源的发送速率，r 为所有信源的发送速率之和。 交换机每秒计算一个反馈变量r ，将r ，设置为r m 信元中的黜值反馈给信源，信源 即按照收到的r m 信元中的e r 值调节其速率。如何选择比例系数足是设计控制器的主要 问题，根据n y q u i s t 图分析得到闭环增益k n a 2 时，系统是稳定的。如果k n a 接近于 2 ，闭环系统将会产生振荡。当然，如果考虑网络的延时，情况会更糟。根据闭环传函 的波德图，分析穿越频率处的相位裕度，来确定最大容许延时。增加而保持k n a 不变， 将增加系统对较大延时的鲁棒性，但是这也降低了网络的吞吐量和增大了系统的响应时 间。同时，足也随之减少，使稳定状态队列长度增加。反过来，降低闭环增益产生的影 响同上述做法的结果是一样的。因此，删必须尽可能的选择得小一些，以使网络在可 能的最大延时下也能保持稳定。此外，由于信源数是可变的，为保持k n l x 不变，足必 须随变化，这就要求交换机能够预估v 值。如果k 必须随v 变化，而又保持k n a 不 变，则稳态队列长度也随值线性增加，这就要求交换机有更大的缓冲区。为了使算法 对延时有更好的鲁棒性和适应更多的用户，算法采用虚队列法方法解决这个问题：采用 稍小于口的值蛸计算出虚队列长度q v n i ，可保证实际的队列长度总是小于虚队列长 度。此算法所建模型过于简单，没有考虑往返延时和v b r 流的影响，只是对p c r a 算法的 一种改进，能够对控制系统进行理论分析，在性能上提高不大。 2 p d 控制器1 1 2 4 1 ：此算法本质上是一种二值算法，它克服了二值算法的不稳定性和 非线性问题。交换机测量缓冲区队列长度和信元输入总速率，网络模型同上一算法。算 法分别运行于交换机和信源，交换机根据预先定义的队列长度阀值设置r m 信元中c 卢l 的概率为p ，则有算法：p ( n a ) = 0 + b ) q ( n l x ) 一a q ( ( n 一1 ) a ) 。信源收到反馈信息p ，则 有算法：r ，( n ) = 球，( 0 1 ) ) 一 + 卢) p 瓜月一1 ) ) + 。经基于闭环传函幅k - f l 曲线的频 率响应分析，参数a 和用于设置相位裕度。带宽和稳定状态的p 值。系统的最大往返 延时受到系统的相位裕度的限制。如果往返延时超过此限制，系统就将运行在饱和区。 而系统一旦运行在饱和区，其性能就与二值算法相同。如何恰当地选择参数t - i 和b ，使 广义预测拥豢控制算法及仿真研究 控制系统运行在线性区域，该算法并没有明确的解决办法。上述两个算法，由于采用的 网络模型过于简化，没有考虑高优先级业务和往返延时对可用带宽的影响，同时算法还 受到最大往返延时的限制。 3 p d 控制器2 2 5 ：算法运行于交换机，交换机测量缓冲区队列长度x ，则有模型为 d x ( n + 1 ) = s a t 。 x ( n ) + f z ，( m ) q ( n + l i ) + ，。( n ) 一c ，设x o 为期望的队列长度，则有拥塞控 。t 一= o |k 制器算法为：q ( n + 1 ) = sa t ，_ 。 g ( 功一口，o 一，) 一妒) 一f l k q ( n 一坳。其中r o ( ) 表示不受控 j 磊面 的流量。为确定控制增益研口的值，设控制增益为g = ( ，口，风，届，卢。) 7 ， l = ( 1 0 ，一一，) 7 为被瓶颈的链路数量，则有个d + 3 维的控制系统，拥塞控制器设计 的核心问题是控制增益g 的选择问题。该算法采用极点配置法设计控制器增益。该算法 是一种比较好的拥塞控制算法，对后续的拥塞控制研究产生了很大的影响。从其模型可 以看出，算法考虑了网络往返延时和v b r 流的影响。但是简单的极点配置设计不适合非 最小相位系统，而拥塞控制系统有可能是非最小相位系统。该算法最大的缺点是把量化 往返延时所产生的测量误差看作是不可控流。交换机能够测量不可控流所占用的带宽， 但是不能测量这种量化误差。再有，该算法计算的e r 值有可能小于零或太于p c r ，使 算法运行在非线性区，降低了暂态响应速度。 4 d p d c 算法 2 6 , 2 7 ：为了克服单p d 控制器暂态响应慢的缺点，此算法采用双p d 控制 器设计。算法所采用网络模型和拥寨控制器设计方法同上算法。第个p d 控制器是低 增益p d 控制器( l g c ) ，用于在输出端口q 被瓶颈的信源数很大的情况下。第二个控制器， 称为高增益p d 控制器( h g c ) ，选择的控制增益较大。实际上该算法还有第三个控制器即 初始恢复速率选择( i r r s ) 控制器，i r r s 控制器的设计采用e r p c a 算法计算平均允许速率 ( m a c r ) 的设计方法。交换机根据队列长度来判断网络负荷处于何种状态，如果是轻载， 则h g c 会很快地增加信元速率，使队列长度接近期望值；如果是过载，则i r r s 会很快减 少信元速率，使队列快速清空，然后h g c 使队列接近期望值；如果是正常状态，队列长 度在期望值附近时，则l g c 会使队列长度稳定在期望值。l g c 在三个控制器中是主要的 控制器。该算法只是克服了单p d 控制算法暂态响应慢、算法可能进入非线性区的缺点， 单p d 控制算法其他的缺点仍然存在。 5 日，算法【2 8 i ：算法运行于交换机。研究结果表明，拥塞发生在低频输入业务速率 超过链路容量的时候。a r b 业务仅需为适应随时间缓慢变化的v b r 业务而调整它的速率。 因此，动态模型的状态变量可定义为低频未使用的链路容量，输入变量是每个a b r 业务 的速率，输出定义为链路容量和当前使用的链路容量的差值，据此可构建一个多输入一 单输出的线性控制系统。为了简化控制，对不同的a b r 控制环进行解偶，将线性动态模 型化为一系列的单输入一单输出的子系统，则有网络模型：x ，( 竹) = 一“，0 一1 ) + 0 3 ，( ”) 。 表示随v b r 业务动态变化的可用带宽，可看作是系统的扰动。控制目标是保证 9 广义预测捅寒控制算：法及仿真研霓 t i m 一。x ，( ”) = 0 ，这可以取忱( n ) l f ：= 、x ? ( 七) 最小来实现a 经z 域稳定性分析，则有h ： yk = l 最优控制器算法：峨( n ) = p x c ，一呓( ) = ，( ”) 或峨( 月) = ( m + 1 ) ，( m ) 一，【 一1 ) 。陔算 法的缺点是对于往返延时和突发业务不能同时具有很好的鲁棒性。 6l q g 自校正算法 2 9 j ：算法运行于交换机，试图在考虑高优先级业务的同时，解决 最优控制队列长度和对延时的鲁棒性问题。此算法对前述算法的模