《基于遗传算法的ospfv3路由算法研究》由会员分享，可在线阅读，更多相关《基于遗传算法的ospfv3路由算法研究（65页珍藏版）》请在金锄头文库上搜索。
1、东北大学 硕士学位论文 基于遗传算法的OSPFv3路由算法研究 姓名：王东军 申请学位级别：硕士 专业：计算机软件与理论 指导教师：高晓兴 20070201 东北大学硕士学位论文摘要 基于遗传算法的O S P F v 3 路由算法研究 摘要 O S P F ( O p e nS h o r t e s tP a t hF i r s t ) 是I E T F ( I n t e r n e tE n g i n e e r i n gT a s kF o r o e ) 于 1 9 8 8 年提出的一种基于链路状态算法的动态路由协议，它是用于I P v 4 网络自治系 统内部的内部网关协议。随
2、着I P v 6 协议的发展和使用，出现了O S P F v 3 。它主要用 于解决I P v 6 数据包的路由问题而提出的新版本路由协议，它仍然沿用S P F 算法来 生成组播树。S P F 算法没有考虑所选路径的带宽、时延、时延抖动、丢包率等参数 ； 是否满足实际应用的需要，又由于搜索的局限性，没有充分利用全网可用路径，所 以S P F 算法没能更好的平衡网络流量。 本文主要利用遗传算法来解决S P F 算法的上述缺点。首先介绍了路由器及路由 选择协议的基本原理。接下来分析了O S P F 路由协议的工作原理和O S P F 采用的路 由计算方法。阐述了有关遗传算法的基本概念，如：建模、编
3、码、杂交、变异等， 并在适应度函数值的引导下对复杂的解空间进行有效地搜索，直到获得最优的解。 最后对基于遗传算法的O S P F v 3 路由算法进行了设计、实现、分析与仿真。 灏键词：遗传算法，O S P F v 3 ，路由选择，S P F ，O P N E T I I 东北大学硕士学位论文 A b s t r a c t R e s e a r c ho fO S P F v 3R o u t i n gM e t h o dB a s eo nG e n e t i c A l g o r i t h m A b s t r a c t O S P F ( O p e nS h o r
4、t e s t P a t hF i r s t ) i sad y n a m i cr o u t i n gp r o t o c o lp u tf o r w a r db y I E T F ( I n t e r n e te n g i n e e r i n gt a s kf o r c e ) i n1 9 8 8 ，i sb a s e do nL i n kS t a t eA r i t h m e t i c a n d u s e da sa nI G P ( I n t e r i o rG a t e w a yP r o t o c 0 1 ) r o u
5、 t i n gp r o t o c o lf o rI P v 4n e t w o r k 。W i t ht h e d e v e l o p m e n ta n de m p l o y m e n to fI P v 6p r o t o c o l ，O S P F v 3c o m e sf o r t ht os u p p o r tt h eI P v 6 n e tw o r k 。I ti san c wv e r s i o no fd y n a m i cr o u t i n gp r o t o c o l ，w h i c hi sr o o ti n
6、O S P EI ti s m a i n l yu s e dt os o l v et h ep r o b l e mo fI P v 6d a t ap a c k a g er o u t i n ga san e wv e r s i o nr o u t e p r o t o c o l ，a n di ts t i l lu s e st h eS P Fa r i t h m e t i ct oc r e a t eM u l t i c a s tT r e e B u tS P Fa r i t h m e t i c d on o tc o n s i d e re
7、 n o u g hw h e t h e rb a n d w i d t h ，t i m e - d e l a y , t i m e d e l a y , m i s s i n gp a c k a g er a t e c a ns a t i s f yt h ep r a c t i c a ld e m a n d A n db e c a u s eo fs e a r c hl i m i t ，t h e r ei sn o te n o u g hn e t r e s o u r c e ；t h eS P Fc a nn o tb e t t e rb a l
8、 a n c et h en e t w o r kf l o w T h ep a p e r m a i n l y s o l v e sh o wt ou s et h eG e n e t i cA r i t h m e t i ct os o l v et h e d i s a d v a n t a g eo fS P ET h ef i r s tp a r ti n t r o d u c e st h et h e o r yo fr o u t e ra n dr o u t i n gp r o t o c 0 1 T h es e c o n dp a r ta
9、n a l y s e sO S P Fr o u t i n gp r o t o c o lw o r kp r i n c i p l ea n da r i t h m e t i c , a n d d e p i c t st h eb a s ec o n c e p t i o no fG e n e t i cA r i t h m e t i c ，s u c ha sm o d e l i n g ，c o d i n g ，c r o s s i n g ， a b e r r a n c ea n ds oO i l U n d e rt h eg u i d eo
10、ft h ea d a p t i n gf u n c t i o n ，G e n e t i cA r i t h m e t i cc a n p r o c e s se f f e c t u a ls e a r c h i n gi nc o m p l i c a t e ds o l u t i o ns p a c e ，u n t i li tc a nf i n dao p t i m i z e d s o l u t i o n T h el a s tp a r ti n t r o d u c e st h ed e s i g n ，i m p l e m
11、e n t ，a n a l y s i s ，a n de m u l a t i n go ft h e O S P F v 3r o u t i n gp r o t o c o lb a s e do nG e n e t i cA r i t h m e t i c K e yw o r d s ：G e n e t i cA r i t h m e t i c ，O S P F v 3 ，R o u t i n gP r o t o c o l ，S P F ，O P N E T I l l 独创声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加 以标注
12、和致谢的地方外，不包含其他人已经发表或撰写过的研究成果，也不包括本人为 获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示诚挚的谢意。 学位论文作者签名：王彖擘 签字日期： 7 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即 学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交 流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名： 互东肇 导师签名：鸣酰写 签
13、字日期： 伽7 - f - 签字日期： 2 一叼q - 矿 东北大学硕士学位论文 第一章绪论 第一章绪论 1 1 研究背景 传统的互联网是基于I P v 4 协议的网络，该协议的成功运用使得互联网的用户呈 高速增长。但是，随着用户的不断增加，以及各种新业务的出现，网络地址匮乏成 为制约互联网发展的瓶颈。此外，随着互联网应用要求的提高，I P v 4 在服务质量、 移动性和安全性等方面的支持也突显乏力。为了解决I P v 4 存在的诸多问题，1 E T F 在9 0 年代中期提出了拥有1 2 8 位地址的I P v 6 互联网协议，并在1 9 9 8 年进行了进一 步的标准化工作。除了对地址空间
14、的扩展以外，I P v 6 还提供了自动配置以及对移动 性和安全性的更好支持。 为普及I P v 6 ，世界知名的设备制造商、运营商和研究机构联合发起成立了I P v 6 论坛，并从1 9 9 9 年开始，每年举行2 3 届I P v 6 全球峰会，还与U M T S 论坛：3 G P P e 以及欧洲通信标准委员会建立了合作关系。同时，I E T F 于1 9 9 6 年建立全球范围的 试验床6 B o n e ，对1 1 6 协议特性进行了研究并积累了I P v 6 组网经验。1 9 9 8 年底， 面向实用的全球性I P v 6 研究和教育网6 R E N 开始启动。所有的这些努力极大地
15、推动 了I P v 6 的商用化进程。 我国不是互联网的发源地，I P 地址资源匮乏更显突出，加上人口稠密，以及近 年来经济和信息技术的快速发展，对地址不足的压力比较敏感，为此，我国政府对 基于I P v 6 技术的下一代互联网的研究和应用非常关注和重视，启动了一系列的研究 项目。1 9 9 9 年底中国教育和科研网C E R N E T 与诺基亚公司合作启动了I P v 6 互联网 I n t e m e t 计划，形成一个大规模的I P v 6 研究和试验网络，开展了许多开拓性的研究。 在8 6 3 计划中，迸一步提出了有关高性能I P v 6 路由器关键技术及系统开发的课题。 高性能的路
16、由器可能应用于各种环境，它必须提供多种路由协议，包括R I P , O S P F ，I S I S 以及B G P 等内部和外部网关路由协议。其中O S P F 协议是为T c P I P 网络设计的自治系统内的路由协议，目前其版本为3 。随着网络拓扑的日趋复杂自 治系统通信内的要求越来越高，O S P F 协议己经成为I n t e r a c t 路由体系结构的基础。 为了能够很好支持未来多媒体业务的需要，充分研究多种约束条件下O S P F v 3 是很 有必要的，为此，本文提出了基于遗传算法的O S P F v 3 路由算法研究。 东北大学硕士学位论文第一章绪论 1 2 选题意义 O S P F v 3 是在O S P F v 2 的基础上随着I P v 6 发展而来的。由于I P v 4 和I P v 6 的协 议的不同，使得O S P F v 3 在O S P F v 2 的基础上做了许多改动。但O S P F v 3 与O S P F v 2 一样，也是使用S P F 算法来产生从源到目的节
