《基于ospf协议的路由优化的研究》由会员分享，可在线阅读，更多相关《基于ospf协议的路由优化的研究（59页珍藏版）》请在金锄头文库上搜索。
1、f 1 1 3 6 学科门女三兰H 娄! ! ! ! 三一 单f t 代日：j 丝2 1 一密 g ： 巾二廓鹰Z 碧 硕士学位论文 沧义题目：基于O S P F | 办议的路由优化的研究 学号 硕0 5 1 0 0 9 指导教师 学利专业 研究方向 论文提交日期 孙知信教授 生簦型! 墼壁兰型堡 软件技术及其在通信中的应用 南京邮电人学颂1 ：研究生学位论文 摘要 摘要 随着网络通信的飞速发展，路由优化显褥越来越重要。最常用的I G P 路由信息协议O S P F 己经逐渐取代T R I P ，得到了世界上绝大多数厂商的支持。因此，研究O S P F 网络具有重要 的现实意义。 路由优化的核
2、心路由算法的改进J 下是顺应网络发展的要求而得到飞速发展的。 O S P F 协议普遍选用基于链路状态的S P F 算法，丽常用的S P F 算法包括最短路径树算法都会在 I n t e r n e t 的飞速发展下显示出性能严重地不足。本文通过对路由问题进行分析，将种采 用节点序列编解码的遗传算法用于对O S P F 路由阅题的建模和具体实现，提出一种启发式路 由遗传算法。该遗传算法与基于二进制编码的通用遗传算法相比，编码，解码过程简单直 戏，并在此基础上引入新的遗传交叉、变异算予，交叉操作和变异操作相结合保证了最优 解的搜索能力和解的全局收敛性。其困的在于探索和应用遗传算法为O S P F
3、 网络路由的选择 开辟一条新的途径。 对路幽表结构的改进是作者提出的路由优化的另一个方面。良好的路由表结构设计 和快速的路幽查找算法是实现高速分组转发的关键。O S P F 就是利用踺由表来找到竣优路 径的，论文提出了一种改进的A V L 树的路由表结构和基于选择调整算法的A V L 路由表结构 快速增删算法，平餐二叉树( A V L 树) 适合于存储位置在内存，要求极快速响应的应用，菲 常适合作为路由表的结构。对A V L 树结构路由表的快速增删算法则具有算法简单、速度较 快、易于更新、存储空闽利用率较高等特点，有效锝提高了路由条髫的增加和删除速度。 相比于已有研究，本文的工作从选路策略和选
4、路机制两个方面进行了路由优化的研 究，最后的实验仿真表明遗传算法的应用提高了O S P F 霹络路由收敛的速度及最优路由的 搜索能力，改进的路由表操作提高了路由查询和更新的效率，二者都达到了路由优化的目 的。 关键字：O S P F ，路幽优化，遗传算法，路由表，A V L 南京邮r 乜人学硕l ：研究生学位论义A B S T R A C T A B S T I 认C T W i t hr a p i dd e v e l o p m e n to fn e t w o r kt e l e c o m m u n i c a t i o n 。r o u t i n go p t i m i
5、 z a t i o nb e c o m e m o r ea n dm o r ei m p o r t a n t O S P Ft h em o s tf r e q u e n t l yu s e da sI G Ph a ss u b s t i t u t e dR I Pa n db e e n s u p p o r t e db ym o s tc o m p a n i e s T h e r e f o r e ，i th a sg r e a tr e a l i s t i cs i g n i f i c a n c et om a k er e s e a r
6、 c h e s o n 0 S P F I m p r o v e m e n to fr o u t i n ga l g o r i t h mw h i c hi st h ek e r n e lo fr o u t i n go p t i m i z a t i o nh a s d e v e l o p e dr a p i d l yc o n f o r m i n gt on e t w o r k Sd e m a n d s O S P Fu s e sS P Fa l g o r i t h mp o p u l a r l yb a s e d o nL i n
7、 k S t a t ep r o t o c o l ，w h i c hh a sg r e a td i s a d v a n t a g e si n c l u d e dS P T a l g o r i t h mi nc o n d i t i o no f t h er a p i dd e v e l o p m e n to fI n t e m e t T h i sp a p e rp r e s e n t san e w g e n e t i ca l g o r i t h m ( G A ) w h i c h a d o p t st h ei n t
8、e g r a ls e r i a li nc o d i n ga n dd e c o d i n go ft h ep a t ht ob u i l dm o d e la n ds o l v eO S P F r o u t i n gp r o b l e m s C o m p a r e dw i t ht h eg e n e r a lG Aa l g o r i t h mb a s e do nb i n a r yc o d i n g ，t h i s a l g o r i t h m Sc o d i n ga n dd e c o d i n gi ss
9、i m p l ea n dc l e a r A c c o r d i n g l y , i ti n t r o d u c e dn e wg e n e t i c o p e r a t o r s ：p a t hm u t a t i o na n dp a t hc r o s s o v e r C r o s s o v e ra n dm u t a t i o nt o g e t h e rp r o v i d eas e a r c h c a p a b i l i t yt h a tr e s u l t si ni m p r o v e dq u a
10、 l i t yo fs o l u t i o na n de n h a n c e dr a t eo fc o n v e r g e n c e 。T h e p u r p o s ei st oa p p l y i n gg e n e t i ca l g o r i t h m sf o rr o u t i n gs e a r c ho fO S P Fn e t w o r ka n dt oo p e n u pa n e w p a t hf o r t h er o u t i n go fO S P Fn e t w o r k 。 I m p r o v e
11、 m e n to fr o u t i n g - t a b l es t r u c t u r ei st h eo t h e rh a n do fr o u t i n go p t i m i z a t i o np r o b l e m t h ea u t h o rp r e s e n t s 。M a n yf e a t u r e sc o n t r i b u t et ot h ep a c k e t sf o r w a r d i n gp e r f o r m a n c e ，a m o n g w h i c ht h er o u t i
12、 n g - t a b l es t r u c t u r ea n dt h er o u t i n gl o o k u pa l g o r i t h mi sc r u c i a l 。O S P Ff i n d st h e o p t i m a lp a t hb yw a yo fr o u t i n g t a b l e 。T h i sp a p e rg i v e san e wr o u t i n g ，t a b l es t r u c t u r eb a s e do n i m p r o v e dA V Ld a t es t r u
13、c t u r ea n di t sr a p i da d d i t i o n & d e l e t i o na l g o r i t h mb a s e do ns e l e c t i o n m e t h o d A V Lf i t sm e m o r ys a v e ，w h i c hn e e d sq u i c kr e s p o n d 。I ti sg o o dt ob ea sr o u t i n g t a b l e s t r u c t u r e T h er a p i da d d i t i o n & d e l e t
14、i o na l g o r i t h mh a ss i m p l eo p e r a t i o n ，h i g hs p e e da n dm o r e s p a c ee f f i c i e n c y I tr a i s e sa d d i t i o na n dd e l e t i o ns p e e do fr o u t i n ge f f i c i e n t l y C o m p a r i n g w i t he x i s t i n gr e a s e a r c h ，t h i sp a p e rr e a s e a r
15、c h e so nr o u t i n g o p t i m i z a t i o nb o t ho n r o u t i n gp o l i c ya n dr o u t i n gm e c h a n i s m T h es i m u l a t i o ns h o w st h a ta p p l i c a t i o no fG Ap r o v i d e s h i g hs p e e do fO S P Fc o n v e r g e n c ea n dt h es e a r c hc a p b i l i t yo fo p t i m a
16、 lr o u t i n ga n dt h ei m p r o v e d r o u t i n g t a b l eo p e r a t i o ne n h a n c e se f f i c i e n c yo fr o u t i n gs e a r c ha n dr o u t i n gu p d a t e B o t ho ft h e m a c h i e v et h ep u r p o s eo f r o u t i n go p t i m i z a t i o n 。 K e y w o r d s ：O S P F ，R o u tin go p ti m iz a tio n ，G e n e tica lg o rit h m ，R o u tin g - t a b le ，A V L 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他
