（计算机应用技术专业论文）基于遗传算法对山西工行qos路由优化的研究.pdf

太原理工大学硕十研究生学位论文 基于遗传算法对山西工行q o s 路由优化的研究 摘要 随着i p 视频会议、9 5 5 8 8 电话银行业务、网上银行等多媒体业务的 应用，山西省工商银行网络系统已经不仅仅是单纯承载柜面业务处理数据 的工具，计算机之间( 包括办公用机及业务应用服务器之间；) 。韵交互越来 越实时和生动，这就对山西工行网络服务质量( q o s ) 提出了更高的要求。 可是无论是作为r i p 路由协议核心的b e l l m a n - f o r d 路由算法还是 o s p f 路由协议核心的d i j k s t r a 路由算法，虽然能够在现有网络环境中尽 力而为( b e s t e f f o r t ) 的对传统业务数据进行传输，然而它们却无法满 足各种多媒体和实时业务对带宽，延时，延时抖动，包丢失率等多约束条 件q o s 的需要，路由算法有待改进”需要进百步优化网络服务质量。 目前，比较理想的q o s 应该包括业务的延时、带宽特性，。同时也包括 网络的吞吐量，即网络资源最有效的利用率等参数。“实际上，有性能服务 要求的q o s 路由就是带多个条件限制的最短路径问题。这是_ 个通常被称 为是组合规划中的n p h a r d ( n o n d e t e r m i n is ticp o l y n o m i a l 即随意性多项 式) 问题，是需要使用多项式算法求解的问题。通过求解多项式来锁定目 标函数的极大点或极小点。为了找到目标函数的最优解或次优解，本文使 用遗传算法对山西工行的q o s 路由选择算法进行优化，通过仿真实验表 明，算法取得了较好的效果。 本文首先针对山西工行网络构架和q o s 路由部署给出课题研究的背 太原理一j ：大学硕士研究生学位论文 景，然后介绍了研究的意义，国内外的研究现状，对课题所涉及的相关基 础理论作了简单的说明，包括遗传算法、o o s 、路由分类的基本原理与研 究内容相关的基础理论。同时，在总结了前人所做工作的前提下，对带宽、 延时、延时抖动和包丢失率约束以及费用最小的q o s 路由问题进行分析和 研究，提出了使用遗传算法对山西工行q o s 路由算法进行改进的策略。最 后，通过多次仿真实验及对结果的分析研究，可以发现通过使用本遗传算 法对山西工行o o s 路由优化后，网络拥塞、传输延迟等服务质量指标得到 明显改进，达到了优化网络路由各项主要性能指标的目的。本文的主要特 占 ，、 1 、在遗传算法的应用上，数据结构用了树型结构，一方面减少了染色体 生成的复杂过程，节省了编码空间，另一方面也省略了编码操作。 2 、在遗传算法的编码方式上采用格雷码编码方法，这种编码方法比二进 制编码方法更便于利用模式定理对算法进行理论分析。 3 、通过使用遗传算法有针对性的对山西工行网络环境进行服务质量的路 由优化j 降低了网络花费，减少了传输延迟，提高了网络利用率，达到了 优化山西工行网络路由传输的目的。 关键字：山西工行，q o s ，o o s 路由算法，遗传算法 太原理t 大学硕士研究生学位论文 r e s e a r c hb a s e do ng e n e t i ca l g o r 【t h m t oo p t i m i z e q o sr o u t i n ga l g o r i t h m o f i n d u s t r i a la n ds h a n x ii c b c a bs t r a c t w i t ht h ea p p l i c a t i o n so ft h em u l t i m e d i ab u s i n e s ss u c ha si pv i d e o c o n f e r e n c e ，9 5 5 8 8i pt e l e p h o n eb u s i n e s s ，i c b c h o m em u l t i m e d i as e r v i c e s s u c ha so n l i n eb a n k i n ga p p l i c a t i o n s ，t h en e t w o r ks y s t e m so fi n d u s t r i a la n d c o m m e r c i a lb a n ko fs h a n x ia r en ol o n g e rt o o l s s i m p l yc a r r y i n gc o u n t e r b u s i n e s sd a t a p r o c e s s i n g e x c h a n gb e t w e e nc o m p u t e r s ( i n c l u d i n go f f i c e m a c h i n e sa n db u s i n e s sa p p l i c a t i o n ss e r v e r s ) ，i sb e c o m i n gm o r er e a l t i m ea n d m o r ev i v i d ，w h i c hp r o p o s eh i g h e rd e m a n dt on e t w o r ko fl c b c b u tw h e t h e rt h eb e l l m a n - f o r dr o u t i n ga l g o r i t h ma st h ec o r eo fr i p r o u t i n g p r o t o c o lo rt h ed i j k s t r ar o u t i n ga l g o r i t h ma st h ec o r eo fo s p fr o u t i n gp r o t o c o l ， a l t h o u g hc a na c c o m p l i s ht h et r a d i t i o n a lb u s i n e s sd a t at r a n s m i s s i o ni ne x i s t i n g n e t w o r ke n v i r o n m e n t ( b e s t e f f o r t ) ，b u tt h e ya r eu n a b l et om e e tt h en e e df o r m o r er e s t r i c t i v ec o n d i t i o n sq o so fa v a r i e t yo fm u l t i m e d i aa n dr e a l t i m e b u s i n e s s ，s u c ha st h en e e df o rt h eb a n d w i d t h ，d e l a y , d e l a yj i t t e r , p a c k e tl o s s r a t e ，t h e r e f o r et h er o u t i n ga l g o r i t h mn e e d st ob ei m p r o v e d ，a n dt h eq u a l i t yo f t h en e t w o r ks e r v i c en e e d st ob eo p t i m i z e d 太原理! l 大学硕士研究生学位论文 i d e a l l y , t h eb u s i n e s ss h o u l di n c l u d eq o sp a r a m e t e r so ft h ed e l a ya n d b a n d w i d t hc h a r a c t e r i s t i c s ，b u ta l s oi n c l u d en e t w o r kt h r o u g h p u t ，t h a ti st h e m o s te f f e c t i v e u t i l i z a t i o n g o fn e t w o kr e s o u r c e i nf a c t ，t h ep e r f o r m a n c e r e q u i r e m e n t so fq o sr o u t i n gs e r v i c e sw i t han u m b e ro fc o n d i t i o n st h a tl i m i t t h es h o r t e s tp a t hp r o b l e m t h i si so f t e nr e f e r r e dt oa st h en p h a r dp r o b l e m si n c o m b i n a t i o no fp l a n n i n gw h i c hn e e dt ob es o l v e dw i t hp o l y n o m i a la l g o r i t h m i no r d e rt of i n dt h eo p t i m a ls o l u t i o no rs u b o p t i m a ls o l u t i o n s ，t h i sp a p e rr a i s e sa 。li ， - 。，4 ，t + g e n e t i ca l g o r i t h mo p t i m i z a t i o n t oi m p r o v et h eq o sr o u t i n g a l g o r i t h m ，。_ 。 ；j j t 一： 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 mh a sa c h i e v e dp o s i t i v er e s u l t s t h i sp a p e re x p o u n d st h eb a c k g r o u n di nc o n n e c t i o nw i t hs h a n x ii c b c n e t w o r ka r c h i t e c t u r e sa n di t sq o sr o u t i n ga tf i r s t ，a n dt h e ni n t r o d u c e st h e s i g n i f i c a n c eo ft h es t u d y , c u r r e n tr e s e a r c hs i t u a t i o nb o t ha th o m ea n da b r o a d a n dt h er e l e v a n tb a s i ct h e o r yo nt h ei s s u e ，i n c l u d i n gg e n e t i ca l g o r i t h m s ，t h e c l a s s i f i c a t i o no fq o sr o u t i n g a tt h es a m et i m e ，o nt h eb a s i so ft h ew o r ko f r ：t o u rp r e d e c e s s o r s ，t h ep a p e ra n a l i z et h eb a n d w i d t h ，d e l a y , d e l a yj i t t e r , p a c k e t l o s sr a t ea n dt h eq o sr o u t i n gc o s t i n gl e a s tm u l t i c a s tr o u t i n gp r o b l e m ，t h e n p r o m o t et h es t r a t e g yt oi m p r o v es h a n x ii c b cq o sr o u t i n ga l g o r i t h mb y u s i n gg e n e t i ca l g o r i t h m s t h ea n a l y s i so fm a n ye x p e r i m e n t a la n ds i m u l a t i o n r e s u l t ss h o wt h a tb yo p t i m i z i n gs h a n x ii c b cq o sr o u t i n gt h r o u g ht h eu s eo f t h eg e n e t i ca l g o r i t h m ，n e t w o r kc o n g e s t i o n ，t h es e r v i c e q u a l i t yi n d i c a t o r ss u c ha s d e l a y e dt r a n s m i s s i o ns e r v i c e sh a v eb e e nm a r k e d l yi m p r o v e d ，a n dt h em a i n p u r p o s et oo p t i m i z ep e r f o r m a n c ei n d i c a t o r so fn e t w o r kr o u t i n gh a sb e e n i v 太原理工大学硕士研究生学位论文 a c h i e v e d t h em a i nc h a r a c t e r i s t i c s ： t h e p a p e r sm a i nc h a r a c t e r i s t i c s ： 1 、i nt h ea p p l i c a t i o no ft h eg e n e t i ca l g o r i t h m ，t h ed a t as t r u c t u r eu s e st h e t r e es t r u c t u r ew h i c ho nt h eo n eh a n dr e d u c e st h e g e n e r a t i o no fc o m p l e x c h r o m o s o m e ，s a v e sc o d i n gs p a c e ，a n do nt h eo t h e rh a n do m i t st h ec o d i n g 2 、t h i sp a p e ru s e s 铲a yc o d eb i n a r ye n c o d i n gm e t h o dt op r o m o t et h e t h e o r e t i c a la n a l y s i so fa l g o r i t h mw i t hp m t e m st h e o r e mb e t t e rt h a nt h eb i n a r y c o d i n gm e t h o d s 3 、b yu s i n gg e n e t i ca l g o r i t h mt oo p t i m i z et h eq u a l i t yo fs e r v i c eo fs h a n x i i c b cn e t w o r k ，w ew i s ht od e c r e a s et h en e t w o r kc o s t s ，r e d u c et h et r a n s m i s s i o n d e l a y , i m p r o v e n e t w o r ku t i l i z a t i o na n d o p t i m i z e t h en e t w o r k r o u t i n g t r a n s m i s s i o no fs h a n x ii c b c k e yw o r d s ：s h a n x ii c b c ，q o s ，q o s b a s e d r o u t i n g ，g e n e t i ca l g o r i t h m v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：日期： 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为：目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：羔：之瑟日期：a 叼暑。6i 订。 导师签名：二芸瑟址日期：一 太原理工大学硕士研究生学位论文 1 1 选题背景和意义 1 1 1 选题背景 第一章绪论 当今世界，网络技术飞速发展，尤其是随着p 视频会议、9 5 5 8 81 - p 电话语音业务、 工行 家、网上银行等多媒体业务的应用，山西省工商银行网络系统已经不再是单纯 一 承载柜面业务处理数据的工具，计算机之间( 包括办公用机及业务应用服务器之间) 的交互也越来越实时和生动，这就对山西工行网络提出了更高的要求 尽管随着网络 技术的发展，电信运营服务商能够提供的网络带宽以及网络速度都得到了极大的提高， 但需要通过网络传输的数据也几乎以与网络发展速度相同的速度增加，甚至超过网络 发展的速度，对那些有带宽、延迟、抖动等特殊要求的应用来说，如i p 视频会议, 9 5 5 8 8 i p 电话语音传输、网上银行业务的办理，现有i p 网络“尽力而为”的服务显然是不够的。 同时在涉及租用带宽费用与带宽利用率这两个问题时，就会使得网络服务质量路由问 题越来越突出。 近年来在山西省工商银行应用起来的一些新的服务如牡丹卡黑名单、因私购汇、 个人征信、c s 2 0 0 2w e b 、c c r m w e b 、p c r mw e b 一、c m 2 0 0 2 、网络管理系统等， 这些对延迟敏感、需要互访的业务不仅增加了网络流量的开销，更因为这些应用改变 了以往只是传输s n a s w i t c h 数据流量性质，它们具有全新的服务要求。由于不能预 留带宽，不能限制网络延迟和抖动，传统的口网络没有服务质量保证的弱点已经显示 出来。 不仅仅是银行业，社会其他行业对如何充分利用网络，也有同样的需求。为此， 业界提出了i pq o s ( q u a l i t yo fs e r v i c e ) 的概念，q o s 应运而生，就是希望在网络传 播速度一定的基础上能够对不同的业务提供不同的带宽、延迟等方面服务质量的保证。 q o s 技术的出现旨在针对不同用户和不同应用的需求，为其提供不同的服务质量保 证， 这使得网络服务质量问题与网络路由依然是一个瓶颈问题。 传统的分组交换网络，如i n t e r n e t ，是面向非实时的数据通信而设计的，采用的 t c p i p 协议主要是为了优化整个网络的数据吞吐量并保证数据通信的可靠性，主要保 太原理1 ：火学硕士研究生学位论文 证网络传输的稳定性，传输时延不是关键。而当今分布式多媒体应用，如视频会议、 视频点播、i p 可视电话、远程教育、虚拟现实等，不仅包括文本数据信息，还包括语 音、图形、图像、视频、动画等多媒体信息。这些多媒体应用不但对网络有很高的带 宽要求，而且要求信息传输的低延迟和低抖动等指标，但只能容忍一定程度的信息丢 失和错误。这就对山西工行网络提出了不同于数据应用的服务质量要求，需要提供端 到端的q o s 控制和保证。在传统的t c p i p 协议的尽最大努力( b e s t e f f o r t ) 转发机制中， 网络层不区分业务，尽管i p v 4 的分组包头中设计了指明优先级和服务类型的字段， 但在路由器选择路由和处理分组时往往被忽略，不加以处理，而将网络资源公平地提 供给各类业务；在分组丢失和时延等方面公平地处理各类业务。这种服务易受分组丢 失、分组重复：路由器缓冲区队列延迟等的影响，缺少必要的q o s 控制和保证；信息 传输控制一般不依赖于网络状态，带宽分配可以动态地改变，但需要流控制；典型应 用包括文件传输( f t p ) 和e m a i l 传输。而多媒体应用至少含有三方面的不同：设备容 量、网络连接性和用户需求。：这不是“尽力而为 服务所能提供的，它己不能满足当 今各种网络应用的需要。由此j 以提高网络资源利用率、为用户提供更高服务质量为： 目标的q o s 控制技术应运而生，并且已经成为下一代网络的核心技术之二。 为了使多媒体应用程序在网络上得到广泛应用，l 种方法是研究开发新的网络协 议，如i p v 6 、r s v p ( 资源预留协议) 、r t p ( 实时传送协议) ；然而最根本的方法是改造 路由器，使其具有处理q o s 请求的功能。由于路由算法直接关系到网络性能，q o s 路由成为解决q o s 问题的一项关键技术。i n t e m e t 工程特别工作组i e t f 在这方面作了 大量工作，设计了新的面向服务质量的网络体系结构以支持实时q o s ，先后提出综合 服务资源预留模型( i n t s e r v r s v p ) 、区分服务模型( d i f f e r s e r v ) 以及多协议标签交换 ( m p l s ) 。q o s 路由在这些网络体系中的应用是当前计算机网络研究的一个热点问题。 1 1 2 选题意义 在山西工行网络环境中，应用在山西分行本部和辖内各二级分行的是o s p f 路由 协议，二级分行所属的城区分行及营业网点则使用r i p 路由协议。r i p 路由协议是距 离矢量路由协议，使用的是b e l l m a n f o r d 路由算法，而o s p f 路由协议是链路状态路 由协议，使用d i j k s t r a 路由算法。可是无论是b e l l m a n f o r d 路由算法还是d i j k s t r a 路由 算法，二者的基础都是最短路径优先算法( s p f 算法) ，虽然在现有的b e s t e f f o r t 服 太原理工大学硕士研究生学位论文 务模式的网络中工作得很好，然而它们都无法满足各种多媒体和实时业务的q o s 需要， 主要表现在【1 7 】： ( 1 ) z 者都采用单一的度量值来寻求到达目的地最短路径，如r i p 采用跳数来计算 路径的长度，o s p f 采用与链路的带宽成反比的c o s t 值来度量距离。因此在这些传统 的路由算法中都没有考虑到同时具有带宽，延时，延时抖动，包丢失率等多个约束条 件的情况： ( 2 ) 由于它们都是要计算一条到目的节点的最短路径，而忽略了其它可用的路径， 。j 。，一 这会使多个业务的最短路径会聚到某条特定的路径上。这就会造成一方面这条特定的 最短路径发生拥塞，而另一方面其它可满足业务要求的路径由于不是最短路径而处于 闲置状态： ( 3 ) 当网络发生拥塞时，网络的延时和包丢失率会急剧增加，如果采用延时和包丢 。 t i，t 失率来度量最短路径，则可以将流量转移到另一条路径上去。但是，这种转移不是部 ， t ? ： ， 分转移，而是全部转移，即所有的处于原来的最短路径上的流量都会转移到新的路径 一 上来。这样，新的路径又会由于负荷太重而造成拥塞， 针对上述山西工行正在使用的最短路径优先算法( s p f 算法) 的不足，通过使用 q o s 路由算法，提出优化方案，充分利用现有网络资源，提高带宽利用率、降低网络 延时和包丢，是此次毕业设计的主要研究内容。 1 2q o s 路由研究现状 i e t f 提出的i n t s e r v 体系结构在文献【2 中给出，将其框架划分为综合服型和参考 实现框架两大部分。在服务层次上，除了原来的尽力而为服务外，i n t s e r v 以每个流为 基础，提供了两种端到端的面向实时传输的服务：质量保证服务、可控负载型服务。 i n t s e r v 依靠资源预留协议r s v p 提供q o s 协商机制，逐节建立或拆除每个数据流的 路径状态和资源预留软状态( s o f t s t a t e ) ；依靠接纳控铝1 ( a d m i s s i o nc o n t r 0 1 ) 决定链路或节 点是否有足够的资源满足用户的资源预留；依靠传输控制( 仃a m cc o n t r 0 1 ) 将i p 分组分 成不同的传输流，并根据每个流态对分组的传输实施q o s 路由、传输调度( s c h e d u l i n g ) 等控制。i n t s e r v 是基于流的( 单独的或聚集的) 状态相关的体系结构，依赖于每个流 ( f l o w ) 的状态和对流的管理。这种实现机制一方面是i n t s e r v 能够提供较状态无关的 体系结构有更高的灵活性和更好的服务级别保证服务，但同时也导致了i n t s e r v 的可扩 太原理工火学硕二 = 研究生学位论文 展性问趑和鲁棒性问题，后果是实现复杂，难以应用。另外，h a t s e r v 的实现必须依赖 r s v p ，而目前只有少量的主机产生r s v p 信令，虽然其数量预计会大增长，但许多应 用却从不产生r s v p 信令，这也更增大了实现的难度。 区分服务体系结构d i f f s e r v 是在i n t s e r v 发展遭遇巨大障碍时产生的，其在于简单 有效，以满足实际应用对可扩展性的要求，实现途径是： i ； ( 1 ) 简化网络内部节点的服务机制。在内部节点只进行简单的调度转发，状态信 息的保存与流监控机制的实现等只在边界节点进行，内部节点是状态无关的。 ( 2 ) 简化网络内部节点的服务对象。采用聚集传输控制，服务对象是流聚( s t r e a m a g g r e g a t e ) 而非单流，单流信息只在网络边界保存和处理。 具体而言，边界节点根据用户的流规定( p r o f i l e ) 和资源预留信息将进入网的单 流分类、整形、聚合为不同的流聚集，这种聚集信息存储在每个i p 包头d s ( d i f f e r e n t i a t e d s e r v i c e s ) 标记域( f i e l d ) q b ，称为d s 标记( d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，d s c p ) ；内 部节点在调度转发口包时根据包头的d s c p 选择特定质量转发服务，其外特性称为逐 点行为( p e r - h o t - b e h a v i o r ，p h b ) 。网络边界对单流作分类聚合，网络内部对聚集流提供 特定质量的调度转发服务，这两个过程通包头内的d s c p 协同起来。 ， d i f f e r s e r v 提供的是相对粗糙的q o s 划分，没有处理单个流( p e r - f l o w ) 的复杂性， 有很好的可扩展性。但是d i f f e r s e r v 注重的是如何划分业务量和快速传输，它仍然是 传统的尽最大努力服务的路由算法，不能保证端到端的q o s 需求。 r 1 1 r f c 3 0 31l l 纠定义了m p l s 多协议标签交换体系。m p l s 是对第二层a t m 标记交 换和第三层路由选择的有机结合，工作在网络层和数据链路层之间。m p l s 既实现了 a t m 的面向连接、简单高速交换、q o s 保证、流量管理、流量又实现了i p 的灵活性、 有效性和可扩展性等优点。 m p l s 分离了传统选路的“控制”和“转发”两个部分的功能。m p l s 域中标记 边缘路由器l e r 将进入m p l s 域的分组进行快速分类，并映射到转发等价类f e c 。 核心标记交换路由器l s r ，能迅速处理分组上的标记，并对己打上标记的分组进行快 速转发。从f e c 得到的标记通过标记分配协议l d p 在m p l s 网络中建立一条标记交 换路径l s p 。打上标记的分组就沿着路径l s p 传送。与a t m 技术中的p v i p v c 一样， 标记只具有本地意义，多个标记可以嵌套构成标记栈，可以实现路由和层次化路由。 由于使用基于标记的转发，不仅省去了每到个节点都三层查找路由表的过程，使分 太原理工大学硕士研究生学位论文 组转发的速率大大加快，而且还能使网络上量负载更加平衡。 如何将q o s 路f 4 ( q o s b a s e dr o u i n g ，q o s r ) 应用到d i f f s e r v 和m p l s 等体系是当 前学术界一个热门的研究课题。为了更好地保证服务质量，最近又提出了一种新路由 机制，称为q o s 服务路由( q o ss e r v i c er o u t i n g ，q o s s r ) 。这样，传统的路由被归类 为q o s 数据路i 由( q o sd a t ar o u t i n g ，q o s d r ) 。 q o s s r 主要基于以下两个假设m 川： ( 1 ) 大多数多媒体服务由一些更小的子服务组成，即服务是可组合的：这样，一定 顺序依次应用多个服务来完成传送一个复杂服务的目的； ( 2 ) 多媒体服务可以由网络的某个特定的地点提供。这样就可| 以在网络的二些特定 的地点设置代理，每个代理都有自己的容量和带宽限制，从而构造一个多媒体服务的 代理服务网络。于是问题就变成寻找一条路径，这条路径包含定顺序排列的所有必须 的服务。 文献【5 提出了q o s s r 的关键步骤：( 1 ) 详述服务需求；( 2 ) 构造覆盖代理；( 3 ) 将服务需求映射到代理网络；( 4 ) 设计路由算法。 q o s s r 不同于q o s d r ，q o s d r 主要描述网络层的q o s 路由，而q o s s rn i 作在应用层，是服务传送网络( s e r v i c ed i l i v e r yn e t w o r k ，s d n ) 的重要组件。二者都能 被应用到i e t f 提出的4 h a t s e r v 、d i f f s e r v 、m p l s 等网络体系结构中。q o s d r 是本文 研究的主要问题，其详细研究情况将在第二章给出。 1 3 q o s 路由研究面临的问题 q o s 路由的主要目标有： ( 1 ) 动态选择可行路径，为每个可接受的q o s 业务流提供服务质量保证。q o s 路 由能从多个可能的选择中，选出最可能满足数据流需求的路径。 ( 2 ) 最优化全局资源利用率。q o s 路由策略通过增大网络吞吐量，有效提络资源利 用率，这也是网络优化管理的基本目的。 ( 3 ) 对性能影响尽量小。在网络负载过重等情况下，路由算法应有较强的性保证网 络的良好性能，提供较高的吞吐量。 当前i n t e r n e t 路由协议，如o s p f 、r i p ，都使用最短路径路由，只优化一个度量， 如时延或跳数。这些路由协议使用当前的最短路径发送数据到目的地，为“机会主义” 太原理工火学硕士研究生学位论文 p 1 路由协议。而那些具有可接受但非最优代价的可选路径却用来传输通信业务。q o s 路由必须从三个基本方面改进当前的路由模式： ( 1 ) 为了使用综合服务业务支持通信传输，必须能计算节点对之间的多条路由。这 里的综合服务( i n t e r g r a t e ds e r v i c e ，i s ) 在文献 2 】中定义，包括最大努力，实时服务和控 制链路共享服务。 ( 2 ) 在当前的机会主义路由协议工作模式下，即使原来的路径满足当前业务服务需 求，一旦找到更好的路径，通信业务就改变传输路径，在新的当前最径上传输业务。 如果路由算法的计算与网络资源( 如可用带宽) 之间有很大，则当网络状态变化比较频 繁时，；传输路由就会产生很大的振动；在可选路径之间来回变换。另外，这样也会增 大终端用户之间的时延抖动。 ( 3 ) 当前最优路径路由算法不支持可选路由，如果最优路径不能满足一个数的传输 要求，即使存在一条更合适的路径，算法也不会选择这条路径来传输。 、因此q o s 路申算荤的设弦是一命很复杂的问题- f 令有救的q o s 路由算法考虑 诸多因素，具体体现在以下几个方面： ( 1 ) 算法的复杂度。复杂度涉及到解决_ 个问题尊执行个算法所需的最勿资源，： 包括时间复杂度和空间复杂度。时间复杂度是q o s r 首先要面对的最重要。由于多约 束q o s 路由问题具有n p 性质，传统的最优算法无法在多项式时求得最优解，其时间 复杂度往往随问题规模的增加而以指数速度增加，因此解决q o s 路由问题多用启发式 算法。启发式算法是一种技术，这种技术使得在可接受的计算费用内去寻找最好的解， 但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最 r f l 优解的近似程度1 。在获得解的最度和计算时间、占用空间之间有一个权衡，目的是 要花费尽量少的时间和空得尽量优的解。 ( 2 ) 算法的可扩展性。现有的路由算法大多不具备很好的可扩展性，计算时往往随 着网络规模的增大而以指数速度增加，不能应用到实际的大规模网络过网络状态聚集 能够以对数缩减信息量，相应的分层路由可以通过限制每节点的数量使用源路由方式， 从而很好地解决可扩展性问题。但这同时又引新的问题：如何聚集状态信息、如何基 于聚集状态设计良好的启发式算法。所设计的状态信息聚集方法会丢失大量可用信息， 严重影响了q o s r 算法的；同时，所设计的启发式算法也往往是基于全局状态源路由 r 7 1 策略的。此外，很多q o s 问题的精确求解复杂度都是n p c 的。，因此需要设计快速、 太原理工大学硕士研究生学位论文 有效的式算法。 ( 3 ) 非精确路由信息问题。网络状态的不断变化、网络的分层体系结构和网息聚合 都会导致路由信息的非精确性。非精确路由信息可能会使路由选择失重新进行路由计 算和发送预约信令，从而增大网络开销和业务时延。分布式中，不准确的路由信息还 可能导致环路。一种解决方案是合理设计路由信息方法。路由信息的更新直接关系到 每个节点保留信息的准确性。信息更新越，节点获得的信息准确性越高，但同时引入 的信息开销也越大。合理的路由信息更新策略能够有效均衡信息准确性与路由开销 同时也可以为路由算法性算法可实现性找至i 恰适的折中点【1 0 ，! 巩。另外一种方法是概 率模型求解。按照参数取值的概率选择一条具有最大可能性的路径 j ，可以克服信息不 准确性为选路带来的影响。 ( 4 ) q o s 路由与尽最大努力服务路由的共存问题。文献 1 2 1 对这个问题进了讨论。5 将q o s r 融入到当前这种尽力发送的路由体系结构中，原有的尽力发送业务将受到巨 大冲击。今后韵网络应该是q o s a 和尽力发送相结合的彦物网络的路由。目标是最大 化资源效用，这包括尽可能地接纳更多的q o s 连接请求，最大化尽力发送业务的吞吐 - 。 、_ ，1 “ 量和相应速度。由于这两者是矛盾的，因此二者的融合过程会产生很多问题。例如，、 在有资源预留的链路空闲时，没有资源预留的链路却可能由于尽力发送业务而造成拥 塞。这种拥塞的链路仍然有可能因为尚留资源而接受q o s 请求。此外，q o s r 算法必 须与其他网络组件结合才能提供q o s 保证，包括状态收集、资源预留、分组调度等， ， 因此可以考虑这种结合过q o s r 算法和其他网络组件的简化。 i 。 ： ( 5 ) 多路路由与重路由。多路路由有两种解释：第一，在多条可能的路径时探测可 行路径，如何与资源预留相结合尚无定论m 。第二，网络提供多源到目的的路径，并 将这些路径并行复用起来( 如增加带宽) 而对用户业务，这是一种多路复用的路由方式。 然而，其主要问题是多条路径之间如何同步及如何避免分组的延迟抖动、乱序等卜。 由于网络资源和可行路径分配的理，因而在某些情况下需要重新路由。重路由在网络 资源不足时进行，能够有效地重新分配网络资源，但由于存在状态保存、同步和开销 等问题，使重路由困难。 ( 6 ) 算法实现问题。假定我们已经解决了算法的复杂度问题，仍然有两点需要来考 虑的：第一，不同的通信业务有不同的度量，所以路由器对每一个新接入的业务必须 太原理i ：人学硕士研究生学位论文 能应用相应的算法；第二，大多数的路由算法都假定在计算之前已得了足够的路由信 息，即假定路由协议已经获得了这些信息。但在实际网络多约束路由、频繁的在网络 中传输多个度量的路由信息将会极大地增加网络负荷。 1 4 本文的主要工作 1 、首先，本文针对山西工行网络构架和q o s 路由部署给出课题研究的背景，然 一 ， 、： 后介绍了研究的意义，国内外的研究现状，对课题所涉及的相关基础理论作了简单的 说明，包括遗传算法iq o s 、路由分类的基本原理与研究内容相关的基础理论。 2 、接下来，本文在总结了前人所做工作的前提下，对带宽、延时、延时抖动和包 丢失率约束以及费用最小的q o s 组播路由问题进行分析和研究，提出了使用遗传算法 对山西工行q o s 路由算法进行改进的策略? 3 、最后，通过仿真实验及对结果的分析研究，可以发现通过使用本遗传算法对山 西工行, q o s 路由优化后，网络拥塞、，。传输延迟等服务质量指标得到明显改进i 1 5 本文的组织结构 全文共分五章，组织结构如下： 第一章绪论 介绍了国内外关于q o s 路由的研究现状和面临的问题，分析研究背景，研究意义， 概述本论文的主要工作内容，最后简述论文的组织结构。 ， 第二章相关基础理论 对课题所涉及的相关基础理论作了简单的介绍，介绍了遗传算法和路由算法理论 知识，通过对遗传算法的发展过程、基本步骤以及遗传算法的特点和应用、路由算法 的分类，总结了路由算法相关的经典算法。 第三章基于遗传算法对山西工行网络传输进行改进的路由算法 在分析山西工行现有q o s 路由基础上，通过介绍q o s 路由和q o s 路由算法的基 本知识，然后由山西工行q o s 路由的现状及不足，提出问题，针对现有网络资源，如 何进行服务质量优化，减少花费，降低延迟，满足多约束q o s ，提出解决方案。 第阴章仿真实验及结果 对本文提出的算法进行了收敛性分析，证明本文使用的遗传算法可收敛到全局最 太原理 ：大学硕士研究生学位论文 优解。然后，将本算法应用在模拟山西工行的测试环境中，经过多次仿真实验证明，分 别与d i j k s t r a 算法和b d l m a n - f o r d 算法的比较，结果表明：该算法有良好的服务性能， 并且能同时满足多个q o s 的约束条件，证明本算法是可行和有效的，确实较现有s p f 算法有很大改进，达到课题设计目的。 第五章结论与展望。 总结了本文的研究成果，并指出了需进一步开展的工作。 9 太原理= 【：大学硕士研究生学位论文 2 1 遗传算法理论 2 1 1 遗传算法的发展概述 第二章遗传算法和路由算法 从本世纪4 0 年代，生物模拟就成为了计算科学的一个组成部分，如早期的自动机 理论就是假设机器是由类似于神经元的基本元素构成的。近几十年来，人们关注着如 诸如机器能否思维、基于原则的专家系统是否胜任人类的工作、以及神经网络可否使 机器具有看和听的能力等等这些有关生物类比的问题。 自从人们接受了达尔文的生物的进化理论之后，科学家们就对生物的进化机制产 生极大的兴趣。自然进化特征在6 0 年代就引起了美国m i c h i g a n 大学的j o h nh o l l a n d 的极大兴趣，那时h o l l a n d 从事如何建立能学习的机器的研究。他注意到学习不仅可 通过单个生物体的适应，而且可通过一个种群的许多代进化适应实现。他受达尔文进 化论“适者生存 的启发，逐渐认识在机器学习的研究中，为获得一个好的学习 方法，仅靠单个策略的建立和改进是不够的，还要依赖于包含许多候选策略的群体的 繁殖。这种研究思想起源于遗传进化，h o l l a n d 就将这个研究领域取名为遗传算法。 从1 9 8 5 年到1 9 9 3 年，召开了五届国际遗传算法学术会议，遗传算法己经有了很 大的发展，并开始渗透到人工智能、神经网络、机器人和运筹学等领域。遗传算法是 多学科相互结合与渗透的产物，它已经发展成- k , 自组织、自适应的综合技术，广泛 用在计算机科学、工程设计l 2 5 j 、管理科学和社会科学等领域【2 6 - 2 8 】。 2 1 2 遗传算法的基本步骤 遗传算法g a 是建立在自然选择和群体遗传机制基础上的随机迭代、进化，具有 广泛适应性的概率搜索寻优算法。 对于某个给定的优化问题： 目标函数h = f ( x ，y ，z )( x ，y ，z ) 2 h r 要求( x o ，y 。，z 。) 使h 为极大值和极小值，以适应优化的需要。此处，q 是 太原理工大学硕士研究生学位论文 ( x , y ，z ) 的定义域日为实数；f 为解空间( 五y ，z ) q 到实数域h r 的一种映射。 g a 要根据目标函数h 设定一个适应性函数，用以判别某个样本的优劣程度。遗传 算法的基本步骤如下： 1 编码 采用二进制编码方案对优化变量进行编码。采用二进制编码的策略是将各优化分 量分别进行编码然后合并成1 个二进