OSPF协议简介.doc

OSPF协议简介前 言OSPF协议是(Open Shortest Path Fist)开放式最短路优先协议的缩写，是用于计算机网络上发现路由，计算路由的一种协议。OSPF入门童话可以把整个网络（一个自治系统AS）看成一个王国，这个王国可以分成几个区(area)，现在我们来看看区域内的某一个人(你所在的机器root)是怎样得到一张世界地图(routing table)的。首先，你得跟你周围的人（同一网段如129.102）建立基本联系。你大叫一声“我在这！”(发HELLO报文),于是，周围的人知道你的存在，他们也会大叫，这样你知道周围大概有哪些人，你与他们之间建立了邻居(neighbor)关系，当然，他们之间也有邻居关系。在你们这一群人中，最有威望(Priority优先级)的人会被推荐为首领（Designated Router）首领与你之间是上下级关系(adjacency邻接)，它会与你建立单线联系，而不许你与其它邻居有过多交往，他会说：“那样做的话，街上太挤了”。你只好通过首领来知道更多的消息了，首先，你们互通消息，他告诉你他知道的所有地图的地名，你也会告诉他你现知道的地名，当然上也许只有你一个点。(Database Description数据库描述报文)你发现地名表中有你缺少的或比你新的东西，你会问他要一份更详细的资料，他发现你的地名表中有他需要的东西，他也会向你索求新资料。(Link State Request连接状态请求报文)当然，你们毫不犹豫地将一份详细资料发送给对方。(Link State Update连接状态升级报文)收到地图后，互相致谢表示收到了。(Link State Ack连接状态响应报文)现在，你已经尽你所能得到一份地图（Link State DataBase连接状态数据库），你去查找地图把到所有地方的路挑一条最近（shortest path最短路）的，记为一张表格（routing table路由表），当然以后查这份表格就知道到目的地的一条最近的路了。地图也要收好，万一表格上的某条路不通了可以通过图去找一条新的路。其实跟你有联系的，只是周围一群人，外面的消息要通过首领来知道。因为你的地图是跟首领的一致，我们假设你是首领，你要去画一份世界地图。你命令所有手下向你通报消息，你可以知道你这一群人的任何一点点小动静（event事件）。你手下还会有同时属于两群人的家伙（同一区内两网段），他会告诉你另一群人的地图，当然也会把你们这一群人的地图泄露，(不过，无所谓啦)。这样，整个区的地图你知道了（对于不知道的那也没办法，我们尽力了）。通过不停地交换地图，现在，整个区的人都有同样的地图了，住在区边境上的人义不容辞地把这个区的地图（精确到每一群人）发送到别的区，把别的区信息发送进来。国王会把这些边境的人命名为骨干（backbone area）。通过骨干人士的不懈努力，现在，整个国家的地图你都了解得一清二楚了。有些人“里通外国”（AS Boundary Router自治系统边界路由器），他们知道一些“出国”(AS External route自治系统外部路由)的路，当然他们会把这些秘密公之与众（import 引入），通过信息的传递，现在，你已经有一张完整的“世界地图”了。OSPF是这样标记最短的路的：对于某个目的地，首先，考虑是否有同一区内部到目的地的路（intra area区域内），如果有，则在其中取一条离你最近的（花费最小），写进你的表格中,这个目的地可能是到本群体某个人也可能是到其他群体的，对于经过其他区域的路由，你会不予考虑，跟自己人（同区域）打交道总比与外人（其他区域）打交道好；如果没有本区的路，你只好通过别的区域了（区域间），你只要在地图上找最近的就是了；如果你发现目的地在国外，你也只能先把它标记到你的表格上，期待什么时候王国扩张到那，你就可以把它标记到国内地图上了。OSPF就是这样，给你一份“世界地图”，并且在上面标记了最短的路，如此而已罢了。OSPF协议分析第一节：背景介绍TCP/IP协议中，寻找一台计算机到另一台计算机的路由是很重要的.1要判断是否能找到路2找到路后找一条短的路（花费时间最小）3在找路时不能循环4最好还应该能动态处理路由变化，如：接口的UP或DOWN，时间花费的变化，网络结构的改变等。 IETF(Internet Engineering Task Force)于1988年提出的OSPF是一个基于链路状态的动态路由协议，协议的基本思路如下：在自治系统中每一台运行OSPF的路由器收集各自的接口/邻接信息称为链路状态，通过Flooding算法在整个系统广播自己的链路状态，使得在整个系统内部维护一个同步的链路状态数据库，根据这一数据库，路由器计算出以自己为根，其它网络节点为叶的一根最短的路径树，从而计算出自己到达系统内部可达的最佳路由。OSPF是一类Interior Gateway Protocol(内部网关协议IGP)，它处理在一个自治系统中，路由器的网络的路由表信息。OSPF路由协议在TCP/IP协议族的位置：图1 OSPF在网络协议族的地位第二节：术语和基本概念l OSPF路由协议术语：OSPF路由协议: Open Shortest Path First 最短路径优先协议路由器（router）：第三层的IP包交换机，以前在IP文献中也叫做网关自治系统(autonomy system)：一群路由器通过相同的路由协议来交换路由信息，缩写为AS区域(area):自治系统的划分单元,一个自治系统可以划分为多个区域.区域 ID(area ID):自治系统内区域的32-bit标识.内部网关协议(internal gateway protocol)：属于一个自治系统的路由器上运行的路由协议，缩写为IGP，每一个自治系统有一个单独的IGP，不同的自治系统可能运行不同的IGP。OSPF是内部网关协议的一种.路由器的ID(router ID)：一个32位的标号对每个运行OSPF的路由器，在自治系统内是唯一的网络(network)：在这种意义下，是IP网络/子网/超网，可能是标记了多重复合IP地址的子网，我们把它们看成是分离的网络，点到点的物理网络是个特例，它们只是被当作简单的网，不管对它们怎样指定IP号。网络掩码(network mask)：一个32位的数指示IP网络的IP地址范围，以十六进制数显示，例如一个C类网的掩码是0xfffff00，在文字上写成255.255.255.0。点到点网络(point to point network)：由一对路由器简单组成的网络，例如一个56Kb的串口线的连接广播网：网络支持许多(两个以上)的路由器。都有能力将地址信息发送到所有连接的路由器上(广播)邻居路由器被OSPF的hello协议动态地发现，OSPF使这种广播能力能得到更大的应用，如果它存在，它上的每一对路由器都假定能和对方直接相连，以太网是一个广播网的例子。非广播网：网络支持许多(两个以上)路由器，但没有广播能力，邻结点也是通过OSPF hello报文来维持，但是由于设有广播能力一些邻居需要靠配置来发现，在邻居间，OSPF协议报文也是互相传送的，X.25网是一个例子。 OSPF可以在两种非广播网上运行，一种是非广播多重访问，(NBMA)它类似于OSPF在广播网上的操作，第二种类型叫点到多点，可看为多个点到点的连接的集合。非广播网类型的判别依靠于对网络的操作模式。接口(interface)： 一个路由器与它连接的一个网络的连接称为接口，一个接口有它的状态信息，可以通过底层协议或是路由协议本身来得到。每个接口有一个唯一一个IP地址和掩码(除非是不标号的点到点连接)，一个接口有时也指一个连接。邻居路由器(neighbor)： 两台路由器有接口连向共同的网络，邻居关系通过OSPF hello协议被维持(通常是动态的)。邻接(adjacency)： 为交换路由而在邻居间建立的关系，不是每对邻居都成都为邻接的。连接状态传送(Link State Advertise)： 描述本地路由器或网络的数据单元对路由器来说，它描述了路由器的接口状态和邻接状态，第一个连接状态传送会发送到整个路由领域，所有的连接状态传送组成了协议的连接状态数据库，这在全局范围内使用,缩写为LSA连接状态数据库(Link State DataBase):所有的连接状态传送组成了连接状态数据库.stub网络:只有一个接口与外部相连的网络,如一个PPP可视为一个stub网络骨干区域(Backbone Area):所有区域边界路由器和它们之间的路由组成骨干区域.自治系统外部路由(AS external route):指由非OSPF协议得到的路由，如BGP（边界网关协议），RIP（Routing Information Protocol),系统的静态配置路由等,系统的静态路由是由配置得到的,其他协议的路由是通过引入操作得到的,外部路由的指定是由用户决定的.路由(route)：指两节点之间的连通路径。路由表（routing table）:到每个目的地有路由，这样的表叫路由表。l 基本概念：OSPF把整个网络(Internet上的子网或其他类型的网)看成一个自治系统(AS)每一个AS内若干个物理上相邻的路由器(Router)，网络(Network)组成Area，这些Area内部一般是不相交的，它们划分了整个AS。如图是一个典型的自治系统划分的例子：图2 OSPF系统网络拓扑结构图例Rxx代表路由器，N*代表网络，1R1,R2,R3,R4,N1组成区域1,R3,R4是区域边界路由器(ABR)2R7,R8,R10,N2,N3组成区域2,R7,R10,R11是区域边界路由器(ABR)3R9.R11,R12,N4组成区域3，R11是区域边界路由器(ABR)4所有区域边节点（R3，R4，R7，R10，R11）及R5,R6共同组成了骨干区域，(backbone area)5Area1,Area2,Area3以及backbone area共同组成了一个自治系统(Autonomous System),R5是系统的边节点(ASBR) OSPF的数据储存结构如下图所示：图3 OSPF的数据储存结构OSPF协议的中心思想是在每一个区域上运行一个OSPF的副本，让我们以区域为基础进行阐述。 通过路由器间的路由信息交换，自治系统内部可以达到信息同步，即LSDB（连接状态数据库）描述的网络拓扑同步。LSDB由LSA（连接状态传送报文）得到，由于LSA的种类不同，可以把LSDB分成五类：1. rtr_LSA 由区域内路由传送来的LSA.2. net_LSA 由区域内子网络传送的LSA.3. netsum_LSA 区域间传送描述网络的LSA.4. asbrsum_LSA 区域间传送描述AS边节点的LSA.5. ASE_LSA AS外部的LSA LSA所描述的信息一般包括:1. 接口信息:接口ID,类型(LS_TYPE),状态(STATE)等2. 网络节点信息:目的地(destination)，掩码（mask）,所属区域，位置等3. 路由信息:下一跳(next hop，即路由下一步该去的顶点),权(metric),类型(route type)等4. 其他信息：时控，该节点收到的连接状态传送报文信息等 所有的LSA组成ROOT的LSDB，通过LSDB，每个节点可以用Dijkstra算法，求出最小树(Shortest Path Tree)通过最小树并改进系统路由表(routing table)，路由表包含目的地(destination)，下一跳(next hop)，花费(metric)等.出于安全性考虑，OSPF协议中还包含认证过程，路由器之间必须通过某个过程来认证它们之间的通信，即在OSPF报文中加入认证字。第三节、得到连接状态数据库 下面我们看看一台机器是怎样通过报文的发送得到一个完整的LSBD的,下图能大概描述两台路由器从开始联系到数据库同步的信息（报文）传递过程。 图 4 两台路由器的数据同步过程l 向物理上能达（广播网同一网段或PPP或NBMA上的指定的节点）所有结点发送Hello报文，同时也收到它们发送来的Hello报文；这样，可以确认哪些机器是相连的，这种相连，确定了它们之间的Neighbor的关系.对HELLO报文的处理详见下图：图5 HELLO报文处理过程图通过Hello报文的所带priority位，和DR、BDR信息，可以选出该网段的DR。所有路由器认可一个优先级最高的路由器作为DR，优先级次高的作为BDR，所有这个网段的路由器与DR，BDR构成邻接关系：图6 DR、BDR选举l 路由信息(连接状态传送报文)只在形成邻接关系的路由器间传递。首先，它们之间互发DD（database description）报文，告之对方自己所拥有的路由信息。DD报文有两种，一种是空DD报文，用来确定Master/Slave关系（避免DD报文的无序发送），确定Master/Slave关系后，才发送有路由信息的DD报文，收到有路由信息的DD报文后，比较自己的数据库，发现对方的数据库中有自己需要的数据，则向对方发送连接状态请求（Link State Request）报文，请求对方给自己发送数据。l LSR报文指示了所需的那部分LSA的内容，让对方给发送收到LSR报文后，按要求发送新的路由信息给对方，即给对方发送连接状态升级报文（Link State Update）报文。l LSU报文给对方一个详细的路由信息收到LSU之后，会给对方发送一个连接状态响应报文（Link State Ack）报文，以示收到，对DR来说，会发送一个包含该连接状态升级报文的连接状态升级报文到网段内所有节点（不发连接状态响应报文）。l LSAck报文指示收到LSU报文DD，LSR，LSU，LSAck在没有收到对方相应的响应时，一般会重传。通过Adjacency间的连接状态传送报文传递信息在同一个网段内达到同步；通过属于多个网段的路由器的“中转”，区域内路由信息可以达到同步。有的路由器的两个或多个接口会配置在几个区域上，这个路由器是在backbone上，它会把它得到的路由信息摘要，发给backbone上其它点，摘要指的是只发网段信息。有些节点会把其它协议的路由（静态，RIP，BGP，EGP等），引入到自治系统内部，用类似的方法把ASE，ASBR信息传送到整个自治系统，。LSA发送可以由下图表示。图7 各类连接状态传送报文的发送在系统达到同步后，某一台路由器的路由表发生变化，则把路由变化部分，以类似链式反应的方式发送，我们称之为“FLOOD”，把升级的路由表在系统内同步了。第四节：计算路由表让我们先看一个例子：图8 一个网络的带权有向图注：网络到路由器是没有花费的。 由上图，得到R1的最短路树：图9 由上图得到的R1的最短路树路由表计算过程： (1)初始化，保存旧的路由表 (2)用Dijkstra算法计算区域内的路由 (3)通过检查SUM_LSA，计算区域间的路由 (4)利用虚连接改进路由 (5)通过ASE_LSA,计算AS外部路由 计算是按根节点所连的区域逐个区域来计算的，对于每一个区域，分别进行计算,且在计算过程中逐步改进路由表。其实际过程应该是如下图所示：图10 路由计算过程图不同路由的比较如下图所示：图11 路由比较过程图第五节：OSPF协议与其它路由协议的比较 通用的路由协议除了OSPF，主要还有RIP路由协议（路由信息协议）等，将OSPF和RIP作一个大致的比较如下：1. 网络结构不同：RIP的拓扑是简单的“小”图，说它简单，是因为它没有系统内外，系统分区，边界的概念，它用的是不分类的路由；说它“小”，是因为它的每一个节点只能处理以自己为头的至多16个节点的链，路由以下一跳个数来描述，无法体现带宽和网络延迟，RIP适用于中小型网络。 OSPF可以适用于较大规模的网络，它把自治系统分为若干个区域，通过系统内外路由的不同处理，区域内和区域间路由的不同处理方法，引入摘要的概念，减少了网络数据量的传输，OSPF对应于RIP中的“距离”的概念，引入了“权”（metric）的概念，对于不同的网络连接可以人工指定或根据网络的带宽和网络延迟动态地计算花费，OSPF所能接受的最大的花费是65534即0XFFFF-1（区域内，区域间和自治系统外为16777214即0XFFFFFF-1），其缺省得花费是1，可以说OSPF的路由处理能力相当大，并且还把其他协议的路由或静态或核心路由作为自治系统外部路由引入，它的处理能力已经是相当完全了。 RIP不支持可变长度子网掩码（Variable Length Subnet Masks i.e. VLSM，RIP的新版本RIP2支持），OSPF支持VLSM。2. 协议的运行有差异：RIP运行时，首先向外广播请求报文，其他运行RIP的路由器收到请求报文后，马上把自己的路由表发送过来；在没有收到请求报文时，定期（30秒）广播自己的路由表，在180秒之内如果没有收到某个相邻路由器的路由表，就认为它DOWN掉了，把它从路由表中作废，120秒后清除，并广播自己新的路由表。OSPF运行时，用HELLO报文建立连接，然后迅速建立邻接的关系，在建立了邻接关系路由器中发送路由信息；以后，是靠定期发送HELLO报文去维持连接，相对来说，HELLO报文数据量比RIP协议的路由表报文小得多，网络拥塞也少了，HELLO报文在广播网上10秒发送一次，在NBMA，PPP，虚连接上30秒发送一次，在一定时间（4倍于HELLO间隔）没有收到HELLO报文，认为对方“死“掉，从路由表中去掉它，在LSBD中给它置位为INFINITY，但并没有真正去掉，以备它再起时减少数据传输量，在它达到MaxAge（3600秒）时，真正去掉它。OSPF的路由表也重发，重发间隔是1800秒。以上这些从另一方面说明了OSPF协议适用性广，RIP相对简单，适用于较小规模网络。3. 使用情况不同： 一般说来（由统计数据得到，参看RFC 1245），OSPF占用的实际链路带宽比RIP少，因为它的路由表是有选择的广播（只在建立邻接关系的路由器间），OSPF使用的CUP时间比RIP少，因为OSPF达到平衡后的主要工作只是发HELLO报文，RIP是发送路由表，OSPF用的路由器的内存比RIP大，因为OSPF相对有一个大的路由表。RIP在网络上达到平衡用的时间比OSPF多，因为它往往要发送及处理一些无用的路由信息。OSPF疑难解析问题1：OSPF的有什么特点？答：OSPF协议的特点有：1它引入了以下的概念：邻接关系：在某些运行OSPF的路由器对（pair）中建立邻接关系，它们的数据库通过交换信息来达到同步。所有路由器和网段上的DR，BDR建立邻接关系。对于没有DR，BDR的点到点网络，是两端直接构成邻接关系的。DR：在广播网和NBMA上，同一网段上的所有路由器通过一定算法选举DR、BDR，DR的作用是与网段内的路由器构成邻接关系，并交换路由信息；把本网段的路由信息“包装”成NETLSA，本网段内有多个接口的路由器发送到其他网段。BDR：在选举DR的同时，BDR也被选举出来，它也与本网段所有路由器建立邻接关系，与DR功能不同的是，它不产生NETLSA，它的主要意义在于网络的DR消失后，能迅速（最坏的情况240秒，最好的情况马上）升级为DR，这样做，能够节省许多开销。区域：OSPF允许把自治系统分为区域，首先，它提供了所谓的路由保护，即区域内路由的优先级高于其余的路由，其次，路由算法所占用的计算时间（占CPU时间的主要部分）也减少了。路由分级：OSPF的路由依照其优先级排列有四种：区域内路由，区域间路由，ASE外部1类路由，ASE外部2类路由。它提供了路由保护的功能（即优先级高的路由比优先级低的路由优先加入路由表），及简化了自治系统的路由管理。虚连接：引入虚连接的概念，保证了骨干区域的路由器的连通性，减少了区域拓扑结构的限制。验证字：OSPF的报文都包含验证字字段，OSPF在处理报文之前，会检查验证字以判断是否要处理该报文。STUB区域：为了减少路由器内存的开销，某些区域可以标记为STUB区域，ASE路由信息（往往在AS的路由信息中占用大部分）不发送进入/通过STUB区域，STUB区域到ASE目的地的路由是通过一个缺省出口出去的。2它有如下功能：支持NBMA：OSPF对NBMA的处理与广播网是基本一样的，其不同之处在于HELLO报文不是以广播的形式发出的，而是向指定的、有权成为DR、BDR的路由器发HELLO报文，其余，都和广播网一样。灵活引入外部路由：OSPF把系统外部路由以ASE-LSA的形式引入，减少了路由的交通拥塞（ASE 路由占路由表的大部分，这样做，我们只需要传送路由的变化，再局部路由表升级即可）；在自治系统的边界有一个“前方地址”的概念，它可以规划ASE的下一跳；ASE有两类花费，使路由多了一个层次；ASE路由还引入了标签（tag）的概念，方便了路由管理。灵活引入花费：OSPF中，花费是配置在外出的路由器接口上的，路由的花费为所有构成该路由的接口的花费的总和，这有利于用户根据带宽、网络延迟、网络费用等因素灵活配置，选取路由。支持VLSM：通过配置掩码，OSPF支持可变长度子网掩码。支持IP多点传送：OSPF通过IP多点传送（IP Multicasting）来传送路由信息，有效地利用了带宽。问题2：OSPF在实际运行中的情况怎样？ 衡量其运行情况的因素主要有：CPU占用率，路由器内存使用情况，带宽使用情况，及路由器的处理量的情况。有一组统计数据，描述了OSPF在一些网络的运行情况，BARRNet；NEI；OARnet分别是（90年数据）： Statistic BARRNet NSI OARnet _ 路由器的数量 14 15 13 数据收集用时 99 hrs 277 hrs 28 hrs SPF计算频率 50 min 25 min 13 min 外部路由增加的频率 1.2 min 0.98 min not gathered LSA重传周期 29.7 min 30.9 min 28.2 min LSU报文中LSA个数 3.38 3.16 2.99 重传概率 1.3% 1.4% 0 .7%数据收集用时是统计用的总时间。SPF计算频率是在数据收集用时内平均的SPF树的计算频率，是占用CPU的主要因素，由统计数据可以看出，在相当的网络上路由计算的时间间隔至少13分钟，而每次计算的时间是小于毫秒级 斯坦福大学的实验数据是：200台路由器组成的网络，SPF计 算的用时是15毫秒； MILNET（美国军用网络）的数据是：230台路由器组成的网络，在网络变化相对较频繁的情况下，CPU占用率也不到5%， 经过计算得到结论，其算法复杂度是O(n*log(n)，其中n是系统中路由器的数量，其运算时间的增长是相当慢的。外部路由增加的频率是衡量路由器路由表和LSDB大小的主要因素，即路由器内存增加的主要部分，因为OSPF的路由绝大部分是ASE，每个ASE占用内存是36字节，加上在路由表中ASE路由占的28字节，共64字节，其他统计数据表明，在一台路由器上，会出现万个以上的ASE，以10000个来计算，其占用的内存是640K,这是个相当大的数字。外部路由增加的频率、LSA重传周期、连接状态升级报文中LSA个数、重传概率是衡量传送数据量的因素，是决定OSPF协议占用带宽的主要部分。一般说来，传送的数据主要是ASE连接数据升级报文，一个报文的大小是52字节，我们可以来计算一下带宽的利用：按照占用带宽的5%来计算，网络速率 每秒发送报文的个数 一个重传周期1800秒发送报文数 _ 9.6 Kb 9.2 16560 56 Kb 53 95400总的说来OSPF占用的带宽还是比较小的（相对RIP）。OSPF网络中，信息量处理最大的路由器是DR路由器，它发送的路由状态信息要比其他路由器要大得多,收到的响应报文也是最多的，DR路由器的处理量的大小，从根本上来说，决定了网络资源的使用。DR处理路由器的数量的上限一般是50台路由器。问题3：OSPF协议中的一些常数是怎样规定的。答：OSPF协议规定了以下常数：1重传周期 1800秒，定义了连接状态数据库的重传的时间间隔。2路由最大存在时间3600秒，正好是重传周期的两倍，即在两个重传时间都没有得到某路由器传来的路由信息，则将其从路由器的数据库中删去。3最小数据报文发送间隔：5秒，指定连接状态数据库发送的最小时间间隔。4最小报文收到时间：1秒，路由器不接受来自同一路由器的过于频繁的连接状态报文。5效验时间：300秒，用于效验和操作的时间常数。6最大连接状态传送报文发送时间：900秒，描述连接状态传送报文到达的时间上限。7不可达花费：定义为0XFFFFFF，大于等于此数的花费认为是无穷，即目的地不可达。8缺省目的地：对于ASE路由和STUB区域的外出路由，有一个缺省目的地0.0.0.0,其掩码也是0.0.0.0，对于路由表中找不到的目的地，一律发送到该缺省目的地。9初始化序列号：连接状态信息传送的第一个报文的序列号0X80000001，即-0X7FFFFFFF。10 最大序列号：连接状态信息传送的最大的序列号0X7FFFFFFF。11 所有OSPF路由器：多重IP地址224.0.0.5，报文广播用12 本网段DR路由器：多重IP地址226.0.0.6，报文广播用需要配置的常数：全局变量：1路由器的ID号。 区域常数：2区域ID号。3网段列表，包括IP地址，掩码4外部路由能力，指明该区域是否STUB5STUB缺省花费 接口常数(包括点到点，NBMA，虚连接)：6接口IP地址，掩码7接口所属区域的ID8发送HELLO的间隔(默认网口10秒，其他接口30秒)9认为连接断开的时间（一般是4倍以上于发送HELLO的时间）10 接口花费（默认1）11 发送接收连接状态传送报文的时间参数12 路由器优先级（默认0）13 验证字