（计算机应用技术专业论文）网络路由排队算法研究及其仿真实现.pdf

哈尔滨工程大学硕士学位论文 摘要 随着互联网的飞速发展，网络拥塞已经成为非常重要的问题。拥塞控制 的目的就是采用一定的控制机制，在即保证达到一定吞吐量的前提下，能够 提高网络的利用率，并能避免拥塞，保证网络的畅通。 网络仿真软件是进行网络性能分析，评估网络设计方案，网络故障诊及 检测拥塞控制算法有效性的常用方法，随着网络规模的增大，各种网络设计 方案、协议和路由算法日趋复杂，仿真技术在现代通信网络设计中的作用越 来越大。 主动队列管理算法是近几年网络拥塞控制研究的重点，为了改进和完善 现有的a o m 算法及设计出更好的新算法，需要对主动队列管理机制进行深入 研究。n s 2 作为开源软件，缺少对改进算法和新研究算法的模拟能力，在现 有软件基础上对其进行功能扩展是模拟研究改进算法和新理论的基础。本文 主要探讨网络仿真软件n s 2 的功能扩展原理及设计实现，主要针对r e d 算法 在包管理上的不足，提出了一种改进的r e d 算法一p r e d ( p a c k e t s i z e o n r a n d o me a r l yd e t e c t i o n ) ，并在n s 22 2 8 中实现p r e d 算法，p r e d 算法利 用平均数据包大小p a v 。和即将进入队列的数据包大小p 。，这两个参数，确定丢 包概率，达到缓解网络拥塞的目的；并使用网络仿真软件对r e d 算法、 d r o p t a i l 算法和p r e d 算法在网络吞吐率、丢包率及抖动时延等方面进行性 能对比分析。 关键词：主动队列管理算法：拥塞控制；p r e d ； n s 2 a b s t r a c 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 l i m p o r t a n ti s s u e w i t ht h e r a p i d d e v e l o p m e n to ft h ei n t e r n e t t h eg o a lo fc o n g e s t i o nc o n t r o li s t oe n s u r eg a i n i n g c e r t a i nt h r o u g h o u tt oi n 口e a s et h eu s co fb a n d w i d t h , t oa v o i dc o n g e s t i o nc o l l a p s e b yt a k i n gc e r t a i nc o n t r o lm e c h a n i s m n e t w o r ks i m u l a t i o ni saw i d e l y - n s e dw a yf o r d e s i g n i n g n e t w o r ka n d e v a l u a t i n gt h ep e r f o r m a n c eo fn e t w o r k , a n dv a l i d a t i n gt h ee f f e c t i v e n e s so f c o n g e s t i o nc o n t r o la l g r i t h m s s i m u l a t i o ni sp l a y i n gt h em o r ea n dm o r ei m p o r t a n t r o l ei n d e s i g n i n gm o d e r nt e l e c o m m u n i c a t i o nn e t w o r kd u et oi n c r e a s i n go f c o m p l e x i t y , s c a l eo fn e t w o r k s a c t i v eq u e u em a n a g e m e n ta l g o r i t h mi st h ek e y s t o n eo nn e t w o r kr e s e a r c h a b o u tc o n g e s t i o nc o n t r o li nr e c e n ty e a r s f o ri m p r o v i n gt h ea q m a l g o r i t h m sa n d d e s i g nn e wa l g o r i t h m s ，r e s e a r c h e r sn e e dt os t u d yt h ea q md e e p l y n s 2 ( n e t w o r k s i m u l a t o rv e r s i o n2 ) a so p e ns o u r c es o f t w a r e ，i tl a c k st h ea b i l i t yt os i m u l a t es o m e i m p r o v e da l g o r i t h m sa n dl a t e s td e v e l o p e da l g o r i t h m s t h i sl e a d st ot h e r e q u i r e m e n to ft h ef u n c t i o n a le x t e n s i o no ft h ec u r r e n tv e r s i o n t h i sp a p e rf o c u s e s o nt h ed e s c r i p t i o no ft h ee x t e n s i o np r i n c i p l ea n di m p l e m e n t a t i o nd e t a i l so fn s 2 a n dd e v e l o p sa ne n h a n c e dr e dm c t h o d - p r e d ( p a c k e t _ s i z eo nr a n d o m e a r l yd e t e c t i o n ) i nn s 22 2 8 ，w h i c hf o r c u so nt h ed e f i c i e n c yo fr e da l g o r i t h m i np a c k a g em a n a g e t h em a i ng o a lo fp r e d a l g o r i t h mi st oc o n g e s t i o na v o i d a n c e b yc a l c u l a t et h ed r o p p i n gp r o b a b i l i t yw i t ht w op a r a m e t e r s ：p 押gi st h es i z eo f a v e r a g ep a c k e t sa n d i st h es i z eo fi n c o m i n gp a c k e t a n da l s oa n a l y s i st h e p e r f o r m a n c eo fr e d 、d r o pt a i la n dp r e da b o u tn e t w o r kt h o u g h p u t 、d r o p p e d p a c k e tr a t i oa n dj i t t e r k e y w o r d s ：a c t i v eq u e u em a n a g e m e n ta l g o r i t h m ；c o n g e s t i o nc o n t r o l ；p a c k e t _ s i z e o nr a n d o m e a r l yd e t e c t i o n ；n e t w o r ks i m u l a t o rv e r s i o n2 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：查叠整 日期：浒舌月心日 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 从上世纪6 0 年代的a r p n e t 开始试验并投入使用以来，网络就以其其它工 具无法比拟的优越性迅速地发展起来。近年来，网络用户的数量迅速增长， 导致网络中通信流量的急剧增加，据统计至u 2 0 0 7 年1 月，全球1 5 岁及以上使用 互联网的人数达到了7 4 7 亿，同比增长1 0 。而且现在的i n t e r n e t 己由以往 的单一数据传送网发展成传送数据、语音、视频等多媒体信息的宽带综合业 务网。因此基于i n t e r n e t 的数据流剧增造成网络性能的下降，使得越来越严 重的网络拥塞问题逐渐暴露出来。解决网络拥塞问题也就成为i n t e r n e t 网络 发展中必须面临的问题。 在计算机通信网络中，拥塞容易造成延迟、延迟抖动和丢包等服务质量 ( q o s ：q u a l i t yo fs e r v i c e ) 性能指标下降，是影响带宽、缓存、吞吐量等 网络资源利用率的关键因素，因此有效解决拥塞问题对于提高网络性能具有 重要意义。网络产生拥塞的根本原因是用户提供给网络的负载大于网络资 源容量和处理能力，在i n t e r n e t 中，存储空间不足、通信信道带宽容量不 足、处理机处理能力较弱等都是产生拥塞现象的直接原因m ，但是无论增加 缓存容量或是提高处理器及链路的速度都不能从根本上解决问题，相反，某 些情况下甚至可能会进一步加剧拥塞。网络中发生拥塞后如果不加以控制， 往往会导致恶性循环，这时如果路由器没有空余的缓存空间，它就必须丢掉 新到的数据包，当数据包丢弃时，源端可能会因为超时而重传此包，由于源 端在未收到确认之前不能丢弃数据包。相应的缓存不能释放，使缓存进一步 消耗，导致拥塞加重，在网络流量非常高的情况下，网络甚至会完全瘫痪， 几乎没有数据包能够送达接收方。网络拥塞已经成为制约网络发展和应用的 一个瓶颈，如何更好的预防和控制拥塞一直是近年来网络研究的热点问题。 拥塞控制的主要目标是控制进入网络的数据流量，保证通信予网不会被 哈尔滨工程大学硕士学位论文 用户发送的数据流淹没，合理地使用瓶颈资源。直观上，解决网络拥塞可以 从两方面入手，一是拥塞避免，即尽量避免拥塞的发生，是网络运行的最佳 状态；二是在拥塞发生后采取补救措施消除拥塞。完全避免网络拥塞必然会 以牺牲网络的资源利用率为代价，在追求公平、高效、高利用率的网络环境 下，采取这种保守的方法显然是不适宜的，因此，采用拥塞避免与拥塞控制 相结合的方法更为合理。拥塞控制策略主要由反馈机制和控制机制两个部分 组成，网络通过反馈机制向源端或目的端通告它的当前状态，端系统则根据 接收到的反馈信息，利用控制机制完成对负载的调整，达到缓解拥塞的目的。 1 2 国内外研究现状 目前拥塞控制的研究主要分为n ，： ( 1 ) 从控制论的角度出发，拥塞控制算法可以分为开环控$ 1 ( o p e n l o o p ) 和闭环控制( c l o s e d l o o p ) 两大类“1 。当流量的特征可以准确规定、性能要 求可以事先获得时，适于使用开环控制。开环控制的典型例子是就是资源预 留( r s v p 协议) 。这种方法虽然是一种很直接的控制拥塞的方法，但由于实 现确定精确的业务特征几乎不可能，因此为保证服务质量、避免拥塞，往往 需要预留多余的网络资源( o v e r p r o v i s i o n ) ，很容易造成网络资源利用率下 降。当流量特征不能准确描述或者当系统不提供资源预留时，适用于使用闭 环控制。闭环的拥塞控制建立在反馈环路的概念上，它首先检测网络中拥塞 的发生，然后将拥塞信息传递到拥塞控制点，最后拥塞控制点根据拥塞信息 进行调整，以消除拥塞。闭环的抑塞控制可以动态适应网络的变化，但是它 的一个缺陷是算法的性能受到反馈延迟的影响。当拥塞发生点和拥塞控制点 之间的延迟很大时，拥塞控制算法的性能会严重下降。 ( 2 ) 根据拥塞控制的实施位置，可以将拥塞控制算法分为两类：链路算 法( l i n ka 1 i z o r i t h m ) 和源算法( s o u r c em g o r i t h m ) 5 1 0 链路算法在网络 设备( 如路由器和交换机) 中执行。它的主要作用是检测网络拥塞的发生， 生成拥塞反馈信息。源算法在主机和网络的边缘设备中执行。它的主要作用 是根据反馈信息调整发送速率。拥塞控制算法设计的关键问题是如何给出反 馈信息和如何对反馈信息进行响应。 2 哈尔滨工程大学硕士学位论文 在源算法中，目前使用最广泛的是t c p 协议中的拥塞控制算法。近年来， 很多新的算法被使用到t c p 的传输控制中，这些算法包括慢启动( s l o w s 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 8 s tr e c o v e r y ) 、选择性应答( s a c k ) 等。 在链路算法方面，目前的研究主要集中在“主动队列管理”( a c t i v e q u e u em a n a g e m e n t ，a q m ) 算法和显式拥塞通知( e c n ，e x p l i c i tc o n g e s t i o n n o t i f i c a t i o n ) 两个方面。 ( 3 ) 从实施控制的类型上，拥塞控制可以分为基于窗口和基于速率两种 类型。t c p 采用的是典型的基于窗口的控制方式，t c p 通过调整拥塞窗口的大 小控制发送到网络中的数据量，其易于实现，且可以限制注入网络的最大流 量；基于速率的控制方式是通过对t c p 的窗口控制机制进行建模，得到t c p 连接吞吐量与网络参数之间的解析式，用来控制源端发送速率的大小，一般 适合于多媒体数据流的传输控制，重点的性能指标是t c p 友好性。 ( 4 ) 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制和隐 式拥塞控制。在显式控制方式中，网络使用显式信号向执行控制的端点通告 其状态( 可用带宽、缓存容量等) ；在隐式控制方式中，控制端使用流量估计 或者通过超时、重复a c k 等隐含信号来推断网络状态。 网络仿真技术的研究现状： 目前对通信网络仿真主要有两种途径m ，：第一种是采用通用计算机语言 或专门用于离散事件仿真的计算机语言通过编程，实现对通信网络仿真；第 二种是借助已有的网络仿真工具进行仿真，它提供了一种新的网络设计和优 化的方法。采用第一种仿真方法难度大且通用性不好，而借助专用网络仿真 工具不需要大量编程，通用性好，很容易实现通信网络仿真，是通信网络仿 真发展方向。 目前世界上的网络仿真软件可以分为高端和低端两类产品。高端产品一 般具有复杂的建模机制、比较完备的模型库、完善的外部接口、强大的功能 并能够得到比较可靠的仿真结果，价位一般在数万美元每个用户l i c e n s e 左右。其主流产品基本上都来自美国公司，例如m i l 3 公司的0 p n e t n ”，c a c i 公司的c o m n e t ，u cb e r k e l e y 大学的n s 仿真软件等；低端产品一般只有简单 的建模机制、较小的模型库、简单的外部接口，功能单一且仿真结果的可靠 哈尔滨工程大学硕士学位论文 性较差，价位在数百至数千美元之问，比较知名的产品也大都产自美国，例 如s e s 的s t r a t e g i z e r 。 对于高端产品，不同产品的定位不同、采用的仿真技术也有很大差异， 因此呈现出不同的特点，也有其各自不同的适用领域。例如，c o m n e t 采用数 学分析模拟方法，仿真效率很高，但是无法得到有关网络和协议细节的结果， 它适用于网络高层性能的仿真。m i l 3 公司的o p n e t 综合采用基于包的建模方法 和数学分析的建模方法，既可以得到非常细节的模拟结果，也可以获得比较 快的仿真计算速度。而u cb e r k e l e yn s 特别适用于t c p 层以上的模拟。w a r s a w 的a n s i m 则是一款专门用于a d - h o c 网络的仿真软件。 随着国内网络建设快速发展，网络仿真研究和应用也得到一些发展。1 9 9 7 年，c e r n e t 网络中心开始开发自己的网络仿真软件；1 9 9 8 年后，我国多家单 位陆续引进0 p n e t 网络仿真软件，用于网络协议开发、网络规划设计和应用的 研究。国内的网络分析、性能仿真方面的软件研发尚在摸索阶段，虽然有一 些专家在网络设计、方针与性能分析方面做过不少工作，但仍未有成果作为 产品问世。 在现有的网络仿真平台中，研发版本仿真工具虽不需经费投入，但还存 在着仿真运算性能及二次开发要求较高等问题。而商业化的仿真软件产品， 虽然用户界面亲切，操作方便，但扩展性较差，无法满足网络协议的研究、 开发及评测需要，且使用费用非常高，不适合大面积使用。为了进一步充分 利用好网络仿真这一技术平台，需要研究人员在使用仿真软件的同时，也要 不断地充实完善网络仿真技术，为后续的网络技术的发展奠定良好的基础。 1 3 论文研究的主要工作 现有的路由排队管理机制都各自有不同的特性，有的使用丢包事件和链 路空闲事件来管理拥塞，有的使用控制数据流量来管理拥塞，有的是在队列 满时丢弃随后到达的分组来控制拥塞，如何对这些路由排队管理机制进行有 效的仿真，有利于分析这些路由排队管理机制的实现过程及其存在的弊端， 有利于研究更完善的排队管理机制。 本课题主要使用网络仿真工具n s 2 对常用的路由排队管理机制进行仿真 4 哈尔滨工程大学硕士学位论文 研究，目的是为不同网络应用环境找出相对可靠的路由排队管理机制，并迸 一步完善n s 2 仿真软件中的路由排队管理算法。 根据研究的目标，本文的主要研究工作有以下几点： ( 1 ) 基于网络仿真软件n s 2 ，分别构建多种网络拓扑模型，在采用不同 队列调度策略时，通过n a m 动画，观察网络运行的全过程。 ( 2 ) 根据模拟输出的跟踪文件计算平均时间延迟，丢失率等指标值。 ( 3 ) 基于以上数据及相关理论，完成网络性能分析，并针对拓扑及排队 调度策略因素影响的网络拥塞进行分析。 ( 4 ) 针对理论成熟的其它路由排队管理机制与n s 2 中现有算法进行比较 分析；设计实现一个与现有算法机制不同的新算法，进一步完善n s 2 中用到 的主动队列管理算法。 ( 5 ) 对设计所得算法进行仿真，验证算法的有效性。 1 4 本章小结 本章介绍了当前网络中的现状，说明改善网络拥塞有利于改善现有网络 的性能，并针对国内外的研究现状进行分析，进一步证实对于网络拥塞问题 的研究的必要性。最后介绍本论文的主要工作。 哈尔滨工程大学硕士学位论文 第2 章网络拥塞与网络拥塞控制分析 2 1 拥塞概述 2 1 1 拥塞的基本概念 当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥 塞一，。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃” ( c o n g e s t i o nc o l l a p s e ) 现象。一般来说，拥塞崩溃发生在网络负载的增加 导致网络效率的降低的时候。最初观察到这种现象是在1 9 8 6 年l o 月，在这 个过程中，l b l 与u cb e r k e l e y 之间的吞吐量从3 2 k b p s 下降到了4 0 b p s 。f l o y d 总结出拥塞崩溃主要包括以下几种：传统的崩溃、未传送数据包导致的崩溃、 由于数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。 图2 1 网络负载与吞吐量及响应时间的关系 对于拥塞现象，可以进一步用图2 1 来描述。当网络负载较小时，吞吐 量基本上随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当负载 达到网络容量时，吞吐量呈现出缓慢增长，而响应时间急剧增加，这一点称 为膝点( k n e e ) 。如果负载继续增加，路由器开始丢包，当负载超过一定量 时，吞吐量开始急剧下降，这一点称为崖点( e l i f f ) 。拥塞控制机制实际上 6 堕釜鎏三堡盔主霉圭兰堡鎏苎 包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种策略。前者的目的是使网络运行在k n e e 附近，避免拥塞的发生；而后者 则是使得网络运行在c l i f f 的左侧区域。前者是一种“预防”措施，维持网 络的高吞吐量、低延迟状态，避免进入拥塞：后者是一种“恢复”措施，使 网络从拥塞中恢复过来，进入正常的运行状态。 2 1 2 拥塞产生的原因 拥塞发生的主要原因在于网络能够提供的资源不足以满足用户的需求， 这些资源包括缓存空间、链路带宽容量和中间节点的处理能力“”，。由于互 联网的设计机制导致其缺乏“接纳控制”能力，因此在网络资源不足时不能 限制用户数量，而只能靠降低服务质量来继续为用户服务，也就是“尽力而 为”的服务。 1 9 2 i c 却o d 图2 2 链路带宽相同的网络结构图 拥塞虽然是由于网络资源的稀缺引起的，但单纯增加资源并不能避免拥 塞的发生。例如增加缓存空间到一定程度时，只会加重拥塞，而不是减轻拥 塞，这是因为当数据包经过长时间排队完成转发时，它们很可能早已超时， 从而引起源端超时重发，而这些数据包还会继续传输到下一路由器，从而浪 费网络资源，加重网络拥塞。事实上，缓存空间不足导致的丢包更多的是拥 塞的“症状”而非原因。另外，增加链路带宽及提高处理能力也不能解决拥 塞问题，例如，图2 2 中，四个节点之间的链路带宽都是1 9 2 k b p s ，传输某 个文件需要用时5 分钟；当第一个节点和第二个节点之间的链路带宽提高到 i m b p s 时( 如图2 3 所示) ，传输完该文件所需时间反而大大增加。这是因 为在路由器r 1 中，数据包的到达速率远远大于转发的速率，从而导致大量数 据包被丢弃，源端的发送速度被抑止，从而使得传输时间大大增加。 7 哈尔滨工程大学硕士学位论文 1 硒p s1 9 拙却。 凰七嚣枷 d 图2 3 链路带宽不相同的网络结构图 即使所有链路具有同样大的带宽也不能解决拥塞问题，例如图2 4 中， 所有链路带宽都是1 g b p s ，如果a 和b 同时向c 以1 g b p s 的速率发送数据， 则路由器r 的输入速率为2 g b p s ，而输出速率只能为1 6 b p s ，从而产生拥塞。 cn 图2 4 产生拥塞的链路 网络拥塞往往是由许多因素引起的。例如，当某个结点缓存的容量太小 时，到达该结点的分组，因无存储空间暂存而不得不被丢弃。现在设想将该 结点缓存的容量扩展到非常大。于是到达该结点的分组均可在这缓存的队列 中排队，不受任何限制。由于输出链路的容量和处理机的速度并未提高，因 此在这队列中的绝大多数分组的排队等待时间将会很久，结果上层软件只好 将它们进行重传。由此可见，简单地扩大缓存的存储空间同样会造成网络资 源的严重浪费，因而解决不了网络拥塞的问题。 又如，处理机处理的速率太慢可能引起网络的拥塞。简单地将处理机的 速率提高，可能会使上述情况缓解些，但往往又会将瓶颈转移到其他地方。 问题的实质往往是整个系统的各个部分不匹配。只有所有的部分都平衡了， 问题才会得到解决。 归纳起来，拥塞产生的直接原因有以下3 点m ，： ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个 哈尔滨工程大学硕士学位论文 端口就会建立排队。如果没有足够的存储空1 日j 存储，数据包就会丢弃。对突 发数据流更是如此。增加存储空间在某种程度上可以缓解这一矛盾，但如果 路由器有无限存储量时，拥塞只会变得更坏，而不是更好，因为在网络里数 据包经过长时间排队完成转发时，它们已经超时，源端认为它们己经被丢弃， 而这些数据包还会继续向下一路由器转发，从而浪费网络资源，加重网络拥 塞。 ( 2 ) 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据 香农信息理论，任何信道带宽最大值即信道容量c = b l 0 9 2 ( 1 十s n ) ( n 为信 道白噪声的平均功率，s 为信源的平均功率，b 为信道带宽) 。所有信源发送 的速率r 必须小于或等于信道容量c 。如果r c ，则在理论上无差错传输就是 不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它 的所有源端带宽要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱、速度慢也能引起拥塞。如果路由器的c p u 在执 行排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥 塞。同样，低速链路对高速c p u 也会产生拥塞。 要避免拥塞的发生，对以上3 点原因需综合考虑。例如，提高链路速率 而不改变处理器，只会转移网络瓶颈，而不能避免拥塞。同样，单纯地增加 网络资源也不能有效地解决拥塞问题，因为拥塞本身是一个动态问题，它不 可能只靠静态的方案来解决，而需要协议能够在网络出现拥塞时保护网络的 正常运行。目前对互联网进行的拥塞控制主要是依靠在源端执行的基于窗口 的t c p 拥塞控制机制。 2 2 拥塞控制的研究现状 拥塞现象是指到达通信子网中某一部分的分组数量过多，使得该部分网 络来不及处理，以致引起这部分乃至整个网络性能下降的现象，严重时甚至 会导致网络通信业务陷入停顿，即出现死锁现象。这种现象和公路上经常所 见的交通拥挤一样，当节假日公路网中车辆大量增加时，各种走向的车流相 互干扰，使每辆车到达目的地的时间都相对增加( 即延迟增加) ，甚至有时在 某段公路上车辆因堵塞而无法开动( 即发生局部死锁) 。 9 哈尔滨工程大学硕士学位论文 网络的吞吐量与通信子网负荷( 即通信子网中正在传输的分组数) 有着密 切的关系。当通信子网负荷比较小时，网络的吞吐量( 分组数秒) 随网络负荷 ( 每个节点中分组的平均数) 的增加而线性增加。当网络负荷增加到某一值后， 若网络吞吐量反而下降，则表征网络中出现了拥塞现象。在一个出现拥塞现 象的网络中，到达某个节点的分组将会遇到无缓冲区可用的情况，从而使这 些分组不得不由前一节点重传，或者需要由源节点或源端系统重传。当拥塞 比较严重时，通信子网中相当多的传输能力和节点缓冲器都用于这种无谓的 重传，从而使通信子网的有效吞吐量下降。由此引起恶性循环，使通信子网 的局部甚至全部处于死锁状态，最终导致网络有效吞吐量接近为零。 2 2 1 拥塞控制方法 拥塞控制可以在网络协议的各个层次上实施。由于数据链路层靠近拥塞 的发生点，所以在数据链路层进行控制可以快速响应拥塞，但它只能对短期 的拥塞现象进行控制，一般来说，不同网络层次中的控制机制具有不同的目 标，拥塞现象持续的时间越长，实现控制的层次也应该越高，明确的拥塞控 制主要在网络层和传输层实现。 1 缓冲区预分配法 该法用于虚电路分组交换网中。在建立虚电路时，让呼叫请求分组途经 的节点为虚电路预先分配一个或多个数据缓冲区。若某个节点缓冲器已被占 满，则呼叫请求分组另择路由，或者返回一个“忙”信号给呼叫者。这样， 通过途经的各节点为每条虚电路开设的永久性缓冲区( 直到虚电路拆除) ，就 总能有空间来接纳并转送经过的分组。此时的分组交换跟电路交换很相似。 当节点收到一个分组并将它转发出去之后，该节点向发送节点返回一个确认 信息。该确认一方面表示接收节点已正确收到分组，另一方面告诉发送节点， 该节点己空出缓冲区以备接收下一个分组。上面是“停一等”协议下的情况， 若节点之间的协议允许多个未处理的分组存在，则为了完全消除拥塞的可能 性，每个节点要为每条虚电路保留等价于窗口大小数量的缓冲区。这种方法 不管有没有通信量，都有可观的资源( 线路容量或存储空间) 被某个连接占 有，因此网络资源的有效利用率不高。这种控制方法主要用于要求高带宽和 l o 哈尔滨工程大学硕士学位论文 低延迟的场合，例如传送数字化语音信息的虚电路。 2 分组丢弃法 该法不必预先保留缓冲区，当缓冲区占满时，将到来的分组丢弃。若通 信子网提供的是数据报服务，则用分组丢弃法来防止拥塞发生不会引起大的 影响。但若通信子网提供的是虚电路服务，则必须在某处保存被丢弃分组的 备份，以便拥塞解决后能重新传送。有两种解决被丢弃分组重发的方法， 种是让发送被丢弃分组的节点超时，并重新发送分组直至分组被收到；另一 种是让发送被丢弃分组的节点再尝试一定次数后放弃发送，并迫使数据源节 点超时而重新开始发送。但是不加分辨地随意丢弃分组也不妥，因为一个包 含确认信息的分组可以释放节点的缓冲区，若因节点无空余缓冲区来接收含 确认信息的分组，这便使节点缓冲区失去了一次释放的机会。解决这个问题 的方法可以为每条输入链路永久地保留一块缓冲区，以用于接纳并检测所有 进入的分组，对于捎带确认信息的分组，在利用了所捎带的确认释放缓冲区 后，再将该分组丢弃或将该捎带好消息的分组保存在刚空出的缓冲区中。 3 。定额控制法 这种方法在通信子网中设置适当数量的称做“许可证”的特殊信息，一 部分许可证在通信子网开始工作前预先以某种策略分配给各个源节点，另一 部分则在子网开始工作后在网中四处环游。当源节点要发送来自源端系统的 分组时，它必须首先拥有许可证，并且每发送一个分组注销一张许可证。目 的节点方则每收到一个分组并将其递交给目的端系统后，便生成一张许可证。 这样便可确保子网中分组数不会超过许可证的数量，从而防止了拥塞的发生。 2 2 2 拥塞控制的主要问题 拥塞控制的问题主要集中在效率和公平性( f a i r n e s s ) 上。网络资源的 使用效率是指源端要求的总资源与网络所能提供的资源之间的关系。如果二 者刚好相等或者很接近，那么这种算法的效率就是高的，否则都是效率不高 的表现。 公平性是指在网络发生拥塞时各连接能公平地共享网络资源。产生公平 性的根本原因在于拥塞发生必然导致数据包丢失，而数据包丢失会导致各数 哈尔滨工程大学硕士学位论文 据流之间为争抢有限的网络资源发生竞争，竞争能力强的数据流将到更多网 络资源，从而损害了其他流的利益。所以说没有拥塞，也就没有公平性问题。 公平性问题表现在两方面：一是拥塞响应的t c p 流和非拥塞响应的u d p 流之 间资源享用不公平；二是t c p 流之间资源享用的不公平。前者主要是在发生 拥塞时对拥塞指示作出的不同反应造成的。由于t c p 流具有拥塞控制机制， 在收到拥塞指示后，源端会主动降低发送速率；而u d p 流由于没有端到端的 拥塞控制机制，因此在收到拥塞指示后，u d p 不会降低数据发送速率。结果 在网络拥塞时，拥塞适应的t c p 流得到的资源越来越少，非拥塞适应的u d p 得到的资源越来越多，从而导致了网络资源分配的不公平。网络资源分配的 不公平反过来会加重拥塞情况，甚至可能导致拥塞崩溃。对于第二个不公平 性问题，研究表明，不同的窗口大小、r t t 值及数据包的尺寸都会影响t c p 流对带宽的占用。窗口较大，或者r t t 较小，或者数据包较大的流，往往能 占用更多的带宽。 在计算机网络中的链路容量( 即带宽) 、交换结点中的缓存和处理机等， 都是网络的资源。在某段时间，若对网络中某一资源的需求超过了该资源所 能提供的可用部分，网络的性能就要变坏。 拥塞常常使问题趋于恶化。如果一个路由器没有足够的缓存空间，它就 会丢弃一些新到的分组。但当分组被丢弃时，发送这一分组的相邻路由器就 会重传这一分组，甚至可能还要重传多次。发送端在未收到确认之前必须保 留所发分组的副本以便进行可能的重传。可见在接收端产生的拥塞反过来会 引起发送端缓存的拥塞。 拥塞控制与流量控制的关系密切，它们之间也存在着一些差别。拥塞控 制所要做的都有一个前提，就是网络能够承受现有的网络负荷。拥塞控制是 一个全局性的过程，涉及到所有的主机、所有的路由器，以及与降低网络传 输性能有关的所有因素。 相反，流量控制往往指在给定的发送端和接收端之间的点对点通信量的 控制。流量控制所要做的就是抑制发送端发送数据的速率，以便使接收端来 得及接收。流量控制几乎总是存在着从接收端到发送端的某种直接反馈，使 发送端知道接收端是处于怎样的状况。 拥塞控制和流量控制之所以常常被弄混，是因为某些拥塞控制算法是向 哈尔滨工程大学硕士学位论文 发送端发送控制报文，并告诉发送端，网络已出现麻烦，必须放慢发送速率。 这点又和流量控制是很相似的。 进行拥塞控制需要付出代价。这首先需要获得网络内部流量分布的信息。 在实旋拥塞控制时，还需要在结点之间交换信息和各种命令以便选择控制的 策略和实施控制。这样就产生了额外开销。拥塞控制有时需要将些资源( 如 缓存、带宽等) 分配给个别用户( 或一些类别的用户) 单独使用，这样就使 得网络资源不能更好地实现共享。十分明显，在设计拥塞控制策赂时，必须 全面衡量得失。 2 3 队列管理机制的比较 由于t c p 拥塞控制在效率、公平性、自相似等方面的问题仍有待解决， 因此尽管t c p 拥塞控制机制是必须的而且是有效的，但仍然需要采用基于路 由器的拥塞控制机制对源端节点的拥塞控制机制进行补充。 拥塞避免机制的首要任务是检测早期的拥塞。由于路由器能够有效的监 控队列的长度，因此也能有效的检测早期的拥塞( i n c i p i e n tc o n g e s t i o n ) 。 拥塞避免机制的另个任务是选择哪个流发出拥塞通知。而路由器能够全面 的审视各个流对产生拥塞的影响，因此也能够有效的决定将拥塞信息通知哪 个源端，使其降低数据发送速度。所以，基于路由器的拥塞控制十分必要。 当前的队列管理算法可以分为两大类：被动队列管理( p a s s i v eq u e u e m a n a g e m e n t ，简记为p q m ) 和主动队列管理( a c t i r eq u e u em a n a g e m e n t ，简 记为a q m ) 。 2 3 1 被动队列管理及其缺陷 路由器的队列管理传统上是在队列满时丢弃随后到达的分组，这种方法 称为d r o p - t a i l ，队尾丢弃算法。算法简短描述如下：数据包到达路由器后， 需要在不同的输出端口缓冲区中进行排队，将该缓冲区的容量设置足够大， 这样当网络发生拥塞的时候，所有新到达又来不及处理的数据包都会保存在 缓冲区中，当系统空闲时再来处理这些保存起来的数据包：当网络持续拥塞 1 3 哈尔滨工程大学硕士学位论文 时，缓冲区就会被填满，所有新到达的数据包将被丢弃。当发送方t c p 检测到 有数据包被丢弃时就会降低数据发送速率，直到拥塞消除“”。它可能引起全 局同步现象，导致链路的低利用率；也可能引起流隔离现象，使少部分流垄 断队列空间。另一种在队列满时触发的管理方法称为d r o p - f r o m - f r o n t ，即从 队列前端丢弃分组，它能防止流隔离产生并改善公平性。若在新分组到达一 个满的队列时随机丢弃队列中的一个分组，则称为r a n d o md r o p ，它能改善对 后启动连接的公平性，并改善r t t 连接流的吞吐量。 虽然“尾部丢弃”算法在当前i n t e r n e t 上已经得到了比较广泛的使用， 但其存在几个重大缺陷n ( 1 ) 死锁( l o c k o u t ) 问题：在某些情况下，“尾部丢弃”算法会让某个 流或者少数几个流独占队列空间，阻止其他流的分组进入队列。这种“死锁” 现象通常是由于同步( s y n c h r o n i z a t i o n ) 或其他定时作用造成的结果。 ( 2 ) 满队列( f u l lq u e u e s ) 问题：由于“尾部丢弃”算法只有在队列缓 存耗尽时才会发出拥塞信号，因此会使得队列在相当长时间内处于充满( 或几 乎充满) 的状态。可是队列管理最重要的目标之一就是降低稳定状态下队列的 长度，而端到端的延迟主要就是由于数据分组在队列中排队等待造成的。 ( 3 ) 全局同步( g l o b a ls y n c h r o n i z a t i o n ) 问题：由于i n t e r n e t 上数据 的突发本质。到达路由器的分组往往也是突发的。如果队列是满的或者几乎 是满的，就会导致在短时间内连续大量的丢弃分组。而t c p 流具有自适应特 性，源端发现分组丢失就急剧的减小发送窗口，分组到达速率就迅速下降， 于是网络拥塞得以解除，但源端得知网络不再拥塞后又开始增加发送速度， 最终又造成网络拥塞，而且这种现象常常会周而复始的进行下去，从而在一 段时间内网络处于链路利用率很低的用状态，降低了整体吞吐量，这就是所 谓的“t c p 全局同步”现象“”。 2 3 2 主动队列管理及其优点 在当前的i n t e r n e t 上，丢弃分组是对端节点进行拥塞通知的重要机制， 解决路由器“满队列”的方法便是在队列缓存耗尽之前丢弃分组，这样源端 节点便能在队列溢出前对拥塞作出反应。这种方法便称为“主动队列管 1 4 哈尔滨工程大学硕士学位论文 理”( a o m ) 。 随着随机早期检测算法的提出，主动队列管理算法的研究已经日益成为 新的研究热点。a q m 解决的问题主要包括：( 1 ) 早期探测路由器可能发生的 拥塞，并通过随机丢弃或标记分组来通知源端采取措施避免可能发生的拥塞； ( 2 ) 公平地处理包括突发性、持久性和间隙性的各种t c p 业务流；( 3 ) 避免 多个t c f 连接由于队列溢出而造成同步进入“慢启动”状态；( 4 ) 维持较小 的队列长度，在高吞吐量和低时延之间做出合理平衡。 a q m 是一种基于f i f o 调度策略的队列管理机制，使得路由器能够控制在 什么时候丢多少分组，以支持端到端的拥塞控制。a q m 有以下优点： ( 1 ) 减少了路由器中丢弃的分组的数量。i n t e r n e t 中数据分组的突发 本质是不可避免的，a q m 通过保持较小的平均队列长度( a v e r a g eq u e u e s i z e ) ，能提供更大的容量吸收突发数据分组，从而大大减少了丢弃的分组数 目。进一步说，如果没有a q m ，会有更多的分组被丢弃，这主要是因为以下 三个原因： 由于使用共享的队列和p q m ，会不可避免的产生全局同步，导致很低 的平均带宽利用率，即吞吐量很低。 t c p 从突发分组的丢弃中恢复要比从单个分组丢弃中恢复更复杂。 如果一个数据分组在到达目的端之前被丢弃，则其在传输过程中所消 耗的资源都被浪费，降低了网络带宽的利用率。因此，不必要的分组丢失也 就意味着带宽的浪费。 ( 2 ) 对交互式服务提供了更低的延迟。a q m 通过保持较小的平均队列长 度，队列管理能够减少分组的排队延迟( q u e u i n gd e l a y ) ，而排队延迟则是造 成端到端延迟( e n dt oe n dd e l a y ) 的主要原因。这对交互式应用比如w e b 浏 览、t e l n e t 业务和视频会议等非常重要。 ( 3 ) 避免了“死锁”现象。a q m 能够通过确保到来的分组几乎总是有可 用的队列空问，从而阻止“死锁”行为的发生。也因为这个原因，a q m 能防 止路由器对低带宽高突发的流的偏见。 哈尔滨工程大学硕士学位论文 2 4 拥塞控制算法的评价指标 对于拥塞控制算法，通常可从用户和系统两个不同的角度进行评价。通 常用户所关心的性能指标主要包括端系统吞吐量、分组丢失率和传输延迟及 时延抖动等。 ( 1 ) 吞吐量：单位时间内在一个连接上传输的最大字节数。通常用户期 望其所获得的吞吐量，特别是有效吞吐量尽可能高，同时吞吐量标准方差接 近于0 。 ( 2 ) 延迟：也称时延，描述的是分组从源端开始传输直到最后成功传送 到目的地的时间间隔。端到端的延迟包括：节点处理延迟、排队延迟、传播 延迟和传输延迟。 3 ) 分组丢失率：数据传输过程中丢失的分组数与传输的总的分组数的 比率。通常数据分组在传递过程中如果出现拥塞，将在交换机和路由器等网 络设备中进行缓存。如果拥塞持续时阃过长，网络设备的缓存空闯将耗尽， 这样一些分组将被丢弃。分组丢失率通常作为反映网络拥塞状态的一个指标。 ( 4 ) 时延抖动：延迟的变化就是抖动。如果所有分组都通过相同的路径 到达接收端，则这些分组具有相同的传播延迟。如果分组大小一样，那么传 输延迟也基本相同。但是网络业务是动态变化的，不同的业务负载情况下， 网络节点的处理延迟和排队延迟具有很大差别，因此相应的分组之间时延差 别将出现很大变化。在拥塞发生时，网络的延迟的时延抖动都会急剧增大。 由于拥塞控制算法对整个网络系统都有影响，在评价拥塞控制算法时， 更应该从整个系统的角度出发进行考虑。两个重要的系统评价指标是资源分 配的效率和分配的公平性m ，。 1 资源使用的效率( e f f i c i e n c y ) 。 网络资源的使用效率是由源端要求的总资源与网络资源的接近程度决定 的。如果源端总资源接近或等于网络所能提供的资源，那么这种算法的效率 就是高的，超载或负载不足都是效率不高的表现。效率只与总资源的利用率 有关，而与各个源端之间的资源利用无关。资源分配的效率可以使用p o w e r 函数来评价”“”。p o w e r 函数的定义为：p o w e r = t h r o u g h p u t 。r e s p o n s e t i m e 。 6 哈尔滨工程大学硕士学位论文 2 资源分配的公平性。 公平性指的是在发生拥塞时各源端( 或同一源端建立的不同t c p 连接或 u d p 数据包) 能公平地共享同一网络资源( 如带宽、缓存等) 。处于相同级别的 源端应该得到相同数量的网络资源。产生公平性的根本原因在于拥塞发生必