OSPF协议设计实现.pd

OSPF协议设计实现1 绪论1 . 1   路由协议简介1 . 2   O S P F 路由协议简介1 . 3   O S P F 主要名词术语1 . 4   实现基本目标和完成情况2 O S P F 概述2 . 1   O S P F 区域划分2 . 2   O S P F 连接方式2 . 3   O S P F 网络类型2 . 4   O S P F 数据包2 . 4 . 1   包头格式2 . 4 . 2   H e l l o 包2 . 4 . 3   数据库描述包/ D D   包2 . 4 . 4   连接状态请求包/ L S R   包2 . 4 .OSPF协议设计实现第3页42接收ISR分组4.5泛洪与 Link State Update处理过程4.5.1单个路由泛洪过程4.52接收LSU分组453泛洪LSA454响应ISR而发送S分组4.55重发LSA46 Link Slate Acknowledgment处理过程46接收 LS ACK分组4.6.2发送 LS ACK分组47路由选择计算471触发路由重新计算472路由计算4.7.3与内核同步路由结论致谢参考文献附录A附录BOSPF协议设计实现第4页绪论1.1路由协议简介路由协议通过在路由器之间共享路由信息来支持可路由协议。路由信息在相邻路由器之间传递,确保所有路由器知道到其它路由器的路径。总之,路由协议创建了路由表,描述了网络拓扑结构;路由协议与路由器协同工作,执行路由选择和数据包转发功能。路由分为静态路由和动态路由,其相应的路由表称为静态路由表和动态路由表。静态路由表由网络管理员在系统安装时根据网络的配置情况预先设定,网络结构发生变化后由网络管理员手工修改路由表。动态路由随网络运行情况的变化而变化,路由器根据路由协议提供的功能自动计算数据传输的最佳路径,由此得到动态路由表。根据路由算法,动态路由协议可分为距离向量路由协议( Distance Vector RoutingProtocol)和链路状态路由协议( Link State Routing Protocol)。距离向量路由协议基于Bellman-Ford算法,主要有RIP、IGRP(lGRP为 Cisco公司的私有协议);链路状态路由协议基于图论中非常著名的 Dijkstra算法,即最短优先路径( Shortest path first,SPF算法,如OSPF。在距高向量路由协议中,路由器捋部分或全部的路由表传递给与其相邻的路由器;而在链路状态路由协议中,路由器烀链路状态信息传递给在同一区域内的所有路由器。根据路由器在自洽系统(AS)中的位置,可将路由协议分为内部网关协议( Interior Gateway Protocol,IGP)和外部网关协议( External Gateway Protocol,EGP,也叫域间路由协议)。域间路由协议有两种:外部网关协议(EGP)和边界网关协议(BGP)。EGP是为一个简单的树型拓扑结构而设计的,在处理选路循环和设置选路策略时,具有明显的缺点,目前已被BGP代替。1.2OSPF路由协议简介OSPF( Open Shortest Path First开放式最短路径优先)是一个内部网关协议( nteriorGateway Protocol,简称IGP),用于在单一自治系统( autonomous system,AS)内决策路由。是对链路状态路由协议的一种实现,隶属内部网关协议(IGP),故运作于自治系统内部。著名 Dijkstra算法被用来计算最短路径树。1.3OSPF主要名词术语Router路由器种三层P分组交换机。OSPF协议设计实现第5页Autonomous System自治系统组使用相同路由协议来交换路由信息的路由器。简写为AS。Interior Gateway Protocol内部网关协议被一个AS内的路由器所使用的路由协议,缩写为GP。每个AS使用单一的IGP,不同的AS会使用不同的IGP。Router d路由器标识个用来识别每台运行OSPF协议路由器的32位数。在一个自治系统中,这个数唯一地标志一个路由器。Network网络表示IP网络子网/超网。一个物理网络上可能设置有多个网络子网号,我们把它们按照独立的网络来对待。Network mask网络掩码个32位的数字,表示IP地址的范围来说明这是一个P网络子网/超网。本文以16进制来表示网络掩码。Point-to- point networks点对点网络仅仅连接一对路由器的网络。Broadcast networks广播网络支持多台(大于两台)路由器接入的网络,同时有能力发送一条信息就能到所有接入的路由器(广播)。网络上邻居路由器可以通过OSPF的Hll协议来动态发现。如果可能,OSPF协议将进一步使用多播。广播网络上的每一对路由器都被认为可以值接通讯。Non- broadcast networks非广播网络支持多台(大于两台)路由器接入的网络,但没有广播能力。网络上的邻居路由器通过OSPF的 Hello协议来维持。但由于缺乏广播能力,需要一些配置信息的帮助来发现邻居。在非广播网络上,OSPF协议的数据通常需要被轮流发送到每一台邻居路由器上Interface接口是指路由器与所接入的网络之间的一个连接。接口通过下层协议和路由协议获取与其相关的状态信息。指向网络的接囗只和单一的IP地址及掩码相关(除非是无编号的点对点网络)。接囗有时也被称为连接。Neighboring routers邻居路由器OSPF协议设计实现第6页在同一网络中都有接口的两台路由器。邻居关系是由OSPF的Helo协议来维持,并通常依靠Helo协议来动态发现。Adjacency邻接用以在所选择的邻居路由器之间交换路由信息的关系。不是每对邻居路由器都会成为邻接。Link state advertisement链路状态宣告描述路由器或网络自身状态的数据单元。对路由器来说,这包含它的接口和邻接状态。每一项连接状态宣告都被泛洪到整个路由域中。所有路由器和网络链路状态宣告的集合形成了协议的连接状态数据库。Hello protocol hello协议在OSPF协议中,用于建立和维持邻居关系的部分。在广播网络中还被用于动态发现邻居路由器。Flooding泛洪在OSPF协议中,用于OSPF路由器之间发送及同步连接状态数据库的部分。Designated router指定路由器在每个接入了至少两台路由器的广播和NBMA网络中都有一台作为指定路由器。指定路由器生成 Network-LSA并在运行协议时完成其他特定职责。指定路由器通过 Hello协议选举。指定路由器的概念减少了广播和NBMA网络上所需要的邻接数量。同时也减少了路由协议所需要的流量及连接数据库的大小。常缩写为DR。Lower-level protocols下层协议为IP及OSP协议提供服务的下层网络接入协议。如为以太网服务的以太网数据链路层。1.4实现基本目标和完成情况骨干区域(区域号为0)中广播网络中的DR、BDR选举。OSPF分组的封装和发送。Router lsa和 Network lsa的实现。最短路径的计算。捋计算出的路由表存入 Linux系绕内核。OSPF协议设计实现第7页1.5实现难点实现了较为独立的类,提供了一定的扩展性。详见3.1.2“主要数据结构”。实现了较为完整的LSA老化,详见3.52LSA老化”。利用特定的数据结构,实现了最短路径算法。详见4.6.1“路由计算”。4、利用 Linux ipya4 routing socket,直接向内核添加或删除路由,用IP转发实现路由功能。详见4.6.2“与内核同步路由”。OSPF协议设计实现第8页2OSPF概述2.1OSPF区域划分因为OSP路由器之间会捋所有的链路状态(LSA)相互交换,毫不保留,当网络规模达到一定程度时,LSA将形成一个庞大的数据库,势必会给OSPF计算带来巨大的压力;为了能够降低OSPF计算的复杂程度,缓存计算压力,OSPF采用分区域计算,烀网络中所有OSPF路由器划分成不同的区域,每个区域负责各自区域精确的LSA传递与路由计算,然后再将一个区域的LSA简化和汇总之后转发到另外一个区域,这样一来,在区域内部,拥有网络精确的LSA,而在不同区域,则传递简化的LSA。区域的划分为了能够尽量设计成无环网络,所以采用了Hub- Spoke的拓朴架构,也就是采用核心与分支的拓朴,如下图Area 3Area 2Area 0Area 4Area 1区域的命名可以采用整数数字,如1、2、3、4,也可以采用P地址的形式,0.00.1、0.0.0.2,因为采用了Hb- Spoke的架构,所以必须定义出一个核心,然后其它部分都与核心相连,OSPF的区域0就是所有区域的核心,称为 Back Bone区域(骨干区域)而其它区域称为 normal区域(常规区域),在理论上,所有的常规区域应该直接和骨干区域相连,常规区域只能和骨干区域交换LSA,常规区域与常规区域之间即使值连也无法互换LSA,如上图中Area1、Area2、Area3、Area4只能和Area0互换LSA,然后再由Area0转发,Area0就像是一个中转站,两个常规区域需要交换LSA,只能先交给Area0,再由Area0转发,而常规区域之间无法互相转发。OSPF区域是基于路由器的接口划分的,而不是基于整台路由器划分的,一台路由OSPF协议设计实现第9页器可以属于单个区域,也可以属于多个区域,如下图:HErE四厂e2.2OSPF连接方式如果一台OSPF路由器属于单个区域,即该路由器所有接口都属于同一个区域,那么这台路由器称为 Internal Router(IR),如上图中的R2,R3和R4;如果一台OSPF路由器属于多个区域,即该路由器的接口不都属于一个区域,那么这台路由器称为AreaBorder router(ABR),如上图中的R1,ABR可以烀一个区域的LSA汇总后转发至另一个区域;如果一台OSPF路由器捋外部路由协议重分布进OSPF,那么这台路由器称为Autonomous System Boundary router(ASBR),如上图中,R5捋EGRP重分进OSPF,那么R5就是ASBR,但是如果只是将OSPF重分布进其它路由协议,则不能称为ASBR。可以配置任何OSPF路由器成为ABR或ASBR下面给出这四种路由器的详细定义●IAR( Interal Area router)区域内路由器所有接口属于一个区域,只生成一条ISA,只有一个LSDB。ABR( Area border router)区域边界路由器同时属于两个以上区域,为所属的每个区域生成一条LSA和保存一个LSDB,根据需要能够生成第三、第四类LSA。●ASBR( AS Boundery router)治系统边界路由器引入其它路由协议的路由器。不一定在AS的边界。生成第五类LSA。BBR( Back Bone router)骨干路由器OSPF协议设计实现第10页23OSPF网络类型·点到点网络( point-to- point),由 cisco提出的网络类型,自动发现邻居,不选举DR/BDR,hell0时间10s广播型网络( broadcast),由 cisco提出的网络类型,自动发现邻居,选举DR/BDR,hell时间10s非广播型(NBMA)网络(non- broadcast),由RFC提出的网络类型,手工配置邻居,选举DR/BDR,hlo时间30s点到多点网络( point-to-multipoint),由RFC提出,自动发现邻居,不选举DR/BDR,hell时间30s点到多点非广播,由 CIsco提出的网络类型,手动配置邻居,不选举DR/BDRhell0时间30s。24OSPF数据包24.1包头格式每个OSPF包都以24字节的头部开始。头部所包含的所有信息用于决定包如何进行下一步操作。201234567890123456789012345678901版本号/ Version#类型/Iype包长度/ Packet length+-+-+-+-+-+-+-+-+-+-+-1-+路由器标识/ Router id区域标识/ Area id+-+-+-11-1-+-1--1-1-1-+--+-+-+-+-+-+-+-++-1-+-+-+-+-+-+-+-+校验和/ Checksum验证类型/ AuType验证/ Authenticat ion验证/ authenticat ion版本号/ Version#OSPF的版本号,本规范所说明的协议版本号为2。类型/TypeOSPF包的类型按如下定义。具体细节见附录A.32到附录A.3.6。类型描述