（控制理论与控制工程专业论文）基于遗传粒群路径优化的网络拥塞控制方法.pdf

基于遗传粒群路径优化的网络拥塞控制方法 摘要 近年来，随着网络规模和网络流量的飞速增长，网络上越来越多的是具有q o s 要求的多媒体业务。但是，传统的路由算法往往约束单一又不能充分利用现有的 网络资源，经常导致有些链路被过度使用，有些链路却空闲不用的负载不均衡局 面，从而致使网络拥塞，业务的服务质量无法得到保证。网络拥塞已成为制约网 络发展和应用的瓶颈。在这种情况下，如何在满足q o s 要求的前提下，通过路径优 化来实现网络拥塞控制是一个崭新的课题。 本文对基于遗传粒群路径优化的网络拥塞控制方法进行了研究，其主要工作 和内容如下： ( 1 ) 在对网络拥塞、拥塞控制、拥塞预防及网络路由对拥塞的影响进行分析 的基础上，给出了利用网络路径优化解决网络拥塞控制问题的思想。对网络仿真 软件n s 2 进行功能扩展，并将其应用于网络仿真中，取得了较好的效果。 ( 2 ) 对o o s 及q o s 路由进行了详细分析，在对网络拥塞分析的基础上，对网 络拥塞路径优化进行了深入地探讨，为实现网络拥塞提供了条件。 ( 3 ) 将粒群( p s o ) 和遗传算法( g 舢相结合，给出了遗传粒群优化算法。算法初 期经过了前端的p s o 优化处理，在初始种群里就有很大的概率包含最优解。随着 进化代数的不断增加，该算法能够快速找到最优解，而在算法后期采用遗传算法 引入新的个体，可以避免算法过早陷入局部最优解。从而使算法在速度和精度上 同时得到提高。将其用于解决多峰值函数优化问题中，仿真表明了该优化算法的 有效性和可靠性。 ( 4 ) 提出了基于遗传粒群路径优化的网络拥塞控制方法，该方法在满足带宽、 延迟、费用多项q o s 指标的条件下对负载进行路径优化，以负载均衡分布函数和 资源消耗函数作为优化目标，旨在消耗尽可能少的网络资源的同时，也使网络负 载的分布尽量均衡，从而避免拥塞。给出了算法实现及其仿真分析，仿真结果表 明该算法的有效性和可靠性。 关键词：遗传算法，粒群算法，q o s 路由，路径优化，网络拥塞控制 郑州大学工学硕士论文 a b s t r a c t i nr e c e n ty e a r s , w i t ht h er a p i dg r o w t ho ft h en e t w o r ks c a l ea n dt r a f f i c ，t h e r ea r e m o r ea n dm o r em u l t i m e d i aa p p l i c a t i o n s t h e yr e q u i r et h en e t w o r kt op r o v i d eq u a l i t yo f s e r v i c e ( q o s ) g u a r a n t e e s b u tt r a d i t i o n a lm u t i n ga l g o r i t h m s ，w i t hs i n g t ec o n s t r a i n c o n d i t i o n ，c a n n o tm a k ef u l lr e s o u r c eu t i l i z a t i o n ，w h i c ha l w a y sl e a dt ot h eu n b a l a n c e d t r a f f i cd i s t r i b u t i o n , s o m el i n k s g e n i n go v e r - u t i l i z e d , w h i l e o t h e r s r e m a i n i n g u n d e r - u t i l i z e d i tr e s u l t si n c o n g e s t i o na n dt h eq u a l i t yo fs e r v i c e sn o tg u a r a n t e e d n e t w o r kc o n g e s t i o nh a sb e c o m eab o t t l e n e c kw h i c hr e s t r i c t st h eg r o w t ha n da p p l i c a t i o n o ft h en e t w o r k i nt h i sc a s e ，o nt h eb a s i so fs a t i s f y i n gq o sr e q u e s t s ，h o wt or e a l i z e n e t w o r kc o n g e s t i o nc o n t r o lb yo p t i n l i z i n gn e t w o r kp a t hi sab r a n d n e wr e s e a r c hs n b j e c t t h i st h e s i sm a i n l yf o c u s e so nt h er e s e a r c ho fn e t w o r kc o n g e s t i o nc o n t r o lm e t h o d b a s e do ng a p s op a t ho p t i m i z a t i o na l g o r i t h m t h em a i nc o n t e n t sa r ea sf o l l o w s ： ( 1 ) b a s e do nt h ea n a l y s i so fn e t w o r kc o n g e s t i o nc o n t r o l ，n e t w o r kr o u t i n ga n d q u a l i t yo f s e r v i c e a ni d e ai sp r o p o s e dt os o l v et h en e t w o r kc o n g e s t i o nc o n t r o lp r o b l e m b yu s i n gn e t w o r kp a t ho p t i m i z a t i o n t oe x t e n dt h ef u n c t i o no fn s 2a n da p p l yi ti n t o n e t w o r ks i m u l a t i o nc a ng e tab e t t e rr e s u l t ( 2 ) q o sa n dq o sr o u t i n gi sa n a l y z e di nd e t a i l o nb a s i so fa n a l y s i so fn e t w o r k c o n g e s t i o nc o n t r o l ，ad i s c u s s i o ni sm a d ei nt h ep a p e rt oa c h i e v en e t w o r kc o n g e s t i o n ( 3 ) ag a p s oa l g o r i t h mi sp r e s e n t e db yc o m b i n i n gp a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h ma n dg e n e t i ca l g o r i t h m i ni n i t i a lp h a s e ，p s oa l g o r i t h mi sa d o p t e dt og e ta n e w p o p u l a t i o n t h e n , i tm a k e su s eo ft h eg aa l g o r i t h mt oo p t i m i z et h er e s u l t w i t h t h ee v o l u t i o ng e n e r a t i o n si n c r e a s e ，t h ep r o p o s e da l g o r i t h mc a ng e tt h eb e s tv a l u er a p i d l y a n dm e a n w h i l ei tc a na v o i dc o n v e r g i n ga tl o c a lb e s tv a l u e a l s o ，i ti m p r o v e si n c o m p u t i n gs p e e da n dp r e c i s i o n a p p l y i n gi t i nt h ep r o b l e mo fm u l t i - f i e a kf u n c t i o n o p t i m i z a t i o n ，s i m u l a t i o nr e s u l t sd e m o n s t r a t et h ev a l i d i t ya n df e a s i b i l i t yo ft h ep r o p o s e d a l g o r i t h m ( 4 ) an e t w o r kc o n g e s t i o nc o n t r o lm e t h o di sp u tf o r w a r db a s e do ng a p s op a t h o p t i m i z a t i o n t h cm e t h o do p t i m i z e st h ep a t ho fn e t w o r kl o a da n dm a k e sn e t w o r k1 0 a d b a l a n c i n ga n di c s o u r c ec o n s u m p t i o na sa i mf u n c t i o nt oa v o i dc o n g e s t i o nb yb a l a n c i n g t h el o a da n dm i n i m i z i n gn e t w o r kr e s o u r c ec o n s u m p t i o ni nt h ec o n d i t i o no fm e e t i n g b a n d w i d t h ，d e l a ya n dc o s tc o n s t r a i n s a l g o r i t h mr e a l i z a t i o n a n ds i m u l a t i o na r e ： p r e s e m e di nt h ep a p e r n 壕s 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 mi se f f e c t i v ea n d n 茎王望生垫登坠丝垡丝盟壁丝垫童堡型壅鎏：一 r e l i a b l e k e yw o r d sg e n e t i ca g o f i t u i l ，p a r t i c l es w a l l l lo p t i m i z a t i o na l g o r i t h m ，q o sm u t i n g , n e t w o r kc o n g e s t i o nc o n t r o l ，p a t ho p t i m i z a t i o n i l l 基于遗传粒群路径优化的网络拥塞控制方法 1 1 引言 1 绪论 近年来，网络技术的日新月异，多媒体技术的飞速发展，以m 为基础的i n t e r a c t 已经逐渐发展成全球性的信息基础设施，其应用领域不断拓展，应用模式不断丰 富。人们不但可以通过网络传送邮件和发送文档，还享受着视频聊天、视频会议、 网络电视、在线点播和网络游戏等等丰富多彩的网络业务。网络中传输的不再是 单纯的文本数据，而是包括数据、声音、视频、图形和图像等的各种信息流。多 种服务要求、多种数据类型流的混合存在，加之用户数目在爆炸式增长，网络服 务模式不断丰富，网络规模日趋巨大，因而网络环境会变得越来越复杂。 在网络通信中，拥塞容易造成延迟和吞吐量等性能指标的下降，是影响缓存、 带宽等网络资源利用率的关键因素。网络拥塞已经成为制约网络发展和应用的一 个瓶颈，如何更好地预防和控制拥塞一直是近年来网络研究的热点问题i l 叫。 1 2 网络拥塞与拥塞控制 网络中当存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞1 3 j ， 是一种持续超载的网络状态。拥塞导致的直接后果是分组丢失率提高，端到端时 延加大，甚至有可能使整个系统崩溃。当网络处于拥塞崩溃状态时，微小的负载 增量都将使网络的有效吞吐量急剧下降。 我们可以进一步用图1 1 来刻画负载与吞吐量之间的关系：负载较小时，吞吐 量与网络负载之间呈线性关系；到达膝点( k n e e ) 之后，随负载的增加，吞吐量的增 量逐渐变小；网络负载继续增加，当超过崖点( c f f ) 之后，网络吞吐量开始急剧下 降。通常将k n e e 点附近称为拥塞避免区间；k n c c 和a i f f 间是拥塞恢复区间；而 a i f f 之外是拥塞崩溃区间。从图1 1 可以看出，网络负载在k n e e 附近时，网络的 使用率最高州。 网络产生拥塞的根本原因是用户( 或叫端系统) 提供给网络的负载大于网络资 源容量和处理能力，表现为数据包延时增加、丢弃概率增大、上层应用系统性能 下降。对网络的大量研究表明，造成目前网络拥塞的直接原因主要有两个p j ：一个 是网络的资源( 如缓存空间不足、通信信道带宽容量不足、处理机处理能力等) 有 郑州大学工学硕士论文 吞 i 址 餐 隧络贫凌 图1 1 网络负载与吞吐量的关系 f i g u r e1 1t h er e l a t i o n s h i po f n e t w o r kl o a da n dt h r o u g h p u t 限，不能满足用户流量的需求【6 】；另一个是资源分布的不均衡。拥塞总是发生在网 络中那些资源“相对”短缺的位置，而拥塞发生在地理上的不均衡性反应了 i n t e r n e t 的不均衡性。i n t e r n e t 中的不均衡性首先体现在资源分布的不均衡。这 些资源包括链路带宽、网关中的缓存和网关中的处理能力等。 所谓的拥塞控制就是网络节点采取措施来避免拥塞的发生或者对拥塞的发生 做出反应。使用图1 1 来说明，拥塞控制的目标就是使网络在k n e e 附近工作。必须 具备灵活高效的拥塞检测、预防与控制机制，才能保证网络运行效率，保证网络 的鲁棒性，同时又牵涉到网络运行的经济性，因此对网络拥塞控制的研究具有重 要的意义。 网络拥塞控制主要考虑了发送端和接收端之间的网络环境，它的目的是保证 网络中的数据不超过网络的传送能力，避免出现图1 1 中网络性能严重下降的情况。 网络拥塞控制策略包括拥塞避免和拥塞控制这两种不同的控制机制【_ 7 1 。拥塞避免是 “预防”机制，它的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低 延迟的状态下拥塞控制是“恢复”机制，它用于把网络从拥塞状态中恢复出来。 在当前所使用的大多数低速网络中，当一个节点发生拥塞时，一般的解决方 法是该节点将拥塞消息通过信令信道传送给周边节点，接到拥塞节点消息的各个 节点将减少转发到拥塞节点的报文数量，直到拥塞解除。这种控制被称为反映性 控制。这种方法偏重于在网络发生拥塞以后再进行控制。因此，与其说这是一种 控制方法还不如说这是一种补救方法。这种方法在低速网络中是适用的，因为在 低速网络中，信息传输速率比较低，因此即使有大量的突发信息，单位时间内到 达网络中某一节点的信息量也是比较少的，所以该节点有足够的时间要求相邻节 点减少向该节点的报文发送量，并在此基础上消除拥塞。 但在高速网络中此方法不再适用。高速t c p f l p 网络中信元的高速传输，在网 2 基于遗传粒群路径优化的网络拥塞控制方法 络正常的传输过程中，单位时间内到达每一节点的信元数都是很大的，如果在有 突发信息存在的情况下，则处在v c 上的相应节点必定承受巨大的信息流压力，一 旦发生拥塞，在极短的时间内就可能使整条v c 上的所有节点都处于拥塞状态，并 迅速传染给网络中的其它节点。这势必会使网络的吞吐能力大幅下降，信元的传 递时间极大的延长，而导致大量的信元被丢弃，甚至有可能导致网络的崩溃。因 此，在高速t c p 口网络中拥塞预防的意义要远远大于拥塞恢复。甚至从某种角度 上说，在高速t c p i p 网络中，传统意义上的拥塞恢复是不可能实现的。一个已经 进入拥塞状态的节点没有充足的时间与带宽要求向其发送信元的相邻节点减少信 元的发送量。由此可见，拥塞的预防在高：i 塞t c p i p 网络中显得尤为重要。 拥塞预防策略的思想是在一开始就将发生拥塞的可能性降到最低，而不是任 其发生，然后再对其进行反应1 8 j 。他们试图通过在不同级别使用适当的策略来达到 这一目的。表1 1 列出了影响拥塞的各种数据链路、网络和传输策略。 表1 1 影响拥塞的策略 t a b 1 1s t r a t e g i e si n f l u e n c i n gc o n g e s t i o n 层策略 传输重发策略 乱序缓存策略 确认策略 流量控制策略 超时终止策略 网络子网内虚电路与数据报 分组排队和服务策略 分组丢弃策略 路由选择算法 分组生命期管理 数据链路重发策略 乱序缓存策略 确认策略 流量控制策略 从数据链路层开始，重传策略处理发送者的速度多块会超时，以及超时后传 送什么。太快的发送者如果使用退后的帧来重传所有分组，那么这对网络造成的 载荷比一个使用选择重发方法的慢速发送者大得多。与此紧密相连的是缓存策略。 塑型查兰：! ：兰堡主丝兰 如果只是机械地丢弃所有乱序的分组，这些分组将不得不重传，造成额外的载荷。 确认策略也会影响拥塞，如果每个分组都要立即确认，确认分组将造成额外 的通信量。但是。如果将确认保存起来，以便被别的反向分组捎带，又可能造成 不应该的超时和重传。一个紧凑的流量控制方案( 例如，一个小窗口) 能降低数 据传输速率，进而减少拥塞。 在传输层，与数据链路层类似，只是决定超时间隔更困难。因为在网络上的 传输时间比在两个路由器间的传输时间更难预测。如果时间间隔太短，会产生一 些不必要的额外分组；如果太长，拥塞会减少，但一旦分组丢失，反应时间太长。 在网络层，虚电路和数据报之间的选择会对拥塞产生影响。因为很多拥塞控 制算法只用于虚电路子网。分组排队和服务策略关系到是否为路由器的每条输入 线路建立一个队列，每条输出线一个队列，或者两者兼而有之。它还关系到分组 的处理顺序( 如，循环排序或基于优先级) 。丢弃策略说明当没有剩余空间时， 哪些分组被丢弃。好的策略能减缓拥塞，坏的策略使它更糟。 路由选择算法能通过将通信量分散到所有线路上来避免拥塞，而坏的路由算 法会将过多的通信量发送到本来已经拥塞的线路上。生命期策略管理决定一个分 组在丢弃前能存活多长时间。如果生命期太长，丢失的分组可能会长时间地阻碍 工作；但如果太短，分组又可能在到达目的地之前就超时，由此导致重传。 1 3 网络路径优化方法概述 1 3 1 传统的网络路径优化问题 在网络中需要依据网络当前的可用资源状况及业务流本身的要求，来为业务 流选择合理的路径。这就需要一种好的路由算法来实现。在当前的i p 网络中，通常 使用的路由算法，如o s p f i 们、i s i s 1 0 l 等，提供的是一种可达性服务，只要确认网 络可以连通到接受方即可，而不考虑数据包何时到达或是否能到达接受方( 中间 的路由器可能因拥塞导致数据包丢失) ，传统的路由算法通常从节省网络资源消 耗出发，采用的是基于目的地址的最短路径路由，即选择到目的地址度量( 距离、 跳数、代价等) 最短的一条路径。 最短路径路由实现起来非常简单，但在这种选路方式下，所有到达同一目的 的i p 地址的数据包所经过的路径都是相同的，会带来以下问题： ( 1 ) 当来自不同源端的多条路径都使用一条链路时，该链路将发生拥塞。 ( 2 ) 当源端到目的端间业务流超过最短路径上的链路容量时，最短路径将发 生拥塞，而他们之间较长的路径却被闲置。 董三望堡塾登坠丝垡些塑竖竺塑至篓! ! 查鎏 为了对最短路径造成的负载不均衡进行改善，后来在o s p f 中提出等价多路径 ( e c m p ，e q u a lc o s tm u l t i p a t h ) i z 】的方法，但对负载分布的调节作用是非常有限 的。在传统的最短路径算法中，如果到目的节点存在两条或多条最短路径，算法 只选择其中的一条。e c m p 对此作了修改。如果存在多条代价相等的最短路径，那 么多条路径都将被选择，负载在它们之间均匀分配。这样可在一定程度上解决第 二个问题，一定程度上均衡负载分布，却无法解决第一个问题，特别是在网络拓 扑复杂时。同时，e c m p 要求每条代价相等的最短路径承担均额的负载，而非依据 每条路径的拥塞情况动态修改这些路径间负载分配的比例，且不周代价的路径不 能分担。当多个业务流都经过某路径时，该路径负载比代价不同的其他路径高而 造成拥塞。 传统的路由算法之所以造成拥塞，其中的一个原因是选择路径时没有考虑网 络当前的可用资源状况及业务流本身的要求，只是根据业务流要去往的目的节点 选择度量值( m e t r i c ) 最小的一条路径。目前网络中使用的是静态度量，不能反应 网络可用资源的当前情况。这样在传统路由算法作用下，多个业务流经网络传输 时，它们将争夺网络资源的使用。如在一段时间内数据包的到达率超过了资源的 处理能力，网络将发生拥塞。拥塞导致到达数据包的延迟甚至丢失，从而将增加 整个传输过程的传输时延、时延抖动、丢包率，降低对用户的服务质量以及网络 服务的可预见性。 在上一节中我们分析了目前网络拥塞的原因，这里我们关心的拥塞是长时间 的拥塞，而不是由突发流量造成的短时间的拥塞。针对资源不足这个原因，通常 采用下边两种途径解决： ( 1 ) 网络扩容。指使用更加先进的交换机、路由器或采用更高带宽的传输媒 介，这种方法是先简单，但往往造价不菲。 ( 2 ) 使用经典的拥塞控制技术。包括速率限制、窗口控制、路由器队列管理 等 针对第二个原因，由负载分布不均衡引起，单靠增加网络容量，不经济也不 是根本的解决方法，本文将从路径优化的角度提出一种新的路由算法，具有q o s 要求，又能优化资源利用。 1 3 2 网络路径优化研究现状 随着计算机网络应用的发展，多媒体业务的传送需要满足用户广泛的o o s 要 求。有q o s 要求的路由就是求带有多个约束条件限制的最短路径问题，是组合优 化中的n f 完全问题，近年来很多研究者都致力于该领域。 w i d y o n o 【1 21 提出蝴a c l l m a n - f o r d ( c b f ) 算法可以找到最优路径，但计算 郑州大学工学硕士论文 时间呈指数规律增长。文献 1 3 ，1 4 1 中提出了在多项式时间内得到次优解的启发式 算法和近似算法，虽然这些算法在计算时间上可能较为合理，但均不能保证所选 路由的最优性。文献【1 5 】对带宽受限时延最小路由问题求解时，首先删除所有不满 足带宽要求的链路，然后采用d i j k s t r a 算法找到一条时延最小的路径。文献 1 6 1 提出 了分布式的启发式算法解决时延受限的路由问题。但是当约束条件较多时，这类 方法实现起来非常困难。w a n g 等研究发现通过求解路由优化问题的对偶问题，可 以得到一组链路权值，使得通过s p f 算法得到的路由与求解线性规划问题得到的最 优路由一致【l ”，但需要在等价最短路径中任意分配流量，这在实际网络中是难以 实现的。 近年来，国内外许多学者利用神经网络、蚁群算法、遗传算法等智能算法来 解决n p 完全问题，并且取得了一定的成果。文献 1 8 1 中提出采用模糊逻辑方法解 决q o s 路由问题，他们将q o s 路由看成一个模糊多目标优化模型，考虑网络的负载 平衡和时延作为优化目标函数，最后采用分级的方法寻找最优解。文献 1 9 - 2 1 1 分 别将蚁群、禁忌搜索和模拟退火等智能优化算法引入q o s 路由问题中，分析了应用 智能算法所面临的关键问题并提出了合理的解决方案。文献 2 2 中吸收蚂蚁圈模 型和m m a s 模型的优点，充分利用蚂蚁算法的自适应性和随机性，探索带宽受限 情况下网络拥塞时的动态路由选择。文献 2 3 1 中针对蚁群算法在网络负载分担方面 的不足，提出了一种改进的蚁群算法。该算法在同一网络中使用多个标记的蚁群， 各个蚁群之间的外激素相互抑制，同一蚁群的外激素相互促进，从而通过减少在最 短路径上的蚁群外激素数量来实现路由的负载分担。文献【2 4 】中提出了种基于蚂 蚁算法的拥塞规避路由算法。该算法加速了蚂蚁路由算法探索最优路径的过程， 并且能够对链路的拥塞状态做出快速反应，分散流量，以避免链路的拥塞。 遗传算法已经被证明是一种解决优化问题的有效工具p j 。这方面的研究很多， 例如文献 2 6 1 提出了一种基于遗传算法的q o s 路由算法。他们选择带宽、时延、丢 包率及时延抖动作为选路时的尺度，利用遗传算法找到满足这些q o s 参数的路径。 文献 2 7 1 提出一种优化网络资源利用的q o s 路由选择的遗传算法，在考虑网络带 宽、时延的基础上，将资源利用函数和网络负载分布作为目标函数利用遗传算法 求出最优值，以达到所选路径消耗较少的网络资源并使负载尽量均衡分布的目的。 粒群算法是一种新的智能算法，文献1 2 8 1 中改进粒子群优化算法采用了新的粒子速 度更新策略和粒子抗拥塞策略，使之成为一种解决多q o s 约束路由问题的新算法， 收敛快。文献 2 9 中提出一种融合了蚁群算法和遗传算法来解决o o s 路由选择策 略。该算法是将改进的蚁群算法与遗传算法相结合，在蚁群算法中加入遗传变异 的进化过程，从而提高了算法的寻优效率。文献 3 0 描述了种适应于研究q o s 多播路由的网络模型，提出了基于遗传算法和禁忌搜索混合策略的具有多q o s 约束 的多播路由算法。该算法充分利用了遗传算法和禁忌搜索的优点，提高了搜索效 基于遗传粒群路径优化的网络拥塞控制方法 率。仿真实验各算法都有各自的优缺点，如何实现优势互补，得到更好的效果， 是个值得研究的课题。 1 4 仿真工具n s 2 简介 1 4 1 网络仿真软件n s 2 介绍 由于网络的复杂性和高度动态性，因此进行网络仿真是一项非常复杂的工作。 而且随着网络的不断发展，也不断地提出新问题，而对于新问题的解决方案，如 提出的新协议、新算法等，除了在理论上的分析和证明之外，大多还需要进行实 验验证，然后才能考虑在实际网络中的应用。n s 2 ( n e t w o r ks i m u l a t o r ，v e r s i o n 就是一个非常优秀的口网络仿真软件，也是目前使用最广泛的仿真软件。 n e t w o r ks i m u l a t o r 网络仿真软件是位于美国加州的l a w r c n c e ! b e r k e l e y 国家实 验室于1 9 9 8 年开始开发的软件，简称n s 软件。n s 是一种可扩展、易配置和编程的 事件驱动网络仿真工具p 1 1 ，而且是一种免费的开放源代码的软件模拟平台。n s 从 s k e s h a v sr e a i 仿真器发展而来。1 9 9 5 年，n s 得到了d a p r a 的支持，发生了实质 性的演进，通过v i n t ( v i r t u a li n t e r n c t w o r kt c s t b e d ) 项目的支持，由l b lx e r o x p a r c ，u c b 和u s c i s i 合作进行。目前n s 开发由d a p r a 的s a m a n 项目和n s f 的 c o n s e r 项且支持。n s 具有开放的结构和良好的可扩充性，从其它研究者那里吸 收了很丰富的模块。它能近乎真实地模拟网络环境，可以在各个层次上模拟网络 运行，可运行在l i n u x 、u n 奴、s o l a r i s 、w i n d o w s 等平台上供研究人员进行二次研 发，为低成本的实验提供了一个良好环境，能够方便地对已有的协议行为进行验 证，比较使用不同的算法对网络性能造成的影响。本文的仿真试验就是通过该软 件完成的。在l i n u x 平台上可以直接安装p 2 1 ；若在w i n d o w s 平台上则需安装一个 l i n u x 的仿真平c y g w i n ，然后再在c y g w i n 中安装n s 2 。目前n s 的最高的主版本是 n s 2 ，最新的次版本号是n s 2 3 1 。源文件及安装文档可以从官方网站 3 2 j 免费下载。 1 n s 2 软件组成及特点 n s 2 用c + + 和o t c l 语言编写而成，它实现了多种网络协议的模拟，如传输层的 t c p 、u d p 协议，应用层的f r p 、t e l n e t 、w c b 协议；实现t d r o p t a i l 、r e d 、s f q 等几种路由器队列管理机制以及d i j k s t r a 、动态路由、静态路由、组播路由等路由 算法。此外，n s 2 还支持组播协议s r m 及：部分m a c 层的协议。n s 2 的源代码完全 公开，且提供开放的用户接口，用户能够方便地对c + + 对象的函数和变量进行修改 与配置，将自己开发的新协议模块集成到n s 2 环境中，充分体现了仿真器的一致和 灵活性。 郑州大学工学硕士论文 完全的n s 2 ( n s 2 的a l l i n o n e 包) 包含1 1 个模块，如图1 2 所示，分别为t d 、t 1 【、 o t c l 、t c l c l 、n s 、n a m 、x g r a p h 、g t - i t m 、s g b 、c w e b 、2 ；1 i b 。其中t c l 模块和t k 模块一起构成了一套开发系统应用程序和图形用户接口接n ( g u i ) 应用程序环境； o t c l 是o b j e c t t c l 的简称，是t c l 语言面向对象的扩展；t c l c l 模块包含t c l c + + 的接口； n s 是n s 2 的核心代码模块，是面向对象的仿真器，用c + + 编写，以0 1 c l 解释器作为 前端：t c l c 坝0 提供n s 和o t c l 的接口，使对象和变量出现在两种语言中；n a m b p n e t w o r ka n i m a t o r ，与n s 协同工作，将n s 仿真过程动态表现出来；x g r a p h 是 x - w i n d o w 应用程序，主要用于仿真结果的图形绘制；g t i t m 产生模拟i n t e r n c t 网络 结构的拓扑图；s g b 是图形产生器；c w e b 模块是与网页相关的工具：z l i b 是通用数 据压缩库。图中，方框里为n s 的模块，方框外的s c r i p t 为我们写的脚本文件。i i s 解释脚本，将输出写到输出文件中，然后调用n a m 或x g r a p h 显示输出文件。仿真所 得到的数据通过后台处理，得到网络性能评价指标如吞吐量、时延、丢包率等等。 图1 2n s 模块示意图 f i g 1 2a r c h i t e c t u r eo f n s n s 2 软件与平台无关，开源的，有大量的协议、代码以及模型可供使用，不同 的协议间容易比较。此外，它还有如下优点： ( 1 ) 基于离散事件驱动的仿真方式，仿真效率高； ( 2 ) 面向对象的建模方式，易于对现实网络进行建模； ( 3 ) 真实网络交互，允许将实际网络流量导入到网络仿真环境，这样在某种 程度上起到类似测试床的作用，从而可以在一个接近真实的环境下，测试协议的 性能： ( 4 ) n s 2 与n a m 软件结合，能够动画显示仿真结果： ( 5 ) 使用两种语言c + + 和o t c l 编写代码，兼顾效率和灵活性。对于需要涉及处 理字节、分组以及大量数据集的算法操作，且不会频繁修改的任务，使用编译型 8 基于遗传粒群路径优化的网络拥塞控制方法 语言c + + 来编写：而对于需要频繁的修改协议对象的配置和数据流的配置，脚本解 释性语言o t c l 修改起来很快，而且是交互的，便于多次模拟配置； ( 6 ) 具有支持多重协议、网络传输详细的图表描述的能力。 n s 2 的不足是对卫星网络提供的支持有限，另外还存在一些b u g ，有些方面的 功能还有待进一步完善，如对卫星网络的无线链路支持还不完善，当开发路由算 法时，用户需要较大的工作量来修改各种链路接口的定义。 1 4 2n s 2 在网络研究中的应用 1 n s 2 的仿真工作机制 进行模拟前，首先要分析仿真涉及哪个层次。n s 2 模拟分两个层次：一个是基 于o t c l 编程的配置、构造层次，利用n s 已有的网络仿真元素实现仿真，无需对n s 本身迸行任何修改，只要编写o t c l 仿真脚本；另一个层次是基于c + + 和o t e l 编程的 编译、配置层次，若n s 中没有所需的仿真元素，n s 提供用户自我升级或修改协议 的技术，即添加新的c + + 和o t c l 类，实现n s 的更新( 如图1 3 虚框内) ，然后再编 写o t c l 脚本。整个仿真过程如图1 3 所示。 图1 3n s 2 仿真工作过程 f i g 1 3n e t w o r ks i m u l a t i v ep r o c e s so f n s 2 通常，一次模拟过程进行如下： ( 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 c l 脚本编写完成； ( 6 ) 利用n s 2 解释执行刚才编写的o t c l 脚本； ( 7 ) 分析t r a c e 文件，得到有用的数据，用x g r a p h 分析数据，也可以使用n a m 等工具观看网络模拟运行过程。 2 n s 2 网络仿真的功能扩展与实现 已有的n s 2 软件往往不能直接提供新的协议和算法，网络研究者要不断研究新 的协议和算法，为网络的发展作前瞻性的研究分析，就需要对n s 2 的功能进行扩展， 图1 3 虚框中，一般步骤如下： ( 1 ) 定义或继承c + + 协议类； ( 2 ) 编写该类成员函数和协议算法； ( 3 ) 建立这个类在t c l 中连接类和变量； ( 4 ) 把c + + 代码绑定到t c l ，即将c + + 类中的成员变量和成员函数影射到t c l 类中； ( 5 ) 在n s d e f a u l t t e l 中为新增参数设置缺省值； ( 6 ) 重新编译i l s 。修改m a k e f i l e 文件，用m a k e 命令重新编译生成 i s e x e 文件， 则新建的对象被加入到n s 的网络组件库中，可以被用户在t c l 中调用。 在影响网络拥塞的路由选择领域，为了进行相关的仿真研究，我们需要对n s 进行功能扩展。q o s 路由的执行主要包括q o s 协商、接入控制、资源预留、数据包 缓冲与调度、路由表查找、资源管理等操作。在1 3 5 2 的仿真执行过程中，n s 2 的n o d e ( 带 点) 内嵌的a g e n t ( 代理) 自动完成数据包缓冲与调度，路由查找与资源管理。n s 2 中实际上的路由功能都是f l a g e n t 实现的。当a g e n t 绑定到每个d e 后，可以设定让 它处理每个包并进行路由操作。所以在a g e n t 中调用n f i n d o ( 执行路由发现功能的函 数1 ，将找到的o o s 路径存入路由表当中，供路由时选择。按照前述功能扩展的步 骤重新编写一个a g e n t 类，完成设想的路由功能，把文件名o 加到m a k e f i l e i n 文档中， 重新编译一下，执行c o n f i g u r e ；m a k e d e p e n d ；m a k e ，即可。 对于数据跟踪和处理问题，在参考文献 3 3 ，3 4 中，对n s 的跟踪和流监视输出 格式有详细的说明，另外也提供了对仿真结果的常用处理方法，这里我们不再赘 述。 1 5 本文的主要工作 在综合考虑已有算法的优缺点的基础上，本文将提出基于遗传粒群路径优化 的网络拥塞控制方法，目标是在满足带宽、时延、费用的基础上，将资源消耗和 负载均衡分布作为优化目标，希望在消耗较少网络资源的同时，使负载尽量分布 在有宽裕空闲资源的链路上，提高吞吐量，便于今后接纳更多的请求，达到避免 基于遗传粒群路径优化的两络拥塞控制方法 拥塞的目的。 本文对基于遗传粒群路径优化的网络拥塞控制方法进行了研究，所做的主要 工作和内容如下： 第l 章绪论。在对网络拥塞、拥塞控制、拥塞预防及网络路由对拥塞的影响 进行分析的基础上，给出了利用网络路径优化解决网络拥塞控制问题的思想。对 网络仿真软件n s 2 进行功能扩展，并将其应用于网络仿真中，取得了较好的效果。 第2 章o o s 路由分析与网络拥塞路径优化。对o o s 及q o s 路由进行了详细 分析，在对网络拥塞分析的基础上，对网络拥塞路径优化进行了深入地探讨，为 实现网络拥塞提供了条件。 第3 章遗传粒群优化算法。将粒群( p s o ) 和遗传算法( g a ) 相结合，给出 了遗传粒群优化算法。算法初期经过了前端的p s o 优化处理，在初始种群里就有 很大的概率包含最优解。随着进化代数的不断增加，该算法能够快速找到最优解， 而在算法后期采用遗传算法引入新的个体，可以避免算法过早陷入局部最优解。 从而使算法在速度和精度上同时得到提高。将其用于解决多峰值函数优化问题中， 仿真表明了该优化算法的有效性和可靠性。 第4 章基于遗传粒群路径优化的网络拥塞控制方法。提出了基于遗传粒群路 径优化的网络拥塞控制方法，该方法在满足带宽、延迟、费用多项q o s 指标的条 件下对负载进行路径调度，以负载均衡分布函数和资源消耗函数作为优化目标， 旨在消耗尽可能少的网络资源的同时，也使网络负载的分布尽量均衡，从而避免 拥塞。给出了算法实现及其仿真分析，仿真结果表明该算法的有效性和可靠性。 第5 章总结与展望。简要总结了硕士论文的主要工作，包括网络拥塞控制、 o o s 路由分析、遗传粒群优化算法、基于遗传粒群路径优化的网络拥塞控制方法 等；并对该研究领域以后需要进一步深入研究的工作进行了展望。 郑州大学工学硕士论文 2 1 引言 2q o s 路由分析与网络拥塞路径优化 当前的i n t e m e t 是面向非实时的数据通信( 如f t p 和e m a i l 的传输) 而设计的， 提供的是一种“尽力而为”( b e s t e f f o r t ) 服务，数据包尽可能快地往前转发，网络 层不区分用户业务的种类，而将网络资源公平地提供给各类业务，在分组丢失、 延迟等方面公平地对待各类业务。这种尽力发送的机制使网络层无法保证对传输 的实时性和准确性。伴随高速网络技术和多媒体技术的飞速发展，诸如视频会议、 视频点播、i p 可视电话等多媒体应用在网络上逐渐流行，其多媒体传输流需要占 用极大的带宽，而且对延迟敏感，要求以无延迟网络进行传输。而传统的文件传 输业务要求分组的丢失率尽可能低，而传输延迟不是关键因素。网络带宽和数据 传输质量问题逐渐暴露出来，而且越来越严重。传统的路由选择机制只考虑连通 性，满足不了分布式多媒体应用丰富多彩的q o s ( q u l i t y o f s e r v i c e ) 需求。由此， 面向服务质量的网络体系结构应运而生。目前，计算机网络的服务质量问题已成 为国际网络研究领域最重要、最富有魅力的研究领域之一，对未来网络技术的研 究、应用和发展具有举足轻重的意义【3 “。 2 2q o s 路由分析 2 2 1q o s 的定义和度量 1 0 0 s 的定义 为了解决在i n t e r n e t 等计算机网上高质量地传输多媒体信息的问题，美国于 1 9 9 6 年底，开始了以提高网络服务质量研究为核心的n g i ( 下一代i n t e m e t ) 研究项 目。i n t e r a c t 工程特别工作组i e t f ( i m e r n e te n g i n e e r i n gt a s kf o r c e ) 也开始制定了有 关q o s 定义与服务的一系列标准。 网络服务质量是网络于用户之间以及网络上相互通信的用户之间关于信息传 输与共享的质的约定，是口数据流通过网络时的性能。它的目的就是向用户提供端 到端的服务质量保证。q o s 可以用一系列度量( m e t r i c ) 来描述： 传输服务的可靠性幅e r v i c ca v a i l a b i l i t y ) ：用户到i n t e r a c t 业务之间连接的可靠 性。 苎三望堡垒登堕丝垡些塑空竺塑奎笙型杰笙 带宽( b a n d w i d t h