爱华网1．概述.................................................................................................................... 3
2．SPF算法.............................................................................................................. 3
3．OSPF协议原理.................................................................................................... 5
3．1 自治系统的分区....................................................................................... 5
3．2 区域间路由.............................................................................................. 6
3．3 Stub区和自治系统外路由........................................................................ 6
3．4 DR和BDR................................................................................................. 7
4．OSPF报文............................................................................................................. 7
4．1 OSPF协议报文......................................................................................... 7
4．2 OSPF包承载的内容............................................................................... 9
5．OSPF协议的运行................................................................................................ 10
5．1 Hello协议的运行............................................................................... 10
5．2 DR和BDR的产生...................................................................................... 10
5．3链路状态数据库的同步............................................................................. 11
5．4路由表的产生和查找................................................................................. 11
1．概述
OSPF协议是由Internet网络工程部(IETF)开发的一种内部网关协议(IGP)，即网关和路由器都在一个自治系统内部。OSPF是一个链路状态协议或最短路径优先(SPF)协议。虽然该协议依赖于IP环境以外的一些技术，但该协议专用于IP，而且还包括子网编址的功能。该协议根据IP数据报中的目的IP地址来进行路由选择，一旦决定了如何为一个IP数据报选择路径，就将数据报发往所选择的路径中，不需要额外的包头，即不存在额外的封装。该方法与许多网络不同，因为他们使用某种类型的内部网络报头对UDP进行封装以控制子网中的路由选择协议。另外OSPF可以在很短的时间里使路由选择表收敛。OSPF还能够防止出现回路，这种能力对于网状网络或使用多个网桥连接的不同局域网是非常重要的。在运行OSPF的每一个路由器中都维护一个描述自治系统拓扑结构的统一的数据库，该数据库由每一个路由器的局部状态信息（该路由器可用的接口信息、邻居信息）、路由器相连的网络状态信息（该网络所连接的路由器）、外部状态信息（该自治系统的外部路由信息）等组成。每一个路由器在自治系统范围内扩散相应的状态信息。
所有的路由器并行运行同样的算法，根据该路由器的拓扑数据库构造出以它自己为根节点的最短路径树，该最短路径树的叶子节点是自治系统内部的其它路由器。当到达同一目的路由器存在多条相同代价的路由时，OSPF能够实现在多条路径上分配流量。
RFC2178中删除了OSPF的TOS功能，但是为了保证和以前版本的兼容性，在各个链路状态宣告中还保留了TOS项目。
2．SPF算法
与V－D算法相比较的一组算法叫作“链接－状态”（link－state）算法，又叫最短路径优先或SPF(Shortest Path First)算法。
按照SPF算法的要求，网关寻径表依赖于一张表示整个Internet网中网关与网络拓扑结构的图。在这张图中，节点表示网关，边表示连接网关的网络（link），我们称之为L－S图。在信息一致的情况下，所有网关的L－S图应该是完全相同的。各网关的寻径表是根据相同的L－S图计算出来的。L－S算法包括三个步骤：
（1）各个网关主动测试与所有相邻网关之间的状态。为此，网关周期性地向相邻网关发出Hello报文，询问相邻网关是否能够访问。假如相邻网关做出反应，说明链接为“开”(UP)，否则为“关”(DOWN)，链接－状态的取名即出于此。
（2）各网关周期性地广播其L－S信息。这里的“广播”是真正意义的广播，不象V－D算法那样只向相邻网关发送V－D报文，而是向所有参加SPF算法的网关发送L－S报文。
（3）网关收到L－S报文后，利用它刷新网络拓扑图，将相应链接改为“开”或“关”状态。假如L－S发生变化，网关立即利用最短路径算法，根据L－S图重新计算本地路径。
在实际应用中有好几种最短路径选择算法，大多数是以A算法（algorithm A）为基础。该算法已作为互连网络SPF协议的模型，并且多年来被用于优化网络设计和网络的拓扑结构。各节点用自己拥有的统一的描述自治系统拓扑结构的数据库，以自己为根，建立一个路径选择的寻径表。在图1中，节点A是源节点，节点J是目的节点。其具体的步骤如下：
（1）在图1中，网络中的每条路径有一个权值，该权值是根据某一标准（如考虑距离、时延、队列长度等）得出的；
（2）为每个节点标上一条已知路径从源端到该节点需要的最小代价。最初不知道任何路径，所以每个节点的标号为无穷大；
（3）为每个节点检测它周围有哪些相邻的节点，源节点是第一个被考虑的节点，并且变为工作节点；
（4）为工作节点的每个相邻的节点分配一个最小代价标号。如果发现一条从该节点到源节点的更短的路径，则修改标号。在OSPF中，当链路状态报文广播到所有其他节点时，会发生这种情况（即因发现更短的路径而修改标号）；
(5)在给相邻节点分配了标号以后，检测网络中的其他节点，如果某个已分配了标号的节点拥有较小的标号值，则它的标号变为永久标号，该节点变为工作节点；
(6)如果某节点的标号与到它的某个相邻节点路径上的权值之和小于该相邻节点的标号，在改变该相邻节点的标号，因为发现了一条更短的路径；
(7)选择另一个工作节点，重复上述过程直到穷尽所有的可能。最后的每个节点的标号就给出了源节点和目的节点之间的一条端到端的代价最低的路径。
图1 A算法的应用
经过了上面的计算可以形成图2所示的路由选择拓扑图（即最短距离树，又称最优树）：
图2 路由器A的路由选择拓扑图
3．OSPF协议原理
3．1 自治系统的分区
OSPF允许在一个自治系统里划分区域的做法，相邻的网络和它们相连的路由器组成一个区域(Area)。每一个区域有该区域自己拓扑数据库，该数据库对于外部的区域是不可见的，每个区域内部路由器的链路状态信息数据库实际上只包含着该区域内的链路状态信息，他们也不能详细地知道外部的链接情况，在同一个区域内的路由器拥有同样的拓扑数据库。和多个区域相连的路由器拥有多个区域的链路状态信息库。划分区域的方法减少了链路状态信息数据库的大小、并极大地减少了路由器间交换状态信息的数量。如图3所示。
AS
Area0
Area2
Area1
Area3
Area4
R
R
R
R
R
R
R
图3 把自治系统分成多个OSPF区域
在多于一个区域的自治系统中，OSPF规定必须有一个骨干区（backbone）－area 0，骨干区是OSPF的中枢区域，它与其他区域通过区域边界路由器(ABR)相连。区域边界路由器通过骨干区进行区域路由信息的交换。为了达到一个区域的各个路由器保持相同的链路状态信息库，这就要求骨干区是相连的，但是并不要求它们是物理连接的。在实际的环境中，如果它们在物理上是断开的，这时可以通过建立虚链路(Virtual Link)的方法保证骨干区域的连续性。虚链将属于骨干区并且到一个非骨干区都有接口的两个ABR连接起来，虚链本身属于骨干区，OSPF将通过虚链连接的两个路由器看作是通过未编号的点对点链路（unnumbered point-to-point）连接。
3．2 区域间路由
当两个非骨干区域间路由IP包的时，必须通过骨干区。IP包经过的路径分为三个部分：源区域内路径（从源端到ABR）、骨干路径（源和目的区域间的骨干区路径）、目的端区域内路径（目的区域的ABR到目的路由器的路径）。从另一个观点来看，一个自治系统就象一个以骨干区作为Hub，各个非骨干区域连到Hub上的星型结构图。各个区域边界路由器在骨干区上进行路由信息的交换，发布本区域的路由信息，同时收到其他ABR发布的信息，传到本区域进行链路状态的更新以形成最新的路由表。
3．3 Stub区和自治系统外路由
在一个OSPF自治系统中有这样一种特殊的区域――存根区域（Stub区域），在这个区域中只有一个外部出口，该区域不允许外部的非OSPF的路由信息进入。到自治系统外的包只能依靠缺省路由。存根区域的边界路由器必须在路由概要里向区域宣告这个缺省路由，但是不能超过这个存根区域。缺省路由的使用可以减少链路状态信息库的大小。对于该自治系统外部路由信息，如BGP产生的路由信息，可以通过该自治系统的区域边界路由器（ASBR）透明地扩散到整个自治系统的各个区域中，使得该自治系统内部的每一台路由器都能够获得外部的路由信息。但是该信息不能扩散到存根区域。这样自治系统内的路由器可以通过ASBR路由包到自治系统外的目标。
3．4 DR和BDR
在自治系统内的每个广播和非广播多点访问（NBMA）网络里，都有一个指定路由器（DR－Designated Router）和一个备份指定路由器（BDR－Backup Designated Router），它们是通过Hello协议选举产生的。DR的主要功能是：
（1）产生代表本网络的网络路由宣告，这个宣告列出了连到该网络有哪些路由器，其中包括DR自己；
（2）DR同本网络的所有其他的路由器建立一种星型的邻接关系，这种邻接关系是用来交换各个路由器的链路状态信息，从而同步链路状态信息库。DR在路由器的链路状态信息库的同步上起到核心的作用。
另一个比较重要的路由器是BDR，BDR也和该网络中的其它路由器建立邻接关系。因此，BDR的设立是为了保证当DR发生故障时尽快接替DR的工作，而不至于出现由于需重新选举DR和重新构筑拓扑数据库而产生大范围的数据库震荡。当DR存在的情况下，BDR不生成网络链路广播消息。
在DR、BDR的选举后，该网络内其它路由器向DR、BDR发送链路状态信息，并经DR转发到和DR建立邻接关系的其它路由器。当链路状态信息交换完毕时，DR和其它路由器的邻接关系进入了稳定态，区域范围内统一的拓扑（链路状态）数据库也就建立了，每个路由器以该数据库为基础，采用SPF算法计算出各个路由器的路由表，这样就可以进行路由转发了。
4．OSPF报文
4．1 OSPF协议报文
OSPF使用五种类型的路由协议包，在各个路由器间进行交换信息，如表1所示。每种协议包都包含24字节的OSPF协议包的首部，如图4所示。
Hello协议用于寻找和维护路由器所连网络上的邻居关系。通过周期性地发出Hello包，来确定和维护邻居路由器接口是否仍在起作用。Hello包被发送到网络上的每个活动的路由器接口。在广播和非广播的多点访问的网络上，DR和BDR的选举也是通过Hello包来完成的。在不同的物理网络上，Hello包的目的地址是不同的；在点到点和广播网络上，其目的地址是AllSPFRouter(224.0.0.5)；在虚链路上是单播，也就是从虚链路的源端直接发送到链路的另一端；而在点到多点的网络上，分离的Hello包分别发送到相连的每一个邻居；在非广播的多点访问网络上，Hello包的发送要看各个路由器的配置信息。
表1 OSPF路由协议包类型
包类型
目的
Hello协议包
发现和维护邻居
数据库描述
汇总数据库内容
链路状态请求
数据库下载
链路状态更新
数据库上载
链路状态确认
扩散确认
图4 OSPF协议包的首部
数据库描述包是类型往为2的OSPF包，在形成邻接过程中的路由器之间交换数据库描述包，且它们描述链路状态数据库。根据接口数和网络数，可能不只一个数据库描述包来传输整个链路状态数据库。在交换的过程中所涉及的路由器建立主从关系。主路由器发送包，而从路由器通过使用数据库描述（Database Description－DD）序列号认可接收到的包。接口MTU域指示通过该接口可发送的最大IP包长度。当通过虚链路发送包时，这个域设置为0。选项域包含3位，用于显示路由器的能力。I位是Init位，对数据库序列中的第一个包，设置为1。M位设置为1，表示在序列中还有更多的数据库描述包。MS位是主从位，在数据库描述包交换期间，1表示路由器是主路由器，而0表示路由器是从路由器。包的其余部分是一个或多个LSA，如图5所示。
图5 数据库描述包格式
链路状态请求包是类型为3的OSPF包，它们的格式如图6所示。当两个路由器完成交换数据库描述包时，路由器可检测链路状态数据库是否过时。当这种情况发生时，路由器可请求新一些的数据库描述包。
图6 路由状态请求包格式
链路状态更新包是类型为4的OSPF包，它们用于实现LSA的传播。链路状态更新包格式显示在图7中。每个链路状态更新包包含一个或多个LSA，而每个包通过使用链路状态确认包来认可。
图7 链路状态更新包的格式
链路状态确认包是类型位5的OSPF包，其格式中除了OSPF包首部外，包括LAS的首部。这些包发送到三个地址之一：多点传送地址AllDRouters，多点传送地址AllSPFRouters，或单点传送地址。
4．2 OSPF包承载的内容
l 路由器链路状态宣告
路由器为每个有活动OSPF接口的区域生成一个路由器LSA。包含在路由器LAS中的信息是路由器接口在该区域中的状态，而LSA在整个区域传播。进入一个区域的所有路由器接口必须在一个路由器LSA中说明。链路状态ID域是路由器的OSPF ID。VEB位用于确定路由器可能有的链路类型。V位显示路由器虚拟链路的端点。
链路ID标识路由器的接口所连接的对象。链路ID一般等于邻居路由器的链路状态ID。链路数据域的内容取决于链路类型。如果路由器与存根区域连接，那么，这个域将包含这个网络的IP地址掩码。对其他类型的链路，这个域包含分配给该接口的IP地址。服务类型域通常设置为0，最后的值是度量值，或链路的费用。
l 网络链路状态宣告
网络LSA是类型为2的LAS，而这样的LSA是由支持两个或多个路由器的每个广播和NBMA网络所生成的。网络LSA是由网络的DR所创建的。这个LSA描述了连接到网络的所有的路由器，包括DR自己。链路状态ID是DR到这个区域的接口的IP地址。
l 汇总链路状态宣告
类型3和类型4的LSA是汇总链路状态宣告。汇总LSA是有区域边界路由器生成的，而且它们说明区域的目标。3型汇总有IP地址目标，链路状态ID是IP的网络号。4型汇总LSA以一个自治系统边界路由器为其目标，链路状态ID是OSPF路由器ID。链路状态ID是两种类型LSA包之间的唯一区别。
l 外部自治系统链路状态宣告
类型5是AS－External LSA，它被用于说明自治系统外的网络。AS－External LSA用于说明到外部网络的路由。链路状态ID域包含IP网络号或0.0.0.0，如果它描述一个默认路由，此时的作为掩码也是0.0.0.0。
5．OSPF协议的运行
5．1 Hello协议的运行
Hello协议的作用是发现和维护邻居关系、选举DR和BDR。在广播型网络上每一个路由器周期性地广播Hello包（目的地址是AllSPFRouter），使得它能够被邻居发现。每一个路由器的每个接口都有一个相关的接口数据结构，当Hello包里的特定参数（如Area ID, Authentication, Network Mask, HelloInterval, RouterDeadInterval 和Options values）相匹配时，Hello包才能被接收。Hello包中包含着本路由器所希望选举的DR和该DR的优先级、BDR和BDR的优先级、还有本路由器通过交换Hello协议包所“看”到的其它路由器。从Hello包里得到的邻居被放在路由器的邻居列表里。当从接收到的Hello包里看到自己时，就建立了双向通信。建立了双向通信的路由器才有可能建立连接（adjacency）关系，能否建立连接关系，要看连接两个邻居的网络的类型。通过Hello协议包的交换，得知了希望成为DR和BDR的路由器以及他们的优先级，下一步的工作是选举DR和BDR。
5．2 DR和BDR的产生
在初始状态下，一个路由器的活动接口设置DR和BDR为0.0.0.0，这意味着没有DR和BDR被选举出来。同时设置Wait Timer，其值为RouterDeadInterval，其作用是如果在这段数时间里还没有收到有关DR和BDR的宣告，那么它就宣告自己为DR或BDR。经过Hello协议交换过程后，每一个路由器获得了希望成为DR和BDR的那些路由器的信息，按照下列步骤选举DR和BDR：
（1）在路由器同一个或多个路由器建立双向的通信以后，就检查每个邻居Hello包里的优先级、DR和BDR域。列出所有符合DR和BDR选举的路由器（他们的优先级要大于0，接口状态要大于双向通信），列出所有的DR，列出所有的BDR；
（2）从这些合格的路由器中建立一个没有宣称自己为DR的子集（因为宣称为DR的路由器不能选举成为BDR）；
（3）如果在这个子集里有一个或多个邻居（包括它自己的接口）在BDR域宣称自己为BDR，则选举具有最高优先级的路由器，如果优先级相同，则选择具有最高Router ID的那个路由器为BDR；
（4）如果在这个子集里没有路由器宣称自己为BDR，则在它的邻居里选择具有最高优先级的路由器为BDR，如果优先级相同，则选择具有最大Router ID的路由器为BDR；
（5）在宣称自己为DR的路由器列表中，如果有一个或多个路由器宣称自己为DR，则选择具有最高优先级的路由器为DR，如果优先级相同，则选择具有最大Router ID的路由器为DR；
（6）如果没有路由器宣称为DR，则将最新选举的BDR作为DR；
（7）如果是第一选举某个路由器为DR/BDR或没有DR/BDR被选举，则要重复2到6步，然后是第8步。
（8）将选举出来的路由器的端口状态作相应的改变，DR的端口状态为DR，BDR的端口状态为BDR，否则的话为DR other。
在多路访问网络中，DR和BDR与该网络内所有其它的路由器建立邻接关系，这些邻接关系也是该网络内全部的邻接关系。
由于DR和BDR的引入，简化了网络的逻辑拓扑结构，将一个网状网络转变成一个星型网络，使协议包的扩散，计算变的简单，并有效防止了邻接关系震荡的发生。
5．3链路状态数据库的同步
在OSPF中，保持区域范围内的所有路由器的链路状态数据库同步极为重要。通过建立并保持邻接关系，OSPF使具有邻接关系的路由器的数据库同步，进而保证了区域范围内所有路由器数据库同步。数据库同步过程从建立邻接关系开始，在完全邻接关系已建立时完成。当路由器的端口状态为ExStart时，路由器通过发一个空的数据库描述包来协商“主从”关系以及数据库描述包的序号，Router ID大的为主，反之为从。序号也以主路由器产生的初始序号为基准，以后的每一次数据库描述包的发送，序号都要加1。主路由器发送链路状态描述包（数据库描述包），从路由器接收链路状态描述包后来检查自己的链路状态数据库，如果发现链路状态数据库里没有改项，则进行添加该项，并将该项加入链路状态请求列表，准备向主路由器请求新的链路状态，并向主路由器发送确认包。主路由器收到链路状态请求包时，发出链路状态的更新包，进行链路状态的更新。从路由器收到链路状态更新包后发出确认包，进行确认，表示收到该更新包，否则主路由器就在重发定时器的启动下进行重复发送。每一个路由器向它的邻居发送数据库描述包来描述自己的数据库，每一个数据库描述包由一组链路状态广播组成，邻居路由器接收该数据库描述包，并返回确认消息。这两个路由器形成了一种“主从”关系，只有主路由器能够向从路由器发送数据库描述包，反之则不行。当所有的数据库请求包都已被主路由器处理后，主从路由器也就进入了邻接完成状态。当DR与整个区域内所有的路由器都完成邻接关系时，整个区域中所有路由器的数据库也就同步了。
5．4路由表的产生和查找
当链路状态数据库达到同步以后，各个路由器就利用同步的数据库以自己为根节点来并行地计算最优树，从而形成本地的路由表。
当收到IP包需要查询路由表时，按照以下规则完成路由查找：
（1）在路由表中选择相匹配的路由记录。相匹配的记录是指需转发IP包的目的地址“落在”该匹配路由记录的目的地址范围内（该匹配记录可能有多个）。如：如果有路由表项为172.16.64.0/18，172.16.64.0/24和172.16.64.0/27供目的地址172.16.64.205选择，则选择最后一项。因为它是最匹配的一个。也就是说要选择一个掩码最长的一个。缺省路由是最后要选择的，因为它的掩码最短。如果没有匹配的路由表项供选择，则有ICMP发送一个目标不可到达的控制报文，而且该IP包将被丢弃。
（2）如果有多个路径匹配，根据路由的类型来进行进一步的选择，它们的优先级依次为区域内的路径，区域间得额路径，E1型的外部路径，E2型的外部路径。
（3）如果有类型和费用都相等的多条路径，则OSPF将同时利用它们。
（4）最后利用所寻找的路径来进行IP包的转发。
