（计算机应用技术专业论文）基于主动队列管理的互联网拥塞控制算法研究.pdf

摘要 i n t e r a c t 是覆盖全球的信息基础设施之一，在当今世界发挥着巨大作用。随着互联 网规模的快速增长，不可避免的出现了拥塞现象，造成业务质量指标下降和网络资源利 用率低下等情况。i n t e r a c t 主要依赖t c p 端到端拥塞控制来避免网络拥塞，但它在很多 方面已经不能满足复杂网络中各种应用的需求，网络本身必须采取某种手段参与拥塞控 制。通过研究表明，在路由器中引入队列管理机制，可以有效地对拥塞进行监测和预防， 路由器中的拥塞控制策略主动队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 技术 已经成为一个研究热点。a q m 通过评估网络状态、预测拥塞的出现，对分组进行有目 的的丢弃，从而可以使发送端更及时地了解网络状况并调整发送速率。但现有的一些主 动队列管理算法由于缺乏系统的理论指导，在响应速度、稳定性及环境敏感性等方面仍 有缺陷。控制理论是一门相对成熟的系统理论，有诸多的方法可以借鉴到拥塞控制中来 提高拥塞控制的性能。 本课题围绕着提高拥塞控制算法的性能等问题，对拥塞控制机制进行了较全面和较 深入的研究。论文的主要工作集中于如何利用经典控制理论的知识分析和改进现有的主 动队列管理算法。主要工作概括如下： 1 分析了拥塞产生的根本原因以及目前常采用的拥塞控制机制，研究了源端算法的 四个阶段和链路算法的几种典型算法，并对各算法的性能进行了对比分析。 2 在深入研究了t c p a q m 流量控制模型的基础上，从控制理论的角度分析了主动 队列管理中的r e d 算法、p 、p i 以及p i d 控制器的实现过程。 3 针对r e d 算法的参数难以调节的问题，以r e d 算法的控制理论模型为基础，结合 不完全微分p i d 控制器，提出了一种改进的不完全微分p i d - - r e d 算法。通过仿真验证了 该算法具有良好的反应速度和鲁棒性。 4 分析了网络参数变化和大时滞对拥塞控制算法性能的影响。针对网络的时变特性 以及时间滞后性，提出了一种新的基于单神经元灰色预测p i d 控制器的主动队列管理算 法。该算法利用神经网络的自学习特性在线调节p i d 控制器的参数，并利用灰色g m ( 1 ，1 ) 预测模型在线补偿时滞对系统造成的影响。仿真表明该算法具有快速响应特性以及很好 的鲁棒性。 关键字：拥塞控制，主动队列管理，随机早期检测，p i d 控制器，单神经元 r e s e a r c ho nt h ec o n g e s t i o nc o n t r o li n c o m p u t e rn e t w o r kb a s e do na c t i v eq u e u em a n a g e m e n t k o n gy m g y i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f z h ul i a n z h a n g a s s o c i a t ep r o f z h a os h i j u n a b s t r a c t i n t e r n e th a sb e e nd e v e l o p e di n t ot h eb a s i cf o u n d a t i o no fi n f o r m a t i o ns o c i e t y a st h e r a p i dd e v e l o p m e n to fi n t e m e t , n e t w o r kc o n g e s t i o nh a sb e c o m ea l li m p o r t a n ti s s u e i n t e r n e t p r i m a r i l yd e p e n d so nt c pe n d t o e n dc o n g e s t i o nc o n t r o lt oa v o i dn e t w o r kc o n g e s t i o n b u t t c pc o u l dn o tm e e tt h ev a r i o u sd e m a n d so fe v e r ya p p l i c a t i o no nt h ec o m p l e xn e t w o r k s ot h e n e t w o r ki t s e l fs h o u l dt a k ep a r ti nt h ec o n g e s t i o na v o i d a n c ea n dc o n t r 0 1 r e c e n tr e s e a r c hh a s i n d i c a t e dt h a ti ti sm o r ee f f e c t i v e f o rd e t e c t i n ga n dp r e v e n t i n gc o n g e s t i o ni ft h er o u t e r s p e r f o r mq u e u em a n a g e m e n ts c h e m e s t h ec o n g e s t i o nc o n t r o ls t r a t e g i e si nt h er o u t e r s - - a c t i v eq u e u em a n a g e m e n th a sb e e nt h eh o t s p o td i r e c t i o n b ye v a l u a t i n gt h es t a t eo fn e t w o r k a n df o r e t e l l i n gt h ec o n g e s t i o n , a q mc a nd r o pt h ep a c k e tp u r p o s e f u l l y ，s ot h a tt h es e n d e rs i d e c a nb ei n f o r m e do ft h es t a t eo fn e t w o r ka n dt h e na d j u s ti t ss e n d i n gr a t e b u tt h e s ep r e v i o u s l y p r o p o s e da l g o r i t h m sa r eh e u r i s t i ca n dl a c ko fs y s t e m a t i ct h e o r ya n dm e t h o dt oa n a l y z ea n d d e s i g n ，a n dt h e ya r en o tp e r f e c ti nt e r m so fr e s p o n s et i m e ，s t a b i l i t ya n dr o b u s t n e s s c o n t r o l t h e o r yi saq u i t em a t u r es y s t e mt h e o r y ，a n ds o m eo fi t sm e t h o d sm a yp r o f i tt h ec o n g e s t i o n c o n t r o l ，a n de n h a n c ei t sp e r f o r m a n c e f o rt h ep u r p o s eo fi m p r o v i n gt h ep e r f o r m a n c eo fc o n g e s t i o nc o n t r o la l g o r i t h m ，t h em a i n c o n g e s t i o nc o n t r o lm e c h a n i s m sa l es t u d i e di nt h i sp a p e r a f t e rs t u d i n gt h ea q m a l g o r i t h m s t h a tp r o p o s e dp r e v i o u s l y , a n dc o m b i n e dw i t ht h ec o n t r o lt h e o r y ，t h en e wa q m a l g o r i t h m sa r e d e s i g n e d t h em a i nr e s e a r c hp o i n t si nt h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 t h ef u n d a m e n t a lr e a s o n so fc o n g e s t i o na n dc o n g e s t i o nc o n t r o lm e c h a n i s mt h a tu s e d m o r er e c e n t l ya l ea n a l y z e d t h ef o u rp h a s e so fs o u r c ee n da l g o r i t h ma n ds o m et y p i c a l a l g o r i t h m so ft h el i n ka l g o r i t h ma r es t u d i e d ，a n da l s ot h ep e r f o r m a n c e so fe v e r ya l g o r i t h ma r e a n a l y z e d 2 o nt h ed e e p l ys t u d yo ft c p a q mf l o wm o d e l ，t h ea c h i e v e m e n tp r o c e s s e so fr e d ，p ， p i ，p i d ，e t c a l ea n a l y z e df r o mt h ea n g l eo fc o n t r o lt h e o r y , a n dt h ep e r f o r m a n c e so fe v e r y a l g o r i t h mk r ea n a l y z e d 3 f o rt h ep a r a m e t e ro fr e di sd i f f i c u l tt ob er e g u l a t e d ，an e wi n c o m p l e t i o nd i f f e r e n t i a l p i d r e dh a sb e e np r o p o s e dt os o l v et h ep r o b l e m ，a n di t sp e r f o r m a n c eo fr o b u s t n e s sh a sb e e n v e r i f i e dt ob eb e t t e rt h a nr e da n dp ia l g o r i t h m s 4 t h o u g ht h el a r g ed e l a yh a si m p a c tt h ep e r f o r m a n c eo ft h en e t w o r k ，a l m o s ta l lt h e e x i s t e da l g o r i t h m sn e g l e c tt h el a r g ed e l a y , f o re x a m p l er e d ，p ia l g o r i t h m sa l ln e g l e c tt h i s i m p a c t i nt h i ss t u d y , an e wa q ma l g o r i t h m - s n g m p i di sp r o p o s e dw h i c hi sb a s e do nt h e c o m b i n a t i o no fn e u r a ln e t w o r ka n dg r a yp r e d i c t i o n i nt h i sn e wa l g o r i t h m ，t h es e l f - s t u d ya n d s e l f - a d a p t i v ec h a r a c t e r i s t i co fn e u r a ln e t w o r ki su s e dt ot u n et h ep a r a m e t e ro fp i dc o n t r o l l e r , a n dt h eg r a yp r e d i c t o ri su s e dt oc o m p e n s a t et h ei m p a c tp r o d u c e db yt h ed e l a y f i n a l l yt h e p e r f o r m a n c e si nq u e u el e n g t hs t a b i l i t ya n dr o b u s t n e s sw e r es i m u l a t e db yt h es i m u l a t o r , a n d t h er e s u l t sh a v eb e e ns t u d i e da n da n a l y z e d ，a n dt h en e wa l g o r i t h mi sv e r i f i e dt ob eb e t t e rt h a n t h er e da n dp ia l g o r i t h m s k e y w o r d s ：c o n g e s t i o nc o n t r o l ，a c t i v eq u e u em a n a g e m e n t ，r a n d o me a r l yd e t e c t i o n ，p i d c o n t r o l l e r ，s i n g l en e u r o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 o t 矗 学位论文作者签名：纽毖至：日期：刀, o o o 年i - 月影e t 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：垫五磊： 指导教师签名：楚鱼鑫二埤 i t 期：加弼年 日期：冲 f 月“日 厂月日 中国石油大学( 华东) 硕士学位论文 1 1 课题的研究背景及意义 第一章绪论 i n t e m e t 主要互联协议t c p i p 的拥塞控制机制( c o n g e s t i o nc o n t r 0 1 ) 对于控制拥塞具 有特别重要的意义。目前在i n t e r a c t 上使用的基本上是建立在t c p 窗口控制基础之上的端 到端的拥塞控制，即源端通过对网络当前状态的感知与探测来相应调整控制发送分组的 窗口大小。但这种拥塞控制不提供任何服务质量( q u a l i t yo fs e r v i c e ，q o s ) 保证，故往 往会导致过高的传输时延和分组丢失率，因此它的作用是有限的。增强中间节点( 路由 器) 的功能是一种有效的手段。此外，中间节点上的队列管理也严重影响着t c p 的性能， 例如，不恰当的队列管理算法可能造成t c p 连接的全局同步、队列长时间处于满状态、 处理突发业务时存在公平性问题。中间节点上的主动队列管理( a c t i v eq u e u e m a n a g e m e n t ，a q m ) 策略利用网络节点提供的标准网络应用编程接1 ：3 ，向用户提供一个 “开放”的网络控制机制，可以使网络具备强大的处理能力，在保证较高吞吐量的基础 上有效地控制队列长度，从而实现了控制端到端的时延、保证q o s 的目的。因此，主动 队列管理策略已经成为拥塞控制中的一个研究热点。但主动队列管理的一些主要算法如 随机早期检测算法( r a n d o me a r l yd e t e c t i o n ，r e d ) ，虽然在网络拥塞控制中获得了很 大的成功，但仍存在很多缺陷：算法的性能敏感于设计参数和网络状况，在特定的网络 负载状况下依然会导致多个t c p 的同步，造成队列震荡、吞吐量降低和时延抖动加剧； r e d 算法的公平性和稳定性也存在问题；r e d 算法的改进工作在很大程度上是依赖于直 觉的、启发性的，并且是针对局部个别问题的，没有系统的理论作为分析和设计的依据。 因此i n t e r a c t 的稳定发展需要更好地理解拥塞控制机制并不断加以改进。 控制理论作为分析和设计复杂系统强有力的工具，已经被广泛应用于管理、经济等 行业。一些科研人员也尝试将控制理论引入到拥塞控制中来。从控制理论的角度看， i n t e r a c t 是一个极其复杂的巨型系统，由于其网络结构复杂、规模巨大、应用种类繁多且 不断演化，网络用户数随时变化且不时发生各种随机性故障等，这使得对i n t e m e t 建模极 其困难。尽管如此，人们还是在利用控制理论与优化理论分析现有拥塞控制的稳态与动 态性能以及设计新的拥塞控制算法方面做了大量的工作，提出了利用p i 、p i d 等经典控 制器作为新的a q m 方案，且取得了一定的效果。但由于拥塞控制算法的分布性、网络 的复杂性，到目前为止，拥塞问题还没有得到很好的解决。应用控制理论来解决拥塞控 第一章绪论 制问题，是一个不同以往的全新的课题，具有相当深远的理论意义和实用价值。 1 2 国内外研究现状 n a 皿e 于19 8 4 年发表了第一篇关于拥塞控制方面的文章【l 】，随后，j a c o b s o n 等学者便 投入到网络拥塞控制的研究中【2 1 。时至今日，网络拥塞控制的研究已经涵盖了计算机网 络各个方面。 目前在i n t e r a c t 上使用的拥塞控制机制主要是建立在t c p 基于窗口的端到端拥塞控 制基础上的，它对i n t e m e t 的稳定性和鲁棒性具有重要的作用。然而，随着i n t e m e t 本身的 迅速发展，其网络规模越来越大，结构日趋复杂，仅仅依靠端到端的拥塞控制是不够的。 事实上在i n t e m e t 这样复杂的异构系统中，不能指望所有用户在i n t e r n e t 应用中兼容这种 端到端的拥塞控制，网络必须参与资源的控制工作。当前在路由器中使用的队列管理算 法可以分为两大类：被动式队列管理( p a s s i v eq u e u em a n a g e m e m ，p q m ) 和主动式队列 管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 。 “去尾 ( d r o p t a i l ) 算法是被动式队列管理的代表算法。基本思想是对每个队列 设置一个极限值( 以包为单位) ，然后接受包进入队列直到队长达到极限值，接下来到 达的包就要被拒绝进入队列，直到队长下降。d r o p t a i l 算法的优点是简单，容易扩展； 缺点是由于满队列后才进行丢包，容易造成队列死锁，进而导致“t c p 全局同步，降 低网络利用率。 主动队列管理一直是一个很活跃的研究领域，在过去的几年中相继产生了许多 a q m 算法。i 扫f l o y d 和j a c o b s o n 在1 9 9 3 年提出的r e d ( r a n d o me a r l yd e t e c t i o n ) 算法【3 l 是最早的主动队列管理算法，也是目前最常用的a q m 算法。其基本思想是路由器通过 监控队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择源端来通知拥塞， 使它们在队列溢出之前降低发送数据速率，以缓解网络拥塞。 但r e d 算法的性能敏感于设计参数和网络状况，在特定的网络负载状况下依然会导 致多个t c p 的同步，造成队列震荡、吞吐量降低和时延抖动加剧。r e d 算法在公平性和 稳定性方面也存在问题。随后国内外专家围绕r e d 算法本身展开了许多研究工作，大多 数的工作都试图完善和改进r e d 存在的缺陷，出现了不少r e d 的派生算法，较有影响力 的有a r e d t 4 ，s r e d 5 1 ，n e wa r e d t 6 1 ，b l u e t 7 1 ，a v q t 钔，r e m t g l 等。它们中的大多数 研究工作在很大程度上是依赖于直觉的、启发性的，并且是针对局部个别问题的，没有 系统的理论作为分析和设计的依据。 2 中国石油大学( 华东) 硕士学位论文 最近几年，人们在利用控制理论分析现有拥塞控制机制的稳态和动态性能以及设计 新的拥塞控制算法等方面做了大量的工作，取得了一定的进展。这方面研究的突破是 m i s r a 等提出的t c p a q m 的微分方程模型【1 0 1 ，如图1 1 。在此模型的基础上，可以将 i n t c r n e t 源端、队列长度以及延时回路的组合视为控制对象，主动队列管理a q m 作为控 制器，可以运用反馈控制理论设计a q m 控制器，并对闭环系统进行性能分析。 f e e d b a c k 图1 - 1t c p 拥塞控制与a q m 算法组成的反馈控制模型 f i g1 - 1 f e e d b a c kc o n t r o lm o d e lo ft c p a q m 2 0 0 1 年，h o l l o t 等人用小信号理论对m i s m 给出的t c p 流量控制模型进行线性化处 理后【】，用经典控制理论分析了r e d 算法的稳定性，并证明了采用r e d 控制的系统稳 定时控制器参数所要满足的条件。清华大学的任丰原等利用非线性控制理论中的描述函 数分析方法分析了r e d 算法的工作特性【1 2 1 。r e d 的控制理论分析揭示了r e d 的两个 局限性：首先是响应速度与稳定裕度之间的矛盾，即较快的响应速度将导致较小的稳定 裕度，而较大的稳定裕度又意味着较慢的响应速度；其次是r e d 的排队长度与丢失概 率具有直接的关联性，当网络超载时，会同时发生高时延和高丢失率。在随后的研究中， h o l l o t 将a q m 算法的设计问题转化为控制理论中典型的调节器设计问题，并提出了一 种用于主动队列管理的p i ( p r o p o t i o n a li n t e g r a l ) 控制器1 1 3 1 。但这种控制器在时变的网络 环境中很难确切地得到系统的临界放大倍数和临界震荡周期，无法整定其参数，因此被 迫使用了试凑方法。清华大学的任丰原等人在2 0 0 3 年又改进了p i 控制器，设计出了用 于主动队列管理的p i d 控制器【l 引，并给出了基于稳定裕度的参数整定方法。这些静态的 控制器虽然在某些情况下都可以达到满意的暂态响应( 较小的上升时间、较小的下降时 间、较小的超调) 以及较小的稳态误差，但是当网络条件变化时，算法性能急剧下降。 鲁棒控制理论在网络拥塞控制中也得到了应用。2 0 0 2 年，h o l l o t 等人将线性化控制 对象中的高频动态分解出来作为系统的不确定动态，运用小增益原理给出了鲁棒p i 控 制器的设计1 1 5 l 。任丰原等人又在非线性源端模型基础上，基于变结构控制的设计思想提 3 第一章绪论 出了一种新的鲁棒主动队列控制器的设计【l6 1 ，但它并没有考虑时延的影响。随后一些控 制理论专家提出自校正方案来改善p i d 在网络条件变化下的性能。这些方案采用在线算 法来估计网络的参数，将这些参数作为真实值来调节控制器的参数。上述自适应的方案 大大地改善了系统的性能，但同时也很费时，并且增加了系统的复杂性。 为了克服大时滞对队列稳定性造成的不利影响，2 0 0 5 年m a s c o l o 基于经典控制中的p ( p r o p o r t i o n a l ) 调节器和s m i t h 原理设计了一个稳定的拥塞控制算法【1 7 】。传输延时是网 络拥塞控制必须考虑的一个重要因素，而s m i t h 预测器则是用于大延时过程的一个典型 的补偿器，其优点是将时延系统设计问题转化为无时延系统的设计问题。华南理工大学 的向少华等人又在m a s c o l o 的基础上提出t s m i t h p i 算法【l 引。这种算法结构简单，易于配 置，具有良好的鲁棒性和网络控制性能，同时也克服了大时滞给队列稳定性造成的不利 影响。 随着智能控制理论的发展，近几年智能控制理论在网络拥塞控制中的应用取得了很 大的进展。智能控制技术主要包括神经网络、模糊逻辑控制等几个较成熟的方法体系。 人们从不同的方面将智能控制技术应用于网络控制中。任丰原等人采用模糊推理技术设 计了a q m 控制器【l9 】。东北大学的控制理论专家井元伟等提出了基于模糊滑模控制的主 动队列管理算法【2 们。由于模糊控制不需要精确的数学模型，因此这些方法适于动态的网 络流量。针对r e d 参数难于构造的特点，w a n gc h o n g g a n g 等人设计了一种基于自适应模 糊控制的a q m 算法( a f r e d ) 2 1 】，它的重要特征是通过自适应机制来动态的调节模糊 规则，使之在动态网络环境下保证系统稳定。 近年来对局域网和广域网的分析研究表明，网络的流量普遍存在自相似性或长相关 性，而目前已有的主动队列管理算法都是以经典的网络模型中所描述的短相关性流量为 研究背景。自相似模型的引入以及自相似的普遍存在性给目前的主动队列管理算法带来 了新的困难。现在已有一些控制理论专家开始研究新的控制算法。东南大学的吴清亮等 人在这方面做了研究并提出了基于预澳l j p i 控制器的自相似主动队列管理算法【2 2 1 。北京邮 电大学的温昱晖等人提出了一种替代i 也d 的主动队列管理算法【捌：信号能量的小波分解 ( w a v e l e t d e c o m p o s e ds i g n a le n e r g y ，w d s e ) 算法。但自相似性的发现使对网络流量的 认识与过去存在很大的不同，而对具有自相似性的网络流量进行流量管理和应用，也同 样需要进行新的探讨和分析，目前这还只是刚刚开始，在网络流量自相似性的问题上还 有很多工作需要去完成。 各种基于路由器的拥塞控制算法虽然在定程度上使系统的性能得到了改善，但由 4 中国石油大学( 华东) 硕士学位论文 于网络所处的复杂环境以及新的应用不断出现，网络的拥塞问题并没有根本解决，这就 需要不断研究新的拥塞控制算法以进一步提高网络性能。 1 3 论文的研究内容 怎样有效地避免拥塞已经成为网络中影响系统性能的一个基本问题。由于网络中存 在时滞以及各种突发业务流，使得源端不能及时地获取最新的网络信息，导致网络流量 不能控制在实际网络状况应有的流量上。而就拥塞控制而言，网络中间节点有可能更及 时，甚至提前准确了解网络的拥塞状态，并依此实施有效的资源管理策略，使网络能有 效地避免拥塞，或尽早从严重的拥塞状态中恢复过来。而传统的控制方法是基于直接推 断的，没有很好的理论知识指导，有很大的随机性和人为因素，控制效果不好。面对日 益复杂的网络环境，利用经典控制理论的有关知识解决拥塞问题，是一个十分有价值的 研究课题，也是当前研究的一个热点。本文以控制理论为基础，研究了拥塞控制中的主 动队列管理策略。研究内容主要包括以下几个方面： 1 研究了t c p a q m 流量控制模型，并在此基础上从控制理论的角度分析了r e d 、 p 、p i 以及p i d 等算法的实现过程。 2 为了提高r e d 算法的鲁棒性，解决传统的r e d 算法参数难以调节的问题，利用 控制理论中的不完全微分p i d 控制器调节r e d 算法中的最大丢弃概率，通过仿真验证 了改进算法的鲁棒性。 3 针对网络的时变特性以及大时滞现象，提出了一种新的基于单神经元灰色p i d 控 制的主动队列管理算法。该算法将人工神经网络和灰色预测相结合，利用神经网络的自 学习特性在线调节控制器的参数，并通过反馈回路中的灰色预测补偿时滞对系统造成的 影响。仿真结果表明该算法具有很好的鲁棒性。 1 4 论文的组织结构 本文的主要工作围绕着如何利用经典控制器改进现有的主动队列管理算法，提高拥 塞控制效果进行深入研究的，论文章节内容安排如下： 第一章主要介绍了拥塞控制的研究背景和意义、国内外研究现状，并对本论文的主 要研究工作和论文组织结构进行了说明。 第二章主要介绍互联网网络拥塞的概念及拥塞产生的原因，分析了拥塞控制的基本 机制，对t c p 拥塞控制源算法和链路算法逐一进行了讨论。 第一章绪论 第三章研究分析了t c p a q m 流量控制模型的建立过程，并在此基础上从控制理论 的角度研究了r e d 算法、p 、p i 以及p i d 控制器等几种主要的主动队列管理算法的设 计问题。 第四章针对随机早期检测算法的参数难以调节的问题，将不完全微分p i d 控制器与 r e d 算法相结合，利用不完全微分p i d 控制器在线调节r e d 算法的最大丢弃概率， 在t c p a q m 控制理论模型中分析了这种算法的有效性，并通过仿真验证了该算法的鲁 棒性。 第五章针对大时滞现象以及网络的时变特性，结合人工神经网络和灰色预测提出了 一种基于单神经元灰色p i d 控制的主动队列管理算法，通过仿真验证了该算法具有很好 的响应性能和鲁棒性。 文章最后总结全文，并展望未来的研究工作。 6 中国石油大学( 华东) 硕士学位论文 第二章互联网拥塞控制概述 本章的内容主要是在分析拥塞产生原因的基础上来研究互联网拥塞控制算法，从终 端控制策略和网络中间节点控制策略两个角度展开。着重研究了端到端的t c p 拥塞控制 机制和i p 层的拥塞控制机制，分析并介绍了各种算法及其改进算法的性能。 2 1 拥塞概念及其产生的原因 i n t e m e t 自出现以来得到了蓬勃发展，近年来更以惊人的速度发展，同时网络环境也 变得越来越复杂，现有的带宽总难以完全满足用户的要求，产生网络拥塞是在所难免的， 这一问题从8 0 年代中期就得到了学术界和工业界的广泛重视。 拥塞( c o n g e s t i o n ) 是一种持续过载的网络状态，它指的是当网络中存在过多报文 时，网络性能降低的情形【2 】。此时用户对网络资源( 包括链路带宽、存储空间和处理器 能力等) 的需求超过了其固有的容量。 拥塞导致的直接结果是分组丢失率提高，端到端的时延加大，甚至有可能使整个系 统发生崩溃。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效吞吐量急 剧下降。因此，拥塞现象是任何网络都应该极力避免的。 网络产生拥塞的根本原因在于用户( 或叫端系统) 提供给网络的负载大于网络的资 源容量和处理能力，网络能够提供的资源不足以满足用户的需求，这些资源包括缓存空 间、链路带宽容量和中间节点的处理能力。表现为数据包延时增加、丢弃概率增大、上 层应用系统性能下降。拥塞产生的直接原因主要有以下四点【1 4 l ： ( 1 ) 存储空间不足 几个输入数据流共同需要同一个输出端口，在这个端口就会建立排队。如果没有足 够的存储空间存储，数据包就会被丢弃，对突发数据流更是如此。增加存储空间在某种 程度上可以缓解这一矛盾，但如果路由器有无限存储量时，拥塞只会变得更坏。因为数 据包在网络里经过长时间排队完成转发时，它们早己超时，源端认为它们己经被丢弃， 而这些数据包还会继续向下一路由器转发，从而浪费网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足 低速链路对高速数据流的输入也会产生拥塞。根据香农信息理论，任何信道带宽最 大值即为信道容量，c = b l o g ：( 1 + ) ，( n 为信道白噪声的平均功率，s 为信源的平均 7 第二章互联网拥塞控制概述 功率，b 为信道带宽) 。所有信源发送的速率r 必须小于或等于信道容量c 。如果r c ， 则在理论上无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其 满足不了通过它的所有源端带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱 如果路由器的c p u 在执行排队缓存，更新路由表等功能时，处理速度跟不上高速链 路，也会产生拥塞。同样，低速链路对高速c p u 也会产生拥塞。 ( 4 ) t c p i p 协议拥塞控制机制中的缺陷 t c p 基于窗口的拥塞控制机制对于i n t e r a c t 的鲁棒性起到了关键性的作用，但其本质 上是端到端的拥塞控制机制，存在较大的延时和滞后性。另一方面，基于u d p 的应用在 i n t e m e t 中所占的比例正在增加( 如视频点播和i p 电话) ，而u d p 数据流在网络拥塞发生 时，不会像t c p 那样减少向网络发送的数据量，导致了网络资源分配的严重不公平性。 因此，拥塞问题己严重影响网络的安全。要避免拥塞的发生，对以上四点原因需综 合考虑。例如，提高链路速率而不改变处理器，只会转移网络瓶颈，而不能避免拥塞。 所以拥塞往往也是系统各部分不匹配的结果。拥塞一旦发生往往会形成一个不断加重的 过程。如果路由器没有空余的缓存，它就必须丢弃新到的数据包。当数据包丢弃时，源 端会超时，重传该包。由于没有得到确认，源端只能保留数据包，结果缓存会进一步消 耗，加重拥塞。 2 2 拥塞控制算法的分类 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大类【2 4 】。当流量 特征可以准确规定、性能要求可以事先获得时，适于使用开环控制；当流量特征不能准 确描述或者当系统不提供资源预留时，适于使用闭环控制。i n t e m e t 中主要采用闭环控 制方式，以动态地适应网络的变化。 闭环的拥塞控制分为以下三个阶段【2 5 】：检测网络中拥塞的发生；将拥塞信息报告到 拥塞控制点；拥塞控制点根据拥塞信息进行调整以消除拥塞。闭环的拥塞控制可以动态 地适应网络的变化，但算法性能受到反馈延迟的严重影响阱】。当拥塞发生点和控制点之 间的延迟很大时，算法性能会严重下降。 根据算法的实现位置，可以将拥塞控制算法分为两大类：源算法( s o u r c ea l g o r i t h m ) 和链路算法( 1 i n ka l g o r i t h m ) 2 6 1 。源算法在主机和网络边缘设备中执行，作用是根据反 馈信息调整发送速率。链路算法在网络设备( 如路由器和交换机) 中执行，作用是检测 8 中国石油大学( 华东) 硕士学位论文 网络拥塞的发生，产生拥塞反馈信息。拥塞控制算法设计的关键是如何生成反馈信息和 如何对反馈信息进行响应。 源算法中使用最广泛的是t c p 协议中的拥塞控制算法。t c p 是目前在i n t e m e t 中使 用最广泛的传输协议。根据m c i 的统计，总字节数的9 5 和总报文数的9 0 使用t c p 传输口7 1 。近年来，t c p 中采用了很多新的算法，包括慢启动( s l o ws t a r t ) 、拥塞避免、 快速重传( f a s tr e t r a n s m i t ) 、快速恢复( f a s tr e c o v e r y ) 、选择性应答( s a c k ) 等，大大 提高了网络传输的性能。t c p 中使用的拥塞控制算法已经成为保证i n t e r n e t 稳定性的重 要因素。 链路算法的研究目前集中在“主动队列管理 ( a c t i v eq u e u em a n a g e m e n t ，简称 a q m ) 算法方面。和传统的“队尾丢弃 ( d r o pt a i l ) 相比，a q m 在网络设备的缓冲 溢出之前就丢弃或标记报文t 2 9 1 。a q m 有以下优势【3 0 1 ： ( 1 ) 减少网关的报文丢失。使用a q m 可以保持较小的队列长度，从而增强网络 中间节点容纳突发流量的能力。 ( 2 ) 减小报文通过网关的延迟。减小平均队列长度可以有效地减小报文在网络设 备中的排队延迟。 ( 3 ) 避免l o c k - o u t 行为【3 1 1 的发生。 a q m 的一个代表是r e d 算法( r a n d o me a r l yd e t e c t i o n ) 【3 1 。研究表明，r e d 算法 比d r o p t a i l 具有更好的性能。在r f c 2 3 0 9 中，强烈推荐使用r e d 作为今后的标准。但 是进一步的研究发现，r e d 算法的性能对算法的参数设置十分敏感，至今没有在i n t e m e t 中得到广泛使用。下面分别介绍几种典型的源端算法和链路算法。 2 3 拥塞控制的源算法 在i n t e r a c t 设计的初期，对于拥塞的控制是通过传输控制协议( t r a n s m i s s i o nc o n t r o l p r o t o c o l ，t c p ) 中端到端基于滑动窗口的流量控制完成的。t c p 拥塞控制( 及其变化形 式) 是一种基于滑动窗口协议的算法，通过调节发送端向网络传输数据的速度来达到控 制拥塞的目的。t c p 端到端的拥塞控制机制是确保i n t e m e t 鲁棒性( r o b u s t n e s s ) 的重要 因素。在发生拥塞时，t c p 源端会降低发送数据的速率，使得拥塞的程度得以减轻以至 于消失，从而使得大量的t c p 连接能够共享一条拥塞的链路。 9 第二章互联网拥塞控制概述 2 3 1t c p 拥塞控制的四个阶段 1 9 8 8 年，v a nj a c o b s o n 在文献【2 】中指出了t c p 在控制网络拥塞方面的不足，并相 继提出了“慢启动( s l o ws t a r t ) 算法、“拥塞避免 ( c o n g e s t i o na v o i d a n c e ) 算法、 “快速重传”( f a s tr e t r a n s m i t ) 和“快速恢复 ( f a s tr e c o v e r y ) 算法。t c p 拥塞控制算 法便是由这四个核心算法构成。其中包含的主要参数如表2 1 所示3 0 1 。 表2 - 1t c p 拥塞控制算法的主要参数 t a b l e2 - 1m a i np a r a m e t e r so f t c p c o n g e s t i o nc o n t r o la l g o r i t h m 拥塞控制的关键参数。它描述了源端在拥塞控制情况下一 拥塞窗口( c w n d ) 次最多能发送数据包的数量。 接收端给源端预设的发送窗口大小，它只在t c p 连接建 通告窗口( a w i n ) 立的初始阶段起作用。 发送窗口( w i n )源端每次实际发送数据的窗口大小。 慢启动阈值( s s t h r e s h )拥塞控制中慢启动阶段和拥塞避免阶段的分界点。 一个t c p 数据包从源端发送到接收端，源端收到接收端 回路响应时间( r t t ) 确认得时间间隔。 描述数据包从发送到失效的时间间隔，是判断数据包丢失 超时重传计数器( r 1 r o ) 与否、网络是否拥塞的重要参数。通常设为2 r t i 或5 r t t 。 能触发快速重传的源端收到重复确认包a c k 的个数。当 快速重传阈值 此个数超过t e p r e x m t t h r e s h 时，网络就进入快速重传阶段。 ( t c p r e x m t t h r e s h ) t c p r e x m t t h r e s h 缺省值为3 。 ( 1 ) 慢启动阶段 当启动一个t c p 连接或者经过一定时间拥塞后恢复t c p 连接传输数据时，源端向网 络发送许多分组，中间节点必须将其保留于缓存之中，这样就有可能耗尽存储空间，从 而导致网络吞吐量( t h r o u g h p u t ) 急剧下降。慢启动机制即是为了避免此现象的发生。 初始化时，c w n d 为l ，t c p 发送端按照c w n d 大小来发送数据，以后每收到一个来自接 收端的a c k 确认，c w n d 的值就随指数增加，一直加到某个最大值为止。借助慢启动机 制，t c p 发送端可以有效地检测网络负载情况，确保不会盲目地向已经出现拥塞的网络 继续发送分组。 ( 2 ) 拥塞避免阶段 l o 中国石油大学( 华东) 硕士学位论文 当网络通信量超过其承受能力时，网络将发生拥塞。一旦探测到拥塞超时，进入拥 塞避免阶段。将慢启动域值( s s t h r e s h ) 设置为当前c w n d 的一半。然后，置c w n d = 1 ， 重新进入慢启动过程，直到c w n d = s s t h r e s h 。在该阶段，c w n d 每收到一个确认字段有 效( a c k ) 就加l 。当c w n d s s t h