（计算机软件与理论专业论文）基于ospf协议的路由优化的研究.pdf

南京邮电人学颂1 ：研究生学位论文 摘要 摘要 随着网络通信的飞速发展，路由优化显褥越来越重要。最常用的i g p 路由信息协议o s p f 己经逐渐取代t r i p ，得到了世界上绝大多数厂商的支持。因此，研究o s p f 网络具有重要 的现实意义。 路由优化的核心路由算法的改进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 网络路由的选择 开辟一条新的途径。 对路幽表结构的改进是作者提出的路由优化的另一个方面。良好的路由表结构设计 和快速的路幽查找算法是实现高速分组转发的关键。o s p f 就是利用踺由表来找到竣优路 径的，论文提出了一种改进的a v l 树的路由表结构和基于选择调整算法的a v l 路由表结构 快速增删算法，平餐二叉树( a v l 树) 适合于存储位置在内存，要求极快速响应的应用，菲 常适合作为路由表的结构。对a v l 树结构路由表的快速增删算法则具有算法简单、速度较 快、易于更新、存储空闽利用率较高等特点，有效锝提高了路由条髫的增加和删除速度。 相比于已有研究，本文的工作从选路策略和选路机制两个方面进行了路由优化的研 究，最后的实验仿真表明遗传算法的应用提高了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 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 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 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 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 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 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 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 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 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 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 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 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 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：牟g 期：单 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 _ 研究生签名： 导薅签每：螂驾期：上蛆 南京邮r 乜人掌顺j i ：研究生学位论文 第一章绪论 1 。羔背景介绍 第一章绪论 ， 路由技术的发展与趋势 所谓路出技术，简单恧言就是采用一种或多种策略，为数据分组从源地址到匿的地址 的转发选择一条或几条理想的路径。路由技术是通过在路由设备( 如路由器等) 运行路由协 议来实现的，协议是路由器的精髓。通过路出器楣互闯的通信，每个路由器都建立一个路 由表，存放网络的路由转发信息。当路由器转发数据分组时，首先根据数据分组的目的地 址查找路嗽表表顼，然后按表顼中提供的相应下一站的地址对该数据分组进行转发 1 】。 路由技术是计算机和通信技术相结合的产物，它随着网络的迅速发展而发展。在各种 网络中，i n t e r n e t 的发展对路由技术的革新起到了关键的作用。在i n t e r n e t 发展的初期， 它是以a r p a n e t 为核心的核心系统结构，其他网络通过核心路由器与a r p a n e t ，主干网相连。 当时的路由协议比较单一，功能也毖较篱单，比较典型的路由协议有r i p l 和e g p 。但随着 网络数量的增长，仍然要求其它网络与核心系统相连，这既不现实也不可能。于是非核心 系统体系结构应运焉生，并弓| 入了鸯治系统( a s ，a u t o n o m o u ss y s t e m ) 的概念。这种j 核 心系统体系结构将整个i n t e r n e t 划分为许多a s ，每个a s 由不同的机构运营管理，在其内部 傻用自己的路由协议，并且可以独立予其他矗s 所选焉的路由协议，随之产主了r i p 一2 ，o s p f 矛d b g p 4 为代表的一批路由协议。 路壶技术发展到现在，缀好地实现了异种嬲络之间互连的墨的。以t c p i p 协议簇为基 础，几乎可以进行任何异种网络间的互连。相对于r i p - 1 ，e g p 等早期路由协议，以r i p 一2 ， o s p f 黍i b g p 4 为代表的路由协议在安全牲、灵活性、稳定性和可扩展性等方面有了极大的改 盏 口a 路由器从静态路由到自治系统内部动态路豳协议再刘自治系统边赛路盘协议，使网络 互连中的路由调整不再仅仅依靠人工操作，而是一旦工作人员配黄完成后，网络上的路由 霹以根据链路的状况和优先条件自动调整最佳路由并随着网络的变化丽动态变化。 对于一个世界范围的网络，要保持它的互通，动态路由协议是必不可少的。 网络通信不断地迅猛发展直接使i n t e r n e t 土产生了许多新的应用。其中不少是高带宽 l 南京邮f 乜人学硕卜研究生学位论文 第一翠绪论 的多媒体应用，譬如网络视频会议、稠络音频视频广播、股市行情发布、多媒体远程教 育、大规模协同计算等。这就带来了带宽的急剧消耗和网络拥挤问题。 为了缓解阙络瓶颈，业赛专家一方强在已有的网络技术和网络运营经验的基础上寻求 新的网络解决方案，另一方面采用方案对现有路由技术进行改进。其中一种方案是改变网 络的软件部分，也就是对现有网络协议的改进。 o s p f 协议是目前i n t e r n e t 广域网和i n t r a n e t 企业网采用最多，应用最广泛的路由协议 之一 2 。由此，o s p f 协议的改进，将对整个路国优曩二阆题来说是非常必要并可行的。 。1 。2 两种基本的动态路由协议类型 ( 1 ) 距离向量路由 这种路 藉类型基于距离向量算法( b e li m a n - f o r d ) 。采用本算法的路由器会周期性 地把自己的路出表拷贝传给与其直接相连的网络邻居。每一个接收者加上个距离向量， 或把它自己的距离“值 i n ! f l 表上，并把这个相加后的结果转发给它的直接邻居。此过程 无定向地发生在直接相连的路融器之闻。这个一步一步的过程导致每一个路由器得到了其 他路由器的信息，最终形成一个网络“距离”的积累视图。积累表用于更新每个路由器的 路幽表。 当这个过程完成时，每个路由器就学习到了到网络资源的“距离的模糊信息。它不 学习和其他路由器相关的任何信息或网络的实际拓扑 通常来说，距离向量协议是非常简单的协议，容易配置、维护和使用。但在一 定环境下会产生路由阉题 3 。比如，当网络失败或发生其他变化时，路由器需要一些时 间才能收敛到对网络拓扑的重新认识。在收敛过程中，网络可能是脆弱的，产生不致的 路囱，甚至路由环。有许多措施来防止这些情况发生，健在收敛避程中，网络的性能仍处 于危险之中。因此，1 日的收敛慢的距离向量协议不适合于大的、复杂的广域网。这样， 随之产生的链路状态路由算法就显示出了极大的优越性。 ( 2 ) 链路状态路由 链路状态路由和距离向量路由这强种动念路由协议类型的基本区裂在于二 者发现和计算到目的地新路由的方式不同。链路状态路由算法，也就是最短路径优先 ( s p f ) 协议，可以维护个复杂的网络拓害 数据蓐。与距离向量路由协议不同，链路 状态协议形成和维护网络路由器的全部信息，以及它们是如何互联的。可以通过和网 络中鲢其德路由器交换链路状态逶告( l s a ) 柬实现这点。交换t l s a 的每一个路由 2 南京邮 【i 人学硕t ：j f 究生学位论文 第一章绪论 器。于是使用收到的l s a 建造一个拓扑数据库。s p f 算法用于计算目的地的可达性。计算的 信息用于更新路由表。这个过程能发现由于组件失败或网络变大而导致的拓扑变化。实际 上，l s a 交换由网络中的事件驱动，而不是周期性地运行，这样能大大减小收敛过程，因为 在这种情况下路由器没有必要等一系列计时器超时后才开始汇聚。链路袱态路由作为 动态路由可以适合任何大小的网络，使网络可以经得起任何不可预知的网络拓扑结构变 化。使用事件( 如变化事件) 来驱动更新( 而不是固定时间间隔的计时器) 能使收敛在拓扑变 化之后更快地进行。但链路状态路由也有不足之处，它对存储器和处理器敏感，并且 可能在在网络传输线路上进行泛洪( f l o o d ) ，因此会大大削弱网络传输数据的能力 4 。 1 。1 3o s p f 协议简介 o s p f 是一种典型的链路状态路由协议，它被设计成在单一自治系统内部运行。采用 o s p f 的路由器彼此交换并保存整个网络的链路信息，从而掌握全网的拓扑结构，独立计算 路由。因为r i p 路由协议不能服务于大型网络，所以，i e t f 的工g p 工作组特别开发出链路状 态协议叫s p f 1 。 最初版本的协议规范见r f c l 2 4 7 ，后来被r f c l 5 8 3 取代，后又被r f c 2 1 7 8 取代，最后发 展成现在的o s p f v 2 ，j m o y 在r f c 2 3 2 8 d p 对o s p f v 2 协议规范做了详尽的描述。每个o s p f 路由 器维持一个同一的描述自治系统拓扑结构的数掘库。从这个数据库，通过构造一棵最短路 径树来计算出一个路由表 1 。 当拓扑结构改变时，o s p f 采用最小路由协议通信量来重新计算路由。o s p f 支持等价多 路访问。它还提供区域路由能力，这使得它能提供额外一级的路由保护和减少路由协议通 信量。另外，所有o s p f 路由协议的交换需经过鉴别认证 2 。 o s p f 是一个内部网关协议，用于在单一自治系统内决策路由。与r i p 相对，o s p f 是链 路状态路由协议。而r i p 是距离矢量路由协议。链路是路由器接口的另一种说法，因此o s p f 也称为接口状态路由协议。o s p f 通过路由器之间通告网络接口的状态来建立链路状态数据 库。生成最短路径树，每个o s p f 路由器使用这些最短路径构造路由表。 o s p f 是一种内部网关协议。这意味着它是在属于同一自治系统的路由器之间发布路由 信，g 。o s p f 协议基于链路状态或s p f 技术。它与基于b e l l m a n - f o r d 算法的传统t c p i p i n t e r n e t 路由协议不同。o s p f 协议由i e t f 的o s p f i 作组开发。它专门为t c p i pi n t e r n e t 环境设计，包括明显支持c i d r 和外部衍生路由信息标签。o s p f 还为路由信息更新提供认证， 当发送接受更新信息时利用i p 多播。许多工作加起来产生了一个能对拓扑变化迅速作出 南京邮也人学硕- i ：研究生学位论文 第一章绪论 反应的协议，赢这些只需要少量的路由信息通信量 1 。 o s p f 仅仅根据在工p 分组首部发现的目的i p 地址来路由工p 分组。o s p f 是一个动态路由协 议。它能迅速侦察到a s 中的拓扑结构变化( 例如路由器接口失效) 和在一段时期的收敛盾计 算出新的无环路由。这个收敛期很短，只包括极少的路由通信量。 在一个链路状态路由协议中，每个路出器维护一个描述自治系统a s 的拓扑结构的数据 库。这个数据库被称为链路状态数据库。每个参与的路由器都有同样的一个数据库。数据 库的每一项描述特定路幽器的局部状态( 例如：路由器的可用接口和可达邻居) 。路由器在 整个自治系统中采用f l o o d i n g 来发布它的局部状态信息。 所有路由器并行运行同样的路出算法。依据链路状态数掘库，每个路由器以自己为根 构造一棵最短路径树。这棵最短路径树给出到自治系统中每一目的地的路径。如果存在到 是的地的多条等价路径，通信量将被均匀分布，这就是o s p f 的负载均衡。 o s p f 将路由范围划分为区域( a r e a s ) ，区域0 ( a r e a o ) ，即主干，是必须的。它将内 部路由分为2 级。如果路由信息必须在2 个域之阍传送，分组必须先送到主干 2 。由于直 到分组到达主干才进行区域域涮路由，这可能导致非最佳路由。小型网络可以只有一个区 域，这个区域必须为区域0 。 o s p f 将网络分为以下几类：点对点( p o i n t - t o p o i n t ) 、多路访问( m u l t i a c c e s s ) 、非 广播式多路访问( n o n - b r o a d c a s tm u l t i a c c e s s ) 。将两台路幽器连接到一起的串行连接为 点对点连接，而以太网和令牌环网段为多路访问。帧中继或x 2 5 为非广播式多路访问。多 路访问网络( 如以太丽) 用指定路由器( d e s i g n a t e dr o u t e r ，d r ) 来避免以太网内每个路由 器与其他每个路由器形成连接。如果每个路由器都和网内其他任一路由器形成连接，将导 致连接数量为2 的爆炸式增长。豫管理以太圈的所有链路状态广告( 1 i n ks t a t e a d v e r t i s e m e n t s ，i s a ) 。选择d r 需要一个选举过程，在这个过程中，也将选举出一个备份 指定路由5 ( b a c k u pd e s i g n a t e dr o u t e r ，b d r ) 。o s p f 提供优先权特征来帮助网络工程师选 择d r 幂n b d r ，但这个实现起来比较困难 5 。 非广播式多路访问网络，如x 2 5 ，也支持指定路由器概念，僵是由于它不支持广播， 所以邻居路由器i d 必须手工指定 5 。在这样一个网络上，如果一个d r 没有邻居的完整列 表，即使网络工作正常，也将导致连接丢失。如果可能的话，建议用点对点连接集合来配 置这样一个网络，这可以避免d r 选举的复杂性。o s p f 检验网络操作的连续性的主要手段是 h e l o 协议。每个o s p f 路由器每隔1 0 秒钟向每个接口发送d 、h e l o 分组。o s p f 邻居通过接受 h e l o 分组获知彼此的存在。h e l o 分组不在o s p f 数据库中记录，但是如果4 0 秒没收到从某个 4 南京邮f 乜大学硕士研究生学位论文 第一苹绪论 邻居来的h e l l o 分组，该邻居就被标记为失效。尽管一个网段的所有路由器的h e l l o 定时器 必须为常量，但是h e l l o 定时器也可以配黄。链路状态广告也有使用期限。如果3 0 分钟还 没有改变，发起路由器将重新广告一个链路状态广告l s a 。 o s p f 作为一种内部网关协议，用于在同一个自治域中的路由器之间发布路由信息。 o s p f 具有支持大型网络、路由收敛快、占用网络资源少等优点，在目前应用的路由协议中 占有相当重要的地位 1 。 有关o s p f 中采用的路由计算方法将在第二章中详细介绍。 1 2 论文课题来源 本课题来源于中兴科技基金一种基于o s p f 的快速路由算法研究与实现，该项目 从改进传统的最短路径算法研究，提出了c d s p t 算法( 更新s p t 完全动念算法) 。本论文 中的内容是对该项目内容的一个扩展，一方面研究基于遗传算法的o s p f 协议的改进，提 出了一种新的遗传算法解决最短路径路由优化问题，探索和应用遗传算法为o s p f 网络路 由的选择开辟一条新的途径；另一方面，考虑到i n t e m e t 路由的不稳定性使得路由表路由 增加和删除的过程变得非常频繁，论文从优化路由查找算法的角度，提出了改进的a v l 树的路由表结构和快速增删算法，以提高路由条目的增加和删除速度。 1 3 论文所要解决的主要问题和组织结构 本论文所要解决的主要问题如下： l 对现有o s p f 路由算法进行分析，总结出其优点和局限。 2 对s p f 算法计算中获得的不够尽如人意的结果，提出一种基于遗传算法的路由算法 模型，从选路策略方面研究基于o s p f 协议的路由优化。 3 研究总结现有的路由表结构和路由查找算法，分析其优缺点，提出一种改进的路 由表结构及其操作算法，从选路机制方面研究基于o s p f 协议的路由优化。 4 对于提出的新的算法，进行网络仿真，分析算法的性能，同现有算法进行比较， 看其是否能够起到路由优化的目的。 本论文的结构安排如下： 第一章，绪论，介绍论文相关背景；第二章，介绍已有路由算法和路由表结构状况： 第三章，介绍用遗传算法实现o s p f 的路由选择：第四章介绍a v l 树结构的路由表及其快速 增删算法：第五章，介绍用z e b r a 进行仿真试验：第六章，总结与展望。 s 南b i i i ；，u 学mj 州究位论丘第市* 盖件研究 第二章相关性研究 21o s p f 中采用的路由计算方法 有关路由表的计算是o s p f 的核心内容，它是动态生成路由器内核路由表的基础。在路 由表条目中，包括有目标地址、目标地址类型、链路路山代价、链路存话时间、链路类型 以及下一跳等内容 6 ，7 8 。 o s p f 能使用下面两种相当简单的方法之一计算链路的路由代价： o s p f 能自动计算使用每个路由接l j 的代价。 非带宽敏感的缺省值可以用于每一个o s p f 接口。 不管使片! | 哪种方法任何一条路山的代价可以通过把路由上遇到的辞个路由器接口代 价相加机制得到。在o s p f 的最短路径树中记录了每个己知目的地的代价。 21 1 自动计算路由 o s p f 能自动计算个接口的代价这个算法以每个接e l 类型支持的带宽为基础 6 。 一条路由上所有接n 计算值的和( g u m ) 形成o s p f 路由决定的基础。基于冗余链路卜可获得 的带宽，这些值能使o s p f i t 算出最小代价的路由。如图2 一l 中的州络显不了这一点。 m 幽2 i 由动计算的路由代价 一妒去 _芦献 璺学。一r o i “ o孵岳一善，广一。_同，占 南京邮电大学颂+ l 研究生学位论文第：章孝只哭性研究 在图2 一l 中，位于网络1 9 3 1 3 0 中的主枫与位于网络1 9 3 。王4 。0 终端系统之间的广域 网路由代价为1 3 8 ( 图中开销即为代价) 。这个代价是这两个网络之间两条t i 链路的代价和 ( 每条6 4 ) ，褥加上以太网接豳至网络1 9 3 。1 。4 。0 的代价。在起点和终点的以太丽接嗣代价 不包含在o s p f 代价计算中，这是因为o s p f 只计算向外的路由器接阴代价表2 一l 汇总了图2 一l 中每个被使焉接园自动计算得出的代价值。 表2 1 每个接口类型的计算路由代价 接口类型代价 l o o m b p sf d d i l lo m b p se th e r n e t1 0 i 。5 4 4 m b p st l 串行链路6 4 5 6 k b p s 串行链路1 7 6 8 2 1 2 使用缺省路由代价计算路由 有一些环境会接受使用缺省路由代价。比如，用户的网络由类似的传输线路组成，那 么缺省值将是可接受的。另外，管理员能手动地为某个特定接口修改代价度量。这样会使 网络管理员在主要仍使用缺省路由代价的前提下，对网络的流量模式进行合理地规划。 ( 1 ) 同构网络 6 】 在同构网络中，所有的传输线路是一样的。比如，所有的l a n 接口都是l o m b p s 的以太 网，所有w a n 接口都跫t l 。在这种情形下，使黑缺省值不大会引起路由闽题。这一点在几 乎没有或有很少路幽冗余的情况下是非常正确的。 如凰2 2 中的网络图就显示了这一点( 图中开销即为代价) 。 7 南京l i i 】f i u 人学i 兜生学位镕i 一目树关忡究 幽22 。l 刖o s i * 缺省路由代价值 在图2 - - 2 中，缺省值1 7 6 8 分配给每一个接口。然而所有的w a n 链路是t i 。考虑到所 有的值都一样，那么分配值为1 1 2 8 ，1 7 6 8 还是1 0 0 0 0 0 0 就没太大关系。例构网络中的路由 决定变成简单算和比较跳数，不管网络中有多少路由兀余，这一点部是f 确的。显然， 在有相当多路由冗余并且使用不同的传输技术的网络中，缺省值将不会选出到任何目的地 的最优路由。 ( 2 ) 手动设置值 6 在一些网络中，希望接受o s p f 缺省路山，之后手动地设置那些不同于缺省链路的特殊 链路值。比如，片j 户网络的铁省代价值可能是1 7 6 85 6 k b p s 目a 行链路的计算值。如果网络 中只有一条或两条链路不提供相同的带宽，就能接受缺省值之后为那些特殊链路设置其他 值。是使用自动计算的路由代价，还是缺省代价，或是手动配詈的代价对o s p f 节点而言都 是小重要的它们会接受所有这样的代价值并训箅得到网络的最短路径树。 213 使用最短路径树计算路由 各种l s a 复制的目的是使路山器能够构成网络拓扑视图。这个拓扑以树的方式安排。 o s p f 路由器形成树的根。这个树给出到所知目的地地址的完整路径，虽然只有下一跳用于 转发报文。其中的原因是简单的，记录到目的地的完整路径使冗余路径的比较和选择最好 路径成为u ，能。如果有多条代价相同的路径，他们会被0 s p f 发现并使用，流量在这些町用 ! ! u ! 二! ! l 型! ! ! ! ! ! ! = ! j ! 壁! ! ! l 链路中大致取得平衡 6 。 出2 - 3 具有路由代价的0 5 旰网鲻 为了更好地理解最短路径树( s p l ，s h o r t e s tp a t ht r e e ) 的概念考虑图2 冲的网 络( 图中丌销即为代价) 。图中的简单网络是个小型0 s p f 网。网络管理员已经启动了路山 代价的自动计算。需要重点注意的是路由器新口6 z 剖的以太网构成了网络1 9 3l 5o 和 1 9 315o 通过路出器2 的另条路径，所以，0 s p f # i 动计算的代价为1 0 ，而相似的代价没 有分配到其它的以太网上。 这个阻络的最短路径树会随路出器的不同而变化。1 訇2 - - 4 是从路由器3 的角度看到的 树。从图中可以明显地看出，树结构使到给定目的地路出代价的计算简化。根路山器( 路 由器3 1 9 3l30 ) 能很快地把到任何目的地的路由上所遇到的路由器接口代价加起柬。从 路由器3 的角度到任何一个网络的路由代价汇总在表2 2 中。对于多于一跳的目的地， 接口代价相加在括号内。 在这个嘲络中，有两条到网络1 9 31 60 的路出。一条路径含更少的跳数，但却有高 得多的代价，这是因为路 b 器2 # u 6 之i j 的低速串行链路的存在。另一条蹄由有更多的跳数， 但却有少得多的总代价。在这种情况f ，0 s p f 会抛弃商代价的路由而使用低代价的路由。 如果这两条冗余的路由具有相同的总代价，0 s w 会在足 由表中维护两条独立的表项并尽可 能平均地在二者之删均衡负载。 南京邮电大学硕+ 研究生学位论文 第二章榻关性研究 图2 4 路由器3 的最短路径树 显然，网络中每个路由器的视图是不一样的。在一个网络中源和目的之间的积累距离 随起点不同而不同。这就是为什么o s p f 路由器使用从其他路由器处通过l s a 更新得到的数 据来构造自己的网络视图，而不直接使用那些信息来更新路出表的原因。 表2 2 从路由器3 到已知目的地的代价 冒的她跳数积累代价 1 9 1 1 3 o0 1 9 1 1 。1 0l6 4 1 9 1 1 2 o26 5 ( 6 4 + 1 ) 1 9 1 1 4 。021 2 8 ( 6 4 + 6 4 ) 1 9 1 1 5 o 31 2 9 ( 6 4 + 1 + 6 4 ) 1 9 1 。l 。6 。o1 8 3 3 ( 6 4 + l + 1 7 6 8 1 9 1 1 6 o41 3 9 ( 6 4 + l + 6 4 + 1 0 ) 2 2 几种路由算法的比较分析 前面简要的介绍t o s p f 计算路由的方法，在这里将几种算法进行简单的比较和说明。 2 。2 。1 最短路径优先算法s p f s p f 算法是e w d ij k s t r a 提出的用来计算在一个图中从个源节点到所有其它节点的 i o 南京邮l 乜人学硕一i ：研究生学位论文 第一二章相关性研冗 最短路径的算法 7 。通常的链路状态路由算法的原理是各个网络节点不必交换通往目的 站点的距离，而只需维护一张网络拓扑结构图，在网络拓扑结构发生变化时及时更新即可。 利用这些图和d i j k s t r a 最短路径算法可以计算出比距离向量协议更为精确的路由实际 上，尽管路由的计算是分布式的，但其结果与集中计算出来的一样精确。 网络拓扑结构图以数据库的形式存在，数据库中的每条记录都代表网络的一条链路， 如图2 5 所示。 图2 5 简单网络拓扑图 采用链路状态数据库形式如表2 3 。数据库中的距离值可以不是1 ，只要使用的量度一 致，则每条直接相连的链路的距离值可以不同。这就保证了有些链路虽然都是直接相连的 但会优先。当然，还可以从另一个角度比如说最小费用的角度去考虑x 2 5 链路l p , f d d i 优先。 设定不同的量度，就可以得到不同优先指数的最短路径表。 表2 3 链路状态数据库 源节点目的节点经过链路距离 a b l1 a c41 a d51 bal1 bc21 bd3l ca 41 c b21 da51 db31 基于链路状态的s p f 算法具有以下优点： 南京邮电大学硕i ；= f i j f 究生学位论文 第二覃相关性研冗 迅速无环路的收敛性。 支持精确的度量值，而且如果需要，可支持多重度量制式。 支持通往一个目的站点的多重路径。 区分不同的外部路由。 当网络中某条链路状态发生变化时，交换扩散协议会迅速把此项变化传遍全网中每个 需要接受此项刷新的节点，每个节点根据此变化重新计算路由表。s p f 算法可以保证即使 网络拓扑结构中无论有多少环路都不影响计算路由过程的快速准确，计算结果无环路且路 由对于网络上链路的敏感性很高。另外，此种算法还可以支持不同的度量制式，可同时支 持最大吞吐量、最短延时、最低费用和最高可靠性等路由表。s p f 算法还支持通往一个目 的站点的多重等价路由和区分不同类型的自治系统外部路由。s p f 是多项式复杂度的。s p f 算法可用来解决树约束问题( 例如，延时约束) 。 虽然s p f 算法在现有的尽力传送业务( b e s t - e f f o r t ) 服务模式的网络中工作的很好， 然而它无法满足各种多媒体业务的o o s 需要，主要表现在： s p f 采用与链路带宽成反比的c o s t 值度量距离来寻找最短路径，没有考虑到多媒体业 务的多个约束条件。 s p f 计算一条最短路径，会忽略了其它可用的路径，这样在业务量迅猛增加的今天， 将会造成一方面最短路径发生拥塞，而其它也可满足业务要求的路径闲置，导致网络业务 的不均衡。 网络拥塞时，网络的延时和丢包率会急剧增加，如果采用延时和丢包率来度量最短路 径，则可以将流量转移到另一条路径上去。但是，这种转移不是部分转移，而是全部转移， 这样，新的路径又会由于负荷太重而拥塞，而原来的路径由于流量的消失而空闲。于是又 会发生新的路径转移，如此反复。这种现象被称为路由震荡 8 。 在新的网络服务模式o o s 中，一方面路由选择策略不再以单一的最小代价为度量值， 而需要满足带宽、延时等多个约束值；另一方面路由选择策略需要对路由进行优化，不仅 要选择最短路径，也要可以选择到其它可行( 次优) 的路径，以充分利用网络中的可用资源， 提高网络资源的利用率。 2 2 2 基于最短路径思想的一些路由算法 组播o s p f 协议是对o s p f 协议的扩展。组播是一种允许一个或多个发送者( 组播源) 发 送单一的数据包到多个接收者( 一次的，同时的) 的网络技术。o s p f 组播路由的拓扑结构通 南京邮| u 大学硕l ：研究生学位论文 第二章相关性硼f 冗 常采用树型结构。这样，一方面可保证信息到不同信宿的并行传输，另一方面，也保证了 数据复制最少 9 ，从而减少冗余信息的传递和降低网络资源的消耗。 目前对于多播路由选择问题己经提出了多种算法。其中最常见的是把路由选择问题形 式化为图论中的斯坦利( s t e i n e r ) 问题，通过求解斯坦利最小树m s t ( m i n i m u ms t e i n e r t r e e ) 来求解代价最小的组播树 1 0 ，1 1 ，1 2 。这问题被证明是n p 一完全问题 9 ，1 3 ， 对这种问题己有了很多启发式算法进行求解，例如k m b 算法 1 1 ，m p h 算法 1 2 ，s p h 算 法 1 4 等。在斯坦利问题中增加q o s 限制条件，提出了采用受限斯坦利最小树解决组播路 由问题的算法。有文献给出了引入延时限制的斯坦利树的启发式算法 9 ，1 5 ，1 6 ，即在满 足一定延时要求的情况下寻找代价最小的斯坦利树。除了启发式算法外，又有人提出了神 经网络的方法计算满足特定延时要求的斯坦利最小树 1 7 ，和采用遗传算法解决时延受限 的组播路由问题 1 8 。但是，后者的算法采用单点交叉算法，其收敛速度不尽人意 1 8 。 此外，又出现了一种遗传算法的解决方案 1 9 ，然而它们在父代交叉操作后生成的斯坦利 树不连续，需要进行修补，实现起来有一定的难度。 基于蚂蚁算法的拥塞规避路由算法 2 0 - 2 2 。该算法模拟自然界中的蚂蚁寻路机制， 能够迅速建立符合一定约束条件的路径，比如最短距离路径、最大带宽路径、最小延时路 径，同时能够预测到链路的拥塞状态，迅速探索一条新的路径，将流量分散，达到解除拥 塞状态的目的。基于蚂蚁算法的路由算法具有分布式特点，可以提供多条路径来应对网络 的变化或者是某个节点发生的故障，从而使网络更加健壮。该算法还可以同时优化不同的 q o s 参数。若以不超过某个时延上限的数据包所占比率来看，该算法要优于链路状态路由 算法，但是该算法也没有很好地解决数据包传输延时和网络丢包问题。 基于模拟退火的多约束路径最优化选择算法。模拟退火( s a ) 算法是最优化问题中用 来获得接近最优解的一种新的方法，自8 0 年代中期以来，已被应用到解决许多最优化问 题中并且能够很好地避免陷入局部最小，s a 算法具有执行简单、很好地给出结果的优点。 该算法将模拟退火方法与路由计算结合起来 2 3 ，提出一种新的组合优化算法。该算法可 以及时从无效的迭代中跳出到其他空间，提高搜索效率，具有全局收敛性，可以在有限次 迭代中快速找到可行路径。该算法是一种有效的启发式算法，在迭代过程中，很好地处理 了局部最优和全局最优的关系，该算法对网络规模和约束个数具有很好的可扩展性。另外 还有一些人将模拟退火算法与路由算法结合起来，应用在不同的网络中，解决不同的问题 2 4 ，2 5 。本算法中，每个节点存储的路径数越多，解的质量越好，温度下降总次数越多， 算法得到解的机会越大。也就是说，该算法要求的参数越多越好，这就大大增加了计算开 销。 1 3 南京邮电人学硕 ：研究生学位论文 第二章相关性研究 2 3 路由表结构设计的主要思路 随着i n t e r n e t 的迅猛发展，用于主干网络互联的核心路由器的接口速率已经达到了 2 5 g b p s 1 0 g b p s 。这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组 分组转发的重要一步就是查找路由表，因此良好的路由表结构设计和快速的路由查找算法 是实现高速分组转发的关键。传统路由器缓慢的转发速度已经成为制约网络发展的巨大瓶 颈 2 6 。 在早期的i n t e r n e t 中，使用分类的i p 地址，路由表结构相对简单，哈希表就能有 效的工作。当一个数据包进入端口，路由器取出网络部分n ，计算出一个哈希函数h ( n ) ， 再进行少量的匹配即可获得转发信息。 引入无分类型编