（计算机应用技术专业论文）网络拥塞控制问题研究.pdf

哈尔滨工程大学硕士学位论文 摘要 h t c m e t 的迅猛发展，带来的直接影响就是通信量的急剧增加和各类实时 业务流量对网络o o s 要求的提高。通信量的迅速增长使得主干网拥塞日益严 重，因此，拥塞控制成为网络研究的重点。 针对拥塞控制问题，v j o b s o n 提出了基于窗口的端到端的t c p 拥塞控 制策略。然而，随着网络规模的迅速扩大和网络应用的拓宽，特别是多媒体 业务的广泛应用，并不是每个用户或应用都有基于窗口的端到端的拥塞控制。 单纯的端到端的拥塞控制已经难以保持网络的高效和公平运行，必须让网络 的中间节点也参与到拥塞控制中来，即口层的拥塞控制。近几年坤拥塞控 制策略成为当前网络研究的一个重点，随机早期检测算法是世r f 推荐的广泛 应用于路由器中的口拥塞控制算法。 本文在分析了t c p i p 拥塞控制原理的基础上，重点对随机早期检测算法 进行了研究。随机早期检测算法中丢弃概率与平均队列长度成线性的增长关 系，造成平均队列长度在最小门限附近或者超过最大门限时，以相对较高的 概率丢弃数据包，降低了网络的链路利用率。对此，本文对随机早期检测算 法中丢弃概率的计算进行了改进，用一种指数的非线性关系来计算丢弃概率， 降低丢包率，提高网络的链路利用率。 另外，对随机早期检测算法的公平性进行了分析。算法在多个流竞争带 宽的情况下，不能保证各流获得相对公平的带宽分配。本文提高算法公平性 的设计中，当丢包率超过门限值时，利用数据流的到达速率与路由器的平均 到达速率的关系来鉴别高带宽流，对鉴别出的高带宽流进行管制，即以一定 的概率丢弃其随后到达的分组，将未被丢弃的分组放入随机早期检测输出队 列中进行排队，通过这种方式来限制高带宽流所占用的带宽。通过实验仿真 证明了算法的有效性。 关键词：拥塞控制；随机早期检测；丢弃概率；高带宽流 哈尔滨工程大学硕士学位论文 a b s t r a c t t h es w i f ta n dv i o l e n td e v e l o p m e n to fi n t e r n e tm a d et h et r a f 行ci n c r e a s e q u i c k l ya n da l lk i n d so fr e a lt i m eb u s i n e s sd e m o n d i n gh i g hn e t w o r kq o s t h e r a p i di n c r e a s eo ft r a f f i cm a k e sc o n g e s t i o no fb a c k b o n em o r ea n dm o r eg r a v e t h e r e f o r e ，c o n g e s t i o nc o n t r o lb e c a m ea ni m p o r t a n ti s s u ei nn e t w o ks t u d y f o rc o n g e s t i o nc o n t r o lp r o b l e m ，v j a c o b s o np r o p o s e dt h ew i n d o w - b a s e d e n d - t o - e n dc o n g e s t i o nc o n t r o lo ft c p b u tn o ta l lu s e r sa n da p p l i c a t i o n sh a v e t h ew i n d o w b a s e de n d t o - e n d c o n g e s t i o n c o n t r o lw i t ht h en e t w o r ks c 目d e b r o a d e n i n gq u l i c k l ya n dn e t w o ka p p l i c a t i o ni n c r e a s i n g , e s p e c i a l l y , t h eb r o a d a p p l i c a t i o no fm u l t i m e d i ab u s i n e s s i ti sd i f f i c u l t yt ok e e pt h eh i g he f f e c ta n d i m p a r t i a lo p e r a t i o no fn e t w o r kb yu s i n ge n d - t o - e n dc o n g e s t i o nc o n t r o lo n l y t h e c e n t r en o d eo fn e t w o km u s tp a r t i c i p a t ei nc o n g e s t i o nc o n t r o l ，w h i c hi si pl a y e r c o n g e s t i o nc o n t r 0 1 a n di th a sb e c o m ea ni m p o r t a n ti s s u eo fn e t w o r ks t u d i n gi n t h e s ey e a r s r a n d o me a r l yd e t e c t i o na l g o r i t h m ，w h i c hi so n eo fi pc o n g e s t i o n c o n t r o la l g o r i t h m s ，h a sb e e nr e c o m m e n e db yi e t ft ou s i n gi nr o u t e rb r o a d l y i nt h i st h e s i s ，r a n d o me a r l yd e t e c t i o na l g o r i t h ms t u d yi se m p h a s i z e do n t h eb a s eo fi n t r o d u c i n gt h ep r i n c i p l e so ft c fa n d1 1 l a y e rc o n g e s t i o nc o n t r o l 。 f o rr a n d o me a r l yd e t e c t i o na l g o r i t h m ，t h ed r o pp r o b a b i l i t yl i n e a r l yi n c r e a s e s w i t ha v e r a g eq u e u el e n g t h ，w h i c hm a k e st h ed r o pp r o b a b i l i t yr e l a t i v eh i g h ， w h e nt h ea v e r a g eq u e u el e n g t hi sc l o s et om i n i m a lo rm a x i m a ll i m i to fq u e u e l e n g t h ，a n dl i n ku t i l i z a t i o nd e g r a d e s oa l li m p r o v e dr e da l g o r i t h mi sp r o p o s e d w h i c ha m e n d e dt h ec o m p u t a t i o no fd r o pp m b a b i f i t y i n d e xn o n l i n e a rr e l a t i o ni s u s e dt od e c r e a s ed r o pp a c k e ta n di m p r o v et h el i n ku t i l i z a t i o ni nr e da l g o r i t h m i na d d i t i o n ，t h ef a i r n e s so fr e di s a n a l y z e d r e da l g o r i t h mc a n n o t g u a r a n t e et h a te a c hf l o wh a sf a i rb a n d w i d t hr e l a t i v e l y ，w h e nm a n yf l o w su s i n g l i m i t e db a n d w i d t h t oi m p r o v et h ef a i r n e s so fr e d ，a ni m p r o v e da l g o r i t h mi s p r o p o s e d t h er e l a t i o n s h i po ft h ea r r i v es p e e do fe a c hf l o wa n dt h ea v e r a g e a r r i v es p e e do fr o u t e ri su s e dt oe s t i m a t ew h e t h e rt h i sf l o wi sh i i g hb a n d w i d t h 哈尔滨工程大学硕士学位论文 f l o wo rn o tw h e nt h ed r o pp a c k e t sa r cm o g et h a nt h el i m t f o rh i i g hb a n d w i d t h f l o w ，d r o ps o m ep a c k e 协r a n d o m l ya c c o d i n gt oc e r t a i nd r o pp r o b a b i l i t y ，t h e np u t t h eo t h e rp a c k e t si n t ot h er e d o u t p u tq u e u e i nt h i sw a y , t h eb a n d w i d t hu s i n g b yh i g hb a n d w i d t hi sl i m i t e d t h ev a l i d i t yo fa l g o r i t h mi sp r o v e db ye m u l a t i o n a l e x p e r i m e n t k e yw o r d s ：c o n g e s t i o nc o n t r o l ，r a n d o me a r l yd e t e c t i o n , d r o pp r o b a b i l i t y ，h i g h b a n d w i d t hf l o w 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：塑竖 日期：伊1 年3 月，日 哈尔滨工程大学硕士学位论文 1 1 研究背景和意义 第1 章绪论 互联网起源于美国国防部的a r p a n e t 计划，最初建立网络是为了军事 指挥的需要，只是将几个军事及研究用电脑主机连接起来。当a r p a n e t 与 美国国家科学基金会( n s f ) 建成的n s f n e t 互联以后，其上的用户数量以 指数增长，并且开始了与加拿大、欧洲和太平洋地区的网络连接。人们把这 些互联的网络称为互联网，它的出现使世界范围内的通信成为可能。t c p i p 体系结构和协议规范的推出，时异种网之间的互联与互通成为可能。t ：p 坤 协议目前已成为最流行的网际互联协议，互联网几乎覆盖了全球的每一个角 落，t i ：p m 协议为互联网的发展做出了巨大的贡献。 随着新型网络应用的不断涌现和用户数量的迅速增加，i n t e r n e t 的流量也 急剧增长。实时多媒体应用的出现，使网络环境更加复杂，t c p i p 数据流和 实时多媒体数据流的并存，使网络的服务质量受到影响。为这些大量出现的 实时多媒体数据流提供服务质量的保证，一个最基本和最重要的要求就是防 止网络发生拥塞崩溃现象。由于互联网上9 0 以上的数据流使用的是t c p i p 协议，所以t c p i p 的拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 机制对控制网络拥塞 具有特别重要的意义。 另外，拥塞控制是确保互联网鲁棒性乜1 的关键因素，也是各种管理控制 机制和应用( 如多媒体通信中q o s 控制、区分服务) 的基础，通过网络的拥 塞控制，可以提高网络的总体性能，保证网络系统长期的稳定性和鲁棒性。 拥塞控制的研究目的不是要完全避免拥塞的发生，而是研究怎样的拥塞 程度才是网络所能够承受的，通过在现有的网络体系结构中增加适当的控制 机制，使网络运行在轻度拥塞的最佳状态，不致发生拥塞崩溃现象，同时保 证一定的公平性。t c p i p 网络采用分组交换技术来提高网络链路的利用率， 使得路由器的队列缓存经常处于充满状态；如果路由器队列缓存总是空的， 尽管网络的传输延迟很小，网络的资源的利用率仍然很低；如果路由器的队 哈尔滨工程大学硕士学位论文 列缓存总是被占用，虽然传输延迟很大，网络的资源利用率会很高。拥塞控 制研究的一个目标是希望达到网络资源利用率和传输延迟等综合性能指标的 最优化。 1 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 年i o 月， 由于拥塞崩溃的发生，美国l b l 到u cb e r k e l e y 的数据吞吐量从3 2 k b p s 跌 落到4 0 b p s 。当网络处于拥塞崩溃状态时，微小的负载增量都将使网络的有效 吞吐量( g o o d p u t ) 急剧下降嘲。f l o y d 总结出拥塞崩溃主要包括以下几种： 传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益 增长的控制信息流造成的崩溃等“1 。 对于拥塞现象可以通过图1 1 ( a ) ( b ) 来进行描述，当网络负载较小时， 吞吐量基本上随着负载的增长而增长，呈线性关系，响应时间增长缓慢。当 负载达到网络容量时，吞吐量呈现出缓慢增长，而响应时间急剧增加，这一 点称为k n e e 。如果负载继续增加，路由器开始丢包，当负载超过一定量时， 吞吐量开始急剧下降，这一点称为c l i f f 通常将k n e e 点附近称为拥塞避免 区间；k n e e 和a i f f 之间是拥塞恢复区间；c l i f f 之外是拥塞崩溃区间。为了 最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想的，但这 也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来加以约束 和限制。 拥塞控制机制包括两种策略，拥塞避免和拥塞控制。拥塞避免是由网络 节点采取措施避免拥塞的发生或者对拥塞的发生做出反应，使网络运行在 k n e e 附近，能网络能够传输较大的有效吞吐量，避免发生拥塞现象；拥塞控 制是使网络运行在c l i f f 的左侧区域。拥塞避免是一种“预防”措施，使网络 保持在高吞吐量、低延迟的状态，避免拥塞发生：拥塞控制是一种“恢复” 措施，使网络从拥塞中恢复过来，进入正常的工作状态。 2 哈尔滨工程大学硕士学位论文 吞 吐 置 响 应 时 间 ( a ) 网络负载与吞吐量( b ) 网络负载与响应时间 图1 1 网络负载与吞吐量和响应时间的关系 1 2 2 拥塞发生的原因 拥塞现象的发生和t c i i p 网络的设计机制有着密切的联系。t ( 卫口网 络的设计机制有以下几个特点： 1 分组交换( p a c k e t - s w i t c h e d ) 网络。不同于电路交换技术，分组交换采 用存储转发技术，通过共享提高了资源的利用率，但存储转发机制容易造成 分组在网络中滞留，数据分组有时不能按照正确的顺序到达，将乱序分组交 给端系统处理，增加了系统的复杂性。 2 无连接( c o 姗o o i o n l e 骆) 网络。从t c = p i p 网络结构中网络层看，节点 之间进行通信时不需要事先建立连接。这种无连接的网络模型使网络的设计 更简单，在网络的中间节点上不需要保存与连接有关的信息。但这种模型很 难把“接纳控制”( a d m i s s i o nc o n t r 0 1 ) 机制加入其中，当用户对资源的需求 大于网络所能提供的资源时，难以保证服务质量( q o s ) 3 “尽力而为”的服务模型“尽力而为”是指网络尽最大的努力传输 到达的每一个分组，不考虑数据传输的服务质量问题。这是因为早期的网络 应用主要是数据业务，这些应用对网络性能的变化不敏感，“尽力而为”的 服务满足业务的需要。但对于一些新出现的实时多媒体应用，它们对延迟、 速率等性能的变化比较敏感嘲，“尽力而为”的服务已经不能很好地满足其 对网络性能的需求。 科学技术的不断发展，提高了网络设备的处理速度，同时使网络带宽不 3 哈尔滨工程大学硕士学位论文 断增长，但是网络硬件的发展速度有时跟不上应用需求的增长。而且，很多 时候，在局部的网络资源很充足的情况下，仍然会出现网络拥塞、分组数据 丢失，使网络的性能下降。 网络中拥塞现象发生的根本原因是，对网络中某一资源的需求超过了该 资源所能提供的可用部分。网络中的有限资源被多个用户共同使用。由于网 络系统中没有引入“接纳控制”策略，使网络不能根据资源的使用情况来限 制用户的数量；并且，互联网是一个分散的控制系统，缺乏有效的中央集成 控制机制，使网络不能很好的控制用户使用的资源数量。i n t c r n c t 上的用户和 应用不断的增长，增加了网络发生拥塞的可能性。虽然拥塞时由于资源短缺 引起的，但仅通过增加网络资源的数量，无法避免拥塞现象的发生，有时甚 至会加重网络的拥塞。缓存空间增大到一定程度时，只会使拥塞加重，而不 是减轻拥塞。例如，增加路由器的队列缓存的同时增大了分组通过路由器的 延迟，如果总的时延超过了端系统重传时钟计数值，就会导致端系统重传分 组，而这些延迟过大数据分组还会继续被传送，浪费了网络的资源，从而使 网络拥塞更加严重。由于缓存空间不足所导致的丢包是拥塞发生的表现并不 实引起拥塞的原因。 拥塞现象大多发生在网络资源相对短缺的地方，这也反映网络资源分布 的不均衡性。这种不均衡性也存在两个方面：一方面是资源分布的不均衡， 如图1 2c a ) 中带宽分布不均衡：若s 以1 m b p s 的速率向d 发送数据，在 路由器r 处会发生拥塞。另一方面是网络流量分布的不均衡，如图1 2 ( b ) 中带宽分布均衡，但如果a 和b 同时以1 m b p s 的速率向c 发送数据，在路 由器r 也会发生拥塞。i n t e r n e t 中资源和流量分布的不均衡性是广泛存在的， 因此而导致网络拥塞现象，通过增加资源的方法不能得到有效地解决嘲。 c a ) 带宽不对称的情况 图1 2 ( b ) 带宽对称的情况 网络的不均衡性 4 哈尔滨工程大学硕士学位论文 1 2 3 拥塞控制的分类 拥塞控制是一个全局性的问题，要确保网络传输数据的能力，涉及到所 有主机、路由器以及所有其他能使网络负荷能力下降的因素。从广义上讲， 拥塞控制涉及到网络中的每一层，而具体的实施，一般是通过网络层和传输 层的相互协作完成的。 拥塞控制可以分为不同的类型： 1 从控制理论的角度，拥塞控制算法可以分为开环控制和闭环控制两大 类。开环控制方法就是在设计网络时事先将有关发生拥塞的因素考虑周到， 力求网络在工作时不产生拥塞。一旦系统安装并运行起来，就不再做任何中 问阶段的更正。适合于整个流量特征可以准确规定、性能要求可以事先获得 的情况下。如果网络的流量特征不能准确描述或者系统不提供预留资源时， 适于时用闭环控制方式。闭环的拥塞控制首先检测网络中拥塞的发生，然后 将拥塞信息回馈给拥塞控制点，由拥塞控制点根据拥塞信息调整状况，消除 拥塞。闭环拥塞控制能够适应网络的动态地变化，但缺点是反馈延迟将影响 算法的性能。在拥塞发生点和控制点之间存在很大的延迟时，算法性能会严 重下降。 2 根据实施拥塞控制算法的位置不同，可以将拥塞控制算法分为两大类； 链路算法( l i n k a l g o r i t h m ) 和源算法( s o u r c e a l g o r i t h m ) 脚。链路算法的作 用是检测网络拥塞的发生，一般在网络设备中执行，将拥塞反馈信息发送给 源端。源算法的作用是网络中反馈回来的信息调整数据的发送速率，实施在 端系统或者网络的边缘设备中。如何生成反馈信息和如何对反馈信息进行响 应是拥塞控制算法设计中的关键问题。目前，在链路算法中，使用广泛的有 传统的“弃尾”( d r o p - t a i l ) 算法和主动队列管理( a c t i v eo u e u em a n a g e m e n t ) 算法，而t c p 协议中拥塞控制算法则是使用最广泛的源算法。 3 从实施控制的类型上，拥塞控制可分为基于窗口和基于速率( 又称基 于方程) 两种类型啪。典型的基于窗口的拥塞控制方式是t c p 协议中的拥塞 控制，t c p 不断调整滑动窗口的大小，从而控制发送到网络中的数据量，这 种方法实现简单，能够限制注入网络的最大流量；基于速率的控制方式适合 对实时多媒体数据流的控制，表现出了对t c p 流的友好性，这种方式是采用 5 哈尔滨工程大学硕士学位论文 对t c p 窗口控制机制进行建模的方式，获得t c p 连接的吞吐量与网络参数之 间的解析式，依此指导源端如何调整发送速率的大小 4 从推断网络状态的反馈信息的类型上，可以分为显式拥塞控制 ( e x p l i c i t ) 和隐式拥塞控制( i m p l i c i t ) 嘲。在显式反馈方式中，网络使用特 定的通知报文向执行控制的端点通知网络的当前状态；在隐式控制方式中， 网络不向源端通知状态，而是由控制端使用流量测量或超时、重复a c k 等信 息推断网络的当前状态。 1 3 网络仿真软件介绍 由于网络的复杂性，目前网络技术的研究很大程度上仅限于理论研究， 在实际上的应用比较困难。随着计算机技术的发展，仿真工具在分析和研究 复杂网络中发挥了很大的作用，所以寻求性能优越的仿真工具对于网络技术 的研究有着非常重要的作用 n s - 2 ( n e t w o r ks i m u l a t o r ) 是由u cb e r k e l e y 大学开发的一个基于事件驱 动的仿真器。它能近乎真实地模拟网络环境，可以在各个层次上模拟网络的 运行，为低成本的实验提供了一个良好的环境，能够方便地对已有的协议行 为进行验证，比较使用不同的算法对网络性能造成的影响“o 】。 1 3 1n s - 2 简介 n s 一2 是面向对象的，基于离散事件驱动的网络环境模拟器它实现了多 种网络协议的模拟，如传输层的t c p 、u d p 协议，应用层的f r l 、t e l n e t 、 w e b 协议，同时还实现了d r o p - t a i l 、r e d 等几种路由器队列管理机制以及动 态路由、静态路由、组播路由等路由算法此外，n s - 2 还支持组播协议s r m 及部分m a c 层的协议。n s 一2 用c + + 和o t c l 语言编写而成。它的一个突出的 优点就是它的源代码全部公开，提供开放的用户接口，并且容易扩展、配置， 用户可以很方便地将自己开发的新协议模块集成到n s 一2 环境中。 n s 一2 网络仿真的主要原理如下； 1 离散事件仿真器 n s 是一个离散事件仿真器。离散事件模拟，是几种常用的系统模拟模型 之一简单地说，事件规定了系统状态的改变，状态的修改只在事件发生时 6 哈尔滨工程大学硕士学位论文 进行在一个网络模拟器中，典型的事件包括分组到达、时钟超时等。模拟 器所做的就是不停地处理一个个事件，直到所有的事件都处理完成或者某一 特定的事件发生为止。n s 中有一个“调度器”( s c h e d u l e r ) 负责记录当前时 间，调度网络事件队列中的事件，并提供函数产生新的事件，指定事件发生 的时间。 2 具有丰富的构建库 n s 构件库支持的网络类型包括广域网、局域网、移动通信网、卫星通信 网等；流量产生模型有t d n e t 流量模型、f t i 流量模型、c b r 流量模型、实 时音频流量模型、r t p 模型、w e b 流量模型、指数分布流量模型、p a r e t o 分 布流量模型等：跟踪监测包括包类型、队列监测和流监测；路由模型有点到 点传播路由、组播路由、网络动态路由、层次路由。由于n s 具有的开放性， 网络研究人员可以根据自己的需要添加各种协议，满足自己的研究需要。 3 分裂对象模型 n s 构件一般都是由相互关联的两个类来实现，一个在c + + 中，一个在 o t c l 中。这种方式称为分裂对象模型。构件的主要功能在c 斗+ 中实现，o t d 中的类用来提供c + + 对象面向用户的接口。通过这种机制，用户可以在c + + 中直接调用o t c l 解释器的功能，o t c l 和c h 能够互相直接操作对方定义的数 据。用户先通过编写c + + 程序来描述链路中的算法和增加各种网络协议，再 使用o t c l 脚本来描述需要仿真的场景、拓扑结构、链路中使用的算法和协议， 并对这些对象进行配置、组合，最后调用n s 来完成仿真。 1 3 2n s - 2 的层次结构 n s 一2 采用了两级体系结构，为了提高代码的执行效率，n s 一2 将数据操 作与控制部分的实现相分离，事件调度器和大部分基本的网络组件对象在后 台使用c + + 实现和编译，称为编译层，主要功能是实现对数据包的处理；n s 一2 的前端是一个o t c l 解释器，称为解释层，主要功能是对模拟环境的配置、建 立。从用户角度看，n s 一2 是一个具有仿真事件驱动、网络构件对象库和网络 配置模块库的o t c l 脚本解释器。n s - 2 中编译类对象通过o t c l 连接建立了与 之对应的解释类对象，这样用户可以在o t c l 空间能够方便地对c + + 对象的函 数和变量进行修改与配置，充分体现了仿真器的一致性和灵活性 7 哈尔滨工程大学硕士学位论文 图1 3 中显示了n s 的模拟体系结构。n s 用户写出t c l 脚本程序，可以 通过o t c l 了解脚本情况，也可以直接提交给n s 系统，n s 调用t c l c l ( t c l c o m p i l el a n g u a g e ) 对脚本语言进行解释，然后n s 的事件调度机制以及构件 库被调用执行。 通常情况下，模拟器模拟工作的开始，就是通过创建一个s h n u l a t o r 类的 实例后开始的。s i m u l a t o r 类可以看成是对整个仿真器的封装，含成员类n o d e 、 l i n k 、a g e n t 、p a c k a g e 、l a n 等。 e v e n ts c h e 眦t e r n g 一2 1 色l c l 0 忙l 耋菱 t e l 8 o i l 图1 3n s 一2 的体系结构 从创建一个仿真器的实例对象开始，通过这个仿真器调用各种方法生成 节点，进而构造拓扑图，对仿真的各个对象进行配置，定义事件，然后根据 定义的事件，模拟整个网络活动的过程。在创建模拟器对象时，在构造函数 中同时也创建一个该模拟器的事件调度器( e v e n ts c h e d u l e r ) ，用来调度当前事 件链中的仿真事件。 仿真器封装了许多功能模块，最基本的是节点、链路、代理、数据包格 式等等。下面分别是这些模块的解释。 1 事件调度器( e v e n ts c h e d u l e r ) 由于n s 一2 是基于事件驱动的，调度器也就成为n s 2 的调度中心，它可 以跟踪仿真时间，调度当前事件链中的仿真事件并交给产生该事件的对象处 理。目前n s - 2 提供了四种具有不同数据结构的调度器，分别是链表、堆、 日历表和实时调度器。 2 节点( n o d e ) 节点是由t e l o b j e c t 对象组成的复合组件，在n s 一2 中可以表示端节点和 8 哈尔滨工程大学硕士学位论文 路由器。每个节点具有唯一的地址( i d 标识) ，节点有单播节点和组播节点 两种不同类型，通过节点内部的n o d e t y p e 变量来区分，n s - 2 中默认的是单播 节点。节点为每一个连接到它的业务源分配不同的端口，用于模拟实际网络 中的端口。另外，节点有一个路由表以及路由算法。由地址分类器根据目的 地址转发数据包。 3 链路( l i n k ) 链路由多个组件复合而成，用来连接网络节点。所有的链路都是以队列 的形式来管理分组的到达、离开和丢弃。在链路中增加了t r a c e e n q t 、 t r a c e d e q t 、t r a c e d r p t 以及t r a c e r r e c v t 等对象可以跟踪每个数据包到达、 进入、离开队列以及被丢弃的时间，还可以用队列监视器( q u e u e m o n i t o r ) 来监测队列长度和平均队长的变化情况。 4 代理( a g e n t ) 负载网络层分组的产生和接收，也可以用在各个层次的协议实现中。 a g e n t 类包含源及目的节点地址、分组类型、大小、优先级等状态变量，并利 用这些状态变量来给所产生的分组的各个字段赋值。每个a g e n t 连接到一个 网络节点上( 一般是端节点) ，由该节点给它分配一个端口号。a g e n t 是实现 u d p 协议及各种版本t c p 协议的基类。 5 包( p a c k e t ) 包由头部和数据两部分组成。头部包括。响h e a d e r 、i ph e a d e r 、t c ph e a d e r 、 n ph e a d e r 及t r a c eh e a d e r 等，其中最常用的是通用头结构c o r nh e a d e r ，该头 结构中包含一个唯一的标识符、包类型、包的大小以及时间戳等。头结构的 格式是在仿真器创建时被初始化的，各头部的偏移量也被记录下来。在a g e n t 产生了一个包之后，所有的头部都同时生成，用户能够根据偏移量来存取各 头部所包含的信息。数据部分携带通信双方索要交换的信息。在实验的过程 中，一般情况下，p a c k e t 只有头部、没有数据部分，指向数据空间的指针为 n u l l ，因为在非实时地模拟中携带真实数据是没有意义的。 1 3 3 网络模拟的方法和过程 ， 进行模拟前，首先要分析模拟涉及哪个层次。n s 一2 模拟分两个层次：一 个是基于o t c l 编程的层次，利用n s 一2 己有的网络元素实现模拟，无需对n s 一2 9 哈尔滨工程大学硕士学位论文 本身进行任何修改，只要编写o t c l 脚本；另一个层次是基于c + + 和o t c l 编程 的层次，如果n s 一2 中没有所需的网络元素，就需要首先对n s 一2 扩展，添加 所需要的网络元素。这就需要利用前面所提到的分裂对象模型，添加新的c + + 和o t c l 类，然后再编写0 l c l 脚本。这个模拟过程如图1 - 4 所示。 图1 4 利用n s - 2 进行网络模拟的过程 假如已经完成了对n s 的扩展，或者n s 所包含的构件已经满足了要求， 那么进行一次模拟过程如下： 1 编写o t c l 脚本，配置模拟网络拓扑结构，确定链路的基本特性。 2 建立协议代理，包括端设备的协议绑定和通信业务量模型的建立。 3 配置业务量模型的参数，从而确定网络的上业务量分布。 4 设置t r a c e 对象。t r a c e 对象能够把模拟过程中发生的特定类型的事件 记录在t r a c e 文件中。n s - 2 通过t r a c e 文件来保存整个模拟过程。仿真完成后， 用户可以对t r a c e 文件进行分析研究。 5 编写其它的辅助过程，设定模拟结束时间，至此o t d 脚本编写完成。 6 利用n s 一2 解释执行刚才编写的o t c l 脚本。 7 分析t r a c e 文件，得到有用的数据，也可以使用n a m 等工具观看网络 模拟运行过程。 8 调整配置拓扑结构和业务量模型，重新进行上述模拟过程。 1 4 本文内容安排 本论文在第1 章绪论中，已经介绍了网络拥塞、拥塞发生的原因、拥塞 控制以及拥塞控制的意义，还对网络仿真软件进行了简单介绍，说明了网络 哈尔滨工程大学硕士学位论文 仿真的一般方法和过程。论文后面的章节安排如下： 第2 章主要介绍t c p 基于滑动窗口的端到端的拥塞控制机制和当前口 层的各种拥塞控制策略，包括t c p 拥塞控制的核心算法，典型的璎拥塞控制 算法，以及各种t c p f l p 拥塞控制算法的优缺点，并对t c p 拥塞控制算法和 m 拥塞控制算法进行了比较。 第3 章着重介绍了r e d 基本原理及算法实现，r e d 算法参数选择的一 般规律，对r e d 算法的改进方案a r e d 、s r e d 和b l u e 算法进行了简单的 介绍，并对各算法特点进行了比较。 第4 章分析了r e d 算法在丢失概率计算上存在的局限性，对算法中丢失 概率的计算方法进行了改进，用一种指数的非线性关系来计算丢弃概率，降 低了丢包率，提高了网络的链路利用率，并且对r e d 算法的公平性进行了研 究，通过占用带宽过高的数据流的限制，在一定程度上保证了网络的公平性。 结论总结了本文的研究工作，并对未来的进一步研究进行了展望。 哈尔滨工程大学硕士学位论文 第2 章t o p ip 拥塞控制策略 2 1 t o p 拥塞控制机制 在源算法中，目前使用最广泛的是t c p 协议中的拥塞控制算法。i n t e m e t 上9 0 的数据流使用的是t c p 协议，t c p 是目前在i n t c m e t 中使用最广泛 的传输协议。所以，t c p 拥塞控制算法已成为保证h t e m e t 正常运行的重要 因素。 t c i 拥塞控制中以下几个重要的参数：拥塞窗口( c w n d ) 、通知窗口 ( a w n d ) 、慢开始门限( s s t h r e s h ) 、往返时延( r t t ) 、超时重传时间( r t 0 ) 。 拥塞窗口是发送端根据自己估计的网络拥塞程度而设置的窗口值，是 来自发送端的流量控制。 通知窗口又称接收窗口，是接收端根据其目前的接收缓存大小所许诺 的最新的窗口值，是来自接受端的流量控制，通过t c p 报文首部中的窗口 字段，传送给发送端。 慢开始门限是为了防止拥塞窗口的增长引起网络拥塞而设置的，当拥 塞窗口超过慢开始门限时，从慢启动阶段进入到拥塞避免阶段，初始值设 为6 5 5 3 5b y t e s 或a w n d 的大小。 往返时延是一个数据包从发送端发出的时间与收到相应确认数据包的 时间之差。 超时重传时间是指数据包从发送到失效的时问间隔，发送端以此来判 断数据包的丢失和网络的拥塞，通常设为2 i r r r 或5 r 1 r r “。 2 1 1t o p 拥塞控制算法 t c p 协议是基于窗口的端到端的拥塞控制机制。这种机制主要是基于 1 9 8 8 年v a n j a c o b s o n 提出的“慢开始”算法、“拥塞避免”算法和1 9 9 0 年出现的t c pr e 版本增加的“快速重传”算法、“快速恢复”算法“”。 为了避免网络数据的突发性导致网络拥塞、报文的丢失，t c p 中设置 哈尔滨工程大学硕士学位论文 了拥塞窗口机制。t c p 拥塞控制的四个阶段分别为： 1 慢启动阶段 当主机开始发送数据时，如果立即将较大的发送窗口中的全部数据字 节都注入到网络中，那么由于此时不了解网络的状况，因而可能引起网络 拥塞经验证明，较好的方法是试探一下，即由小到大逐渐增大发送端的 拥塞窗口数值。通常在刚刚开始发送报文段时可先将拥塞窗口c w n d 设置为 一个最大报文段m s s 的数值。而在每收到一个对新的报文段的确认后，将 拥塞窗口增加至多一个m s s 的数值。用这样的方法逐步增大发送端的拥塞 窗口e w n d ，可以使分组注入到网络中的速率更加合理。慢启动算法为每个 连接设置两个变量：c w n d 和s s t h r e s h ，在一开始，发送端先设置e w n d = l ( 缺 省为5 1 2 或5 3 6b y t e s ) ，发送端按c w n d 大小发送数据，每收到一个a c k 确认，e w b d 就增加一个数据包发送量，这样e w n d 就将随着回路响应时间 l 盯r 呈指数增长，发送端向网络发送的数据量将急剧增加。事实上，慢启 动算法并不是指e w n d ，的增长速率慢。但即使e w n d 增长的很快，和一开 始就将e w n d 设置为较大的数值相比，使用慢开始算法可以是发送端在开始 发送时向网络注入的分组数大大减小，对防止网络拥塞是个非常有力的措 施。 2 拥塞避免阶段 如果t c p 连接的发送端发现超时或收到3 个相同的a c k 副本时，即认 为网络发生了拥塞( 主要因为由传输引起的数据包损坏和丢失的概率很小 c l ) 。此时就进入拥塞避免阶段，慢开始门限设置为当前拥塞窗口大小 的一半；如果超时，拥塞窗口被置1 ；如果c w n d s s t h r e s h ，t c p 就执行拥 塞避免算法，此时，c w n d 在每次收到一个a c k 时只增加1 c w n d 个数据包， 这样，在一个r t t 内，c w n d 将增加l ，所以在拥塞避免阶段，c w n d 不是呈 指数增长，而是线性增长。无论在慢开始阶段还是在拥塞避免阶段，只要 发送端发现网络出现拥塞，就要将慢开始门限s s t h r e s h 设置为出现拥塞时的 发送窗口值的一半( 但不能小于2 ) 。这样设置的考虑就是：既然出现了网 络拥塞，那就要减少向网络注入的分组数。然后将拥塞窗口c w n d 重新设置 为l ，并执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中 的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完 毕。 1 3 哈尔滨工程大学硕士学位论文 在g e n o t c p 版本中，慢启动和拥塞避免算法一起实现，算法描述如下： 初始化：c w n d = l ； s s t h r c s h = 6 5 5 3 5b y t e s ： w i n = r a i n ( c w n d ，a w n d ) ； 有新的a c k 确认到达时，执行下列算法： f o re v e r ya r r i v e dp a c k e t s i f ( c w a d 3 ) ，将c w n d 设为s s t h r e s h + n * m s s 。 ( 4 ) 若发送窗口值还允许发送报文段，就按拥塞避免算法继续发送报 文段。 ( 5 ) 若收到了确认新的报文段的a c k ，就将c w n d 缩小到s s t h r c s h 。 在采用快恢复算法时，慢开始算法只是在t c p 连接建立时才使用。上 述四个算法协同工作，成为在i n t e r n c t 上使用的主要端系统拥塞控制机制。 图2 2 反映了快速重传和恢复阶段拥塞控制窗口随时间的变化情况。 窗 口 尺 寸 0 i 7 11 图2 2 快速重传和恢复阶段 2 1 2t c p 拥塞控制算法演进 t c p 解决拥塞是采用基于窗口的端到端的算法，以前主要有两种t a h o e 1 5 哈尔滨工程大学硕士学位论文 和r e n o 分别对通过重复应答所判断出的丢包现象进行不同的处理。后来随 着网络技术的发展在r e n o 算法的基础上出现t n e w - r e n o 算法“”，下面就这 几种算法做一概述。 1 t i c p t a h o e 算法 早期的t c p 实现算法是基于积极响应并通过重传超时来重发丢失的数 据，当丢包时，t c p 减小拥塞窗口，并重传被丢失的分组，然而在使网络拥 塞达到最小方面，这些算法的性能很差t c pt a h o e 参考了早期的实现方法， 并增加一些算法，包括慢启动、拥塞避免、快速重传。t c pt a h o e 还包括对 往返时间估计量的修改，这一参量的准确估计非常重要，因为它被用来设 置重传超时定时器的基值。此外t h h o e 弓l 入快速重传机制，即当接受方收到 几个对同一t c p 报文的相同应答时，发送方就推断已经发生了丢包，而没有 必要等到重传定时器超时，并且重传相应的包。这样以来提高了信道利用 率。 2 t c p r e n o 算法 r e n o 修改t a h o e 的快速重传为快速恢复( 指由三个重复应答判断有包丢 失时仅使拥塞窗口减半) ，新的算法防止通信管道在快速重传之后变空， 因而避免了慢启动在单包丢失之后重填。快速重传主要决定于收到的重复 应答数目的初始门限值( 一般设为三) 。一旦达到门限值，发送方就重传一 个包同时使拥塞窗口减半，与t a h o e 的慢启动不同r e n o 的发送方用额外到达 的应答来为后续包定时。发送方的可用窗口变为m i n ( a w n d ，c w n d + n d u p ) ， 这= 里n d u p