（计算机科学与技术专业论文）基于流量工程的ospf路由算法.pdf

独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 申请学位论文与资料若有不实之处 本人签名：盘堡 本人承担一切相关责任。 日期：型! ：! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在 校攻凄学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和磁盘，允许学位论文被鸯阅和借阅：学校可以公布学位论文 的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密 的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释： 本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 盘堡 身夸 同期： 日期： 纵，3 - 2 - 北京邮屯大学颁上学位论文 基于流量工程的o s p f 路由算法 摘要 o s p f 使用最短路径优先( s p f ) 算法来进行路由计算，也就是在图 论所说的d i j k s t r a 算法。 o s p f 运行最短路径算法，计算出一条费用值最小的路径，来转发 数据包。当网络中需要转发的数据报文很多时，只用最短路径来转发， 势必造成拥塞，而网络中另外的一些费用值稍大的路径却处于空闲状 态。这样网络资源就没有得到充分的利用，造成了服务质量的低下。 在开发o s p f 协议软件的基础上，我阅读了关于路由算法和流量工程 的学术论文，提出了基于流量工程的o s p f 路由算法。该算法的核心 思想是，在o s p f 网络发生拥塞时，强制性地把到特定目的地的一条 路径转化为最短路径的等价路径。运行完扩展路由算法以后，相应的 更新路由表。根据o s p f 的负载平衡特性，网络的流量就会平均分配 到两条链路上，这样就缓解了网络的拥塞，提高了网络资源的利用率。 当网络的拥塞没有得到解决时，重复执行以上步骤，添加第三条等价 路径甚至更多。本文描述了该算法的实现方法和理论推导，并用具体 实验评测了该算法。 关键字流量工程最短路径路由算法负载均衡 第1页 北京邮电大学硕士学位论文 t h eo s p fr o u t i n ga l g o r i t h mb a s e do n t r a f f i ce n g i n e e r i n g a b s t r a c t o s p fu s e st h es h o r t e s tp a t hf i r s t a l g o r i t h mt oi m p l e m e n tt h er o u t i n g a l g o r i t h m ，w h i c h i sc a l l e dd i j k s t r aa l g o r i t h mi ng r a p h i ct h e o r y t h el e a s tc o s tp a t hi sf o u n d b yr u n n i n g t h es h o r t e s t p a t hf i r s ta l g o r i t h m t h es h o r t e s tp a t hi su s e dt of o r w a r dt h ed a t ap a c k e t s i ft h e r ea r el o t so f d a t ap a c k e t st ob ef o r w a r d e di nt h en e t w o r k ，w eh a v en oc h o i c eb u tr e l yo n t h es i n g l es h o r t e s tp a t h t h e nt h ec o n g e s t i o no c c u r s h o w e v e r , t h ep a t h s w i t hal i t t l e l a r g e rc o s tr e m a i ni d l e s ow ed on o tm a k ef u l l u s eo ft h e n e t w o r kr e s o u r c ea n dh a v eb a d q u a l i t yo f s e r v i c e b a s e do nt h ee x p e r i e n c e o f d e v e l o p i n go s p fs o f t w a r e ，ir e a dt h et h e s e sa b o u tt r a f f i ce n g i n e e r i n g a n dr o u t i n ga l g o r i t h m ip u tf o r w a r dt h eo s p f r o u t i n ga l g o r i t h mb a s e d o n t r a f f i c e n g i n e e r i n g w h e nc o n g e s t i o nh a p p e n s o no s p fn e t w o r k ，t h i s e n h a n c e da l g o r i t h mc h a n g e sap a t hc o n n e c t i n gt ot h es p e c i f i cd e s t i n a t i o n i n t oap a t hw i t ht h es a m ec o s ta st h es h o r t e s tp a t h s ow e c a nm a k eu s eo f t h el o a db a l a n c et oa l l e v i a t et h e c o n g e s t i o n i ft h ec o n g e s t i o n i sn o t r e s o l v e dc o m p l e t e l y , w ec a nl o o pt h ea l g o r i t h mt oa d dm o r ee q u a lc o s t p a t h s m yt h e s i s d e s c r i b e st h e i m p l e m e n tm e t h o da n dt h e o r y o ft h i s 第2页 北京邮电大学硕上学位论文 a l g o r i t h m a ne x p e r i m e n t i sa l s od o n et oe v a l u a t et h i sa l g o r i t h m k e y w o r d s ：t r a f f i c e n g i n e e r i n gr o u t i n ga l g o r i t h m l o a db a l a n c e 北京邮电大学硕l 学位论文 1 1研究背景 1 1 1 路由协议的发展 第一章绪论 i n t e r n e t 网络的主要节点设备是路由器，路由器通过路由来决定数据的转发方 向。这种转发策略称为路由选择，这也是路由器名称的由来。决定数据的转发的 方法可以是人为指定，但人为指定工作量大，而且不能采取灵活的策略，于是动 态路山协议应运而生，通过传播、分析、计算、挑选路由，来实现路由发现、路 由选择、路由切换和负载均衡等功能。 在上世纪8 0 年代中期，最常用的内部路由协是路由信息协议( r i p ) 。尽管r i p 对于实现小型或中型同机种互联网络的路由选择是非常有用的，但是随着网络的 不断发展，其受到的限制也越加明显。 随后，i g r p 得到了推广，i g r p 也是一种距离向量( d i s t a n c e v e c t o r ) 内部网 关协议( i g p ) 。为具有更大的灵活性，i g r p 支持多路径路由选择服务。在循环 ( r o u n dr o b i n ) 方式下，两条同等带宽线路能运行单通信流，如果其中一根线路 传输失败，系统会自动切换到另一根线路上。在上世纪9 0 年代，又推出了增强的 i g r p ，进一步提高了i g r p 的操作效率。e i g r p ( e n h a n c e di g r p ) 协议对所有 的e i g r p 路由进行任意掩码长度的路由聚合，从而减少路由信息传输，节省带 宽。另外e i g r p 协议可以通过配置，在任意接口的位边界路由器上支持路由聚 合。 e n h a n c e d i g r p 不作周期性更新。而是当路径度量标准改变时，e n h a n c e d i g r p 只发送局部更新( p a r t i a lu p d a t e s ) 信息。局部更新信息的传输自动受到限制，从 而使得只有那些需要信息的路由器才会更新。 随着i n t e r a c t 技术在全球范围的飞速发展，o s p f 已成为目前i n t e r n e t 广域网 和i n t r a n e t 企业网采用晟多、应用最广泛的路由协议之一。o s p f 路由协议是一种 典型的链路状态( l i n k s t a t e ) 的路由协议，般用于同一个路由区域内。在这里， 路由区域是指一个自治系统( a u t o n o m o u ss y s t e m ) ，它是指一组通过统一的路由 政策或路由协议互相交换路由信息的网络。在这个a s 中，所有的o s p f 路由器都 维护一个相同的描述这个a s 结构的数据库，该数据库中存放的是路由域中相应 链路的状态信息，o s p f 路由器正是通过这个数据库计算出其o s p f 路由表的。作 为一种链路状态的路由协议，o s p f 将链路状态通告数据报文l s a ( l i n ks t a t e 第6页 北京邮电大学硕上学位论文 a d v e r t i s e m e n t ) 传送给在某一区域内的所有路由器，这一点与距离矢量路由协议 不i 列。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻 的路由器。 o s p f 有很多优点：它的收敛速度快，能够在最短的时间内将路由变化传递到 整个自治系统；将自治系统划分为不同区域后，通过区域之间的对路由信息的汇 总，大人减少了需要传递的路由信息数量，也使得路由信息不会随网络规模的扩 大向急剧膨胀；具有良好的安全性，o s p f 支持基于接口的明文及r o d 5 验证：严 格划分路由的级别( 共分四级) ，提供可信的路由选择；可以适应各种规模的网络。 1 1 2 流量工程概念的提出 流量工程是一种能将业务流映射到实际物理通路，同时又可以自动优化网络 资源以实现特定应用程序服务性能要求的、具有宏观调节和微观控制能力的网络 技术。流量工程实施的主要目标是实施网络操作的高效率和优化网络资源，提高 业务服务性能。 随着i p 网络的进一步发展，用户对使用的网络要求在任何情况下都能提供优 良性能、相对稳定的服务。传统i p 网络的路由体系只能提供数据传输的可达性服 务，不具有对全网资源的利用和调节能力，从丽导致网络中传输的数据流可能汇 聚到同一链路，或者同一节点的同一端口上去，引起局部严重拥塞和网络资源利 用率大大下降。 1 1 3 流量工程的演进 传统的i n t e m e t 采用t c p 进行捐j 塞控制。但是随着i n t e r n e t 的发展并成为全球必 不可少的通信基础设施之后，传统的t c p 方法已无法满足o o s 要求。在早期基于路 由器的核心网中，流量工程技术是通过简单地使用路由量度值来实现的。这样做 存在很多的局限，因为内部网关协议的路由计算是通过网络拓扑来驱动的，它只 是基于一个简单的附加量度，并不发布带宽可用性和业务特征等之类的信息。这 就意味藿，当内部网关协议计算其路由表时并不考虑网络的业务负载，从而可能 导致业务不能在网络连接中均衡分配，造成部分网络资源不能被充分利用。 然后又提出了重叠模型和集成模型两种流量工程解决方案，重叠模型的特点 是，它的流量工程问题都交由a t m 解决，且需要地址解析。采用此类技术时，a t m 第7页 北京邮电大学颤上学位论文 端点使用a t m 地址和i p 地址来标识，网络中设置服务器完成a t m 地址和i p 地址的 地址映射功能，在发送端得到接收端的a t m 地址之后，建立a t ms v c 链接，并传 送i a n 数据包。重叠技术的优点是采用了标准的信令标准，与标准的a t m 网络及 、i p 务兼容。缺点是传送i p 包的效率太低。 集成模型的特点是选路和交换的集成统一，选路作为控制功能模块出现，并 且不需要地址解析。采用此类技术时，a t m 层被看作i p 层的对等层，a t m 端点只 需使用i p 地址来标识，在建立链接时使用非标准的a t m 信令协议。集成技术的优 点是传送i p 包的效率比较高，不需要地址解析协议；缺点是与标准的删技术融 合较为困难。在集成模型中，比较成熟的是m p l s 协议。它为流量工程的自动实现 提供了可能性，这主要体现在以下几方面： 1 ) 7 号信令网络相同，每个交换机都具有第三层智能，可以重新进行选路连接， 当中继主干线出现故障时，将选择另一条路由疏通业务流量，并使网络迅速 恢复。 2 ) m p l s 流量工程是基于业务流所需的资源和网络中的可用资源为业务流穿过 网络时进行选路。此方式中。业务流经过的通道是满足业务流资源要求的最 短通道。业务流选路有带宽要求，媒质要求，优先级要求等参数。 3 ) 节点和链路的故障往往使骨干稠的拓扑结构发生改变，而m p l s 流量工程可以 通过适应一系列新的资源约束情况，有效地规避发生故障的节点和链路所带 来的影响。 所以，流量工程的发展趋势是简明性和开放性，简明性避免了追求技术上的完 美而错失占领市场的机会，在i n t e m e t 上运行的协议必须遵循开放性才有利于 i n t e m e t 的可持续发展。 1 1 4s p f 算法的提出 在o s p f 网络中，每台路由器都有一个链路状态数据库，这个链路状态数据 库反映了整个网络的拓扑结构。将链路状态数据库作为s p f 算法的输入，算法运 行结束后，得到的输出结果就是一张列出了到整个网络中的每个节点的路径的路 由表。 在d i j k s t r a 算法中，有三个数据库： 1 ) 生成树的数据库：通过在这个数据库中加入链路来实现在最短路径树上加入 节点。当d i j k s t r a 算法运行完毕后，这个数据库就描述了一条最短路径树。 第8页 北京邮电大学硕士学位论文 2 ) 候选数据库：当一条链路变成候选链路，将要添加到最短路径树上时，它就 被从链路状态数据库中按照指定的顺序拷贝到候选数据库中。 3 ) 链路状态数据库：是一个存储所有链路的仓库。它反映了整个网络拓扑的 信息。在链路状态数据库中，用一个三元组( r o u t e r i d ，n e i g h b o r i d ，c o s t ) 来唯一地标识一条链路。 对路l u 器的d i j k s t r a 算法描述如下： 1 路由器把自己当作最短路径树的根加入到生成树数据库中。 2 在链路状态数据库中的所有三元组里，找到最短路径树的根的所有邻 居，把它们加入到候选数据库中。 3 计算从最短路径树的根到候选数据库中存储的候选节点的链路的费用， 选择费用壤少的一条链路，并将候选数据库中连接到这条链路的节点 加入到生成树数据库中。如果有多条链路到根的费用相同，那就随枫 地选择其中的一条。 4 每个链接的n e i g h b o ri d 在加入到生成树数据库之前必须被检查，防止 已有三元组已经存在于生成树数据库中，并且它的n e i g h b o ri d 与待加 入的相同。这样，这个待加入的三元组就不能提交给生成树数据库， 而只能被存储到候选数据库中。 5 在链路状态数据库中，查找刚加入到生成树数据库的节点的邻居，并将 这些邻居加入到候选数据库中。 6 。如果候选数据库不为空，算法转移到步骤3 。如果候选数据库为空，则 算法结束。 用一张拓扑图来具体浣明s p f 算法的过程。网络拓扑如图卜l 所示：图中数字 表示该接口在转发数据包时所需的费用。 r a名二罚丐 ，1 髓 j 。y ，盆、- l ，厶 l 订j lr e26 r h 52 _ p “警童警- r f 图1 - 1 网络拓扑图 第9页 北京邮电大学坝t 学位论文 基于这个网络拓扑结构，网络中的每个路由器都维持一个链路状态数据库，如图 卜2 所示 i t t 儿j 1 0 ri dn e i g h b o r c o s t r ar i 2 r ar )4 r ar e4 r 上r a 2 r | r c l r br e 1 0 r ( r b 5 r ( 、r f 2 r i )r a 4 r dr e 3 r dr g 5 r er a 5 r 拄r b2 r er d 3 r i 三r f 2 r !r 6 1 r f 刚i8 r fr c 2 r fr e2 r f础i 4 r ( ；r d5 r ( ；r e l r t - ir e8 r jr f6 图1 - 2 链路状态数据库结构 以r a 为例说明计算最短路径树时具体的步骤，在该计算中r a 是最短路径树的 根，表1 1 详细描述了该过程： 候选数据库到根的费用生成数据库具体实现的描述 r a ，r a ，0 r a 把自己当作生成树的根 r a r b ，2 2 r a ，r a ，0所有的r a 的邻居都被加入到候选数 r a ，r d ，4 4 据库中 r a ，r e ，4 4 r a ，r d ，4 4 r a ，r a ，0( r a ，l i b , 2 ) 是在候选数据库中费用最 r a ，r e ，4 4 r a ，r b ，2小的链接，所以它被加入到生成树数 r b ，r c ，l 3据库中。r b 的邻居，除了那些已经 在候选数据库中的都被加入进来。 ( r a ，r e ，4 ) 是一条比( r b ，r e ，1 0 ) 费用更少的链路，所以( r b ，r e ，1 0 ) 被抛弃。 第1 0页 北京邮电大学硕上学位论文 r a r d ，4 4 r a ，r a ，0( r b ，r c ，1 ) 是候选数据库中费用最低 r a ，r e 4 4 r a ，r b ，2的链路，所以被选中加入到生成树数 r c ，r f 2 5 r b ，r c ，1据库中。所有r c 的邻居被加入到候 选 数据库中。 r a ，r e ，4 4r a r a 0 ( r a ，r d ，4 ) 和( r a ，r e ，4 ) 到r a 的费 r c ，r f ，2 p 0 r a ，r b ，2用都是4 ，选择( r a ，r d ，4 ) 加入到 7 r b ，r c ，1生成树数据库中，r d 的邻居被加入 r d r g 59 r a ，r d ，4到候选数据库中。在候选数据库中有 两条到r e 的路径，将其中费用大的 那条删除 r ( r a ，r e ，4 ) 被加入到生成树数据库r c ，r f ，2 0 r a ，r a ，0 9 r a ，r b ，2中，所有r e 的邻居被加入到候选数 r e ，r f ，2 6 r b ，r c ，1据库中。在候选数据库中有两条到 r e ，r g ，1 5 r a ，r d ，4r o 的路径，费用大的那条被删除掉 r e ，r h ，8 1 2 r a ，r e ，4 6 r a ，r a ，0( r c ，r f ，2 ) 被加入到生成树数据库 r e ，r g ，1 5 r a ，r b ，2中，它的邻居被加入到候选数据库 1 2 r b ，r c ，l中。候选数据库中有两条到r h 的路 r f ，r i d ，4 9 r a ，r d ，4径，将费用大的那条删除掉。由于选 r a ，r e ，4择了( r c ，r f ，2 ) 这条路径，所以 r c ，r f ，2( r e ，r f ，2 ) 这条路径就会被删除。 r f ，r h ，4r a ，r a ，0( r e ，r g ，1 ) 被添加到生成树数据库中 r a ，r b ，2 r b ，r c ，1 r a ，r d ，4 r a ，r e ，4 r c ，r f ，2 r e ，r g ，1 r a ，r a ，0( r e r h ，4 ) 被添加到生成树数据库 r a ，r b ，2中，由于候选数据库为空，所以该算 r b ，r c ，i法结束。这样，最短路径树就生成了。 r a ，r d ，4 r a ，r e ，4 r c ，r f ，2 r e ，r g ，1 r f ，r h ，4 表卜1最短路径树生成的具体步骤 当候选数据库中没有候选节点时，说明最短路径树已经生成。 第1 1页 北京邮电大学硕l 学位论文 1 2 实践工作 我在研究生阶段做的主要工作是，对北京邮电大学计算机网络技术中心近年来 自主成功刀i 发出的v l r t 系列路由器中的路由协议进行了一系列的一致性测试， 负责o s p f 路山协议的版本升级。o s p f 协议的程序的升级部分主要是与m v i i 接 口有关的部分，在旧的版本中，m m l 在接收到用户指令后，负责收集相关的参数， 并把这些特定的参数传递给相应的程序。在升级版本中，m m t 只负责将接收到的 用户指令转化为字符串传递给o s p f 程序，所以o s p f 程序需要增加一些额外的 功能，来分析字符串并得到程序运行所必需的参数，将这些参数添加到相应的数 据结构中做处理。在新的版本下，一些静态的全局数组被摒弃，而代之以动态的 链表结构。 1 2 1 硬件环境 本系统的开发硬件平台，其主控制器采用m o t o r o l a 公司的m p c8 6 0 芯片。 m p c8 6 0 是一个单片集成有微处理器、外围控制器和协议处理器的多功能通信控 制芯片，具有硬件设计简单、系统可靠性高、c p u 利用率高、成本低等特点，在 许多通信产品的设计中已成为用户的首选器件。 1 2 2 操作系统平台 操作系统采用北京万林克通讯技术有限公司自行开发的嵌入式实时多任务操 作系统r m o s 。r m o s 由内核，控制台进程和接口库组成。r m o s 目标代码不超 过1 6 k ，是一个离效、精炼的专用操作系统。它可以提供进程、信箱、信号量、 事件和时钟等多种资源管理，以及进程间通信和差错告警等多种功能。 1 2 3 开发工具 使用标准c 语言和m i e r o t e k 公司的在d o s 平台上面向3 6 0 或面向8 6 0 的交叉 编译环境。手工通过串口和以太网下载和创建程序。 1 2 4 进程通讯机翩 信箱是r m o s 操作系统提供的一种进程闻通信的机制，它是一种系统资源。 r m o s 提供系统调用来使用信箱，一个任务可以向任何一个信箱发送消息，也可 以从任何一个信箱取得消息。一个消息驱动的进程可以等待在一个信箱上，如果 第1 2页 北京邮电大学硕士学位论文 没有消息，此进程处于等待状态，并不占用处理机资源，直到信箱中有消息将其 唤醒。进程阳_ | 传递的消息采用固定的消息头结构，不定长的消息长度的消息格式， 这样使得长短消息都适用，方便灵活，节省内存空间。 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 协议的基本原理和运行机制。 第三章阐述了现有o s p f 路由算法的机制。 第四章在参考相关技术文献的基础上提出了一种新的o s p f 路由算法来解决 网络拥塞问题。 第1 3页 北京邮屯大学倾j 一学位论义 2 1o s p f 概念简介 2 1 1r o u t e ri d 第二章o s p f 路由协议综述 每一个运行o s p f 路由协议的路由器都需要有一个i d 号在网络中唯一地标识 自己，这个i d 号是通过如下原则得到的： 1 路由器选择回环接口地址中最高的i p 地址作为路由器的r o u t e r i d 。 2 如果路由器没有配置回环接口，则将物理接口中最大的i p 地址作为路由器 的r o u t e r i d 。 2 1 2h e l l o 协议 h e l l o 协议有以下几个作用： 1 用来发现邻居。 2 宣告关于接口的参数，两个路由器在成为邻居之前必须就这些参数达成一 致。 3 用束维持两台路由器之间的邻居关系。 4 用来在广播网络上选举指派路由器和备份指派路由器。 2 1 3 网络类型 o s p f 中定义了五种网络类型： 1 点对点网络 2 广播网络 3 非广播多接入网络 4 点对多点网络 5 虚链接 除了这五种网络类型之外。所有的网络被分成两大类： 1 传输网络：该网络连接着两个或更多的路由器，这个网络用来传送数据报 文，这些数据报文既不是从这个网络产生的也不是以这个网络为目的地 的。 第1 4页 北京邮电大学硕七学位论文 2 残端网络：这种网络只连接一个路由器，网络上的数据报文要么是这个网 络产生的，要么是要到达这个网络。o s p f 将主机路径宣告为残端网络。 回坏接r | 被看作残端网络并被当作主机路径来宣告。 2 1 4 指派路由器和备份指派路由器 指派路由器有以下作用： 1 代表它所在的多接入网络和所有连接在该多接入网络上的路由器。 2 在多接入网络上管理扩散进程。 指派路由器概念的提出是把网络看作一个虚节点，网络上的每个路由器都与 虚节点形成邻接关系。关于指派路由器的一个很显著的问题是，如果现有的指派 路出器不能正常工作，则必须选举新的指派路由器。在选举过程和随后进行的同 步过程中，网络都不能传送数据报文。为了避免这种问题产生，在选举指派路由 器的同时要选举备份指派路由器，所有的路由器不仅与指派路由器形成邻接，而 且与备份指派路由器形成邻接。如果指派路由器不能正常工作，那么备份指派路 由器变为指派路由器。因为网络上的其它路由器已经与备份指派路由器形成邻接， 所以网络的不稳定性被降到最低。 2 1 5 区域 在o s p f 协议中，繁多的数据库和复杂的算法给路由器的内存和处理器带来了 沉重的负担。o s p f 协议中引入了区域的概念来减少这些负面影响，区域是o s p f 路由器和链接形成的逻辑上的组，这些逻辑上的组有效地将赘个o s p f 域分成多 个子域。在每个域内的路由器并不知道域外的网络拓扑结构。每一个路由器只是 与所在区域内的而不是与整个系统内的路由器保持一致的链路状态数据库，这样 就减少了数据库的规模，也减少了对路由器内存的影响。较小的链路状态数据库 意味着较少的链路状态通告需要处理，因此对路由器的处理器有较小的影响。 2 1 6 链路状态数据库 路由器收到的所有链路状态通告都被存储在链路状态数据库里，所有收集到的 链路状态通告描述了一张区域的网络拓扑。区域中的每个路由器都是基于这个数 据库计算出一条最短路径树。 第1 5页 北京邮电夫学硕上学位论文 2 2o s p f 链路状态数据库的形成过程 2 2 1 链路状态数据库的组成 所有路出器收至u 的合法的l s a ( 链路状态通告l i n ks t a t e a d v e r t i s e m e n t ) 都被 存储存路由器的链路状态数据库中。所有收集到的l s a 描述了区域拓扑的一张图。 由于每个路由器都是基于这个l s a 的集合来计算出它的最短路径树，所以为了精 确地选路，必须保持区域中的每个链路状态数据库都是相同的。 在链路状态数据库中，主要包含以下几种l s a ：r o u t e rl s a 、n e t w o r kl s a 、 n e t w o r ks u m m a r yl s a 、a s b r s u m m a r y l s a 、a se x t e r n a ll s a 。 r o u t e rl s a 是由网络中的每一个路由器产生的，这种最基本的l s a 列出了路 由器的所有的链接、接口阻及接口的状态和从每条链路转发数据包的费用。r o u t e r l s a 只在它产生的那个区域中扩散。r o u t e rl s a 的格式如图2 1 所示： a g eo p t i o n st y p e = 1 l i n ks t a t ei d a d v e r t i s i n g r o u t e r s e q u e n c en u m b e r c h e c k s u m l e n g t h 0 0 0 0 0vebo x 0 0n u m b e ro fl i n k s l i n k i d l i n kd a t a l i n k t y p e n u m b e ro f t o sm e t r i c t o s0 x 0 0t o sm e t r i c 图2 - ir o u t e rl s a 的格式 具体解释一下这个报文格式中的各个字段的含义： l i n ks t a t ei d ：该字段表示生成这个r o u t e rl s a 的路由器的r o u t e ri d 。 v ：该字段如果被设置为1 ，则表示生成这个r o u t e rl s a 的路由器是虚链接的一个 端点。 e ：浚字段如果被设罱为l ，则表示生成这个r o u t e r l s a 的路由器是一个自治系统 边界路由器。 b ：浚字段如果被设置为1 ，则表示生成这个r o u t e rl s a 的路由器是一个区域边 第1 6页 北京邮电夫学硕上学位论文 2 2o s p f 链路状态数据库的形成过程 2 2 1 链路状态数据库的组成 所有路由器收到的合法的l s a ( 链路状态通告l i n ks t a t e a d v e r t i s e m e n t ) 都被 存储存路由器的链路状态数据库中。所有收集到的l s a 描述了区域拓扑的一张图。 由于每个路由器都是基于这个l s a 的集合来计算出它的最短路径树，所以为了精 确地选路，必须保持区域中的每个链路状态数据库都是相同的。 在链路状态数据库中，主要包含以下几种l s a ：r o u t e rl s a 、n e t w o r kl s a 、 n e t w o r ks u m m a r yl s a 、a s b r s u m m a r y l s a 、a se x t e r n a ll s a 。 r o u t e rl s a 是由网络中的每一个路由器产生的，这种最基本的l s a 列出了路 北京邮电大学硕j 二学位论文 界路由器。 n u m b e ro f l i n k s ：该字段表示这个r o u t e rl s a 描述的链接的条数。 l i n k t y p e ：该字段描述了这条链接的类型。链接的类型主要分为4 种，如表2 1 所示： 链接类型描述 i 点对点连接到另一台路由器 2 连结到一个传输网络 3 连结到一个残端网络 t t 虚链接 表2 - 1 链接的类型 l i n ki d ：该字段描述了这条链接的对端。在路由表计算的过程中，该字段被用来 在链路状态数据库中查找该路由器的邻居生成的l s a 。 键接类型l i n k i d 字段的值 l 邻居路由器的r o u t e ri d 2 指定路由器接口的i p 地址 i p 子网的地址 4 邻居路由器的r o u t e ri d 表2 - 2l i n k 【d 的值 链接类型l i n kd a t a 字段的值 1 生成这个l s a 的路由器连接到网络的接口的i p 地址 2 生成这个l s a 的路由器连接到网络的接口的i p 地蛙 3 网络的i p 地址或子网掩码 4 生成这个l s a 的路由器的接口的m i bi i 值 表2 - 3l i n k d a t a 的值 m e t r i c ：从这条链路( 或接口) 转发数据报文的费用。 n e t w o r k l s a 是由指派路出器产生的。这种l s a 对外宣告了一个多接入的网络以 第1 7页 北京邮电大学硕士学位论文 及所有连接到这个网络的路由器。和r o u t e rl s a 一样，n e t w o r kl s a 只在它产生 的区域内扩散。n e t w o r kl s a 的格式如图2 2 所示： a g eo p t i o n st y p e 2 2 l i n ks t a t ei d a d v e r t i s i n gr o u t e r s e q u e n c e n u m b e r c h e c k s u m l e n g t h n e t w o r km a s k a t t a c h e dr o u t e r a 饿l c h e dr o u t e r 图2 - 2n e t w o r kl s a 的格式 l i n ks t a t ei d ：指派路出器的网络接口的i p 地址。 n e t w o r km a s k ：该字段指明了当前网络的子网掩码。 a t t a c h e dr o u t e r ：该字段列出了网络中所有与指派路由器形成完全邻接的路由器 的r o u t e ri d ，其中也包括指派路由器自己的r o u t e ri d n e t w o r k s u m m a r yl s a 和a s b rs u m m a r yl s a 具有相同的格式。不同的地方在于 t y p e 字段和l i n ks t a t ei d 字段。区域边界路由器可以产生这两种s u m m a r y l s a 。 n e t w o r ks u m m a r yl s a 负责广播区域外的网络，而a s b r 负责广播区域外的自治系 统边界路由器。这两种l s a 都在单个的区域内扩散。这两种l s a 的格式如图2 3 所不： a g e o p t i o n st y p e = 3o r 4 l i n ks t a t ei d a d v e r t i s i n g r o u t e r s e q u e n c e n u m b e r 第1 8页 北京邮电大学硕上学位论文 lc h e e k s u r n l e n g t h j n e t w o r km a s k i f。x 。m e t r i c t o st o sm e t r i c 尉2 - 3s u m m a r yl s a 的格式 l i n ks t a t ei d ：对于n e t w o r kl s a 来讲，该字段的值是它所要宣告的网络的i p 地址。 而刺于a s b rs u m m a r yl s a 来讲，该字段的值是所要宣告的自治系统边界路由器 的r o u t e r i d 。 n e t w o r km a s k ：对于n e t w o r kl s a 来讲，该字段的值是它所要宣告的网络的子网 掩码。而对于a s b rs u m m a r yl s a 来讲，该字段没有意义，设置为0 0 0 0 。 如果n e t w o r kl s a 宣告的是一条默认路径，那么l i n ks t a t ei d 和n e t w o r km a s k 字段都将被设置为0 0 0 0 。 a u t o n o m o u ss y s t e me x t e r n a ll s a 是由自治系统边界路由器生成的。用这种l s a 来宣告自治系统以外可以到达的目的地地址。a u t o n o m o u ss y s t e me x t e r n a ll s a 的 格式如图2 4 所示： a g eo p t i o n st y p e = 5 l i n ks t a t ei d a d v e r t i s i n g r o u t e r s e q u e n c e n u m b e r c h e c k s u m l e n g t h n e t w o r km a s k e0 0 0 0 0 0 0m e t r i c f o r w a r d i n g a d d r e s s e x t e r n a lr o u t e t a g 图2 - 4a u t o n o m o u ss y s t e me x t e r n a ll s a 的格式 第1 9页 北京邮电大学坝 学位论文 l i n ks t a t ei d ：该字段是a se x t e r n a ll s a 所要宣告的目的地的i p 地址。 n e t w o r km a s k ：该字段是a se x t e r n a ll s a 所要宣告的目的地的子网掩码。 e x t e r n a lm e t r i c ：如果陔字段被设置为l ，那么度量类型为e 2 。如果该字段被设置 为0 ，那么度量类型为e l 。 f o r w a r d i n ga d d r e s s ：该字段表明了发送给所宣告的目的地的数据报文首先要转发 给哪个地址。 2 2 2 链路状态数据库的形成 在o s p f 网络中，为了使每个路由器中的链路状态数据库保持一致，有个 数据库同步的过程，这个过程也就是链路状态数据库的形成过程。 在o s p f 网络中，两台路由器的链路状态数据库如果形成了同步，那么意味着 这两台路由器形成了邻接。在邻接的建立过程中，用到了三种o s p f 报文： 数据库描述报文( t y p e 2 ) 链路状态请求报文( t y p e 3 ) 链路状态更新报文( t y p e 4 ) 数据库描述报文对于整个邻接的建立过程是非常重要的，报文中简要描述了路 由器的链路状态数据库的每一个报文。这种描述并不是描述整个的l s a 报文，而 只是l s a 报文的报文头。对于接收到数据库描述报文的路由器来讲，这些报文头 的信息足以判断它自己的数据库中的l s a 是否是最新的。数据库描述报文的格式 如图2 - 5 所示： v e r s i o n t y p e = 2 p a c k e tl e n g t h r o u t e ri d a r e a i d c h e c k s u m a u t y p e a u t h e n t i c a t i o n a u t h e n t i c a t i o n i n t e r f a c em t u o p t i o n s 0 0 0 0 0imm s 第2 0页 北京邮电大学硕士学位论文 d d s e q u e n c en u m b e r l s ah e a d e r s 图2 - 5 数据库描述报叉的格式 i ( i n i t i a l ) 一b i t ：浚字段被设为l ，表明这是邻接建立过程中用到的第一个数据库描述 报文。 m ( m o r e ) 一b i t ：该字段被设为l ，表明这不是邻接建立过程中用到的撮后一个数据库 描述报文。如果设置为0 ，表示这是最后一个报文。 m s ( m a s t e r s l a v e ) 一b i t ：浚字段被设为1 ，表明这个报文的产生者在数据库同步的过 程中是主。设为0 ，表明是从。 d ds e q u e n c en u m b e r ：该字段用来确保在数据库同步过程中，所有的数据库描述 报文都被路由器接收到，s e q u e n c e n u m b e r 由主路由器在生成第一个报文时设定， 在后续的报文中，该字段依次加l 。 l s a h e a d e r s ：列出了路由器的链路状态数据库中的l s a 的报文头。这些报文头中 包含有足够的信息来唯一标识一个l s a 。 邻接建立的具体过程如下： 两个想要建立邻接关系的路由器首先进行主从协商。两个路由器都发送一个 空的数据库描述报文，并把m s 位置1 ，声明自己是主路由器。这两个报文中的 s e q u e n c e n u m b e r 字段按照产生它们的路由器的算法被设置为不同的值。在协商中， 具有较低r o u t e ri d 的路由器成为从路由器。它向主路由器发送一个数据库描述报 文，该报文的m s 字段设为0 ，s e q u e n c e n u m b e r 字段设置为主路由器规定的s e q u e n c e n u m b e r 。 在邻接的建立过程中每个路由器通过向对方描述自己的链路状态数据库来 达到同步。这种描述是通过向对方发送数据库描述报文来实现的。这些报文中包 含有自己数据库中的l s a 的报文头。 如果一台路由器发现对方有一个l s a ，而自己却没有：或者对方有一个l s a ， 比自己数据库中的那个l s a 更新。那么，它就把这个l s a 放在自己的链路状态 请求队列中。它就可以发送一个链路状态请求报文来请求对方将这个更新的报文 传送给它。对方收到请求后，就发送一个包含有被请