（检测技术与自动化装置专业论文）智能优化算法及其在atm网络流量控制中的应用研究.pdf

河海大学硕+ 学位论文 摘要 摘要 综合业务数字网是未来通信技术的发展趋势，a t m 网络已被国际电信联盟作 为一项典型传输技术加以推广。在a t m 网络中，信息的拥塞及丢失是影响网络 业务服务质量的主要因素。由于a b r 业务是唯一一种可采用反馈机制进行流量 控制的业务，a b r 业务流量的控制和管理问题目前已成为一研究热点，引起了控 制和通信学者的广泛关注。本文将控制理论引入到网络通讯中，对控制、通信而 言均具有重要的理论意义和实用价值。为了较好地解决可控流的拥塞控制问题， 本文主要作了以下研究工作： 首先，在分析了a b r 业务反馈机制的基础上，给出了a t m 网络单瓶颈节点 模型，在此基础上，将p i d 控制引入到网络控制中，设计出了适用于a t m 网络 模型的p i d 控制器，并给出了保证系统闭环稳定的充分条件。 其次，为了较好地应用p i d 控制，本文选用了遗传算法和粒子群算法对p i d 控制器进行参数优化，经过优化的p i d 控制器能较好地控制a t m 网络流量，减少 拥塞，提高网络资源利用率。 另外，针对基本粒子群算法容易陷入局部最优值的缺点，提出了两种改进的 粒子群算法。一种是基于粒子运动方向变异的改进粒子群优化算法，此算法通过 改变部分粒子的运动方向来达到扩大种群多样性的目的；另一种是基于混沌思想 的混合粒子群算法，此算法通过引入算法早熟判断机制，并结合混沌算法的随机 性、遍历性、规律性来提高算法的搜索能力和搜索效率。这两种改进的粒子群算 法都具有较强的全局搜索能力，能较好的解决普通粒子群算法容易陷入局部最优 解的问题。 最后，将经过智能优化算法整定的p i d 控制器应用于提出的a t m 网络模型 中，使得系统的稳态动态性能有所改善，并使系统具有一定的鲁棒性，抑制了 交换机的队列长度的大幅波动。 关键词：a t m 网络；a b r 业务；拥塞控制；p i d 控制；p i d 参数整定；遗传算法； 粒子群算法；混沌算法 河海大学硕士学位论文 a b s 虹a c t a b s t r a c t i n t e g r a t e ds e r v i c ed i g i t a ln e t w o r k ( i s d n ) i sc o n s i d e r e da st h et e n d e n c yo ft h e c o m m u n i c a t i o nt e c h n i q u ei nt h ef u t u r e a s y n c h r o n o u st r a n s f e rm o d e ( a t m ) i s a d o p t e da sat 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 ) t h el o s so fd a t aa n dt h ec o n g e s t i o no fi n f o r m a t i o na y em a i nf a c t o r st h a ta f f e c tt h e q u a l i t yo fs e r v i c e 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 eo n l yt y p eo f t r a f f i ct h a tc a l l b ec o n t r o l l e db yt h ef e e d b a c km e c h a n i s m t h ec o n t r o la n dm a n a g e m e n to fa b r s e r v i c eh a v eb e c o m eaf o c u sa n da t t r a c t e dal o to fp e o p l ei nt h ec o n t r o la n d c o m m u n i c a t i o n sf i e l d t h er e s e a r c ho nc o n g e s t i o nc o n t r o lo fa t mn e t w o r kh a sg r e a t s i g n i f i c a n c ei nb o t ht h e o r ya n dp r a c t i c e t oc o n t r o la t m n e t w o r kb e t t e ra n ds o l v et h e c o n g e s t i o np r o b l e mo fc o n t r o l l a b l ef l o w , t h ef o l l o w i n gr e s e a r c hw o r k sh a v eb e e n d o n e ： f i r s t l y ，b a s e do nt h ef e e d b a c km e c h a n i s mo fa b rs e r v i c e ，t h em o d e lo fs i n g l e b o t t l e n e c kn o d ei sg i v e n b a s e do nt h i s ，t h ep i dc o n t r o lm e t h o di si n t r o d u c e di n t ot h e n e t w o r kc o n t r o la n dt h ep i dc o n t r o l l e ri s d e s i g n e d f u r t h e r m o r e ，t h e s u f f i c i e n t c o n d i t i o no f t h es t a b i l i t yo f c l o s e dl o o pi sa l s og i v e n s e c o n d l y ，t oa p p l yp i dc o n t r o l l e rb e t t e r , t h eg e n e t i ca l g o r i t h m ( g a ) a n d p a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h m ( p s o ) h a v eb e e nu s e dt ot u l l et h ep a r a m e t e r so ft h e p i dc o n t r o l l e r t h ec o n t r o l l e r sb a s e do nt h eo p t i m i z a t i o nc o n t r o la t mn e t w o r kf l o w b e t t e r ，r e d u c et h ep r o b a b i l i t yo fc o n g e s t i o na n di m p r o v et h eu t i l i z a t i o no fn e t w o r k r e s o u r c e t h i r d l y ，t oo v e r c o m et h ed i s a d v a n t a g eo fe a s yt r a p p i n gi n t ol o c a lo p f i m a lv a l u e f o rt h eg e n e r a lp s oa l g o r i t h m ，t w om o d i f i e dm e t h o d so fp s oa l g o r i t h ma r ep r e s e n t e d o n ei st oi n c r e a s et h ed i v e r s i t yb yc h a n g et h em o v i n gd i r e c t i o no fap a r to fp a r t i c l e s ； t h eo t h e ri st oc o m b i n et h ea l g o r i t h mw i t hc h a o s t h e s et w om o d i f i e dp s oa l g o r i t h m s h a v es t t o n ga b i l i t i e st os e a r c hg l o b a lo p t i r e a lv a l u e ，a n da r ea b l et oo v e r c o m et h e s h o r t c o m i n go ft h eg e n e r a lp s oa l g o r i t h mw h i c hi se a s yt ot r a pi n t o l o c a lo p t i m a l v a l u e a tl a s t ，t h ep i dc o n t r o l l e rt u n e db yi n t e l l i g e n to p t i m i z a t i o na l g o r i t h mp r o p o s e d a b o v ei sa p p l i e dt oe x p l i c i ta b rs e r v i c ec o n g e s t i o nc o n t r 0 1 t h i sc o n t r o l l e rr e s t r a i n s o s c i l l a t i o ni nac e r t a i ne x t e n t ，i m p r o v e ss t e a d ya n dd y n a m i cp e r f o r m a n c eo fs y s t e m ， a n dm a k e st h es y s t e mh a v es o m er o b u s t n e s sp e r f o r m a n c ea tt h es a m et i m e k e y w o r d s ：a t mn e t w o r k ；a b rs e r v i c e ；c o n g e s t i o nc o n t r o l ；p i dc o n t r o l l e r ；g e n e t i c a l g o r i t h m ；p a r t i c l es w a r l no p t i m i z a t i o na l g o r i t h m ；c h a o sa l g o r i t h m i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任： ，、f 论文作者( 签名) ： 丝塑塾勿。7 年3 月砂6 日 ( 注：手写亲笔签名) 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘 版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用 影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部 分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ： 垄i 麴窒伽。7 年j 月z 6 日 ( 注：手写亲笔签名) 河海大学硕士学位论文 第一章绪论 1 1 引言 第一章绪论 近十几年来，计算机网络经历了飞速的发展，使得信息的交流变得方便和快 捷。借助计算机网络，人们解除了地理位置的束缚，处在不同地方的用户可以共 享网络上的软件资源和硬件资源。多媒体计算机网络的应用，使声、文、图、像 等多种信息的收集、传送、存储和处理融为二体，给用户提供了很大的方便。可 以说计算机网络已经成为现代社会重要的组成部分和赖以生存的基础。 随着远程通信、多媒体和计算机工业与技术的日益发展和相互结合，计算机 网络互联逐渐采用一种称为异步转移模式( a s y n c h r o n o u st r a n s f e rm o d e ，简称 a t m ) 的技术。该技术已被国际电信联盟( 1 1 ut ) 推荐为b i s d n 的复用和交 换方式，也是当前宽带网络( 如a d s l ，v d s l 等) 的核心技术。自1 9 9 4 年以来， a r m 网络己从实验室研究大量走向实际应用，它结合了电路网络和计算机网络 的优点，能承载语音、数据和图像等多种业务；它同时支持专用和公用网络，具 有动态分配信道带宽的优点，从而简化了网络结构，有效地利用了网络资源。与 此同时，a t m 网络的国际标准也已由a t m 论坛【1 1 和i t u 2 f 6 1 j 定并正在完善与发 展。 网络中，当两个突发业务同时到达一个节点，队列长度会迅速增加，从而导 致交换机缓冲区溢出，不能保证服务质量，或当慢速网络引入更高速率的链路， 造成输入链路速率大于输出链路速率时，就产生了拥塞问题。由于a t m 网络传 输速率高和业务种类多，网络流量具有突发性和波动性，所以即使在设计很好的 网络中，拥塞也经常发生。拥塞一旦发生，传输延时就增大，信元丢弃率迅速上 升，拥塞持续时间过长，还会导致整个网络崩溃。因此，拥塞控制 3 1 1 4 1 是a t m 网 络设计中的一个关键问题，引起了越来越多的国内外学者及各大网络设备生产商 的广泛关注。 很多像计算机网络这样的复杂系统中的问题，都能从控制理论的角度进行分 析。y a n g 和k e d d y 依据控制论将拥塞控制方法分为两类：开环和闭环控制f 5 1 。 开环控制运行于网络端系统，它致力于通过良好的设计避免拥塞的发生，典型的 a t m 网络开环控制方法如漏桶算法【6 】。但是，开环控制是一种预防式的控制方 法，其主要缺点是当拥塞发生后不能快速消除拥塞，而且网络资源利用率低。与 之相比较，闭环控制的解决方案是建立在反馈环路上的，其工作原理是根据网络 中的反馈信息，动态地调节每个连接的信元发送速率，从而提高网络带宽利用率， 河海大学硕士学位论文 第一章绪论 及时消除网络拥塞。 1 2 基于速率的a b r 业务拥塞控制之研究现状 a t m 网络的一个重要特征就是它能提供几类服务以满足不同应用的服务质 量要求。这包括：恒定比特率业务( c b r ) ，可变的比特率业务( v b r ) ，可用比 特率业务( a b r ) 以及未指定比特率业务( u b r ) 。这些服务中，c b r 和v b r 属于“受保护”的服务，它们被网络中的交换机赋予更高的优先权，优先获得链 路带宽的分配。a b r 则是利用c b r 和v b r 连接剩余的带宽来承载“尽力传输” 的业务；此外，a b r 服务主要用于支持数据应用，在网络信息传输中有着重要 的地位。因此a b r 业务的拥塞控制显得尤为重要。 a b r 业务采用基于速率反馈的拥塞控制机制，而且是网络中唯一会向发送 者提供速率反馈的服务类型。以往基于速率的a b r 拥塞控制机制研究中，大多 采用直觉的启发设计方法，不可否认，这种模式为网络设计积累了很多经验，发 掘了不少新的方法与策略，在一定程度上控制了网络拥塞。但是，它们存在两个 不足，一是网络流量或信源发送速率呈现有振荡性；其次是在具有大的带宽时延 乘积的网络中，控制效果不佳。这是因为a t m 网络中，大的带宽时延乘积意味 着在信源确认网络拥塞时，己有大量信元( 未受控) 发给网络1 7 1 。此外，在以往 基于速率的控制机制研究中，很少考虑其它业务流的影响【8 】，这也是已存在的基 于速率的方法会引起振荡性的原因之一。因此，近年来利用控制理论方法分析或 设计拥塞控制机制( 尤其是基于速率的闭环控制) 已广泛开展。 基于控制理论的方法，给出一个a b r 业务的网络受控分析模型，所以可方 便地使用各种控制理论方法进行速率调节器的设计。此外，还可根据控制目标( 如 稳定性、瞬态响应、鲁棒性和公平性等) 进行参数整定，从而有效地控制或避免 网络拥塞，提高网络运行性能，保证不同用户所要求的服务质量。a t m 网络拥 塞控制中，已提出的控制方法主要有：比例控制器( p 控制器) 9 1 ，r p 调节器【m 】， p d 控制器【1 1 】，c a e r a 控制器【1 2 1 。s p d i 控制器( s i m p l i f i e dp d ) 0 3 ，s p d 2 控制 器【1 4 1 ，d u p 控制器( 双p d 调节器) 【1 5 】、h 2 调节器f 1 6 1 、l q 控制器i 切。这些方法 从理论上保证了控制机制的稳定性，比较好地解决了资源利用率问题，但仍然存 在着如下一些问题： ( 1 ) 控制机制设计时，未考虑公平性问题。 ( 2 ) 控制参数难以确定。 ( 3 ) 突发干扰时，受控参数变化较大，可能产生过大的超调，使缓冲区溢出， 信元丢失率上升。 对于给定的受控模型，可通过采用最优化方法使网络的运行效率最优，以最 2 河海大学硕士学位论文第一章绪论 大限度地提高网络资源利用率。近些年来，智能优化算法与常规p i d 控制技术 相结合，形成所谓的智能优化p i d 控制，这种控制器己引起人们的普遍关注和 极大兴趣，并已得到较为广泛的应用。但是，以往基于速率的拥塞控制很少采用 这种控制方法，因此本文将结合这两种技术，对a t m 网络中a b r 业务的拥塞 问题进行研究。 1 3 基于智能优化的p i d 参数整定之研究现状 p i d 控制是最早发展起来的控制策略之一，由于其具有算法简单、鲁棒性好、 可靠性高等优点而被广泛应用于工业过程控制领域。为了更好地应用p i d 控制， p i d 控制器的参数整定与优化已成为一个重要的研究课题【i 研。目前参数的优化方 法有很多，如间接寻优法，梯度法，爬山法等，而在热工系统中单纯形法、专家 整定法则应用较广。虽然这些方法都具有良好的寻优特性，但却存在着一些弊端， 单纯形法对初值比较敏感，容易陷入局部最优解，造成寻优失败。专家整定法则 需要太多的经验，不同的目标函数对应不同的经验，而整理知识库是一项长时间 的工程。随着智能控制理论的飞速发展，出现了基于知识推理的专家p i d 控制、 基于规则的自学习p i d 控制、基于连接机制的神经网络p i d 控制以及基于模糊 逻辑的智能p i d 控制等先进p i d 控制方法【1 9 j 。这些智能p i d 控制策略或要求对 被控过程和控制规律有全面的先验知识，或建立在要求具有连续导数的光滑搜索 空间的基础上，若参数空间为非线性时，则得不到全局最优。美国h o l l a n d 提出 的遗传算法【2 0 j 是一种不需要任何初始信息并可以寻求全局最优解的、高效的优 化组合方法，近年来也被用于p i d 参数整定。但这种算法有“过早成熟”和收 敛速度较慢的缺点，而且需要设定的参数较多。粒子群算法( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 是由k e n n e d y 和e b c r h a r t 等 2 1 1 于1 9 9 5 年提出的一种演化计 算算法。它是对鸟群觅食过程中的迁徙和聚集的模拟，更确切地说是由简单个体 组成的群落与环境以及个体之间的互动行为。该模拟系统利用局部信息，从而可 能产生不可预测的群体行为。目前已广泛应用于函数优化、神经网络训练和模糊 系统控制瞄l 】等领域。将p s o 算法应用于p i d 控制器的参数整定也是一个新的 尝试。 1 4 本文的主要工作 传统的拥塞控制方案大多是基于启发式法则，缺乏正式的理论支持，并且依 靠一系列的测量值，这些测量值不是很难测量就是在估计时产生显著的噪声。滤 除这些噪声将导致队列振荡，较高的信元丢失和较低的链路利用。因此，本文摒 弃了直觉的启发式设计方法，应用控制理论中成熟的分析和设计方法，研究了 河海大学硕士学位论史第一章绪论 a t m 网络中显式a b r 业务的拥塞控制问题，期望对拥塞控制机制和算法的性能 在理论上有一个全面深入的理解，本文主要进行了以下工作： l 、分析介绍了a 刚网络的基本服务类型及不同服务类型所采用的拥塞控 制机制，指出了a b r 业务拥塞控制的重要性，并从控制理论角度总结 了目前研究较多的基于速率反馈的a b r 拥塞控制方法，指出了该领域 研究的热点和难点。 2 、对遗传算法、粒子群算法、混沌算法进行了分析和研究，并对粒子群算 法提出了两种改进算法。经过改进的粒子群算法具有较强的全局搜索能 力，能很好的解决普通粒子群算法容易陷入局部最优解的问题。 3 、将p i d 控制与上述智能优化算法结合，得到了基于智能优化算法整定的 p i d 控制器。将这种控制器应用于显式a b r 流的拥塞控制问题中，使 线性p i d 控制器在一定程度上抑制了系统振荡，使得系统的稳态，动态 性能有所改善，并使系统具有一定的鲁棒性。 4 、分析比较了各类拥塞控制方法，指出了它们的优缺点及a t m 网络a b r 业务拥塞控制的进一步改进思路，并对拥塞控制的进一步研究及智能控 制的应用前景进行了展望。 1 5 章节安排 本文的章节安排如下： 第一章：绪论，介绍本文的研究背景、研究现状和主要研究方向等。 第二章：介绍a t m 网络及a b r 业务流量控制。 第三章：提出了a b r 流量控制的单瓶颈节点网络模型及a b r 业务流量的p i d 拥塞控制算法。 第四章：提出了基于遗传算法整定的p i d 网络流量控制。 第五章：提出了基于粒子方向变异的改进粒子群算法，并将其运用于p i d 网 络流量控制中。 第六章：提出了基于混沌思想的改进粒子群算法，并将其运用于p i d 网络流 量控制中。 第七章：对上述几种经过参数优化的p i d 控制器进行分析和比较，并对进一 步的研究作了展望。 4 河海大学硕士学位论文第二章a t m 魇络及a b r 业务拥塞控制机制简介 第二章a t m 网络及a b r 业务拥塞控制机 制简介 2 1a t m 网络简介 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 ) 即异步传输模式，是一种面向连接的快 速分组交换技术。其建立在异步统计聪分复用基础上，并使用固定长度的信元， 支持包括数据、语音、图像在内的各种业务的传送。a t m 网络吸收了传统网络 技术的优点，避开了某些不足之处，它最突出的一个特点是采用了一种固定长度 的信元作为分组交换和统计复用技术的基础。a t m 信元由5 3 个字节组成，其中 包括4 8 个字节的有效载荷和5 个字节的信头。较小的信元长度使交换机能够接 收和处理大批量信元，而定长的信元结构减小了各种延时( 传输和交换机处理) ， 降低了信元丢弃率，提高了网络利用率，使网络能够支持更高的传输速率。本章 对a t m 网络及其a b r 业务拥塞控制进行简要介绍。 2 1 1a t m 网络的业务类型 a t m 论坛定义了四种类型的业务，分别为恒定比特率业务、可变比特率业 务、可用比特率业务、不确定比特率业务。每种业务类型有自己的流量特性、 q o s ( 服务质量) 指标和拥塞控制策略。 1 恒定比特率业务( c o n s l a n tb i tr a t es e r v i c e ，c b r ) ，是一种预留带宽的 业务。它要求在整个连接期间必须有恒定大小的带宽来支持该业务，带 宽的大小由c b r 业务的峰值信元速率来确定。c b r 业务主要用来支持 对时延有严格限制的实时性应用，如语音、视频、电路仿真等。在c b r 中，信源在任何时间都可以用等于或小于协定的峰值信元速率向网络发 送信元，并且持续时问可任意长，网络必须以协商而定的q o s 支持这些 遵守一致性测试的信元流。 2 可变比特率业务( v a i l a b l eb i tr a t es e r v i c e ，v b r ) ，主要用于支持数据 应用，可分为实时可变比特率业务( r t - v b r ) 及非实时可变比特率业务 ( n r t - v b r ) 。实时可变比特率业务主要用来描述具有可变数据流并且 要求严格实时的服务，比如交互式的压缩视频( 例如电视会议) 。非实时 可变比特率业务主要用于定时发送的通信场合。在这种场合下，一定数 量的延迟及其变化是可以被应用程序所忍受的，如电子邮件。v b r 与 河海大学硕士学位论文第二章a t m 网络及a b r 业务拥塞控制机制简介 c b r 一样，在网络中赋予极高的优先权并优先获得链路带宽分配。 3 可用比特率业务( a v a i l a b l eb i tr a t es e r v i c e ，a b r ) ，是为带宽范围大致 已知道的突发性信息传输而设计的。a b r 业务是一种“尽力传输”的业 务，具有很高的统计复用增益，对带宽和时延没有定量要求，为许多应 用业务所接受。a b r 是唯一网络会向发送者提供速度反馈的服务类型。 当网络中拥塞发生时会要求发送者减小发送速率。 4 未指定比特率业务( u n s p e c i f i e db i tr a t es e r v i c e ，u b r ) ，是延时和时延 偏差没有严格要求的非实时性应用，如传统计算机网络中的应用程序， 如文件传输和电子邮件等。对u b r 业务，没有定义信元丢失率，也没有 流量控制参数，因此当使用u b r 业务是信元丢失会严重影响系统的整体 性能，为避免以这种方式浪费网络资源，可以在网络的任何中间结点上 进行适当处理。 2 1 2a t m 拥塞的原因 在a t m 网络中，当两个突发业务同时到达一个节点，队列长度迅速增加， 导致缓冲区溢出而不能保证服务质量( q o s ) ，或当慢速网络引入更高速率的链 路，造成输入链路速率大于输出链路速率时，就产生了拥塞问题。 造成拥塞的因素主要是：( 1 ) 存储空间不足，即没有足够的内存来存放通信 子网中的分组，但无限大的内存并不能解决拥塞问题，反而使拥塞更加厉害，因 为分组在达到队列时已超时而所有的这些分组也要尽职的转发给下个路由器从 而增加了到达目的地的载荷；( 2 ) 带宽容量不足，低速链路对高速数据流的输入 会产生拥塞：( 3 ) 处理器的处理能力弱、速度慢也能引起拥塞。 要避免拥塞的发生，对以上三点原因需综合考虑，例如，提高链路速率两不 改变处理器，只会转移网络瓶颈，而不会避免拥塞。所以拥塞往往也是系统各个 部分不匹配的结果。 2 1 3a t m 网络拥塞的危害 网络的各种资源，比如网络节点中的节点缓冲器，容量总是有限的。因此， 如果不对进入网络的信息流加以限制，就会出现由于缓冲器过负荷而造成的拥塞 现象。图2 1 描绘了这种症状。当主机转存到网络中的数据包在其传输容量之内 时，所有数据包将全部送达目的地( 除了因传输错误而不能正确发送的少量数据 包外) ，且送到的数量与发送的数量成正比例。然而，当通信量增加太快时，路 由器不再能应付，就开始丢弃数据包，并会导致情况恶化。在通信量非常高的情 况下，几乎没有数据包能够送达，此时就出现了所谓的“死锁”现象。此时，信 6 河海大学硕士学位论文 第二章a t m 网络及a b r 业务拥塞控制机制简介 息的传递也就停止了。 图2 - 1 网络吞吐量与负荷的关系 此外，拥塞对网络性能影响的另一方面是使信息传递时延增加。当网络的信 息量增加到一定程度时，在各节点等待处理的排队队列变长了，因此使排队时延 增加。 2 2 a b r 业务基于速率的拥塞控制机制 在a t m 论坛业务量管理规范已经定义的4 类服务中，c b r 和v b r 属于“受 保护”的服务，它们被网络中的交换机赋予更高的优先权，优先获得链路带宽的 分配。a b r 和u b r 服务则是利用c b r 和v b r 连接剩余的带宽来承载“尽力传 输”业务。 此外，a b r 服务主要用于支持数据应用，在网络信息传输中有着重要的地 位。但是，a b r 服务不是提供严格的服务质量保证，而是试图以延迟为代价使 信元丢失最少，并允许源端系统通过调整其瞬时发送速率来充分利用可用的网络 链路带宽。它是唯一会向发送端提供速率反馈的服务类型。因此a b r 业务的拥 塞控制显得尤为重要。 2 2 1a b r 流量控制方案 a b r 流量控制是a t m 网络中一种有效的拥塞控制手段。为了适应高速网络 发展的需要，a t m 论坛在最终选择流量控制方案时放弃了源于滑窗机制的信誉 ( c r e d i t - b a s e d ) 流量控制方案脚】，选择了基于速率( r a i e - b a s e d ) 的流量控制机制1 3 0 l 。 a b r 流量管理规范( t m 4 1 ) 【2 5 】中给出了基于速率的流量实现的技术框架。 对于一个a b r 连接，每个连接终点既是一个源端又是一个目的端，图2 2 为规 范4 1 中所定义的面向a b r 服务的基于速率流量控制模型。图中，a b r 源定时 河海大学硕士学位论文第二章a t m 网络及a b r 业务拥塞控制机制简介 ( 如每3 2 个数据信元) 发送一个前向资源管理( f r m ) 信元，其目的将接受到 的带有网络状态信息的f r m 加上本地的资源状态信息后，发还给源端，此时称 后向资源( b r m ) 信元，根据接收到的b r m 中的信息，源调节其信元发送速率 以适应变化着的网络环境。 图2 2 基于速率的a b r 服务流量的控制模型 在a t m 网络中，根据拥塞管理标准和所采用的反馈机制，各种基于速率的 流量控制机制广义上可以分为两类： ( 1 ) 二进制速率反馈( b i n a r yr a t ef e e d b a c k ，b r f ) 。在此反馈机制中，交换 机主要执行两种运算：探测初始的拥塞和向源结点提供二进制反馈。其 中，b r f 有两种具体的实现机制，分别是显式前向拥塞标识( e x p l i c i t f 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 ) 和相对速率反馈( r e l a t i v er a t e ， l 承) 机制。 ( 2 ) 显式速率反馈【3 1 】( e x p l i c i tr a t ef e e d b a c k ，e r f ) 。对于显式速率机制， 交换机执行三种主要运算：计算可支持每个v c 的带宽公平分享值； 决定负载，这可通过管理队列长度或其增长率来实现；决定实际 显式速率( e r ) 并将其发往源结点。c h a m y ，c l a r ka n dj a i n 等人提出 e r 策略的原因在于二进制反馈机制响应慢，队列长度和信元速率的稳 态振荡造成链路利用率的降低和缓存需求量的加大。e r 策略能保证任 何初始速率的连接很快稳态运行的最佳工作点上，而且具有很强的鲁棒 性，对交换机缓存的需求也相对较小，典型的算法如e p r c a l 2 6 1 ， e r i c a 2 7 ，d e r a 2 s ，p h a n t o m p 2 9 等。本文所研究的就是这种显式速率 反馈机制。 2 2 2a b r 流量控制算法的设计目标 a b r 流量控制算法的设计目标主要体现在以下几个方面： ( 1 ) 可伸缩性，朋n 讧技术具有良好的可伸缩性，从2 到6 2 0 0 m b s ，直到未 8 河海大学硕上学位论文 第二章a t m 网络及a b r 业务拥塞控制机制简介 来的g b s 级速率接口，从城域网到广城网都可以采用一种交换手段。相 应地，a t m 网络的拥塞控制机制也不能只局限于较低的传输速率、交换 节点数目和v c 数量上，同一个拥塞控制算法应该能够适用于各种级别 的应用需求。 ( 2 ) 链路利用率高，使网络吞吐量达到最大，带宽可以得到有效地利用。 ( 3 ) 信元丢失率低，使丢失敏感而延时不敏感应用的q o s 得到保证。 ( 4 ) 稳定性，使网络在具有大量连接且彼此延迟均不相同的条件下仍能收敛 于平衡点。 ( 5 ) 具有很好的瞬时特性，如与连接数量无关的快速一致性收敛。 ( 6 ) 鲁棒性，拥塞控制机制应该对异常情况有一定的承受能力。比如，用户 的某些参数的不完全恰当的没置，或者拥塞控制信息的少量丢失都不应 引起网络崩溃。 2 3 本章小结 本章简要介绍了a t m 网络提供的四种服务类型及不同服务类型采用的拥塞 控制机制。同时，本章指出了a b r 业务拥塞控制的重要性，它是网络中唯一会 向发送者提供速率反馈的服务类型。在实际的a b r 业务服务中，往往通过良好 的流量控制达到拥塞控制的目的，为此，本章对a b r 业务基于速率的两种流量 控制机制，l l p _ - 进制速率反馈流量控制及显式速率反馈流量控制机制，进行了介 绍。 9 河海大学硕士学位论文第三章a b r 业务流量的p i d 拥塞控制算法研究 第三章a b r 业务流量的p i d 拥塞控制算法 研究 3 1 引言 对于显式速率拥塞控制来说，为了将p i d 控制器应用于网络流量控制，首先 应该建立一个比较准确的模型，一个模型的准确与否直接影响到控制效果的好 坏。本章就将介绍如何建立单瓶颈节点模型，并根据这个模型建立起p i d 控制所 需的p i d 控制模型，并从理论上分析这个控制模型的带宽公平分配和链路带宽利 用率。 3 2 单瓶颈节点网络模型 根据第二章的介绍，可知a t m 业务可以分为可控业务和不可控业务。对于可 控业务( a b r ) ，其优先级别要比不可控业务的优先级低，也就是说a b r 业务只能 使用高级别业务的剩余资源。充分利用带宽资源正是设置a b r 业务类型的初衷之 一a 网络传输链路的容量是有一定限度的，这也就限制了物理链路上虚连接的发 送速率。对于一条虚连接而言，在从源端到终端的传输过程中会经过若干条链路 和多个交换机，本文称将一条虚连接的发送速率限制到最小值的链路为该虚连接 的瓶颈链路或瓶颈节点。可以假设一条虚连接在传输路径上只有一个瓶颈节点。 由于源端可以根据反馈信息( r m 信元) 控$ i j a b r 信元流的发送速率，源端相 当于控制系统的执行机构。对于单瓶颈节点网络模型，参数的检测和算法的实现 主要位于交换机处，因此可以将交换机看作是检测装置和控制器。而r m 信元中 记录了表征当前网络运行状态的参数，自然就是系统的反馈环节。在控制器、执 行器即反馈信息之间存在着固有的时延，而这些时延并非固定，时延变化存在着 一定的随机性。针对上述特点，建立单瓶颈节点网络模型如图3 1 所示。 在以后的拥塞控制算法中，采用的控制算法均位于交换机处，控制的目标为： 控制队列长度g 至期望值r q 或稳定在一定的范围之内。而信元传输过程中的时 延f ，和可用带宽c 始终是影响系统性能的两个重要因素。对于该模型的离散时 滞时变描述如式( 3 1 ) 所示。 i o 河海大学硕士学位论文 第三章a b r 业务流量的p i d 拥塞控制算法研究 其中 速率调节执行机构 图3 - 1 单瓶颈节点a 1 m 网络模型 咖+ 1 ) ：s a t b ( 盯) + x t = 1 o f f ) 一”一t c ( ”) ( 3 - 1 ) x q x b1 其中 s a t b = x0 f ( r o ) - - r e h ( j r o ) ， l = o m = o g ( ) = i m h ( j w ) 。方程h ( s ) = 0 所有根落在s 左半平面( 所有根均具有负实部) 的充要条件为： 1 在区间【- 2 七万+ s ，2 七石+ 占】内，g ) 或f ( 国) 具有4 盘膨手个实数根，k 为 正整数，占为一个合适的常数。 2 对于g ( c o ) 或f ( 缈) 的每一个根6 0 f 满足f ( w a o ( a , f ) 0 ( 或 一f ( o j j ) g ( ( 0 i ) 。) 设方程a = & s i n o ) 在区间( 。，訇，( 刳的根为蛳 m 0 2 ，于是可得定理3 i 。 定理3 - l 如式( 3 3 ) 所示系统在控制器( 3 - 3 ) 作用下，闭环系统稳定的充分条件 为p i d 参数满足如下约束条件 o 口 要，0 c 一c o s 0 0 2 , o b c o o l 2 ( c o s o ) 0 l + c ) 其中口，b ，c ，c o s o ) 0 1 ，c o s ( o 为i i 面定义的参数。 证明由式( 3 - 5 ) 可知l = 2 , m = i 。 令 1 4 河海大学顽士学位论文第三章a b r 业务流量的p i d 拥塞控制算法研究 日( s ) = s 2 e 8 + a s + b + c s 2 其国) = r e h ( j e ) ) = 叫2 c o s 一c m 2 + 6 g ( 功) = i m ( j r a ) = 一c 0 2s i n a i + a c o 下面分两步证明按照定理确定参数可以满足引理3 1 的两个条件。 首先分析引理3 1 中的条件1 。 令g ( 国) = 0 ，即国( 口一m s i n t a ) = 0 ，其根由= 0 和口= a s i n c o 的根组成。若 选取o 口 至2 ，s = 三2 易知方程g ( ) = o 在区间卜2 ：t + 8 , 2 z + s 】内存在5 个根分 黜于区间 吧升b ， o ，升 升 2 以爿矾 再加上0 根 在k - - t 时，4 k i d + l = 6 ，共有6 个根由于每增加2 z 个长度，函数r o s i n 一a 过一次 零点，则对于o 口 三，k 每增j j i1 ，c o $ i n 缈与a 的交点增加4 ，即在区间 - 2 k z + s , 2 k 万十】内g ) 存在黼个实数根。因此选取o 0 由于a 0 b 0 所以 f ( 彩) g ( ) 0 ，( c o = 0 ) 由条件1的验证过程可知g ( c o ) = 0 的非零根分别位于 河海大学硕士学位论文 第三章a b r 业务流量的p i d 拥摩控制算法研究 一z 七万一万，_ 2 七万一三 ， 一z 七万一号，2 七石 ， 2 七万，z 七厅+ 三 ， 2 七石+ 詈，z 七万+ 石 内。且a = 国s i n 则 g ( m ) = 0 j 2c o s 国+ o s i n o 定义函数 g ( c o ) = e o s i n c o - a 显然g ( c o ) 为朐偶幽数，g ( 国) = 0 的根具有对称性，因此可以只讨论位于 正半轴根的情况。 g ( m ) 的非零正根分别位于区间 2 i 石，2 七厅+ 三 ， 2 七万+ 三，2 七石+ 石 内，记为 c o k l ，a k 2 ( k = 0 ，1 ，2 ) 。 考虑t - 2 k x , 2 k n + 三 的情况 易知 g ( o ) k 1 ) = ( - o k i ( ( o k lc o s ( o k l + s i n ( o k i ) 0 定义函数 f ( o j t l ) = c o k l 2c o s0 ) t l + c 吼1 2 = ( 0 k 1 2 ( c o s a k l + c ) 由于s i i l 吼l = a 0 ，c o s m k l 0 ，p ) 似f ( c o t l ) 是吼l 的增函数进而是i 的增函 g o k l 数，f ( o j 1 ) 存在极小 直f ( c 0 0 1 ) 。f h c 0 ，6 o 下面考虑国t z 2 肋+ 三，2 切+ 疗 的情况 易得 g ( ) = 3 缈c o s 缈一m 2s i n c o + s i n d o 又吼z 2 七石+ 三，z 七万+ 万 ，且国t ： z 后万+ 三，2 七疗+ 石 ，可知 g f 1 = 3 国c o s 一国2s i n 国+ s i n 1 6 河海大学硕士学位论文 第三章a b r 业务流量的p i d 拥塞控制算法研究 即0 ( 2 ) 是钒2 的减函数，进而是七的减函数，o ( o j t 2 ) 存在极大值0 ( 国0 2 ) 。 一hc 0 0 2 2 ，疗 ，c o s i b c o = a ( 。，三) ，由图解法显而易见 o ( c o k 2 ) 0 ，( 1 2 ) 在讨论区间内是t 2 的减函数，进而是j j 的减函数，f ( c o k 2 ) 存在极大值 f ( c 0 0 2 ) 又c 0 ) 0 2 2 ( c o s o ) 0 2 + c ) ，贝0 f ( c 0 0 2 ) = 0 2 2c o s ( 0 0 2 + c 嘞2 一b 0 f ( c o k 2 ) = 珊1 2 2c o s o ) t 2 + c 嘶2 2 一b o ( 证毕) 至此得出采用式( 3 3 ) 控制器结构，取o 口