第四章 网络层之IP支持协议--OSPF（2）起源、概述、工作原理_spf算法原理

OSPF路由协议概念及工作原理

——随着Internet技术在全球范围的飞速发展，OSPF已成为目前Internet广域网和Intranet企业网采用最多、应用最广泛的路由协议之一。OSPF（Open Shortest Path First）路由协议是由IETF（Internet Engineering Task Force）IGP工作小组提出的，是一种基于SPF算法的路由协议，目前使用的OSPF协议是其第二版，定义于RFC1247和RFC1583。

1.概述

——OSPF路由协议是一种典型的链路状态（Link-state）的路由协议，一般用于同一个路由域内。在这里，路由域是指一个自治系统（Autonomous System），即AS，它是指一组通过统一的路由政策或路由协议互相交换路由信息的网络。在这个AS中，所有的OSPF路由器都维护一个相同的描述这个AS结构的数据库，该数据库中存放的是路由域中相应链路的状态信息，OSPF路由器正是通过这个数据库计算出其OSPF路由表的。

——作为一种链路状态的路由协议，OSPF将链路状态广播数据包LSA（Link State Advertisement）传送给在某一区域内的所有路由器，这一点与距离矢量路由协议不同。运行距离矢量路由协议的路由器是将部分或全部的路由表传递给与其相邻的路由器。

2.数据包格式

——在OSPF路由协议的数据包中，其数据包头长为24个字节，包含如下8个字段：

* Version number-定义所采用的OSPF路由协议的版本。
* Type-定义OSPF数据包类型。OSPF数据包共有五种：
* Hello-用于建立和维护相邻的两个OSPF路由器的关系，该数据包是周期性地发送的。
* Database Description-用于描述整个数据库，该数据包仅在OSPF初始化时发送。
* Link state request-用于向相邻的OSPF路由器请求部分或全部的数据，这种数据包是在当路由器发现其数据已经过期时才发送的。
* Link state update-这是对link state请求数据包的响应，即通常所说的LSA数据包。
* Link state acknowledgment-是对LSA数据包的响应。
* Packet length-定义整个数据包的长度。
* Router ID-用于描述数据包的源地址，以IP地址来表示。
* Area ID-用于区分OSPF数据包属于的区域号，所有的OSPF数据包都属于一个特定的OSPF区域。
* Checksum-校验位，用于标记数据包在传递时有无误码。
* Authentication type-定义OSPF验证类型。
* Authentication-包含OSPF验证信息，长为8个字节。

3.OSPF基本算法

3.1 SPF算法及最短路径树

——SPF算法是OSPF路由协议的基础。SPF算法有时也被称为Dijkstra算法，这是因为最短路径优先算法SPF是Dijkstra发明的。SPF算法将每一个路由器作为根（ROOT）来计算其到每一个目的地路由器的距离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑结构图，该结构图类似于一棵树，在SPF算法中，被称为最短路径树。在OSPF路由协议中，最短路径树的树干长度，即OSPF路由器至每一个目的地路由器的距离，称为OSPF的Cost，其算法为：Cost = 100×106/链路带宽

——在这里，链路带宽以bps来表示。也就是说，OSPF的Cost 与链路的带宽成反比，带宽越高，Cost越小，表示OSPF到目的地的距离越近。举例来说，FDDI或快速以太网的Cost为1，2M串行链路的Cost为48，10M以太网的Cost为10等。

3.2 链路状态算法

——作为一种典型的链路状态的路由协议，OSPF还得遵循链路状态路由协议的统一算法。链路状态的算法非常简单，在这里将链路状态算法概括为以下四个步骤：

当路由器初始化或当网络结构发生变化（例如增减路由器，链路状态发生变化等）时，路由器会产生链路状态广播数据包LSA（Link-State Advertisement），该数据包里包含路由器上所有相连链路，也即为所有端口的状态信息。

所有路由器会通过一种被称为刷新（Flooding）的方法来交换链路状态数据。Flooding是指路由器将其LSA数据包传送给所有与其相邻的OSPF路由器，相邻路由器根据其接收到的链路状态信息更新自己的数据库，并将该链路状态信息转送给与其相邻的路由器，直至稳定的一个过程。 当网络重新稳定下来，也可以说OSPF路由协议收敛下来时，所有的路由器会根据其各自的链路状态信息数据库计算出各自的路由表。该路由表中包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一个路由器（next-hop）。

第4个步骤实际上是指OSPF路由协议的一个特性。当网络状态比较稳定时，网络中传递的链路状态信息是比较少的，或者可以说，当网络稳定时，网络中是比较安静的。这也正是链路状态路由协议区别与距离矢量路由协议的一大特点。

4.OSPF路由协议的基本特征

——前文已经说明了OSPF路由协议是一种链路状态的路由协议，为了更好地说明OSPF路由协议的基本特征，我们将OSPF路由协议与距离矢量路由协议之一的RIP（Routing Information Protocol）作一比较，归纳为如下几点：

——RIP路由协议中用于表示目的网络远近的唯一参数为跳（HOP），也即到达目的网络所要经过的路由器个数。在RIP路由协议中，该参数被限制为最大15，也就是说RIP路由信息最多能传递至第16个路由器；对于OSPF路由协议，路由表中表示目的网络的参数为Cost，该参数为一虚拟值，与网络中链路的带宽等相关，也就是说OSPF路由信息不受物理跳数的限制。并且，OSPF路由协议还支持TOS（Type of Service）路由，因此，OSPF比较适合应用于大型网络中。

——RIP路由协议不支持变长子网屏蔽码（VLSM），这被认为是RIP路由协议不适用于大型网络的又一重要原因。采用变长子网屏蔽码可以在最大限度上节约IP地址。OSPF路由协议对VLSM有良好的支持性。

——RIP路由协议路由收敛较慢。RIP路由协议周期性地将整个路由表作为路由信息广播至网络中，该广播周期为30秒。在一个较为大型的网络中，RIP协议会产生很大的广播信息，占用较多的网络带宽资源；并且由于RIP协议30秒的广播周期，影响了RIP路由协议的收敛，甚至出现不收敛的现象。而OSPF是一种链路状态的路由协议，当网络比较稳定时，网络中的路由信息是比较少的，并且其广播也不是周期性的，因此OSPF路由协议即使是在大型网络中也能够较快地收敛。

——在RIP协议中，网络是一个平面的概念，并无区域及边界等的定义。随着无级路由CIDR概念的出现，RIP协议就明显落伍了。在OSPF路由协议中，一个网络，或者说是一个路由域可以划分为很多个区域area，每一个区域通过OSPF边界路由器相连，区域间可以通过路由总结（Summary）来减少路由信息，减小路由表，提高路由器的运算速度。

——OSPF路由协议支持路由验证，只有互相通过路由验证的路由器之间才能交换路由信息。并且OSPF可以对不同的区域定义不同的验证方式，提高网络的安全性。

——OSPF路由协议对负载分担的支持性能较好。OSPF路由协议支持多条Cost相同的链路上的负载分担，目前一些厂家的路由器支持6条链路的负载分担。

5.区域及域间路由

——前文已经提到过，在OSPF路由协议的定义中，可以将一个路由域或者一个自治系统AS划分为几个区域。在OSPF中，由按照一定的OSPF路由法则组合在一起的一组网络或路由器的集合称为区域（AREA）。

——在OSPF路由协议中，每一个区域中的路由器都按照该区域中定义的链路状态算法来计算网络拓扑结构，这意味着每一个区域都有着该区域独立的网络拓扑数据库及网络拓扑图。对于每一个区域，其网络拓扑结构在区域外是不可见的，同样，在每一个区域中的路由器对其域外的其余网络结构也不了解。这意味着OSPF路由域中的网络链路状态数据广播被区域的边界挡住了，这样做有利于减少网络中链路状态数据包在全网范围内的广播，也是OSPF将其路由域或一个AS划分成很多个区域的重要原因。

——随着区域概念的引入，意味着不再是在同一个AS内的所有路由器都有一个相同的链路状态数据库，而是路由器具有与其相连的每一个区域的链路状态信息，即该区域的结构数据库，当一个路由器与多个区域相连时，我们称之为区域边界路由器。一个区域边界路由器有自身相连的所有区域的网络结构数据。在同一个区域中的两个路由器有着对该区域相同的结构数据库。

——我们可以根据IP数据包的目的地地址及源地址将OSPF路由域中的路由分成两类，当目的地与源地址处于同一个区域中时，称为区域内路由，当目的地与源地址处于不同的区域甚至处于不同的AS时，我们称之为域间路由。

OSPF的骨干区域及虚拟链路（Virtual-link）

——在OSPF路由协议中存在一个骨干区域（Backbone），该区域包括属于这个区域的网络及相应的路由器，骨干区域必须是连续的，同时也要求其余区域必须与骨干区域直接相连。骨干区域一般为区域0，其主要工作是在其余区域间传递路由信息。所有的区域，包括骨干区域之间的网络结构情况是互不可见的，当一个区域的路由信息对外广播时，其路由信息是先传递至区域0(骨干区域)，再由区域0将该路由信息向其余区域作广播。

——在实际网络中，可能会存在backbone不连续的或者某一个区域与骨干区域物理不相连的情况，在这两种情况下，系统管理员可以通过设置虚拟链路的方法来解决。

——虚拟链路是设置在两个路由器之间，这两个路由器都有一个端口与同一个非骨干区域相连。虚拟链路被认为是属于骨干区域的，在OSPF路由协议看来，虚拟链路两端的两个路由器被一个点对点的链路连在一起。在OSPF路由协议中，通过虚拟链路的路由信息是作为域内路由来看待的。下面我们分两种情况来说明虚拟链路在OSPF路由协议中的作用。

1.当一个区域与area0没有物理链路相连时

——前文已经提到，一个骨干区域Area 0必须位于所有区域的中心，其余所有区域必须与骨干区域直接相连。但是，也存在一个区域无法与骨干区域建立物理链路的可能性，在这种情况下，我们可以采用虚拟链路。虚拟链路使该区域与骨干区域间建立一个逻辑联接点，该虚拟链路必须建立在两个区域边界路由器之间，并且其中一个区域边界路由器必须属于骨干区域。

——在上面所示的例子中，区域1与区域0并无物理相连链路，我们可以在路由器A及路由器B之间建立虚拟链路，这样，将区域2作为一个穿透网络（Transit-network），路由器B作为接入点，区域1就与区域0建立了逻辑联接。

2.当骨干区域不连续时

——OSPF路由协议要求骨干区域area0必须是连续的，但是，骨干区域也会出现不连续的情况，例如，当我们想把两个OSPF路由域混合到一起，并且想要使用一个骨干区域时，或者当某些路由器出现故障引起骨干区域不连续的情况，在这些情况下，我们可以采用虚拟链路将两个不连续的区域0连接到一起。这时，虚拟链路的两端必须是两个区域0的边界路由器，并且这两个路由器必须都有处于同一个区域的端口。

——在上面的例子中，穿过区域1的虚拟链路将两个分为两半的骨干区域连接到一起，路由器A与B之间的路由信息作为OSPF域内路由来处理。

——另外，当一个非骨干区域的区域分裂成两半时，不能采用虚拟链路的方法来解决。当出现这种情况时，分裂出的其中一个区域将被其余的区域作为域间路由来处理。 残域（Stub area）

——在OSPF路由协议的链路状态数据库中，可以包括AS外部链路状态信息，这些信息会通过flooding传递到AS内的所有OSPF路由器上。但是，在OSPF路由协议中存在这样一种区域，我们把它称为残域（stub area），AS外部信息不允许广播进/出这个区域。对于残域来说，访问AS外部的数据只能根据默认路由（default-route）来寻址。这样做有利于减小残域内部路由器上的链路状态数据库的大小及存储器的使用，提高路由器计算路由表的速度。

——当一个OSPF的区域只存在一个区域出口点时，我们可以将该区域配置成一个残域，在这时，该区域的边界路由器会对域内广播默认路由信息。需要注意的是，一个残域中的所有路由器都必须知道自身属于该残域，否则残域的设置没有作用。另外，针对残域还有两点需要注意：一是残域中不允许存在虚拟链路；二是残域中不允许存在AS边界路由器。

6.OSPF协议路由器及链路状态数据包分类

6.1 OSPF路由器分类

——当一个AS划分成几个OSPF区域时，根据一个路由器在相应的区域之内的作用，可以将OSPF路由器作如下分类：

——内部路由器：当一个OSPF路由器上所有直联的链路都处于同一个区域时，我们称这种路由器为内部路由器。内部路由器上仅仅运行其所属区域的OSPF运算法则。

——区域边界路由器：当一个路由器与多个区域相连时，我们称之为区域边界路由器。区域边界路由器运行与其相连的所有区域定义的OSPF运算法则，具有相连的每一个区域的网络结构数据，并且了解如何将该区域的链路状态信息广播至骨干区域，再由骨干区域转发至其余区域。

——AS边界路由器：AS边界路