开放最短路优先(OSPF)

OSPF是由IETF的IGP工作组为IP网络设计的路由协议，此工作组于1988年设计了基于最短路优先（SPF）算法的IGP用于Internet。同IGRP一样，OSPF的产生是因为80年代中期RIP协议已经不能用于大型异构的Internet结构了。下面我们谈一下OSPF的路由运行环境，路由算法和通常的协议组件。
OSPF是在包括Bolt，Beranek的努力下完成的，它使用了Newman的最短路优先（SPF）算法进行工作。它有两个基本特点，首先它是开放的，第二个非凡就是它是基于SPF算法进行的，也就是我们在图论所说的Dijkstra算法。 OSPF是内部使用连接状态路由协议，协议通过向同层结点发送连接状态信息（LSA）工作，当路由器接收到这些信息时，它就可以根据SPF算法计算出到每个结点的最短路了。它的工作方式与我们熟悉的RIP和IGRP协议不同，SPF只使用发送当前结点到相邻结点的路由信息，而RIP和IGRP需要结点把自己结点保留的由路表或路由表的一部分全部到相邻结点，相邻结点根据这些信息更新自己的路由表，前者发送的信息量少，而后者发送的信息量多。
与我们熟悉的RIP不同，OSPF的路由信息在一个树状结构内传送，这个树状结构内最大的结构就是一个自治域（AS），它们是使用同一路由策略的一组网络。OSPF是一个内部路由协议，但这并不是说它不能向其它AS向送路由信息，我们可以知道，OSPF的方法就是寻找一个AS内的最短路，它建立在一个基本的假设之上，也就是假如在每个小范围内都最短那整个路径一定最短。一个AS可以被分为不同的域，这不同的域包括同构的网络和与之相关的主机，有多个接口的路由器可以属于不同的域，它些非凡的路由器称为域边界路由器，它保存每个域的拓朴结构数据库。拓朴结构数据库内保存了与这个路由器相连的网络的拓朴结构，同时它也保存了同一域中所有路由器发送来的LSA信息，我们已经知道了，在同一域中的路由器有相同的路由信息，因此它们有相同的拓朴结构数据库。我们在阅读关于OSPF的文档时，经常会看到域这个名词，它是描述拥有相同拓朴结构数据库的路由器的那部分网络，它有时和AS相互混用，希望注重。对于域外的实体而言这个域的拓朴结构对它们来说是可见的，OSPF使用将AS分块的方法减少网络通信量。既然分了一个域的概念，那路由方法也要分为两种了，一种是用于目的结点和源结点在同一个域内和另一种是用于目的结点和源结点在不同的域内。
OSPF主干负责在域之间传送路由信息，它包括所有的边界路由器和未完全包括在任何单独一个域中的网络结构以及与此网络结构相关的设备。下图就显示了不同情况，体现了由路由器连接的不同域。

在上图中，路由器4，5，6，10，11和12构成了主干，假如在域3中的主机H1希望发送数据到域2中的主机H2，那它就必须把包发到路由器13，由它将信息发送到路由器12，再由12发送到路由器11，由路由器11将路由信息发送到域边界路由器10，再由两个域内路由器9和7将信息发送到主机H2。刚才我们提到了主干，主干自己也是一个OSPF域，此域内的路由器使用相同的路由策略，此域的结构对所有域内路由器来说是可见的。大家要注重到，主干域的结构是不同构的，因此主干域的相互连接要使用虚拟连接方式进行，也就是说，两个主干域内的路由器必须通过一个非主干域进行通信，而这种通信又是对这两个主干域路由器透明的。
说到现在，我们有些人仍然对SPF算法如坠云雾，下面我们就来简单地说一下这个算法，假如不理解这个算法就无法理解OSPF的工作过程。当一个SPF路由器启动时，它初始化它的路由信息结构表，然后等待下层接口，当它确定下层接口可用时，它就使用OSPF的Hello协议向相邻的路由器发送一个问候包，然后接收这些路由器发回的信息。这个问候包不但可以帮助路由器在初始工作时了解相邻结构，而且可以在运行中了解相邻路由器的工作情况，假如相邻的路由器关机了，那就不会从它那里收到回应信息了。假如网络支持多个路由器，Hello协议可以帮助选择一个主控路由器和一个备份路由器，由主控路由器向整个网络发送LSA。
假如两个相邻结点路由器的连接状态数据库同步了，我们就称它们相邻了，在有主控路由器的网络中，主控路由器有权决定哪些路由器可以是相邻的，拓朴结构数据库在相邻的路由器之间是同步的，路由信息包的发送也仅仅在相邻的路由器间进行。每个路由器要定期发出LSA，假如它的路由信息发生了改变，那它需要立即通知其它路由器。通过获得相邻路由器发送的信息，能够很快知道哪些路由器不能工作了，能够对网络拓朴结构的变化做到快速反应。通过接收到LSA产生拓朴结构数据库，再经过SPF算法可以得到了个最短路树，树的根结点就是当前这个路由器，通过这个树可以产生路由表。
下面我们来看一下OSPF包结构，所有的OSPF包都有一个24位的包头，包头内的信息如下图所示：
首先是版本号，它标明了使用的OSPF版本信息，下一个数据域是数据类型，它说明了包内的数据是干什么的，可以分以下几种数据类型：
问候：用于建立和维护相邻结点信息；
数据库描述：用于描述拓朴结构数据库的内容，在建立相邻路由器时，必须交换这些信息；
连接状态请求：用于从相邻路由器请求获得拓朴结构数据库内的一些数据，当某个路由器发现自己路由表的某部分已经过期时就要使用这一请求获得更新过的信息；
连接状态更新：用于响应上面所说的连接状态请求包，也可以从它在同一个连接状态包内提取LSA；
连接状态确认：用于确认连接状态更新包；
下面的的数据域用于表示包长度，这个长度包括包头的长度并以字节表示；数据域后面是路由器号，它用于标明是哪个路由器发送的此包，路由器号后面是域号，它标明包属于的域，每个包只能属于一个域。OSPF协议还支持对紧急信息的优先发送功能，它为网络治理提供了灵活方便的手段。