（信号与信息处理专业论文）ospf路由协议的研究与实现.pdf

o s p f 路由协议的研究与实现 摘要 目前，随着网络规模不断扩大，对路由协议提出了越来越高的要 求，而现今普遍运行的r i p 协议已不能满足这要求。该论文从理论 上阐述了选择o s p f 路由协议的原因及优点。但是由于o s p f 协议 自身的庞大、复杂性，以及网络运行环境的多样性，o s p f 协议在实 际应用中存在众多问题。 本人承担了路由器中动态路由协议o s p f 的改进实现和研究工 作j 主要取得了以下几个方面的成果： 1 针对d i j k s t r a 算法在网络应用中的不足，提出了改进d i j k s t r a 算法。改进d i j k s t a 算法不仅考虑了通信链路上的带宽和传播 延迟的因素，还考虑了路由器上的排队延迟和发送延迟，能 够更加全面的刻画网络状态，找出更为合理的最短路径树。 2 对于虚电路网络上运行o s p f 的改进建议，使o s p f 在虚电路 网络上经济有效的运行。 3 根据网络的需求，编程实现了o s p fv 2 定义的虚连接 ( v i r t u a ll i n k ) 4 同时对o s p f 的q o s 扩展问题进行定性的研究，并探讨了动 态路由协议o s p f 今后的发展情况。 关键词：r i p ，o s p f ，d i j k s t r a ，虚电路，虚连接，q o s t h er e s e a r c ha n di 酽l e m 匣n t a t i o n o f0 s p fr o u t i n gp r o t o c o l a b s t r a c t w i t ht h ed e v e l o p m e n to ft h en e t w o r ks c a l e i tb e c o m e sm o r e i m p o r t a n t t ot h ep e r f o r m a n c eo ft h er o u t i n gp r o t o c 0 1 h o w e v e r t h er i p p r o t o c o l ， w h i c hi s p r e v a l e n t l y u s e di n r o u t i n gt e c h n o l o g y ，c a n n o tr e a c ht h e d e v e l o p i n gr e q u i r e m e n t h e n c e ，i t n e e d so t h e r r o u t i n gp r o t o c o l s t h i s p r o j e c tj u s ta i m s a tt h i sn e e dt oi m p l e m e n tt h eo s p f r o u t i n gp r o t o c 0 1 t h i sd i s s e r t a t i o ni n t r o d u c e st h et h ea d v a n t a g eo ft h er o u t i n gp r o t o c o l 0 s p f b u t ，i ta l s oh a sm a n yp r o b l e m sw t h e nu s e di n a c t u a ln e t w o r k b e c a u s eo ft h ec o m p l e xo ft h eo s p fa n dt h ev a r i e de n v i r o n m e n to ft h e n e t w o r k it a k ei nt h ei m p r o v e m e n ta n dr e s e a r c hj o bo ft h eo s p f , a n dg e ts o m e a c h i e v e m e n t ： a 、a i m e da tt h ei n s u f f i c i e n c yo f d i j k s t r aa l g o r i t h mi nt h ea p p l i c a t i o n o f n e t w o r k ，a ni m p r o v e dd i j k s t r aa l g o r i t h m f o rt h eg r a p h sw i t h c o s t so nt h ee d g e sa n dt h ev e r t i c e si sp r e s e n t e da n dd i s c u s s e di n d e t a i l t h ei m p r o v e d d i j k s t r aa l g o r i t h mc a n d e s c r i b et h es t a t e so f n e t w o r k sm o r e c o m p l e t e l y , a n d i tc a nf i n db e t t e rs h o r t e s t - p a t ht r e e b 、i m p r o v e m e n t a b o u t0 s p f r u n n i n g o nv i r t u a lc i r c u i tn e t w o r km o r e e c o n o m i ca n de f h c i e n t c 、i m p l e m e n t a t i o n o f t h ev 矾u a ll i n kb a s e do nt h eo s p fv 2 小s o m er e s e a r c ha b o u tq o se x t e n s i o no no s p f , a n d t h ee v e l o p m e n t o f0 s p fi nt h ef u t u r e k e y w o r d ：r i p , o s p f ，d i j k s t r a ，v l r t u a lc i r c u i t ，v i r t u a ll i n k 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名；磁蔫日期：五矿坪留咎 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅 和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规 定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 臼期：聊享、 日期： 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 第一章概述 1 1i n t e r n e t 上路由协议的使用现状 在路由器上使用的路由协议有静态路由协议和动态路由协议之分。静态路由 协议不利用网络的信息，只是按照某种固定的规则去选择路由。这样，在网络 的拓扑发生变化的时候，它不能及时的调整自己的路由信息，最多只是由操作 人员偶尔对网络的状态的变化作出反应。由于它不能对网络的改变作出反映， 故一般用于网络规模不大，拓扑结构固定的网络中。其优点是简单，高效，可 靠。与之相反，动态路由协议则能根据网络拓扑的变化( 比如某个网络端口不 能工作) ，在一段网络路由信息汇聚的时间后，计算出新的，正确的路由，以 适应网络流量和拓扑的变化。当然，动态路由协议也有不正常工作的情况，这 就需要静态路由作为它的补充，在这里我们讨论的仅是动态路由协议。 在自治系统内的路由器我们称之为内部网关，它们之间通过交换网络拓扑信 息，来寻找可达路径。在此过程中所使用的路由协议，被称之为内部网关协议 ( i g p ) 。常见的i g p 有：r i p ，o s p f ，i g r p ，e l g r p 等。 在自治系统外的路由器我们称之为外部网关，它们只通过交换可达信息，来 寻找可达路径。连接两个自治系统的外部网关并不需要了解这两个自治系统的 具体的网络拓扑，只需要了解通过它可以到达哪些网络。在此过程中所是使用 的路由协议，被称之为外部网关协议( e g p ) 。常见的e g p 有：e g p ，b g p ， b g p 4 等。 1 2 课题研究的背景及意义 “我们为什么需要网络? ”这是一个老师曾经问他的学生的一个问题。有学 生说“因为我们想去更远的地方。”是的，我们能够通过网络了解发生在很远 的地方的事情。网络是信息的高速公路，它是靠作用于立交桥一样的路由器将 它连接并延伸的。路由器通过查找自己的路由表来获知该将信息往哪一条路上 送，由此可知，路由器需要掌握网络的路由情况，而路由器又是通过路由协议 北京邮电大学硕士研究生毕业论文o s p f 路由协议的研究与实现 来彳导到这一信息的。因此，路由协议对路由器来说是非常懿羼的。路由协议的 好环会壹接彩旗裂蹿鑫器静淫憝。 现在，嗣络上普遍使用的路由协议是r i p 。它是一个非常简单的路由协议， 入们对于它已经作聚深入静绩究，并不甑遗对它进行改进。扶产品的角度来 讲，应用它的路由器已经是很成熟的了。但是，由于它自身的一些没有办法改 变的致命弱点，限稍了它适用的范豳，使褥它只能适用于规模较小豹两络。从 市场的角发来讲，随着i n t e r n e t 的发展，接入i n t e r n e t 的路由器越来越多， 路由负载不断增加，网络规模不断扩大，我们需要滔用于大网的路由协议，以 改善网络的性能。 o s p f 是一种链路状态协议。对予链路状态协议来说，露向整个网络告知自 己黪邻羼瘩患。弱鼗，在这个魏；浚中，各令掰终节点不必变换逶往嚣静站蠡豹 距离，而只需维护张网络的“拓扑图”，在网络捅扑结构发生变化的时候及 对受耨这张辐矜图。各个鼹蠹器裰攥这张圈，分裂计算羁不同嚣静缝静距离， 从而生成各自的路淑袭。它解决了r i p 所不能解决的一些问题。 但是，幽于它的复杂性，完全掌握该技术鲍团体和个人惩是少数。人们对于 它的研究也远远不如r i p 那样深入，该协议也许还察很多需要改进的地方e 因 此，对于我们来讲，有必要对该路幽协议进行研究。 1 3 课题的主要讲究内褰及结巢 o s p f 路由协议缀然在理论上徽成熟，趋在实际酌网络波用中述是存在不少 问题。可以大致分为两类：第一类，由于o s p f 协议的庞大及复杂性，所以在 程序编写时，存在缎多漏稠；第二黉为o s p f 协议不适应麓前五花八门的嗣络 应用。第一类问题在o s p f 的调试和测试过程中，通过修改源程序代码方式已 经褥蓟解凌。本课趱主要舒对第二爨阏瑟滋彳亍研究帮改进，同辩搽讨了o s p f 今膳的发展情况，以及o s p f 的q o s 扩展问题。 下面燕攀奔绍一下本谦繇静主蘩研究肉察及缝鬃： 1 ) 课题针对d i j k s t r a 算法在网络应用中的不足，提出了改进d i j k s t m 算法，使 褥在诗舞最短路径嚣，溪考虑了经过迭熊 弋徐，又考虑了经过肇熹翡钱 价，找出更为合理的最短路径树。在网络寻径袭的刷新中，如果直接依据 d i j k s t r a 舞法，羯稷纹考虑了豢竟霾传攒延迟等链路状态，囊奁实骣熬潮络 中，数据流通过路由器时还有排队延迟和发送娥迟，假d i j k s t r a 算法并没有 2 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 将路由器上的延迟考虑并计算在内，与真实的网络环境有比较大的偏差。 改进d i j k s t a 算法不仅考虑了通信链路上的带宽和传播延迟的因素，还考虑 了路出器上的排队延迟和发送延迟，能够更加全面的刻画网络状态，找出 更为合理的最短路径树，从而得到更为合理的网络寻径表。 2 ) 在虚电路网络上当需要发送数据时才会建立虚电路，例如，x 2 5 网和 f r a m e r e l a y 网，为了降低通信费用，用户会要求如果在很长一段时间内无 用户数据，则虚电路不应该由于协议数据的传送而频频建立和拆除。但由 于o s p f 协议规定接口每隔一个h e l l o 间隔就发送一次h e l l o 报文，因此会 使得虚电路至少每隔h e l l o 间隔就建立和拆除一次。这是一些小的用户所不 能容忍的。如何能使o s p f 在此种虚电路网络上经济有效的运行成为本课题 讨论的话题。 3 1 根据网络的需求，编程实现了o s p fv 2 定义的虚连接( v i r t u a lu 【l k ) 。 3 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与整现 第二章o s p f 动态路由协议中的路内计算 2 1 怒褰炙蠢算法r i p 的不是 凌适爰予羹治系绫内部懿鼹峦嚣上，帮蠢部霆美主，爨麓多罴麓靛是r i p 辏 议。r i p 协议之所以被广泛威用，主要是由于它很简单。r i p 是种距离向掇协 议。黠予鼹蹇藏量捺议来我，它告皴邻居整个躅终懿拓羚。r i p 通过周期墼l 粒 将自已的路由表广播出去来实现这点，这样还可以达到维护路由器之间的相 邻关系的馋瘸。冠时它也会收到别人广援豹踺盎表，它会擞摄这些鼹由表载内 容来生成自融的路豳表。当然，简单也必须溪付出一定的代价： 1 ) 对予魔大两笈杂斡网络来说，r i p 可能根本嚣法胜任。虽然农网络的据 扑结构发生变化后，r i p 会熬新计算新的路由，计算到各个网络和路由 器的距离僮，在这晕申情况下，如果遇到距离馑计算到无穷大簿情况，计 算就变得非常缓慢，网络的收敛速度将变得相当缓慢。为了加快网络的 收敛速度，将1 6 设掇为极限值，在进行计数对，只瓣距离德达到了1 6 就认为两点之间不可达。然而，这样就将r i p 限制巍小礴络上使用了， 因为在大网络上两点之间的距离值往往会大于1 6 。 2 ) 周期性豹广播路亩表将渚耗大量的潮络带宽。这个闷题对予大网，尤其 是慢速链路和广域网就更加突出了。 3 ) 在羹新诗算潞由豹遵程中，貉由器娥予一种过度酸羧，网络上会出现大 量的广播报文，并会引起循环，从而造成网络暂时的搁塞。 4 ) r i p 在聪两赢之滔豹距离送行量度鹣嚣尊侯，葜标准燕路径上褥经过翡鼹 由器的数目( h o p ) ，选择h o p 数量少的那祭路径。这样就没有考虑列 秘络延迟和链菇获态等怼之瓣传输巍离懿影螓。 当计数到无穷大的过程中，网络的中间状态极为混乱，大量分鳃循环发遴， 链辫翔塞，并显广攒掇文零身也会寤予翔爨嚣丢失。毽交予苇患广撵其爨离囱 量袭是一个随机过獠，因此这种慢收敛是不可避免的，切脊可能随时发生。 攫然凌褒鸯稷多秽铮黠这一趣题熬李 救捺麓，魏分粪 蔻瓣、使翅莹患漾搀铡 法、毒性逆转法及触发更新法等。但不幸的是，这些技术解决一必问题，却又 豢采了一些藜戆阕趱。铡鳐，在谗多鼹壹器共享个公共网终驰缨掏中袋孀魅 发照新技术的情况下，个广播就能改变邀些路由器的选踞表，引发新轮的 广播。如暴纂二广播改变? 路由表，宅又会弓l 发起更多静广攘，遮裁产生了雪 崩。使用广播技术和使用抑制技术彷止漫收敛问题，可使距离矢羹算法的应用 4 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 工作效率极低。广播要耗费大量宝贵的带宽资源。即使不出现广播雪崩现象 所有机器周期性地进行广播意味着网络流量随着路由器数目的增加而增加。 2 2o s p f 路由算法的原理 2 2 1s p f 树 s p f 算法，又n q d i j k s tr a 算法，是通过到达网络节点的不同途径与度量得到 从计算节点到网络众多节点的最短路径。该算法涉及的数据结构有：计算节点 s 、最短路径树e 、候选链表c 。算法描述如下： 1 将计算节点s 定义为树根。 2 初始化树结构e ，使之只包含源节点s 。初始化候选链表c ，使其包含一些 从s 起始的路径。这些路径的度量等于相应链路的度量值，并以递增顺序排 列链表c 。 3 若链表c 为空，或者c 中第一个路径长度为无穷大，则终止算法。 4 寻找链表c 中的最短路径p ，从c 中删除p 。设v 为p 的最终节点，若v 已在 集合e 中，即跳回步骤3 ，继续向下执行。否则，p 为通往v 的最短路径， 将v 加入e 中。 5 建立一个与p 相连并从v 开始的所有链路构成的候选路径集合。这些路径的 度量是p 的度量加上与p 相连的度量。将这些新的链路插入有序链表c 中， 并放置在其度量所对应的等级上。跳回步骤3 ，继续向下执行。 图1 1 中简单表示了网络的拓扑，并将链路的度量标明。假设路由器r 1 、 r 2 、r 3 、r 4 、r 5 都运行o s p f 协议且属于同一域，n 1 ，n 2 ，, n 6 为通过路由 器互连的6 个网络。 图2 1s p f 算法举例 5 北京邮电大学颈士研究生毕业论文 o s p f 路由协议的研究与蜜现 下面以路由器r 3 为例来说明s p f 算法的计算过程：此时，计算节点s = r 3 。 s p f 算法的整个计算过稷是前面介绍的5 个步骤的循环。在第1 轮循环中， 首毙，摇算法第2 步，秘始傀檬结毒奄e ； s ，翅始佬候选链轰c = s n 4 ( 1 ) ， s r 5 ( 8 ) ) ，其中，括号内的数值为度量值。其次，执行算法第4 步，从候选链 表c 中找出壤短路经p = s 。n 4 ，将其扶镁选链表孛删除，势将其终节点v 。 n 4 加n s p f 树中，此时e = ( s ，n 4 ( s ) ) ，其中，括号内为节点的父节点。然 后，细算法第5 步，豳薮节点v = n 4 开始，建立与路径p 超遗豹其它候选路径， 于撼找到了r 1 、r 2 、r 4 ，加入候选链表，即c = s n 4 一r i ( 1 ) ，s n 4 r 2 ( 1 ) ，s - n 4 - r 4 ( 1 ) ，s * r 5 ( 8 ) 。以上过程完成了算法鲍一轮循环。 紧接着开始第2 轮循环，再再重复执行步骤4 ，此时，p 一 s n 4 r 1 ) ，v = r 1 ，c = s - n 4 - 1 t 2 ( 1 ) ，s n 4 一r 4 ( 1 ) ，s r 5 ( 8 ) ，e = s , n 4 ( s ) ， m c s 4 ) 。樽由v = r 1 开始执行步骤5 ，找到了n 1 、n 4 ，值n 4 已经在e 上，所以 候选链表变为c = s n 4 - r 2 ( 1 ) ，s - n 4 r 4 ( 1 ) ，s - r l - n l ( 4 ) ，s r 5 ( 8 ) 。 下轮的循环再出p = s n 4 ，r _ 2 ) ，v 一1 1 2 开始，继续貔到了n 2 、n 3 、 n 4 节点，执行结果为： e 2 s n 4 r 4 ( 1 ) ，s r t n t ( 4 ) ，s - r 2 n 2 ( 4 ) ，s 1 1 2 - n 3 国，s t t 5 ( 8 ) ，e = s ，n 4 ( s ) ，r 1 ( n 4 ) ，r 2 0 ) 。 激螽一豢挠行上褥静循环，撬行结果魏下： 籀4 轮p = s n 4 一r 4 ，v = i ( 4 ，c 。 s r 4 ”n 5 ( 2 ) ，s - r 1 - n l ( 4 ) ，s - 1 1 2 一n 2 转) ，s - r 2 一n 3 国，s - r 4 r 5 ( 5 ) ，e = s 荩4 b 定，所以算法结束。最终得到了图1 - 2 所示s p f 树。 勰3 e 瀑 2 2 2o s p f 路由表的计算 图2 - 2s p f 树 r 5 6 o n 6 鼹由表数据结章留 路由表熄路由黯宪成转发包任务的依据。路由器在转发识时，通过将目的地 缝与路由表条舀中搽述豹磊的逮蹬滋行院较，我嚣瀑大匿酝颈，从褥决定潞由 策略。因此，路由袭数据结构包括的内容有：目的地址、目的类型、目的网络 掩弱、接日际谖、域标 鬟、路径类黧、路韵度量、链路状态标识、下一虢簿。 路由衷的计算过程 ( 一)瑗蠹鼹交豹计舞 城内路由计算分两个阶段，第一阶段，利用s p f 算法生成到域内各节点的煅短 路经往先瓣，毽瑟雾雪瓣节点廷考虑鼹由器耪僮赣霹终。第二羚段，将溃瓣终翻至l 最短路径优先树中，最短路径优先树的建立如前面s p f 算法的介绍。但在该阶 段，计箕鼹凌器炅考虑其链路凝态数据蓐( l i n ks t a t ed a t a b a s e ，麓称, l s d b ) 孛 的路由器链路状态通告和网络链路状态通告。因为路由器链路状态通告描述了 每个黪壹嚣与趣应域夔连接毒爰援，嚣网络链鼹状态逶告描述了鹅终孛连接熬路 由嚣状况，它们二者可以究全地构成对网络拓扑的映射。这里主要考虑如何由 最斑鼹径优先蜒生成0 s p f 域内鼹囊表。 最短路径优先树已经描述了计算路由器刻达网络中各节点的最短路径，所 噬，在生戏域内路出表时黪关键是瓣决下一跳的诗冀。魇t 爨下一跳，是撑鼹由 7 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 器在“存储一转发”数据包时，对于到达特定目的的数据包应该转交的地址。 下一跳的计算可以用图2 3 来说明。 广 广 广 l 根卜1 父节点卜一 目的 j l _ jl _ j l _ j 图2 3 下一跳的计算 如图2 3 所示，计算时要涉及根、父节点、目的三个参数。根与父节点间的 虚线表示可以有很多节点在中间。有关计算的规则为： 1 ) 如果目的和根之间至少有一个路由器，则下一跳只需直接从父节点继 承。 2 ) 否则，目的和根之间没有路由器，分两种情况讨论：( a ) 父节点就是 根。即对点到多点网络需查看目的节点路由器链路状态通告的链路数据 域：对直连或点到点不需要下一跳：对虚链路，下一跳要在检查传输域 摘要链路状态通告时得到。输出接口就是直连到目的的接口。父节 点是网络。需查看目的节点路由器链路状态通告的链路数据域。输出接 口从下一跳的i p 地址获取。 ( 二)域问路由的计算 域间路由是指本域中路由器到达其它域的路由。域问路由有两种情况，即到 达其它域网络的路由和自治系统边界路由器( a u t o n o m o u ss y s t e mb o r d e r r o u t e r ，简称a s b r ) 的路由。这两种情况由o s p f 中摘要链路状态通告描述。 如果路由器连接到多个区域，则只考虑主干域的摘要链路状态通告。对于每条 链路状态通告有下面的原则： 1 ) 若该链路状态通告的度量值或存活时间为最大值，或者它是由本路由器 发出，则不予考虑。 2 ) 若该链路状态通告描述的目的为一个网络，且它由域边界路由器产生， 则增加到目的网络的路由，相应的度量为本路由器到路由器的度量加路 由器到目的网络的度量。若路由器不可达，则不予考虑。 3 ) 若该链路状态通告描述的目的为一a s b r ，且路由表中优先级没有高于 域间路由的条目，则增加相应的路由。 4 ) 根据路由表中到达目的地路由的优先级决定是否增加替换相应路由。 ( 三)检查传输域摘要链路状态通告选择更优路由。 这一步只在连接到一个或多个传输域上的域边界路由器上执行。它的目的有 两个：一是查看有没有比前两步中得到的路由更优的路由存在；二是为虚链路计 算真正的下一跳。值得注意的是，这一步计算只是更新主干域的域内路由和域 问路由。如图2 4 所示：边界路由器r 1 、r 2 与网络n 1 有共同的联系，网络 8 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 n 1 属于主干域，为了保持主干域的连通性，在路由器r 1 、r 3 之间建立了虚链 路。从图5 中可看出，路由器r 2 到达n 1 的度量5 要远比r 1 的度量4 0 d , ，因此，在 传输域1 中的所有路由器将选择r 2 把包转发给n 1 。但通过路由表计算过程中第 ( 一) 步的计算，r 3 已经得到了通过r 1 将包转发给n 1 的路径，显然与实际情况不 符，因此，通过第( 三) 步计算，r 3 将选择r 2 作为转发包的途径。 图2 4 较优路由的选择 ( 四)a s p b 部路由的计算 a s 夕f 部路由主要考虑通往自治系统外部目的的路由，它是由a s # b 部链路状 态通告计算得到的。在每一条a s # b 部链路状态通告中，都通告了到达某一特定 目的的度量、转发地址、外部路由标签等内容。因此，a s # b 部路由的计算相对 内部路由计算来说比较简单。对每一条链路状态通告，只需经过下面的一些判 断： 1 ) 若度量值、存活时间和通告路由器中任一个不符合条件，则不予处理。 2 ) 若不存在到通告路由器的路由，则不予处理。 3 ) 若转发路由器为0 0 0 0 ，则表明数据包应转交给通告路由器a s b r ，按 照这一前提增加相应路由。 4 ) 若转发路由器不为0 ，但其不可达，则不予处理。 5 ) 根据a s # f 部链路状态通告中通告的路由情况，决定度量类型和度量值， 并按情况增加或更新相应的路由。 通过以上描述的计算过程，o s p f 根据链路状态数据库中的内容就会生成路 由表。这里的路由表仅是o s p f 自身的路由表，它不同于路由器实现路由转发时 用到的内核路由表。因此，在完成上述计算之后，往往还要通过路由增强功能 与内核路由表进行交互，从而实现多种路由协议的学习。 2 3 为什么要实现o s p f 路由协议 针对于r i p 的不足，我们大都采用o s p f 协议。o s p f 是一种链路状态协 议。对于链路状态协议来说，它向整个网络告知自己的邻居信息。因此，在这 9 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 个协议中，各个网络节点不必交换通往目的站点的距离，而只需维护一张网络 的“拓扑图”，在网络拓扑结构发生变化的时候及时更新这张拓扑图。各个路 由器根据这张图，分别计算到不同目的地的距离，从而生成各自的路由表。它 解决了r i p 所不能解决的一些问题： 1 ) 无h o p 数的限制，因此不必被限制在小网中使用 2 ) 每个路由器都掌握了网络的拓扑结构，各自按照网络拓扑结构来进行路 由优化算法，形成自己的优化路由。 3 ) 更新报文的发送是在路由发生了变化的时候，而不是周期性的发送，故 减少了网络上的路由信息的流量，有利于带宽的有效利用。 4 ) 支持多种度量制式，充分考虑网络延迟，链路状态和吞吐量等因素对两 点之间传输距离的影响。 5 ) 支持具有相同量度值的多条链路之间的负载分担。 1 0 北京哪电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 第三章o s p f 协议解析 在前面一章我们已经简要的介绍了一些o s p f 协议的特点，现在，我们将就 其中的一些主要细节和关键技术进行一个较深入的讨论。这都将围绕着链路状 态数据库来展开。 3 1 链路状态路由协议 作为一种链路状态的路由协议，o s p f 将链路状态广播数据包l s a ( l i n k s t a t ea d v e r t i s e m e n t ) 传送给在某一区域内的所有路由器，这一点与距离矢量路由 协议不同。运行距离矢量路由协议的路由器，是将部分或全部的路由表传递给 与其相邻的路由器。链路状态路由的原理非常简单，所有节点维护依仗完整的 网络图，并按该图计算出全部的最佳路由。网络图保存在一个数据库中，其中 每个记录都代表网络的一条链路。 链路状态算法，或者成为s p f 算法，其思路可以分为以下4 个部分来描述： 1 1 发现邻居节点 2 ) 构造链路状态分组 3 ) 发布链路状态分组 4 ) 计算新路由 3 1 1 发现邻居节点 当一个路由器启动以后，它的第一个任务是要知道谁是它的邻詹。这是通 过发送h e l l o 分组来实现的。发现该路由器的邻居，获取它们的网络地址， 建立相邻关系，并测量到每个相邻路由器的开销或延迟。 3 1 2 构造链路状态分组 当用于交换的信息收集起来后，构造一个包含所有数据的分组。该分组以 发送者的标志符开头，紧跟着是顺序号和年龄，和一个邻居节点列表，对应于 每个邻居节点，都给出了到它们的延迟。图3 - 1 给出了一个示例子网，其延时 标在线路上，相应的6 个链路状态分组见图3 2 。 北京邮电大学硕士研究生毕业论文o s p f 路由协议的研究与实现 a 图3 - 1 子网拓扑结构 a 序号 年龄 b4 e5 d 序号 年龄 c3 f7 b 序号 年龄 a4 c f6 e 序号 年龄 a5 c1 f8 c 序号 年龄 b2 d3 e1 f 序号 年龄 b6 d7 e8 图3 2 该子网的链路状态分组 创建链路状态分组很容易，难的是决定何时创建分组。一种可能性是定期创 建，即每隔一定时间就创建一次。另一种可能性是当出现重大事件时再创建， 象线路或邻居节点的增删，或它的特征值的明显改变时。 3 1 3 发布链路状态分组 通过f l o o d ( 扩散) 算法，向所有的其他路由器发送该分组，如何可靠地发 布链路状态分组在链路状态路由选择算法中占相当大的比重，链路状态算法的 实现的好坏在一定程度上取决于f l o o d 算法的优劣。为了控制扩散，每个分组包 含一个顺序号。该顺序号在每次发送新分组时加1 。路由器记下它所见过的所 有信息对( 源路由器，顺序号) 。当一个新的链路状态分组到达时，先查看一 下该分组是否已收过。如果是新的，把它再向除了进入的那条路之外的所有线 路发布，如果是重复的，则丢弃它。如果一个分组的顺序号比目前为止己到达 的最大的顺序号还小，则被认为已过时而拒绝。 1 2 北京邮电大学硕士研究生毕业论文o s p f 路由协议的研究与实现 该算法有一些问题。首先，如果顺序号循环使用，就会发生冲突。解决办法 是使用3 2 位的顺序号。如果每秒发送一个链路状态分组，就得花1 3 7 年才能使 计数循环回来，所以避免了发生冲突的可能性。 其次，如果一个路由器崩溃了，它将丢失其顺序号。如果它再从0 开始，那 么后面的分组可能被当作重复分组而被拒绝。 第三，如果顺序号传送后出现错误，可能被当成过时分组而遭拒绝。 解决这些问题的办法是，在每个分组的顺序号之后再加年龄字段( a g e ) ， 每秒将年龄递减1 。当年龄变成0 时，来自于那个路由器的信息就被丢掉。在 初始化扩散过程中，年龄字段也一样递减，以保证没有任何分组会丢失并无限 长地存活下去。另外，为了防止路由器到路由器之间的线路出问题，所有的链 路状态分组都要应答。 3 1 4 计算新路由 一旦一个路由器积累了一整套的链路状态分组，它便可以重组整个子网结 构，用d i j k s t r a 算法确定到所有可能目的地的最短路径。此算法的结果可以安 装在路由选择表中，并且通常通过操作恢复。 3 2 链路状态数据库 网络的拓扑结构在o s p f 中用链路状态数据库来表述，它是o s p f 协议中关 键的一部分。在一个自治系统中，所有运行o s p f 的路由器都需要维护一个相 同的链路状态数据库。其实，这个数据库就是一张有关这个自治系统拓扑结构 的图，同时它还是一张加权的图。图中每一条边都与一个权值相关联，权值表 示沿这条边所示的方向传输数据的代价。这个代价值可以是由管理员自己配置 的，也可以是从其它的路由协议中获得的。这样一来，所有路由器都了解了整 个自治系统的拓扑结构。在此基础之上，每个路由器根据这张加权图利用 d i j k s t r a 的s p f 算法来计算到每一个目的地的最短路径，从而生成路由表。正是 由于这个原因，使得尽管路由计算是分布式的，但其计算的结果与集中式计算 出来的结果一样精确。 一个自治系统是由一系列的网络和路由器所组成的，那么，我们应该怎样来 表示这个自治系统呢? 在存放这个自治系统拓扑结构的链路状态数据库中，我 们应该怎样来表示这些网络和路由器? 我们用有向图来描述一个自治系统。网络和路由器是这个图中的顶点。网络 和路由器之间以及路由器和路由器之间的关系则用图中的点和边来表示：如果 表示两个路由器的点用一条边连接起来，则表示这两个路由器通过一个点到点 1 3 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 的网络相连；如果一个表示路由器的点和一个表示网络的点用一条边连接起 来，则表示这个路由器有一个接口与这个网络相连。按照这样的规则，图3 3 所示的网络，就可以用图3 - 4 所示的图来表示。其中r t a ，r t b ，r t c 和r t d 分别表示路由器a ，b ，c 和d ，n i n 5 分别表示1 5 。每条边旁边的数字表示 这条边所对应的权值。 图3 3 网络实例 1 4 北京邮电大学硕士研究生毕业论文o s p f 路由协议的研究与蜜现 图3 - 4 网络结构图 在图3 q 所示的阐中，r t l a ，r t b 和r _ t 与n 1 之间的连接是双向的，这表 示n l 是一个t r a n s i t 薅终，它为其它网终瓣懿逯镶提供遴鼹，嚣其它的嬲终与 路幽器之间的连接熄单向的，对网络而言就是只育入边，而没有出边，这表示 这燃络是一个s t u b 网终，这秘网终只提供阕络走的曩的之阕兹遗馕，不为蒸德 网络间的通信提供通路。这两种网络是o s p f 中典型的两种网络类型。 藤瑟所讨论的都是怎样煺鼹来表示嬲终救撂扑续牧，那么，在瘸子该鑫嬷系 统的所有路幽器上又是怎样来存放遮张图的昵? 表3 - 1 描述了链路状态数掇库 的逻辑表示。 1 5 匏寨邮电大学硕士研巍生毕控论文 o s p f 路由拂议曲研究与窭现 袭3 - t 链骆获态数据露的逻瓣表示 在有了这个数据蓐以舞，各个路由器麟再跬根据它来生戏最短掰，执搿计算 嫩自己的路出表。 3 3 生成辩 每令o s p f 黪瀣器聪羯黪或熬键臻状态数据瘁，逶避d j j k s t r a 舅法，叛是己 必壤节点樗到一个爨短挺，鼹魏避矮撼嚣遮行该算法懿路幽器不弱两不阉。最 短树给出了去饪 霉鞠豹网络和主梳耱整令路径，但其枣下一雾i 地址在i p 转发中 健用。 蠛在，鼗搬藏浚r t a 为铡，在冀上遮野d 0 k m a 冀法，褥到簸短树，热屠 程檄据这个矮蛭树寒诗冀爨r t a 的鼹由表。由予这个镳路状态数据麾哭是有关 本强治系统蠹鹣，援班，得到静鼹囊表瞧廷是本自演系绫蠹的踌出袭。只蕊强 3 - 5 给出了r t a 计冀的缳短树。袭3 - 2 则是r t a 计算豳张的路由表。 浅3 - 2 r t a 获鼹密袈 1 6 北京邮电大学硕士研究生毕业论文 o s p f 路由泌的研究与实现 图3 - 5r t a 计算的最短树 弧表3 - l 我稻霉弦看篷，在这个链路状态数蠢露牵包含了整令叁滚系缓搿骞 的网络和路由器。从表3 - 2 可以看出，整个自治系统中所有的网络在路由表中 餐餐鼹应懿袭凌。这群一条，姿蠡渗系统熬艇蠖扩大熬对饺，裁会产生一黧离 题：所包含的网络和路由嚣的数目就会增多，链路状态数据库也就会变得相当 庞大，献薅趣爨一是豹袋鬏；裂薅这个链黪毒爰态数援疼诗冀最短撼豹鞋闯纛会 因此而超出一定的限额；路由表的大小也会因此而超出一定的限额 当某一条 链路的状态发生了变化的穗嫉，o s p f 臻由嚣会向爨澹系统孛溪有鲍踌由器遴蠹 这个变化，大量的路由更新报文会使得网络带宽的商效利用率变低，我们叉一 次露对与r i p 带绘我们的同榉鹣闻爨。为了鳃决这个阉题，o s p f 协议允谗把鱼 治系统划分为更小豹单位，我们称之为区域( a r e a ) 。 3 4 区域的剃分 蓠先我秣器要说赣熬令淹蓬藏是：幸 么是蘧城? 在o s p f 臻议孛允诲将连 续的网络和主机组合在一起形成一个集合，再加上衡接口与这个集禽中的任何 一个耀终稷连戆路漆器形裁了一令溪域。这徉一寒，我识就霹浚将鑫浚系统楚 分为若干个区域。每个区域独立的遂行链路状态算法，区域内的网络拓扑绪构 露予区域终熬薅由嚣楚不蕹夔，鼹撵区域努熬撂馨结秘鼹予区域蠹戆鼹哟器 同样是不可见的。处于同一个区域中的路由器共同维护一个相同的链路状悉数 据露。这裁镬褥位予一令a s 蠹懿鼹蠢器懿键鼹状态数据露瞧不再宠垒穰阉， 不同愿域的路由器舆有不同的链路状态数攒库。由于这个数据库中只记录了该 1 7 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与实现 区域中的网络拓扑结构，所以链路状态数据库的大小被缩小了。这种拓扑结构 魏鞴离接褥网络弱扩数过毽止步予嚣蠛戆逡器，姨露减少了网终懿滚量。 这一个一个独立的区域又是怎样联系起来的呢? 它们是通过接在不同区域的 鼹巍器联系起来的。这样数路由器我 f 】恕宅称之为嚣域边爨路由爨( a b r ； a r e ab o r d e rr o u t e r ) 。它们属于多个区域，在其上维护多个链路状态数据庵。 为? 区分不同的区域，我们黠区域送行了缡号，不蠲的区域分以不阕鲍编粤。 但魑，在这鼹面有个特殊的区域，它的编号必须是0 ，这个区域我们称之为 主于区域( b a c k b o n ea r e a ) ，它是出鼹有的区域边：器路由器所组成的。它负责 非燕于区域间的通储，因此，它必须是连续的( c o n t i g u o u s ) ，即馒不是物理上 连续的，也废该通过虚拟镳路的建立保证其逻辑上姻连续。 这就是在一个自治系统溺中我们采取的一些改进措施，如果一个自治系统要 与其它的自治系统避行路由的交换，那又威该怎样办昵? 这是通过爨治系统边 界潞由器( a s b o r d e r r o u t e r ) 来实现的。通过它将a s 外的路亩信恿传进囊治 系统内，同时也向其它a s 寂告本a s 的一然可达信息。 有了这样静翻分之籍，一个自治系统孛静路交器赣阿 薹分为潋下三释： 1 区域内部路由器：壹连的所肖网络都在一个区域的路由器。 ： 2 医域逑赛鼹囱器：写多夺区域穗连戆路由器，它将令区域豹路交臻惑 汇总压缩后向主干区域发布，同样也将主干区域的路由信息向其他区域 菱蠢。 3 a s 边界路由器：负赞与a s 外的路豳器交换路由信虑的路由器。 3 s 链路状态数据库的澎成与维护 我们已疑讨论了链路状态数据霹豹内容，现在我们自然该来讨论它是怎样形 成的，以及当网络的拓扑结构发生变化的时候，它又是怎榉来进行更新，从而 维护一张有关网络的最蓊的籀矜图。 在o s p f 协议中链路状态数据库的形成与维护是通过三种协议( h e l l o 协 议，交换秘议和扩散协议) 来完成的。 3 5 1h e l l a 协波 从前面的讨论，我们知道运行o s p f 协议的路由器向全网告知自己的邻居信 愚，警邻嚣狡态笈童交德瓣游谈，宅又会融垒蹰通告这夺燮仡。那么，o s p f 路 由器怎么知道自己的邻居是谁，怎样检测刘自己的邻居已缀发生了变化? 这一 切镲是壶h e r o 狯议来完裁瓣。狳鼗之拜，在蘸嚣_ | 舞提蘩黪箨派黠凌器纛备贽 1 8 北京邮电大学硕士研究生毕业论文 o s p f 路由协议的研究与蜜现 指派路由器的选举，也是由它来完成的。因此，我们可以从以下的几个方丽来 摇述h e l l o 协议： 1 动态发现新邻居 h e l l o 协议孛援突，一个远行o s p f 诲议麴踌耄嚣鼓它鸯籍a 鼹终爬，裁辩要 定期的向网络发送h e l l o 分缎。邻居通过收到这个h e l l o 分组来发现它的存猩。 瑟宅樊l 逶嚣收至l 邻嚣发送斡h e l l o 努缓寒发瑷耋己豹邻器。 2 确认邻居间的双向连接关系 邻霆之瓣要进嚣滋一步蟾操佟，必须先建立双鹦连接。如果o s p f 路自瓣检 测到邻居发来的h e l l o 报文韵邻居列液中包含自己，说明邻膀已经收到了自忍发 送懿h e l l o 搬文，能够在露终上看照鑫己。戴对，邻媛阕熬毅向连接关系裁建立 起来了。 3 维持与邻居闯蛇邻接关系 个o s p f 路由器通过定期( 如1 0 秒) 向网络发送h e l l o 分组采告知邻屠自 己的存在，同时它邋过收到邻居的h e l l o 攮文，来确保邻居还活黄。如果一个 o s p f 路由器在规定的时间内( 通常为发送h e l l o 分缀时间闻隔的4 倍，如4 0 秒) 没有收到邻居发送的h e l l o 分组，则该鼹由器可以确认此邻居淤经死撑了， 从黼来发璃拓扑结构的交纯。 4 。指派路由器的选举 对于广播型网络和n b m a ( n o n - b r o a d c a s tm u l t i - a c c e s s ) 网络，我们程所有 与该o s p f 路由器建立了双向连接的邻居之间，通道路由器的优先级，i d 的比 较，寐选密疆派路国器，其它的所裔踌由鬃需要与它交换缓诧的链鼹状态数据 库，从而建立邻接关系。 h e l l o 努缀的发送可孩戳缝撵静澎式，发给网络上靛爨富o s p f 踌盘器，藏 者以单播的形式发给自己的邻居。 瓣子选举了指澈潞蠹器豹弱络，窿指滠魏由嚣粒菲捂澈褥密器之滔；对予萁 它的网络，猩建立了双向连接的路幽器之间，都需爨建立邻接关系，这就需要 随时黎跨链薅获态数据痒熬一致。这个致是逶遂交挨蛰议程扩教伤淡采突残 的。 3 。5 2 交接漭议 交换渗议饺震挚链鼹状态数据露熬秘始弱步，宅溪定了潮建立激囊连接露又 需要建立邻接关系的路由器之间的链路状态数据库怎样进行初始的交换。 程这令交换过程孛，鼹囊器