（计算机软件与理论专业论文）基于ospf协议的快速路由收敛算法研究.pdf

南京邮电大学硕士学位论文中文摘要 中文摘要 o s p f 协议是目前广泛使用的链路状态协议之一。路由算法在对路由协议的性能起着 重要的作用。所以提高路由算法的效率从而使路由达到快速收敛，是当前路由研究方面的 一个热点。 本文在总结他人研究成果的基础上，提出一种完全动态s p t ( c o m p l e t e l yd y n a m i co f s h o r t e s tp a t ht r e e ) 算法，简称c ds p t 算法。该算法的主要思想是在网络拓扑发生变化 时，充分利用旧的s p t 中的有用信息，通过动态更新的方法得到新的s p t ，从而生成新的 路由表，由于该算法能够在很大程度上减少计算量，从而可以达到路由的快速收敛。网络 拓扑的变化主要包括链路状态的改变，即链路权值得增加或减少( 把链路故障的出现和恢 复看作权值增加和减少的极端情况) 和节点的变化，即节点的增加与减少( 把节点故障的 出现和恢复看作节点的加入与退出的极端情况) 。 c d _ s p t 算法在解决链路的变化时借鉴他人提出的较为成熟的算法并稍加完善，而在 结点增加或者减少所引起相应的边发生变化的情况，给出了一个新的解决方案。该算法可 以有效地利用旧的s p t 信息对网络状态的变化做出反应，快速的计算出新的s p t 。经过测 试，与原来的算法相比，该算法在构造s p t 方面的效率有所提高。 关键词：路由协议，最短路径优先算法，最短路径树，动态更新 南京邮电大学硕士学位论文 a b s t r a c t a bs t r a c t o s p f ( o p e ns h o r t e s tp a h tf i r s t ) p r o t o c o li s o n ek i n do fm a n yw i d e l yu s e dl i n k - s t a t e p r o t o c o l s ，r o u t i n ga l g o r i t h mp l a y sa ni m p o r t a n tr o l ei nt h ep e r f o r m a n c eo fr o u t i n gp r o t o c o l s ，s o h o wt oi m p r o v et h ee f f i c i e n c eo f r o u t i n ga l g o r i t h ms oa st oa c h i e v ef a s tc o n v e r g e n c ei sah o t t o p i ci nr o u t i n gr e s e a r c hn o w a d a y s t h i sp a p e rp r e s e n t sac o m p l e t e l yd y n a m i ca l g o r i t h mo fc o m p u t i n gs h o r t e s tp a t ht r e e ，t h a t i sc d s p ta l g o r i t h m t h eb a s i ct h e o r yo ft h i sa l g o r i t h mi st ou s ea v a i l a b l ei n f o r m a t i o ni nt h e o l ds p ta n dg e tt h en e w s p t t h r o u g hd y n a m i cu p d a t ew h e nt h en e t w o r kt o p o l o g yc h a n g e s ，a n d t h e nc r e a t eai l e wr o u t et a l b ea c c o r d i n gt ot h en e ws p t c d s p ta l g o r i h mc a l lg r e a t l yr e d u c e c o m p u t a t i o n ，f u r t h e rm o r e ，i tc a i la c h i e v ef a s tc o n v e r g e n c eo fr o u t i n g t h ec h a n g e so fn e t w o r k t o p o l o g ym a i n l yi n c l u d ec h a n g e so fl i n ks t a t e ，t h e ya r et h ei n c r e a s eo rr e d u c eo fl i n k s w e i g h t ( a l i n kf a i l u r eo r r e c o v e r yi st a k i n ga st h eo u t m o s to ft h el i n kw e i g h t si n c r e a s eo rr e d u c e ) a n d c h a n g e so fn o d e s ，t h e ya r ee n t r a n c eo re x i to fn o d e s ( an o d ea d d i n gt oo re x i tf r o mt h en e t w o r k i st a k i n ga sa s p e c i a ls t u a t i o no fn o d e si n c r e a s eo rr e d u c e ) w h e ni tc o m e st os o l v ec h a n g e so fl i n k s ，c d _ s p ta l g o r i t h mu s e sa ne x i s t e d c o m p a r a t i v e l ym a t u r ea l g o r i t h mf o rr e f e r e n c ea n di m p r o v e st h ea l g o r i t h m ，f o rt h ec h a n g e so f n o d e si n c r e a s eo rr e d u c e ，c d s p ta l g o r i t h mp r e s e n t san e ws o l u t i o n t h i sa l g o r i t h mc a l l e f f i c i e n t l yu s et h eu s a b l ei n f o r m a t i o no fo l ds p ta n dr e s p o n s et ot h ec h a n g e so fn e t w o r k t o p o l o g y , t h e ni tc a nc o m p u t ei l e ws p tf a s t l y t e s t i n gr e s u l t ss h o wt h a tc d s p ta l g o r i t h mi s m o r ee f f e c t i v ei nc r e a t i n gs p tc o m p a r e dt ot h ee x i s t e da l g o r i t h m k e yw o r d s ：r o u t i n gp r o t o c o l ，s h o r t e s tp a t hf i r s ta l g o r i t h m ，s h o r t e s tp a t ht r e e ，d y n a m i c u p d a t e i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：蔓望堑日期：! 篁：生! ； 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：南耗娟导师签名：碰吼盟 南京邮电大学硕士研究生学位论文 第一章引言 1 1 课题背景 第一章引言 目前的t c p i p 网络，全部是通过路由器互连起来的。路由协议 1 2 ( r o u t i n g p r o t o c 0 1 ) 是路由器之间实现路由信息共享的一种机制，它允许路由器之间相互交换和维 护各自的路由表。当台路由器的路由表由于某种原因发生变化时，它需要及时地将这一 变化通知与之相连接的其他路由器，以保证数据的正确传递。 路由动作包括两项基本内容：寻径和转发 3 4 。寻径即判定到达目的地的最佳路径， 由路由选择算法来实现。由于涉及到不同的路由选择协议和路由选择算法，要相对复杂一 些。为了判定最佳路径，路由选择算法必须启动并维护包含路由信息的路由表，其中路由 信息依赖于所用的路由选择算法而不尽相同。路由选择算法将收集到的不同信息填入路由 表中，根据路由表可将目的网络与下一站( n e x th o p ) 的关系告诉路由器。路由器间互通 信息进行路由更新，更新维护路由表使之正确反映网络的拓扑变化，并由路由器根据量度 来决定最佳路径。这就是路由选择协议( r o u t i n gp r o t o c 0 1 ) ，例如路由信息协议( r i p ) 5 、 开放式最短路径优先协议( o s p f ) 和边界网关协议( b g p ) 等。 路由转发协议和路由选择协议是相互配合又相互独立的概念，前者使用后者维护的路 由表，同时后者要利用前者提供的功能来发布路由协议数据分组。下文中提到的路由协议， 除非特别说明，都是指路由选择协议 6 。 路由算法【7 】是一个通信网路中的重要组成部分，它在很大程度上决定了网络的性能。 路由算法层出不穷，目的都是为了寻找最优路径( 或者满足要求的路径) 来传递信息，提高 服务质量。路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的 寻径结果，因此选择路由算法一定要仔细，在选择路由算法中，其中有一点很重要，就是 快速收敛性质：所谓收敛，是指直接或间接交换路由信息的组路由器在网络的拓扑结构 方面或者说在网络的路由信息方面达成一致。路由协议必须通过某种算法使各路由器尽快 达到收敛状态。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由 更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路 径。收敛慢的路由算法会造成路径循环或者网络中断。 笫1 页 南京邮电大学硕士研究生学位论文第一章引言 链路状态法是现在网络常用的路由算法，o s p f 算法是一种基于区域实现的、建立在 链路状态( l i n ks t a t e ) 算法和最短路径优先( s p f ) 算法基础之上的内部网关动态路由协 议【9 】。每个运行o s p f 算法的路由器都维护一个用于跟踪网络链路状态的链路状态数据 库( l s d b ) 。该数据库中存储的是反映路由器及其链路状态的各种链路状态通告( l s a ) ， 这些状态包括路由器可用接口、已知可达路由和各链路的状态信息。链路状态数据库实际 上就是一张有关该区域的完整的网络映射图，是路由器建立路由表的依据。一个自治系统 内的路由器要形成对网络拓扑结构的一致视图，就必须保持链路状态数据库的同步。o s p f 依靠邻接协议、交换协议和扩散协议来完成o s p f 包的交互过程，并最终实现同一路由区 域中所有路由器的l s d b 同步。o s p f ( o p e ns h o r t e s tp a t hf i r s t ) 是一种链路状态路由协 议，它更适合于口网络，对于整个网络的发展，保证网络的性能，具有十分重要的意义 【l o 。 o s p f 中计算s p t 时使用的是d i j k a s t r a 1l 】算法，它是一种静态算法，当网络的拓扑 结构发生变化时，需要调用d i j k a s t r a 算法重新计算s p t ，也就是说，几条链路状态的变 化会导致每个路由器重新计算自己的s p t 和相应路由表的完全更新。然而通过研究发现， 在很多情况下，与旧的s p t 比较，新的s p t 只有一点甚至没有发生什么改变，这是因为 在一个相当大的路由区域内只有很少几条链路状态的改变不会对s p t 产生太大的影响。 这样一来，由静态算法重构s p t 导致了许多不必要的计算和路由表的完全更新，增加了 计算量，不利于快速收敛和网络稳定 1 3 】。目前已有人提出不少新的或者改进的路由算法， 但都存在不同程度的缺点，期待人们更进一步、深入完善的研究【1 2 】。 鉴于此，本文以动态更新s p t 为基本思想，在总结他人研究成果的基础上，提出了一 种更新s p t 的完全动态s p t ( c o m p l e t e l yd y n a m i co fs h o r t e s tp a t ht r e e ) 算法，该算 法将网络拓扑变化情况进行分类，并根据不同的情况给出不同的解决方案，在更新s p t 时充分利用旧s p t 的有用信息，从而大大减少计算量，在尽量保持原有s p t 信息的同时也 保持了路由表的稳定，从而维护网络的稳定与原有算法相比，c d _ s p t 算法能够有效提高 计算速度，达到路由协议的快速收敛。 1 2 课题来源及研究目标 本课题来源于中兴基金项目路由协议的快速收敛。路由协议的快速收敛包括快速 第2 页 南京邮电大学硕士研究生学位论文 第一覃引言 的检测，快速的路由计算和快速的路由生效。该项目对这三个方面都进行了研究，本论文 中的内容属于该项目中一个子模块快速的路由计算，基于目前网络上o s p f 协议的广 泛使用，本文主要研究o s p f 协议中s p f 算法的快速计算。 本文的主要目标是提出一种完全动态更新s p t 的算法，即c d s p t 算法。该算法基 于分析边在构建新的s p t 时时否发生作用，把发生作用的边应用的我们的算法中，其余 的保持不变，c ds p t 算法能够针对网络拓扑的不同变化做出相应的反应，c d s p t 算法 在解决链路的变化时借鉴他人提出的较为成熟的算法并稍加完善，而在结点增加或者减少 所引起相应的边发生变化的情况，给出了一个新的解决方案。并且尽可能地保持已有s p t 的拓扑结构来保持路由表的稳定性，从而能够达到路由的快速计算。 1 3 本文组织 全文共分六个章节，内容组织如下： 本文第一章介绍了本课题的背景、来源，以及本文提出的完全动态更新s p t 算法， 并给出了本文组织； 第二章介绍了o s p f 协议的相关概念，包括o s p f 协议的原理和工作机制、o s p f 中 的网络类型、o s p f 中的路由器类型、链路状态数据库的概念以及本文重点关注的s p t 概 念，分析了目前已有的改进s p f 算法的研究，看到其值得借鉴的优点，也找到了他们的 不足之处。 第三章主要介绍了完全动态更新s p t ( c ds p t ) 算法的设计思路，给出了算法的实 例介绍，相关定义描述和算法的伪码描述。 第四章主要介绍了完全动态更新s p t ( c ds p t ) 算法的实现，给出了算法中用到的 相关数据结构的定义，包括通用数据库的定义、s p t 结构的定义、链路状态数据库( l s d b ) 的定义和其他相关定义，并且给出了算法的工作流程图和整体设计。 第五章对得到的该算法系统进行了详细的测试，并对测试得到的大量数据进行仿真， 通过与原有算法进行比较，可以看出本文提出的c ds p t 算法在重新计算s p t 方面的效 率大有改善。 第六章总结了本文所做的工作，并对该课题进一步研究的方向进行了展望。 第3 页 南京邮电大学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 第二章基于o s p f 的改进路由算法研究 上一章介绍了路由协议和路由算法的基本概念，并给出了全篇文章的组织结构。本章 重点介绍o s p f 协议的相关概念，路由算法的分类和设计目标，以及快速收敛的路由算法 的研究现状。 2 1o s p f 协议概述 2 1 1o s p f 协议工作原理 早期的i n t e r n e t 是由a r p a n e t 及其伙伴网络的互联发展起来的，一直到8 0 年代初期， 它还是一个单一的网络。随着i n t e r n e t 的发展，接入i n t e r n e t 的路由器越来越多，路由 负载不断增加，路由表的大小也随着接入的网络数量的增加而增加。将i n t e r n e t 划分成 一系列的自治系统( a u t o n o m o u ss y s t e m ，a s ) 可解决统一网络内路由器数目增加带来的 一系列问题。自治系统之间通过专门的路由器进行连接，这些路由器之间交换可达性信息， 寻找可达路径。这样一来，可大大的减少路由表的条数，减小网络的规模，让网络更加便 于管理。 o s p f 是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 ) 提出的一种基于链路状态的内部网关 路由协议，其工作过程概述如下 1 4 - 1 5 ： ( 1 ) 运行o s p f 的路由器在自身的所有启动了o s p f 协议的端口发送h e l l o 协议分组。如 果在同一数据链路上的两台路由器能够就h e l l o 协议分组中包含的参数进行协商 达成一致，它们之间就能成为n e i g h b o r s 。 ( 2 ) 邻接关系( a d j a c e n c i e s ) 。我们可以将这种关系看作是虚拟的点到点链路，它形成 于己经构成n e i g h b o r 关系的路由器之间，取决于交换h e l l o 协议分组的路由单元 类型和端口目前所处于的网络类型。 ( 3 ) 每个路由单元都会与所有已经和它建立了邻接关系的路由单元交换链路状态公告 ( l s a ) 。l s a 描述了所有路由单元的链接或接口，还包括这些链路的状态。这些链 路可能连接到存根网络( s t u bn e t w o r k ) ，也就是没有连接其它任何路由器的网络： 第4 页 南京邮电大学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 也连接到其它路由器或其它区域内的网络：甚至可能连接到路由域外。正是因为存 在多种类型的链路信息，o s p f 定义了多种l s a 类型对它们进行描述。 ( 4 ) 每一个路由单元从它的邻接路由器那里收到一个l s a 记录以后，会在将该记录存放 到链路状态数据库中的同时将该l s a 的副本发送给其它邻接路由器。 ( 5 ) 使用这种区域内洪泛l s a 的机制，所有域内路由器都会拥有一致的链路状态数据 库。 ( 6 ) 一旦数据库信息被收集完整，每一个路由单元都会独立运行s p f ( 最短路径优先) 算 法，以自己为生成树的根，为每一个目的网络计算出一条代价最低的无环路径，我 们将计算的结果称为s p t 树。 ( 7 ) 每个路由单元都根据自己计算得出的s p f 生成树构建自身的路由表。 当所有的链路状态信息被洪泛到本区域内的所有路由器以后，也就是，链路状态数据 库在本区域内同步以后，下一步的任务就是建立路由表。我们可以看到，o s p f 是一个“安 静”的路由协议，一旦l s a 数据库的同步完以后，在相邻路由器之间交换h e l l o 协议单元 作为链路存活信号，而对l s a 来说，以3 0 分钟作为更新周期。如果网络拓扑在此期间没 有发生改变，就不会有任何其它路由协议相关事件产生。 2 1 2o s p f 协议中路由器类型 在划分自治系统的基础之上，在o s p f 协议中，又将一个自治系统划分为若干个集合， 这样按照一定的o s p f 路由法则组合在一起的网络或路由器的集合被称作区域( a r e a ) 。 随着区域概念的引入，各个路由器的作用于它们连接的区域密切相关，o s p f 协议定义 了四种路由器类型 1 6 3 ： ( 1 ) 区域内路由器( i n t e r n a lr o u t e r s ) ，该路由器的所有端口都处在同一区域内，这 种路由器拥有唯一的链路状态数据库。 ( 2 ) 区域边界路由器a b r ( a r e ab o r d e rr o u t e r ) ，该类路由器将多个二级区域连接到 骨干区域，作为非骨干区域到达骨干区域流量的网关。它可以同时属于两个以上的 区域，但其中一个必须是骨干区域。a b r 与骨干区域之间可以是物理连接，也可以 是逻辑上的连接。 ( 3 ) 骨干路由器( b a c k b o n er o u t e r s ) ，该类路由器至少有一个接口属于骨干区域。因 第5 页 南京邮电大学硕士研究生学位论文 第二章基于o s p f 的改进路由算法研冗 此，所有的a b r 和位于骨干区域( b a c k b o n ea r e a ) 的内部路由器都是骨干路由器。 ( 4 )自治系统边界路由器a s b r ( a u t o n o m o u ss y s t e mb o u n d a r yr o u t e r ) ，与其他a s 交 换路由信息，是o s p f 路由区域内通往外部世界的网关。a s b r 将它从外部路由区域 得到的路由信息注入o s p f 路由区域。a s b r 也可能同时充当i n t e r n a lr o u t e r 、 b a c k b o n er o u t e r 和a b r 的角色。 2 1 3o s p f 协议的网络类型 o s p f 定义了五种网络类型，包括 1 7 - 1 8 ： ( 1 ) 点对点网络( p o i n t - t o - p o i n t ) ，点对点网络用来连接单个路由器对。点对点链路 上的邻居路由器形成邻接关系以后，在这样的网络上，o s p p 数据单元的目的地址 常常用d 类保留地址2 2 4 0 0 5 表示，称为a l l s p f r o u t e r s 。 ( 2 ) 广播网络( b r o a d c a s t ) ，当链路层协议是e e t h e r n e t 、f d d i 时，o s p f 缺省认为网 络类型是b r o a d c a s t 。在这里最好把它称为广播多路访问网络，以便与后面的非广 播多路访问网络相区别。在该类型的网络中，通常以组播形式( 2 2 4 0 0 5 和 2 2 4 0 0 6 ) 发送协议报文。 ( 3 ) 非广播多路访问网络( n o n - b r o a d c a s tm u l t i - a c c e s s ，n b m a ) ，当链路层协议是帧 中继或a t m 时，o s p f 缺省认为网络类型是n b m a 。在该类型的网络中，以单播形式 发送协议报文。 ( 4 ) 点到多点网络( p o i n t t o m u l t i p o i n t ，p 2 m p ) ，没有一种链路层协议会被缺省地认 为是p 2 m p 类型。点到多点网络必须是其他的网络类型强制更改的。常用的做法是 将非全连通的n b m a 改为点到多点的网络。在该类型的网络中，以组播形式 ( 2 2 4 0 0 5 ) 发送协议报文。 ( 5 ) 虚拟链路( v i r t u a ll i n k s ) ，虚拟链路是一种特殊的配置方式，它被路由单元视 为非编号的点对点网络( u n n u m b e r e dp o i n t - t o - p o i n tn e t w o r k ) ，o s p f 协议单元 在虚拟链路上一单播( u n i c a s t ) 的形式发送。 除了这五种类型的分类方式以外，我们有一个更加简单的分类方式，仅仅将网络分成 传输( t r a n s i t ) 网络和存根( s t u b ) 网络两种： ( 1 ) 传输网络( t r a n s i tn e t w o r k ) 与两个以上路由器连接，传输的数据单元可能源于或 第6 页 南京邮电人学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 者中止于本网络，也可能源端和目的端均不在本网络内部。 ( 2 ) 存根网络( s t u bn e t w o r k ) 仅仅与一个路由器相连接。存根网络上数据单元的源地址 或者目的地址至少有一个属于本网络。 2 1 4l s a 及l s d b 介绍 作为一种链路状态的路由协议，o s p f 将链路状态广播数据包l s a ( l i n ks t a t e a d v e r t i s e m e n t ) 传送给在某一区域内的所有路由器。o s p f 中有五种常见的l s a 1 5 ： ( 1 ) 类型l r o u t e rl s a ，这是每一个o s p f 路由区域内的路由器都要产生的基本l s a 类型，包含了每个路由器链路、接口的代价和当前状态，该l s a 仅仅在它产生的 o s p f 区域内传播。 ( 2 )类型2 - n e t w o r kl s a ，如果o s p f 路由域内存在多路访问网络，该多路访问网络 的d r 路由器就会生成n e t w o r kl s a ，描述该多路访问网络上包括自己在内的所有 路由单元，该l s a 也仅仅在它产生的o s p f 区域内传播。 ( 3 ) 类型3 叫e t w o r ks u m m a r yl s a ，同样由a b r 产生，目的是为了向该a b r 连接的 某一区域通告目的网络的可达性。该l s a 的产生方向既可能是向二级区域通告外部 目的地的可达性，也可能是向主干区域通告二级区域的可达性。当路由器收到来自 a b r 的第三类l s a 以后，它并不通过运行s p f 的方法来构成新的路由表项目，而是 简单的将自己到达a b r 的代价加上l s a 中所描述的代价后直接添加到路由表当中。 ( 4 ) 类型4 a s b rs u m m a r yl s a ，也源于a b r ，该类型l s a 与类型3 的l s a 目的地有 所不同，a s b rs u m m a r yl s a 的目的地是a s b r ，而不像n e t w o r ks u m m a r yl s a ，目 的地是某一个网络， ( 5 ) 类型5 a u t o n o m o u ss y s t e me x t e r n a ll s a ，由a s b r 产生，目的是将o s p f 路由 区域以外的路由信息或者是默认路由信息注入区域内。 o s p f 由两个互相关联的主要部分组成：h e l l o 协议和可靠泛洪( f l o o d i n g ) 机制。h e l l o 协议检测邻居并维护邻接关系，可靠泛洪机制可以确保统一域中的所有的o s p f 路由器始 终具有一致的链路状态数据库。 第7 页 堕塞坚皇奎堂堡圭堕塑生堂垡丝茎墨三雯茔王全兰坚塑墼鲨堕堕墨鲨型塑 在o s p f 路由协议中，将一个自治系统划分为若干区域。在一个区域内，所有的o s p f 路由器都需要维护一个相同的链路状态数据库，这个数据库其实是一张关于这个区域的网 络拓扑图，它是一个有向图，网络和路由器是这个图中的顶点，网络和路由器之间以及路 由器和路由器之间的关系则用图中的边来表示：如果一个表示路由器的点和一个表示网络 的点用一条边连接起来，则表示这个路由器有一个接口与这个网络相连。按照这样的规则， 可以得出如图2 1 所示的一个有向图用于表示网络拓扑。所有属于该区域的路由器都通过 一定的方式来存放该拓扑图，这种方式便是链路状态数据库。图2 - 1 所示的拓扑结构在链 路状态数据库中可以逻辑表示为表2 1 所示。在这个数据库的基础上，就可以通过 d i j k s t r a 算法得出到达目的地的最短路径。到达网络中各个节点的最短路径可以用一个 最短路径树来表示 1 6 ，最短路径树的计算将在下一小节介绍。 图2 - 1 网络拓扑 表2 - 1 链路状态数据库的逻辑表示 第8 页 南京邮电大学硕士研究生学位论文 第二章基于o s p f 的改进路由算法研究 l ur b r cr dn l r a o r b 0 r c o r d2 0 n l 1 055 n 2 5 n 35 n 42 0 n 4 2 0 2 1 5 最短路径优先算法和最短路径树 在0 s p f 路由协议中，将一个自治系统划分为若干区域。在一个区域内，所有的0 s p f 路由器都需要维护一个相同的链路状态数据库，这个数据库其实是一张关于这个区域的网 络拓扑图，图中的每一条边都有一个相应的权值，表示向该方向传输数据的代价。在这张 图的基础上路由器就可以通过s p f 算法来计算到每一个目的地的最短路径，得到一个以自 己为根节点的最短路径树，从而生成路由表 1 9 。就0 s p f 协议而言，主要的消耗就在s p f 算法的处理中。目前最常用的s p f 算法是d i j k s t r a 算法。 以r a 为例，在其上运行d i j k s t r a 算法，得到最短路径树如图2 2 所示。然后再根据 这个最短路径树来计算出r a 的路由表，如表2 - 2 所示。由表2 - 2 可以清楚地获得到达目 的地的费用和路径。如由r a 到达网络n 2 ，由表2 - 2 可知，其费用是3 5 ，下一跳网关是 r b 。 r a n l n 4 n 5 图2 - 2 以i r a 为根的最短路径树 表2 2r a 的路由表 第9 页 r e 3 南京邮电大学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 目的网络地址下一跳网关费用 n l1 0 n 2r b3 0 n 3r c 1 5 n 4r b3 0 n 5r b3 5 2 2 路由算法 路由算法是一个通信网路中的重要组成部分，它在很大程度上决定了网络的性能。链 路状态法是现在网络常用的路由算法。 2 2 1 路由算法分类 路由算法按照种类可分为以下几种：静态和动态、单路和多路、平等和分级、源路由 和透明路由、域内和域间、链路状态和距离向量。这里只介绍链路状态算法和距离向量算 法【8 】。 链路状态算法( 也称最短路径算法) 发送路由信息到互联网上所有的结点，然而对于 每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。距离向量算法( 也 称为b e l l m a n f o r d 算法) 则要求每个路由器发送其路由表全部或部分信息，但仅发送到 邻近结点上。从本质上来说，链路状态算法将少量更新信息发送至网络各处，而距离向量 算法发送大量更新信息至邻接路由器。 由于链路状态算法收敛更快，因此它在一定程度上比距离向量算法更不易产生路由循 环。但另一方面，链路状态算法要求比距离向量算法有更强的c p u 能力和更多的内存空 间，因此链路状态算法将会在实现时显得更昂贵一些。除了这些区别，两种算法在大多数 环境下都能很好地运行。 路由算法使用了许多种不同的度量标准去决定最佳路径 1 8 1 1 2 5 1 。复杂的路e h 算法可 能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度量、再填 入路由表中，作为寻径的标准。通常所使用的度量有：路径长度、可靠性、时延、带宽、 负载、通信成本等 2 0 】。 第1 0 页 南京邮电大学硕士研究生学位论文 第二章基于o s p f 的改进路由算法研究 2 2 2 路由算法设计目标 在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果，因此 选择路由算法一定要仔细。通常需要综合考虑以下几个设计目标【8 】： ( 1 ) 最优化：指路由算法选择最佳路径的能力。根据m e t r i c 的值和权值来计算。例如 有一种路由算法可能使用跳数和延迟，但可能延迟的权值要大些。当然，路由协议 必须严格定义计算m e t r i c 的算法。 ( 2 ) 简洁、低耗：算法设计简洁，利用最少的软件和开销，提供最有效的功能。 路由协议必须高效地提供其功能，尽量减少软件和应用的开销。当实现路由算法的软件 必须运行在物理资源有限的计算机上时高效尤其重要。 ( 3 ) 健壮、稳定：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或 操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障 时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境 下被证实是可靠的。 ( 4 )快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事 件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络， 引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由 算法会造成路径循环或网络中断。 ( 5 )灵活性：路由算法可以快速、准确地适应各种网络环境。例如，某个网段发生故障， 路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径。 2 3 快速收敛的路由算法 在前面已经提到过，o s p f 的消耗主要在s p f 算法的处理上。因为，在一个路由区域 ( r o u t i n ga r e a ) 内，当网络拓扑发生变化时，例如，一条链路d o w n 掉、恢复或者路由 代价发生改变，甚至是路由器d o w n 掉或者恢复，每台路由器都会获得变化的信息，在网 络拓扑更新之后，每台路由器就会重新计算s p t 。在目前的实际应用中，重新计算s p t 就 是删除当前的s p t ，调用最短路径优先算法重新构造s p t 。构造s p t 树最常用的算法就是 著名的d i j k s t r a 算法 1 1 ，这是一种静态算法。使用静态算法有两个缺点：一是网络中 的链路不断变化时，重新计算s p t 的计算量大，耗费c p u 。二是容易导致网络的不稳定 第1 l 页 南京邮电大学硕二t 研究生学位论文 第二章基于o s p f 的改进路由算法研究 2 2 2 4 。因为从一个路由器到另一个路由器可能同时存在多条具有相同最短距离的路 径，在重新计算s p t 时，这个路由器可能会随机选择一条具有相同最短距离的路径来转发 它的信息表，这会引起路由器经常性地更新路由转发表的信息，从而增加路由错误和路由 器失败的风险。因此，要提高0 s p f 协议的收敛速度，关键就是要改进s p f 算法。 2 3 1 改进的d i j k s t r a 算法 文献 2 3 中提出了在d i j k s t r a 算法基础上设计的一种改进算法，使得在考虑边上代 价的同时，亦将节点上的代价计算在内，能找出更合理的最短路径。 设一个带权有向图为g ，g = ( v ，t ) ，其中v 为顶点集合，t 为边的集合。g 中顶点数 为n ，该算法中的图g 限于讨论简单图( 无环和重边) 。使用改进算法求从顶点v 0 ( 称为源 点) 到其它各顶点的最短路径长度和所经过的最短路径，无向图的存储结构如图2 4 。 图2 - 3 无向图 ( 1 ) 用链表数组m g r a p h 来存储矩阵g 。将邻接矩阵的每一行用一个单链表来表示，链 表中只有非的元素，每个节点有两个元素，一个为所在的列值，一个为此点的 权值，图2 - 3 中无向图的存储格式如图2 - 4 所示。 ( 2 ) 一维数组d 来存储各顶点到v 0 的最短距离。 第1 2 页 南京邮电大学硕士研究生学位论文 第二章基于o s p f 的改进路由算法研究 图2 4 无向图的存储结构 ( 3 ) 用一维数组p 来存储前驱点。 ( 4 ) 用一个辅助双向链表，用来存储正在参与比较的节点，使用双向链表的目的是在 删除节点时降低时间复杂度。 实际应用中的邻接矩阵大多是稀疏矩阵，在计算过程中有大量的参与计算，所以改 进算法的主要思路就是消除冗余存储和冗余计算。 用一个链表数组m g r a p hg n 来表示邻接矩阵，算法步骤如下： ( 1 ) 将与v o 直接相连的节点的d v i 初始化为其权值，其余的置为机器所允许的最大 值。 ( 2 ) 将与v o 直接相连的顶点加入到链表p a t h 中。 ( 3 ) 在p a t h 中找到权值最小的节点w ，并在p a t h 中删除此顶点，如果剩余节点数为0 则结束。 ( 4 ) 修改最短路径：在g 里与w 直接相连的其余各节点v i 的权值中比较d v i 与 d e w l + s ( w ，v i ) 的大小，如果d v i 小于d w + s ( w ，v i ) ，并且如果d v i 为则将 v i 加入到p a t h 中，然后将p v i 的前驱设置为w ，并修改最短路径d v i i = d w + s ( w ，v i ) 。重复步骤( 2 ) 。 但改进的算法仍然存在不足，即在边的代价发生改变时，会影响到整个网络，需重新 计算所有节点的代价，而且如果不采用任何技巧，未标记点将以无序的形式存放在一个链 表或数组中，那么要选择一个最小的权值就必须把所有的点都扫描一遍，在大数据量的情 况下，这无疑是一个制约计算速度的瓶颈。 通过研究发现，通常情况下，当链路状态有所该变时，重新计算得到的sp i i 和原来的 s p t 相比，并没有发生太大的变化。有的甚至完全没有变化。在利用静态算法计算s p t 时 第1 3 页 南京邮电大学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 没有充分利用旧s p t 中的有用信息从而造成效率低下，不必要的变化不仅会引起路由转发 表的冗余更新，而且还会引起一条路由上网络流量的波动 2 4 2 5 ，从而造成网络的不稳 定 2 1 ，这就促使人们研究动态更新s p t 的算法。 2 3 2 基于球绳模型的动态更新s p t 的算法 动态s p t 构造算法是一种根据图的变化和已有s p t 构造新s p t 的生成算法。目前对动 态s p t 构造问题的研究不多，而且相关算法都是在国外文献中提出来的。第一个有效的动 态s p t 算法在文献 2 6 中提出，它是基于d i j k s t r a 的静态计算s p t 的算法演化而来的一 个“算法框架，然而并没有仿真试验结果。文献 2 8 中提出的更新s p t 的算法，它只能 处理边的权值发生变化的情况，并且是边的权值为整数的情况，该算法只是分析了基于整 个网络拓扑结构的算法的最坏复杂性，没有考虑最短路径发生变化的结点的数目，即没有 考虑基于目的结点的算法的复杂性。因此，这样的复杂性并不能表明该算法与静态算法相 比的优越性。因此，找到一个有效地动态更新s p t 的算法至关重要。由计算最短路径引发 的问题引起了人们广泛的关注 3 1 3 2 3 3 。在这些研究中，为了减少计算时间，更新过 程一般分为两个操作：权值增加的操作和权值减少的操作，与静态算法相比确实提高了更 新效率，更新过程也减少了计算时间，但是该算法中仍然存在一些冗余计算，并且这些算 法都没有提出结点发生变化时的解决方案，因此都是一种半动态算法。在文献 3 0 儿3 4 3 5 3 3 6 中，提出一个基于球绳模型( b a l l - s t r i n gw o d e l ) 的算法，该算法把一 条边权值的改变和绳子长度的改变对应起来，下面就简要介绍一下该算法。 球绳模型即是指一种以球代表结点，绳代表边长，绳的长度代表权值的图模型。图 2 5 所示的s p t 树对应图2 - 6 的球绳模型。 下面结合图2 5 和图2 - 6 说明拓扑改变时的模型处理：当拓扑改变前所对应的球绳模 型中的绳a b 断开后，球绳模型会最终稳定到变化后的球绳模型所示的状态。在这一过程 里，首先是绳a b 从模型中断开，随后球b 由于再没有绳可以使其保留在球绳模型内，所 以球b 将从模型中消失；球b 消失后，其上的绳b d 和b g 也将从球绳模型中消失；此时球 g 受重力作用，首先将绳e g 拉直；然后球d 受重力作用将绳c d 拉直，同时其下的球f 也 停止下落，得到了变化后的球绳模型。 第1 4 页 南京邮电大学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 d f h a c d f 发生拓扑变化的s p t s p t 变化前的球绳模型 h 拓扑变化后的s p t s p t 变化后的球绳模型 h 图2 5 图2 - 6 球绳模型的变化 扩展算法的拓扑改变处理正是模拟了这一过程来生成新的s p l i ，算法的完成过程在实 质上是拓扑改变在图中的一个传播过程。算法的详细描述见参考文献 3 5 ， 3 6 。该算法 同样存在冗余计算，因为它在计算过程中把对更新s p t 没有贡献的边同样保存在队列中。 第1 5 页 南京邮电大学硕士研究生学位论文第二章基于o s p f 的改进路由算法研究 2 3 3 一种有效的动态更新s p t 的算法 文献 3 7 3 9 中提出的算法是迄今为止最好的一个算法。该算法基于分析边在构建新 的s p t 时是否发生作用，对构建新的s p t 有用的边被保存在一个队列中，稍后用于s p l i 的更新。与上面的算法相比，该算法中队更新s p t 有用的边的数目大大减少。这样不但减 少了更新s p t 时的计算复杂度，同时通过尽可